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

質問

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

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

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

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

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

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

回答No.3

axsies

構文解析における文法定義は、普通のプログラムにおけるソースコードなので、「文法察してください」っていうのは、「テキスト処理してるんですがうまく動きません。ソースコードは晒せませんが、入力はこんな感じです。原因を特定してください」って言ってるようなものです。できるわけありません。
そして文法も謎です。察せません。なんか関数型言語をイメージしているような雰囲気はしますが…。

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

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

お礼

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

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

回答No.2

uyama33

マイクロコンピュータのための
コンパイラ・コンパイラ

サイエンス社

では、Ｇコードを使って高速化しています。

文法はＬＬ（１）です。

ベクターには、WINDOWS　で動くものも公開されています。
無料ですので、一度試してみたらいかがでしょう。

お礼

そうですね、変に先読みしようとしている感じがしますので
基本的に「関数名+(」まで検知できればほとんどの文法を一意に決められるので
LL(2)もあればほとんどの解析はうまくいくはずので
ちょっとライブラリの中調べなおして
まともな速度が出る方法調べてきます

回答No.1

Tacosan

自力で構文解析したら?

お礼

正直言語ひとつ勉強しようとすると、知らないといけないことが多すぎですから、本当に検証したいところに焦点を合わせて他は自分で書かない選択をしないと辛いですよ