問題タブ [lr]

すべてのLL文法はLR文法ですが、その逆ではありませんが、私はまだその区別に対処するのに苦労しています。同等のLL表現を持たないLR文法の小さな例が存在する場合は、それについて興味があります。

ボトムアップパーサーは、左再帰文法を受け入れることができるため、トップダウンパーサーよりも優れていることを私は知っていますが、トップダウン構文解析よりもボトムアップ構文解析を好む他の理由は何でしょうか。

次の文脈自由文法があると仮定すると、その特定の順序で (YACC の場合):

• z→x
• z → zx

次の入力がある場合：

(z (zx

パーサーは削減しますか:

1. 「x」から「z」
2. 「z x」から「z」

私はその2番だと思っていますが、その理由はよくわかりません。どうもありがとう

編集：明確にするために入力を変更しました

私は次の文法を持っていますが、それはLR（1）ですが、SLR（1）ではないと言われています。

S :: = a A | b A c | dc | bda

A :: = d

なぜなのかわかりません。これをどのように証明しますか？

次の (簡略化された) Bison 文法は、reduce reduce conflict を生成します。

問題はわかります。先読みのトークンが 1 つしかないため、 が であるか(an_idである'(' expr ')'かを判別することは不可能fnです。しかし、どうすれば解決できますか？

パーサーがどのように機能するかを理解したいと思います。LL、LR(0)、LR(1)の部分、構築方法、NFA、DFA、パーステーブルなどについて学びました。

問題は、ある状況でパーサーの要求に応じてレクサーがトークンを抽出する必要があることです。1 つの個別のパスですべてのトークンを抽出することはできません。私はこの種の状況を正確に理解していないので、これについての説明を受け付けています。

問題は、レクサーがどのように仕事をするべきかということです。現在の「コンテキスト」、つまり解析されるはずの現在の非端末に基づいて認識すべきですか？それはまったく違うものですか？GLR 構文解析についてはどうですか?レクサーがさまざまな端末を試すことができる別のケースですか、それとも構文上の問題にすぎませんか? また、それが何に関連しているのかを理解したいと思います.

どうもありがとう

私がしなければならないタスクは次のとおりです。

マジックまたはタウステップの助けを借りてシフト還元ステージを実行する非決定論的マシンを定義することから始めます

ただし、 Compilers: Principles, Techniques & Tools (Aho et. al) またはインターネットで検索しても、マジックまたはタウのステップとは何かについての参照は見つかりません。

誰かが私を正しい方向に向けることができますか？

私は現在、いくつかの言語のパーサーを作成中です。私はこの言語の文法を与えられましたが、この文法にはいくつかの左再帰と非 LL(*) 構造が含まれているため、ANTLR はバックトラッキングを使用してもうまく機能しません。

これらの左再帰と非 LL(*) 構成を削除することは、一見したよりも難しいため、LR(k) または LALR(k) パーサー ジェネレーターを試してみたいと思います。k が高いほど良い。

これらの要件を満たすパーサージェネレーターを誰かに勧めてもらえますか?

• 生成されたパーサーは、ある程度高い（または任意の）ｋを持つＬＲ（ｋ）パーサー、または少なくともある程度高いｋを持つＬＡＬＲ（ｋ）パーサーであることが好ましい。
• 生成されたパーサーは C または C++ で記述されており、C で記述されている場合は C++ コードにリンク可能です。
• ANTLR に似た機能セット (特に AST の書き換え) があればよいでしょう。
• パフォーマンスは最も差し迫った問題ではありません。生成されたパーサーは、多くのメモリと CPU パワーを備えたデスクトップ マシンで使用することを目的としています。

ありがとう、
ジョスト

PS: 自分でググることができないので質問しているわけではありませんが、自分でいくつかのジェネレーターをテストする時間が残っていないためです。したがって、推奨されるパーサー ジェネレーターの使用経験がある場合にのみ回答してください。