問題タブ [lalr]

.NET 用の優れた yacc/bison タイプの LALR パーサー ジェネレーターはありますか?

YACC (実際には Bison) で文法を書いていますが、シフト/リデュースの問題があります。これは、後置インクリメント演算子とデクリメント演算子を含めることによって生じます。以下は、文法の縮小版です。

Bison は、12 個のシフト/リデュースの競合があることを教えてくれましたが、接尾辞のインクリメントとデクリメントの行をコメントアウトすると、問題なく動作します。この競合を修正する方法を知っている人はいますか? この時点で、LL(k) パーサー ジェネレーターに移行することを検討しています。これにより、はるかに簡単になりますが、LALR 文法は常に、より自然に記述できるように見えました。GLR も検討していますが、優れた C/C++ GLR パーサー ジェネレーターを知りません。

LALR(1) パーサー ジェネレーター (Bison ですが、問題はそのツールに固有のものではありません) を使用して単純な文法を解析しようとしていますが、shift-reduce の競合が発生しています。これらの修正について私が見つけたドキュメントやその他の情報源は、次の1つ以上を言う傾向があります:

• 文法があいまいな場合 (if-then-else のあいまいさなど)、言語を変更してあいまいさを修正します。
• 演算子の優先順位の問題である場合は、優先順位を明示的に指定してください。
• デフォルトの解像度を受け入れ、ジェネレーターに文句を言わないように伝えます。

ただし、これらのどれも私の状況には当てはまらないようです: 私が知る限り、文法は明確です (もちろん、先読みの文字が 1 つしかないためあいまいですが)、演算子は 1 つしかなく、デフォルトの解決では解析エラーが発生します正しく形成された入力で。文法の定義を作り直して、上記のバケツに当てはまらない shift-reduce 競合を取り除くテクニックはありますか?

具体的に言うと、問題の文法は次のとおりです。

その意図は、"[A-Za-z]+" または "[A-Za-z] -> [A-Za-z]+" の形式のセミコロンで区切られた行を解析することです。

Bisonの文法全体を通して、私は右再帰を使用しています。最初にスタック全体を構築する必要がないため、左再帰の方が優れていることを読みました。

しかし、それらのいずれかで左再帰に切り替えようとすると、常に多くの競合が発生し、その理由がわかりません。

右の代わりに左の再帰を使用すると競合が発生する一般的な例を誰かに教えてもらえますか（右の再帰が競合を引き起こさない場合）。次に、そのような競合を修正するために左に切り替えるときに何をする必要がありますか。基本的な例は、自分の文法を修正するだけでは不十分だと思います。

編集：
しかし、私の理解は完全ではないので、とにかく特定の例を含める必要があると思います:-)「listseparatorcommand」を「commandseparatorlist」に変更すると競合が解決します。

PLY を使用して自分の言語用のパーサーを構築してきましたが、shift/reduce の競合が発生して問題が発生しています。私の言語には、構文 ala C++ テンプレートを持つジェネリック型があります。だから今、私は次のようなルールを持っています：

ただし、解析できないことがわかりました。

（これは明らかな理由で問題です）。デバッグ出力は次のとおりです。

さらにパーサーが必要な場合は、提供できます。ありがとう。

編集:私に提案された1つの解決策は、型を独自のトークンにすることでした。私の言語は C/C++ のようなプリプロセッサ インクルード システムを使用していないため、これには少し作業が必要になりますが、それでも可能だと思いますが、文法に制限されたソリューションを希望します。

LALR（2）は、ぶら下がっているelseケースを自然に処理できますか（LALR（1）のように、特別なルールはありません）？

ありがとう

本当に良いエラー メッセージを生成できる、C++ 用の LALR パーサー ジェネレーターの最適なソリューションを探しています。私は MySQL が生成する構文エラーが本当に嫌いで、パーサーを取り込んで、それを「リント」チェッカーに置き換えたいと思っています。

YACC/LEX と BISON/FLEX を使用しました。Mac または Linux で動作する必要があります。

単純なLALR（1）文法がありますが、問題が発生しています。

ドットはルールの終わりを示し、角かっこの間の端子には結合性が割り当てられています。ASSIGNは右結合、COMMAは左結合です。

しかし、レモンは、「empty_stmt_list::=」というルールを減らすことはできないと言っています。開始シンボルに接続されていないためです。きっと:-)

「invoke」の解析の競合もあります。empty_stmt_listが実際にステートメントの空のリストである場合、RPARENとCOMMAのどちらかを決定することはできません。

私が達成しようとしているのは、（void）パラメーターを持たない関数呼び出しを解析できることです。

他のすべては期待どおりに機能します。

ありがとう

編集：元の投稿を編集し、削除された文法全体を投稿しました。

更新: この質問は古くなっていますが、情報提供のために残されています。

元の質問

2002 年以来、同じバージョンの bison++ (1.21-8) と flex++ (2.3.8-7) を使用しています。

現時点では、LALR(1) または GLR に代わるものは探していません。最新のオプションを探しているだけです。Cygwin に依存しない、オリジナルより後のこれらのポートを知っている人はいますか?

Windows 環境で C++ コンパイラの開発に (ANTLR または Boost.spirit 以外に) 使用している他の人々は何ですか? 直接の経験があれば、商用オプションも問題ありません。Linuxでもコンパイルする必要があります。

更新: この古い質問は、ツールの推奨に関するポリシーを知らなかったときに尋ねられました (2010 年にポリシーが存在したかどうかはわかりませんが、関係なく...

それ以来、私は GLR 機能を備えた Bison 3.0 に更新し、その実験を開始しました。

最終的に、エラー報告を改善し、コンパイラー以外のツールでの使用を容易にするために、パーサーの書き直しは再帰的な降下になると判断したので、今のところ Bison で参照バージョンを完成させます。現時点では、別の PG ツールに変換する意味はほとんどないと思います。

皆さん、私は flex と bison を使用してスクリプト エンジンを開発しており、現在、この言語の eval 関数と load 関数を実装しています。例を挙げると、構文は次のようになります。

だから、私の字句解析器で私は関数を実装しました:

しかし、うまくいかないようです。まあ、そうですが、文字列（ファイルからロードされたもの、または直接評価されたもの）が終了すると、 sigsegv を取得します：

お気づきかもしれませんが、sigsegv は私のものではなく、flex/bison コードによって生成されます...ヒント、または少なくともこれらの種類の関数を実装する方法の例はありますか?

PS: include ディレクティブの実装に成功しましたが、解析時ではなく実行時 (PHP の include/require ディレクティブのようなもの) で機能するには、eval と load が必要です。