LL(n)構文解析機での高速化手法

締切済

質問者：m_matsubara
質問日時：2014/03/17 00:19
回答数：3件

プログラム言語の処理系の勉強のために、実際に処理系を作成してみています
四則演算などの基礎的なところが動くようになって喜んでいたのですが
次のような文法で大きく解析速度が落ちてしまうという問題が起きてしまいました
(構文解析だけで１分ほどかかってしまいました)

->(n) do
if(
n.(==)(1),
do 1 end,
do n.(*)(fact(n.(-)(1))) end
)
end

文法の詳細は何となく察していただくとして
解析速度の大きな低下の原因を探ってみたところ
括弧「()」の入れ子階層が深く入り組むほど倍々ゲームで解析速度が落ちている処まで絞り込めてきました
おそらく閉じ括弧「)」を先読みしても間違ったものを拾って失敗しているのではないかなと推測しています

一応使っている環境は下に挙げますが
おそらくはLL(n)構文解析での一般的な問題だと思いました
どうすれば高速化できるか教えていただけないでしょうか？

・開発言語はC#
・パーサー・コンビネーターでSparacheというライブラリを使用させていただきました
https://github.com/sprache/Sprache
・ライブラリは開始括弧「(」をっ見つけると閉じ括弧「)」の先読みを、してくれている…様子です
・トークナイズや中間表現への変更は行わないで直接文字列をプログラムとして評価しています

はじめて作ってみた処理系なので失敗してはその原因を調べなおして勉強しているものですが
お知恵を貸していただければ幸いです

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (3件)

最新から表示
回答順に表示

No.3

回答者： axsies
回答日時：2014/03/19 03:07

構文解析における文法定義は、普通のプログラムにおけるソースコードなので、「文法察してください」っていうのは、「テキスト処理してるんですがうまく動きません。

ソースコードは晒せませんが、入力はこんな感じです。原因を特定してください」って言ってるようなものです。できるわけありません。
そして文法も謎です。察せません。なんか関数型言語をイメージしているような雰囲気はしますが…。

LL(k)文法は最大k個のトークンを先読みすれば、バックトラックなしに一意に決定できる文法です。LL(k)パーサはその事に基づき、トークンとスタックの先頭を見て動作を決めるアルゴリズムなので、「（」を読むと「）」を先読みするという動作が不可解です。
入れ子の階層が深くなるほど重くなるというのも…。
トークナイズしてないせいで、異常なサイズの解析表が構築されているとかでしょうか？
単に文法が悪いかもしれませんし、ライブラリの問題かもしれません。
いずれにしても、この辺はSparacheを知らないため私はこれ以上のアドバイスできませんが…。

まぁ、個人的にはいきなりLINQ使ったパーサーコンビネーターみたいな変態的な代物で、参考にできるものが少ない変な文法に挑戦しないで、まずは適当な本でも見ながら、再帰下降パーサーとかLL(1)パーサーで、四則算電卓を作るところからはじめて、JavaScriptとかBASICライクなメジャーで簡単な文法に挑戦した方がいいと思います。
（もっとも、私が初めて書いたパーサもHaskellのParsecを使ったものだったのであまり人のこと言えないかもしれませんがｗｗｗ）

- 0
- 件

通報する

この回答へのお礼

正直、言語ひとつを理解するためには、できないといけない範囲が広すぎるので
最初はある程度ツールの力を借りてでもひとつ作ってみて、その後興味の続いた分野を深堀していく姿勢でないといけないと思うのです
その結果アレ？って事になってここで質問を行っている人間の言葉ではないのかもしれませんが・・・

Parsecの場合は先読みしたい場合はtry関数に食べさせてあげる必要がありますので
文法が複雑になってくると、後でtry地獄になりますが、Sparacheはそういうのが表に出てこないので
やりやすいなと思っていたのですが、最後になって問題が浮いてくるタイプでしたね
今回のような入れ子の関係が確定している場合はLL(1)文法の方が良いよいです
ちょっとデフォルトが先読みをきかせているので、先読み聞かせない方法を探します

通報する

お礼日時：2014/03/22 04:49