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

すべてのLL文法はLR文法ですが、それ以外の方法はありませんが、私はまだこの区別には苦労しています。私は、等価なLL表現を持たないLR文法の小さな例があれば、それがあるかどうか不思議です。LLで表現できないLR文法の例？

2012-01-10 Puppy

文法に関する限り、簡単な左回帰文法はLR（おそらくLR（1））であり、LLではありません。したがって、リスト文法のようなものは次のようなものです：リスト文法は、次のようなものです：リストの文法は、LR（1）（LRではありません）ではなくLLです。そのような文法は、左ファクタリングなどによってLL文法にかなり簡単に変換することができるので、あまり面白くない。

さらに興味深いのは、LRですがLLではなく、LR（1）文法は存在しますが、任意のkに対してLL（k）文法は存在しない言語です。オプションの末尾のマッチを必要とするものが例です。例えば、任意の数のaシンボルの後に同じ数字またはそれ以下の数字が続くbシンボルの言語ですが、それ以上ではありませんb s - {a^i b^j | i> = j}となる。

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

文法はありませんが、LL（k）文法はありません。その理由は、LL文法は、aを見るときにa + bペアまたは奇数aに一致するかどうかを決定する必要があるのに対して、LR文法はbまたは入力の最後を見るまでその決定を延期することができるからです。 cs.stackechange.com上

This postはむしろ考えにくいこの

出典

2012-01-10 22:33:11

についての言及がたくさんあります。その文法は 'if/else'とまったく同じように見えます。つまり、' statement :: = if（...）statement | if（...）statement else（...）statement'です。これは、私が知る限り、LLパーサによってうまく処理されます。 – Puppy

@DeadMG：あなたが気づいているように、他の文法は同じパターンなので、LLではないし、LLパーサでもきれいに扱うことができません。もちろん、手書きのパーサでは、アドホックな回避策（通常はこのケースではミニLRパーサ）を使用できますが、文法がLLではないという事実は変わりません。 –

興味深い。これは、この構文に従う事実上すべての*言語が非LL文法を持ち、事実上すべてのLLパーサ生成者が回避策を持っていなければならないということですか？ – Puppy

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

答えて

関連する問題