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

Question

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

Answer 1

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

list ::= list ',' element | element

LR（1）（要素の生産があると仮定）が、LLではなく。このような文法は、左翼などによってLL文法にかなり簡単に変換される可能性があるため、これはあまり面白くありません。

より興味深いのは、LRではないがLRである言語です。これは、LR（1）文法が存在する言語ですが、kにはLL（k）文法はありません。例は、オプションのトレーリングマッチが必要なものです。たとえば、任意の数の言語 a シンボルに続いて、同じ数が少ない b シンボルですが、それ以上ではありません bs- {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では、これについて多くの参照があります