Beispiel für eine LR -Grammatik, die nicht durch LL dargestellt werden kann?

Question

Alle LL -Grammatiken sind LR -Grammatiken, aber nicht umgekehrt, aber ich habe immer noch Schwierigkeiten, mit der Unterscheidung umzugehen. Ich bin gespannt auf kleine Beispiele, falls vorhanden, von LR -Grammatiken, die keine äquivalente LL -Darstellung haben.

Answer 1

Nun, was die Grammatiken betrifft, ist es einfach-jede einfache linksrezisive Grammatik ist LR (wahrscheinlich LR (1)) und nicht LL. Also eine Listen -Grammatik wie:

list ::= list ',' element | element

ist LR (1) (unter der Annahme, dass die Produktion für Element ist), aber nicht ll. Solche Grammatiken können durch linke und so links in LL-Grammatiken ziemlich leicht umgewandelt werden, so dass dies jedoch nicht zu interessant ist.

Von mehr Interesse sind Sprachen, die LR, aber nicht LL sind - das ist eine Sprache, für die es eine LR (1) -Keppich, aber keine LL (k) -Keppich für km. Ein Beispiel sind Dinge, die optionale nachverfolgende Übereinstimmungen erforderlich sind. Zum Beispiel die Sprache einer beliebigen Anzahl von a Symbole gefolgt von der gleichen oder weniger gleichen Anzahl b Symbole, aber nicht mehr bs - {a^ib^j | i> = j}. Es gibt eine triviale LR (1) Grammatik:

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

Aber keine LL (k) Grammatik. Der Grund dafür ist, dass eine LL -Grammatik entscheiden muss, ob sie ein A+B -Paar oder ein ungeraden A übereinstimmen, wenn Sie sich ein A ansehen, während die LR -Grammatik diese Entscheidung bis nach dem Ende des B oder dem Ende der Eingabe verschieben kann.

Dieser Beitrag Auf cs.stackechange.com hat viele Referenzen dazu