6
Chaque grammaire LL (1) est-elle aussi LR (1)?Chaque grammaire LL (1) est-elle aussi LR (1)?
A
Répondre
8
Oui, puisque LL et LR analysent les données de gauche à droite; et puisque LL (1) regarde devant un seul jeton, il doit nécessairement être un LR (1). Ceci est également vrai pour LR (k), où k> 1, puisqu'une grammaire LR (k) peut être transformée en grammaire LR (1).
La différence entre les grammaires LR et LL est que LR produit la dérivation la plus à droite, alors que LL produit la dérivation la plus à gauche. Cela signifie donc qu'un analyseur LR peut en fait analyser un ensemble plus grand qu'une grammaire LL à mesure qu'il se construit à partir des feuilles.
Disons que nous avons des productions comme suit:
A -> "(" A ")" | "(" ")"
Alors LL (1) va analyser la chaîne (()):
(()) -> A
-> "(" A ")"
-> "(" "(" ")" ")"
Où que le LR (1) analysera comme suit:
Input Stack Action
(()) 0
()) 0 '('
)) 0 '(' '('
) 0 '(' '(' ')' Reduce using A -> "(" ")"
) 0 '(' A
- 0 '(' A ')' Reduce using A -> "(" A ")"
- 0 A Accept
Pour plus d'informations, voir: http://en.wikipedia.org/wiki/LL_parsing
+0
mais la séquence (des productions) utilisée par LL (1) pour analyser n'est pas toujours dans l'ordre inverse (des productions) utilisé par LR (1) analyser. Même si l'ancien étant le haut et le bas étant l'analyseur de bas en bas, votre raison pour que tout LL (1) soit LR (1) ne semble pas suffisant. – siddharth
+1
Quelque chose étant LR ne signifie pas que l'arbre d'analyse soit identique à l'arbre d'analyse LL inverse, et donc l'analyseur n'utilise pas nécessairement les productions dans l'ordre inverse. Ce que cela signifie, c'est qu'un parseur LR peut correctement analyser le même ensemble de chaînes donné la même grammaire. – Mike
+0
Est-ce que ce fait contredit? http://cs.stackexchange.com/questions/60763/does-my-grammar-contradict-ll-⊆-lr1/60764#60764 – Pranav
Je pense avoir eu cette question au collège un jour il y a plusieurs lunes;) – foreyez