parsing - LL（0）パーサーのようなものはありますか？

Question

LL（0）パーサーとLR（0）パーサーの違いを尋ねる質問をどこかで見ました。LL（0）パーサーのようなものはありますか？もしそうなら、トークンを見ずにどのように解析しますか？

Answer 1

LL（0）パーサーはトークンを調べますが、どのプロダクションをトークンに適用するかを決定しません。シーケンスがその言語に属しているかどうかを判断するだけです。これは、すべての非終端記号の右側が1つでなければならず、再帰がない可能性があることを意味します。

G == ID name lastname
name == STRING
lastname == STRING

# lexer rules
# -----------
ID == [0-9]+
STRING == <unicode>+

@ 280Z28で述べたように、可変長の部分（IDおよびSTRING）を処理するには別のレクサーが必要であることに注意してください。そうしないと、文法は。になりませんLL(0)。

その文法で入力を解析するために適用する一連のプロダクションでは、先読みがゼロである必要があります。

指定された入力シーケンスの一部が解析された後に適用できるプロダクションが複数ある場合、決定論には先読みが必要です。

理論的には、文法は言語を生成し、その点で、あいまいさ（特定のフレーズを導出するための複数の方法がある）は問題ありません。構文解析では、唯一無二の方法を持つことは意味論（意味）の方法であり、それが私たちが望んでいることです。

プログラミング言語の構文解析では、先読みは、次に使用する文法生成を知るために必要な情報です。

LL（0）言語では、選択肢がないため、入力シーケンスが受け入れられて解析されるか、拒否されます。

Answer 2

LR（k）のkは、先読みトークンの数を示します。実行するアクションを決定するために、常に少なくとも1つのトークンを使用します。ウィキペディアのページページには、これに関する詳細情報があります。

直感的には、追加の先読み記号を使用すると、より多くの情報を使用して削減を選択できるため、より大きなクラスの文法を競合することなく表現できます。

Answer 3

私がコンパイラーを取り上げたとき、LL（1）については話しましたが、コンパイラーについては話しませんでした。ウィキペディアにはそれらについての言及はありません。

LL（0）パーサーは、パーサーがストリーム内の次のトークンを知らなくても決定を下すことができることを意味します。そのプロパティを持つ言語が存在する場合、それらはかなりまれであると思います。

Answer 4

他の回答に示されている理由により、通常、LL（0）解析については耳にしません。重要な解析では、何らかの入力を確認する必要があります。ただし、LL（1）パーサーの一部は、実際にはLL（0）パーサーとして実行できます。

たとえば、これは1つのプロダクションで先読みを必要とする単純なBNF文法です。

S -> A
A -> B
B -> 'a' | 'b'

Bプロダクションには、入力の2つの別個の文字列「a」と「b」に対応する2つの右側があります。したがって、パーサーは適切なRHSを選択するために入力を確認する必要があります。

ただし、SプロダクションもAプロダクションも選択の余地はありません。したがって、実際にはFIRSTセット（「a」と「b」の両方を含む）が関連付けられていますが、構文解析の決定を行うためにFIRSTセットは必要ありません。つまり、S->AおよびA->B製品はLL（0）サブグラマー。したがって、最適化は、これら2つの非終端記号のFIRSTセットを無視することです。

これを明確にするために、入力が文字列'b'であると仮定します。次に、パーサーは、入力を確認する前に、トップダウンの派生S-> AaおよびA->Bを自動的に生成できます（これはオートマトンと呼ばれます）。次に、最も内側の派生では、Bの場合、入力を調べて、解析ツリーを完成させるために使用するBプロダクションを決定する必要があります。

この種の最適化の利点は、エラー検出（入力がないか、「a」または「b」以外の入力が検出される）を、他のプロダクションを解析するときではなく、入力が検査された時点で実行できることです。 。必要に応じて、エラーメッセージは、Bプロダクションだけでなく、AおよびSプロダクションもすでに生成されているため参照できます。最適化なしでSの最初のセットを調べた場合、S-> Aが試行されていることがわかっている場合は、エラーを報告する必要があります。これは、ユーザーのコンテキスト情報ではありません。