Exemple d'une grammaire LR qui ne peut pas être représenté par LL?

Question

Toutes les LL sont grammaires LR, grammaires, mais pas l'inverse, mais je lutte encore pour faire face à la distinction. Je suis curieux de petits exemples, le cas échéant exist, de grammaires LR qui n'ont pas une représentation équivalente LL.

Answer 1

Eh bien, en ce qui concerne les grammaires, il est facile - tout simplement laissé récursif la grammaire est LR (probablement LR (1)) et non LL. Donc, une grammaire de liste comme:

list ::= list ',' element | element

est LR (1) (en supposant que la production de l'élément est), mais pas LL. Ces grammaires peuvent être assez facilement convertis en grammaires LL par-gauche et l'affacturage tel, donc ce n'est pas trop intéressant cependant.

plus d'intérêt est les langues qui sont LR mais pas LL - qui est une langue pour laquelle il existe un LR (1) grammaire mais pas de grammaire LL (k) pour tout k. Un exemple est des choses qui ont besoin de matchs facultatif à la fin. Par exemple, la langue d'un certain nombre de symboles de a suivi par le même nombre ou moins de symboles de b, mais pas plus bs - {a ^ i b ^ j | i> = j}. Il y a un LR trivial (1) grammaire:

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

mais pas de grammaire LL (k). La raison en est qu'une grammaire LL doit décider si correspond à a + b paire ou un étrange quand on regarde un un, alors que la grammaire LR peut reporter cette décision qu'après avoir voit le b ou la fin de l'entrée.

Ce message sur cs.stackechange.com a beaucoup de références sur cette