Jeder LR (0) Grammatik SLR (1), aber umgekehrt muss nicht unbedingt wahr sein, warum?

Question

Jeder LR (0) Grammatik SLR (1), aber umgekehrt muss nicht unbedingt wahr sein, warum?

Answer 1

Grundsätzlich ein SLR (1) Grammatik kann shift-reduzieren Konflikte lösen, die in einem entsprechenden LR existieren (0) Grammatik. Nehmen wir das Beispiel Grammatik auf Wikipedia SLR-Parser Seite (was dies zu einem niedrigeren, strengere Ebene erklärt) :

1. S ? E
2. E ? 1 E
3. E ? 1

Wenn ein LR (0) Parser ein E-Parsing und eine "1" ist das nächste Eingabesymbol, könnte es erkennen E und reduzieren (Regel 3) oder es könnte zu verschieben, um eine Gefolgschaft E (Regel 2) zu analysieren. Weil es nicht nach vorne schauen kann, ein LR (0) kann nicht bestimmen, welche zu tun. Dies wird noch deutlicher, wenn wir an der Artikel die LR (0) könnte die Verarbeitung, wenn es trifft auf ein "1" (das End-of-string Symbol hinzugefügt wurde):

• E ? 1 • E $
• E ? 1 • $

Die erste wäre eine Verschiebung erfordern, die zweite erfordert eine reduzieren.

Mit der obigen Grammatik, ein SLR (1) Grammatik kann ein Symbol nach vorne schauen und festzustellen, welche Maßnahmen zu ergreifen. E kann nur von $ gefolgt werden, so eine Aktion zu reduzieren am Ende der Zeichenkette nur gültig ist. Dies entspricht den zweiten Punkt, wo Sie das nächste Symbol sehen können, ist ein „$“.

Für ein weiteres Beispiel Grammatik, die SLR (1) und nicht LR (0), siehe Fegaras'