Inicjalizacja stosu wartością S Wczytuje symbol z wejścia while (true) if Action(top(stack), input) = S NS <- Goto(top(stack),input) push NS Czyta następny symbol else if Action(top(stack), input) = Rk output k pop |RHS| of production k from stack NS <- Goto(top(stack), LHS_k) push NS else if Action(top(stack),input) = A output valid, return else output invalid, return
Przykład Poniższa gramatyka może być analizowana przez parser SLR, ale nie przez parser LR(0):
(1) E → 1 E (2) E → 1
Rodzina zbiorów sytuacji LR(0) wygląda tak samo dla parserów SLR i LR(0):
Zbiór sytuacji 0 S → • E + E → • 1 E + E → • 1
Zbiór sytuacji 1 E → 1 • E E → 1 • + E → • 1 E + E → • 1
Zbiór sytuacji 2 S → E •
Zbiór sytuacji 3 E → 1 E •
Tabele goto i action dla parsera LR(0) wyglądają następująco: Stan Action Goto1$E0s121s1/r2r232acc3r1r1
Jak można zaobserwować występuje konflikt przesunięcia-redukcji dla stanu 1 i symbolu terminalnego 1. Jednakże zbiór FOLLOW(E) ma postać { $ } dlatego redukcje r1 i r2 będą wstawione tylko dla kolumny $. Rezultatem będą tabele action i goto bez konfliktów:
Stan Action Goto1$E0s121s1r232acc3r1
Zobacz też Generowanie parserów LR Parser LR Parser LALR Parser GLR Analiza składniowa
Bibliografia
Kategoria:Parsery