[解決済み】LL(0)パーサーというものがあるのですか？

質問

LL(0)パーサーとLR(0)パーサーの違いを問う質問をどこかで見かけました。LL(0)パーサーというのはあるのでしょうか？もしあれば、どのようにトークンを見ずに解析するのでしょうか？

どのように解決するのですか？

LL(0)パーサーはトークンを見ますが、どのプロダクションを適用するかは決めません。ただ、そのシーケンスが言語に属しているかどうかを判断するだけです。これは、すべての非終端記号は単一の右辺を持たなければならず、再帰は存在してはならないことを意味します。

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

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

なお、@280Z28 が言っているように、可変長の部分 ( ID と STRING )でなければ、文法は LL(0) .

その文法で入力を解析するために適用するプロダクションのシーケンスは、ルックヘッドをゼロにする必要があります。

入力シーケンスの一部がパースされた後に適用できるプロダクションが複数ある場合、決定論のためにルックアヘッドが必要です。

理論的には、文法 が生成します。 その中で、曖昧さ（あるフレーズを導き出す方法が複数あること）は問題ないのです。構文解析では、1つの方法しかないことは意味論（意味）の邪魔になるし、それが私たちの望むところです。

プログラミング言語の解析において、次にどの文法生成物を使うかを知るために必要な情報がルックアヘッドである。

LL(0)言語では、選択肢がないため、入力シーケンスは受け入れられてパースされるか、拒否されるかのどちらかです。