文法があり、LL(1) であるかどうかを確認できます。しかし、文法によって生成された言語が LL(1) であるかどうかを確認する方法はありますか? では、LL(1) 文法と LL(1) 言語の正確な違いは何ですか?
6288 次
1 に答える
16
LL(1) である文法は、LL(1) 言語を定義します。定義上、LL(1) である言語を生成する文法がある場合、その言語は LL(1) です。したがって、その言語に LL(1) 文法があるという事実は、その言語が LL(1) であることを自動的に意味します。 .
詳しく説明すると、言語は一連の文字列であり、その言語の文法はその言語を記述する手段です。LL(1) 文法を持つ言語もあれば、持たない言語もあります。ただし、文法が LL(1) ではないという事実は、それが記述する言語がそうではないという意味ではありません。たとえば、次の文法を考えてみましょう。
A -> ab | ac
この文法は LL(1) ではありません。ターミナル a を見たときに A の生成を予測しようとすると、FIRST/FIRST 競合が含まれるためです。ただし、言語は文法によっても記述されるため、LL(1) 言語を記述します。
A -> aX
X -> b | c
したがって、これらの文法 (ab と ac のみを含む) によって生成される言語は、実際には LL(1) です。
任意の文法によって記述された言語が LL(1) であるかどうかを判断することははるかに困難であり、私の知る限り、それを行う唯一の方法は、最初の文法によって生成された言語の LL(1) 文法を明示的に示すことです。 (これはトリッキーです) または、そのような文法が存在しないことを数学的に証明します。
お役に立てれば！
于 2011-08-20T18:39:25.860 に答える