4

私は現在、LL(1) 形式に取り組めることを望んでいる BNF 文法で遊んでいる最中です。しかし、今日で 3 回目の文法の変更と新しい FIRST および FOLLOW セットの計算を手動で行ったばかりで、もううんざりしています。もっと良い方法があるはずです！

文法が与えられた場合、すべての非端末の最初のセットと次のセットを自動的に計算するツールを誰かが提案できますか?

4

3 に答える 3

3

1 年前、私が通っている大学で 1 学期のプロジェクトがあり、そこでの仕事はプログラミング言語を作成することでした。グループとして、パーサーをゼロから手書きできるようにしたいと決めたので、LL(1) 文法を目指す必要がありました。

もちろん、私たちの出発点は LL(1) にはほど遠いものでした。そのために、AtoCCパッケージの kfgEdit ツールを使用しました。ルールを入力するだけで、ボタンをクリックするだけでそれが LL(1) 文法かどうかをチェックできます。

警告の公正な言葉: このツールは、受け入れるものについて少し気難しいです。実際の文法には EBNF をよく使用しますが、次のように書くことができます。* と + は、そのトークンがそこに何回出現する必要があるかを示しますが、これはサポートされていません。グループ化もサポートされていません。これを行うには非常に長い時間がかかることに気付くかもしれません.LL(1)に達した後、文法を読みやすくするために何らかの「再配置」を行うことをほぼ確実に望むでしょう.

もちろん、扱っている文法のタイプによっては、これはあまり問題にならないかもしれません。私たちは一種の Pascal/C ハイブリッドを作成しました。かなり制限された一連の構成要素 (プロシージャ、関数、組み込みのプリミティブ型とそれらの配列のみ、if、単一のループ構成要素の代わりに独自に作成したもの) を使用しました。標準の 3...) であり、それを LL(1) 文法にまとめるのに少なくとも 1 週間かかりました。これは約 4 か月の合計のうちの 1 つであることに注意してください。

絶対に LL(1) 文法を持っている必要がある場合、このような状況に陥った場合は明らかに先に進む必要がありますが、yacc/bison や SableCC などのパーサー ジェネレーターの使用が許可されている場合は、長期的には、そのルートをたどる方がはるかに簡単であることがほとんどです。それはあなたがその道をたどるべきだという意味ではありません-実際にすべてを手で書くことは、おそらく他の方法では得られなかったであろう洞察を提供することがわかりました-しかし、あなたの現在とは異なる状況でその洞察を得る方が良いかもしれません. .

tl;dr バージョン: AtoCCパッケージの kfgEdit を使用します。

于 2010-02-14T02:13:00.597 に答える
0

再帰降下解析については、 ANTLRを調べる価値があります。ただし、あなたの質問に対する正確な答えが得られるかどうかはわかりません。特定の文法の FIRST および FOLLOW セットを見つけてください。

于 2010-02-14T02:32:56.830 に答える
0

DMS Software Reengineering Toolkitには、FIRST および FOLLOW セットを計算するパーサー ジェネレーターがあります。また、それが生成する L(AL)R ステート マシンを調べることもできます。

ただし、正当な文脈自由文法を使用している場合は、それを LL 形式に「論争」する必要はありません。DMS パーサー ジェネレーターは、任意の文脈自由文法から GLR パーサーを生成します。

于 2010-10-15T20:35:21.867 に答える