parsing - LLで表現できないLR文法の例？

Question

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

Answer 1

まあ、文法に関する限り、それは簡単です -- 単純な左再帰文法はすべて LR (おそらく LR(1)) であり、LL ではありません。したがって、リスト文法は次のようになります。

list ::= list ',' element | element

は LR(1) ですが (要素の生成が であると仮定)、LL ではありません。そのような文法は、左因数分解などによってかなり簡単に LL 文法に変換できるため、あまり興味深いものではありません。

さらに興味深いのは、LR であるが LL ではない LANGUAGES です。これは、LR(1) 文法は存在しますが、任意の k に対して LL(k) 文法は存在しない言語です。例としては、オプションの末尾一致が必要なものがあります。たとえば、任意の数のa記号の後に同数またはそれより少ないb記号が続くが、それ以上bの記号が続く言語 -- { a^ib^j | i >= j }。簡単な LR(1) 文法があります:

S ::= a S | P
P ::= a P b | \epsilon

しかし、LL(k) 文法はありません。その理由は、LL 文法では、a を見るときに a+b のペアまたは奇数の a のどちらに一致するかを決定する必要があるのに対し、LR 文法では、b または入力の末尾が検出されるまでその決定を延期できるためです。

cs.stackechange.com のこの投稿には、これに関する多くの参照があります。