問題タブ [glr]

私は最近、flex/bison bison ペアを使用したパーサーを開発しています。パーサーを希望どおりにアプリケーションに適合させるのに苦労していました。これには、パーサーを再入可能でスレッド セーフにすること、およびアプリケーション フレームワークに適切に適合させることに関する問題が含まれていました。

私はごく最近、flex++/bison++ に移行しました。これは、C++ でのプログラミングに多くの利点を提供し、OOP を使用してパーサーとのインターフェイスと拡張を行う非常に明確で管理しやすい方法を提供します。Bison++ は、そのインターフェースの大部分を元の bison と共有しています。欠点は、特定の使用法に関するドキュメントが貧弱であることです。一般的に、インターフェースははるかに直感的であるため、これは今まで問題ではありませんでした.

パーサーの開発が進むにつれて、より精巧なパーサーのいくつかで GLR を使用する可能性に気付きました。

質問: GLR を bison++ で具体的に使用することは可能ですか? また、オプションを有効にするにはどうすればよいですか?

私は文法を作成しました。その簡略版を以下に再現します。

この言語は明確であり、LR解析可能である必要があると思います。（私が間違っている場合は私に知らせてください！）

ただし、この文法のLR（1）パーサーを生成しようとすると、シフト/リデュースの競合が発生します。パーサーがexp3先読み?で表示すると、シフトするかリデュースするかがわからないためです。

この言語をLR（1）解析可能（競合なし）にするための合理的な方法はありますか？

それとも、GLR（またはおそらくLR（2）？）は、このような言語の唯一の現実的なオプションですか？
（または、そもそも言語が明確であると信じるのは間違っていますか？）

参考までに、私が生成したあいまいなステートマシンは次のとおりです（♦はEOFです）。

GLR パーサーがいくつかのテキストを 2 つ以上の方法で同じ非終端記号に縮小すると、解析サブツリーがマージされます。Rekers はこれに「シンボル ノード」を使用します。

これは、各非端末がマージを引き起こす可能性があるわけではありません。どの非終端記号がマージされないかを事前に知っておくと、解析ツリーの構築が大幅に簡素化されます。

たとえば、Elkhound Technical Report では、著者は GLR パーサー用に C++ 文法を実装しました。彼はそれを次のように説明しています。

現在、文法には 37 の shift/reduce 競合、47 の reduce/reduce 競合、および8 つのあいまいな非終端があります。

特定の CFG のあいまいな非ターミナルと明確な非ターミナルを分離するにはどうすればよいですか? これについてどこで読むことができますか？

DParser形式用に記述され、Python バインディングを使用する大きな文法があります。この文法を使用してコードを解析すると、次の例外が発生しますが、渡すコードによって記号が異なります。しかし、あいまいな記号は常に同じ非終端記号です。あいまいさが何であるかを知るにはどうすればよいですか？

ヒントやアイデアをいただければ幸いです。

DParser用に記述され、Python バインディングを使用する大規模な文法があります。パーサーを初めて実行し、DParser がその内部テーブルを生成すると、次のような多くの警告が表示されます。

これらの警告の原因が何であるかはわかりません。私が見つけた唯一のものは、DParser ソース コード "write_tables.c" にありました。

ヒントやアイデアをいただければ幸いです。

セクション 1.5.4 任意の述語による解析の制御: bison のマニュアルでは、次の形式のブラケット間の述語の戻り値をチェックすることで、ルールのオプションの前もって解析を失敗させることができると指定しています。

問題は、文法ファイルで上記の形式を使用すると、次の構文エラーが発生することです。

マニュアルに記載されているように%glr-parser、最初のフラグの前にフラグを追加しました。%%足りないものはありますか？

更新: 投稿する前に bison バージョン 3.0 でこれを試みましたが、うまくいきませんでした。ドキュメントが言うように、この「実験的機能」に関する人々の経験に関するオンラインの情報はあまりありません。それが彼らのために働くことを誰かが確認または否定できますか?

更新 #2: rici が投稿した解決策に従った後、結果の .c ファイルに問題があります。コンパイルのデバッグを支援するために、bison は次の形式の #line ディレクティブを出力しているようです。

任意の述語生成の場合、ルールの上記の述語オプションは、パーサー ファイルのメイン スイッチ ブロックで次のようになります。

もちろん、これはコンパイルされません。残りのルール一致オプションで見られるように、case ステートメントの開始前の行に出力されることを意図していると思います。バグレポートが提出されたら、バグレポートに追加する別の情報がありますか? 今のところ、これらを検索して置き換えて先に進むことができます。

GLRパーサー、つまりあいまいな文法を処理できるパーサーを生成できると主張するいくつかの異なるパーサージェネレーター（Bison、DParserなど）を試しました。これは、私が話しているタイプの非常に単純なあいまいな文法です。

パーサーを問題なく生成できますが、有効なはずのパーサー入力を与えると、「未解決のあいまいさ」エラーまたは完全なクラッシュが発生します。文法を明確なバージョンに変更しても、何の問題もありません。

GLR パーサーについて理解していないことは何ですか? 全体的なポイントは、あいまいな場合、可能なすべての解析がマージされるか行き止まりに達するまで追跡されるということだと思いました。必要なのは、入力の有効な解析があるかどうかを教えてくれるパーサーだけです。

助けてくれてありがとう。

編集：

これはイライラします。%dprec と %merge を使用して、Bison にあいまいなルールとターミナルを処理させることができましたが、処理が必要な種類の非常に単純だが非常に病理学的な疑似英語の文法が依然として詰まっています。

「a boy saw a girl」という入力に対して、Bison は解析できず、コード 1 を返します。一方、Tom は、この文法とこの入力文を完璧に処理し、未知の端末を可能な限りすべて割り当てるだけで自然に処理します。端末タイプ。しかし、Bison とは異なり、Tom は大きな文法で窒息します。（「チョーク」とは、さまざまな方法で失敗することを意味します。失敗モードが役立つ場合は、それらを報告できます。）

他にアイデアはありますか？

happy から GLR パーサーを生成しようとしていますが、ファイルが生成されるとエラーが発生します。

これが ABC.y の例なので、私が何をしようとしているのかは明らかです:

この例は、

ただし、 --glr に満足しているため、結果をビルドできません。私はそれを間違っているのだろうかと思っています。正確に言うと、 --glr を実行すると、ABC.hs という 2 つの出力が生成されます。ただし、ABCData.hs

今失敗します。私が得るエラーは、「Could not find module 'System', It is a hidden member of haskell-98...」です。また、文法を BNFC にコーディングして -glr オプションを使用しようとしましたが、明らかに廃止された Data.FiniteMap への依存など、他のエラーが発生します。このコンパイルを取得する方法はありますか?

幸せな文法を定義するとします

これをコンパイルすると

私は一般的に、自明でないあいまいさを持つ文法に興味があります。ただし、この例は、私を混乱させているビットを示しています。

Haskell パーサーを取得します。トークン ストリームが abba または b の場合にのみ成功します

しかし、私は失敗にもっと興味があります。私は非常に早く失敗したいと思っており、必要と思われるよりも多くのトークンが必要なようです。

たとえば、トークン ストリーム a,a,a をフィードすると、失敗するのに 3 番目の a が必要です。bbb をフィードすると、失敗するのに 3 番目の b までかかります。余分な先読みはなぜですか？f を一致させるとき、2 つの 'a' が表示されると、一致する文法はありません。