Embed Size (px)
DESCRIPTION
Syntaxanalyse Bottom-Up und LR(0). Daniel Matthey. Agenda. Basics Compileraufbau Grammatiken Ableitungen Beispiel Parse-Baum Mehrdeutigkeit Bottom-Up-Parsing Shift - Reduce -Parser inkl. Beispiel LR(0)-Syntaxanalyse Items Die Funktionen CLOSURE(I) und GOTO(I,X) - PowerPoint PPT Presentation
Citation preview
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Syntaxanalyse Bottom-Up und LR(0)Daniel Matthey
2
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
3
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
4
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Compileraufbau
Lexikalische Analyse
Syntaxanalyse
Semantische Analyse
Zwischencode-Generator
Code-Optimierer
Code-Generator
5
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
6
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Grammatik
Besteht aus:- Terminalen - Nichtterminalen - Produktionen - und einem Startsymbol
7
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Grammatik
Beispiel: E E + E E E * E E ( E ) E id
8
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
9
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Ableitungen
E → E + E → E + id → id + id
E → E + E → id + E → id + id
E E + E E E * E E ( E ) E id
10
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
11
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parse-Baum für id + id
E
E E + E E E * E E ( E ) E id
12
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parse-Baum für id + id
E
+E E
E E + E E E * E E ( E ) E id
13
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parse-Baum für id + id
E
+E E
id
E E + E E E * E E ( E ) E id
14
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parse-Baum für id + id
E
+E E
id id
E E + E E E * E E ( E ) E id
15
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
16
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Mehrdeutigkeit
E E + E E E * E E ( E ) E id
E
+
EE
* id
Beispiel: id * id + id
id id
E
+
EE
*id id id
17
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
18
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Bottom-Up-Parsing
E E + E E E * E E ( E ) E id
+id id
19
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Bottom-Up-Parsing
E E + E E E * E E ( E ) E id
+id id
E
20
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Bottom-Up-Parsing
E E + E E E * E E ( E ) E id
+id id
E E
21
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Bottom-Up-Parsing
E E + E E E * E E ( E ) E id
E
E E
id id+
22
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
23
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
Neue Grammatik:
E E + T | TT T * F | FF ( E ) | id
Rechtsableitung zu id * id: E → T → T * F → T * id → F * id → id * id
24
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
25
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
26
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
$ id * id $ Reduzieren(reduce) durch F → id
27
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
$ id * id $ Reduzieren(reduce) durch F → id
$ F * id $ Reduzieren durch T → F
28
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
$ id * id $ Reduzieren(reduce) durch F → id
$ F * id $ Reduzieren durch T → F
$ T * id $ Verschieben
29
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
$ id * id $ Reduzieren(reduce) durch F → id
$ F * id $ Reduzieren durch T → F
$ T * id $ Verschieben
$ T * id $ Verschieben
30
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
$ id * id $ Reduzieren(reduce) durch F → id
$ F * id $ Reduzieren durch T → F
$ T * id $ Verschieben
$ T * id $ Verschieben
$ T * id $ Reduzieren durch F → id
31
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
$ id * id $ Reduzieren(reduce) durch F → id
$ F * id $ Reduzieren durch T → F
$ T * id $ Verschieben
$ T * id $ Verschieben
$ T * id $ Reduzieren durch F → id
$ T * F $ Reduzieren durch T → T * F
32
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
$ id * id $ Reduzieren(reduce) durch F → id
$ F * id $ Reduzieren durch T → F
$ T * id $ Verschieben
$ T * id $ Verschieben
$ T * id $ Reduzieren durch F → id
$ T * F $ Reduzieren durch T → T * F
$ T $ Reduzieren durch E → T
33
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Stack Eingabe Aktion
$ id * id $ Verschieben(shift)
$ id * id $ Reduzieren(reduce) durch F → id
$ F * id $ Reduzieren durch T → F
$ T * id $ Verschieben
$ T * id $ Verschieben
$ T * id $ Reduzieren durch F → id
$ T * F $ Reduzieren durch T → T * F
$ T $ Reduzieren durch E → T
$ E $ Akzeptieren Angelehnt an DragonBook S.286
34
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
35
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR(0)-Syntaxanalyse
LL(k) und LR(k)-Sprachen:
- erste Buchstabe steht für die Eingabe- zweiter Buchstabe steht für umgekehrte Ableitung- k wird Lookahead genannt
36
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
37
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Items
Statt Grammatiksymbole auf dem Stack nun Zustände, die aus einer Menge von Items bestehenFolgende Items, für die Entscheidungsunterstützung, enthält die Produktion T T * F:
- T .T * F- T T .* F- T T * .F- T T * F.
Wir sehen 3 verschiedene Fälle
38
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
39
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
CLOSURE(I)
Bildet eine Hülle von einer Menge von Items durch:
1. Füge I zu CLOSURE(I) hinzu2. Gibt es ein Item A a.Bb in CLOSURE(I) und eine
Produktion B x, so füge B .x zu CLOSURE(I) hinzu
40
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
GOTO(I,X)
Spezifiziert einen Folgezustand innerhalb eines LR(0)-Automaten anhand der gegebenen Informationen I: Item Menge und X: Grammatiksymbol
41
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
42
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR(0)-Automat
Zunächst Erweiterung der Grammatik zu: E‘ E
E E + E E E * E E ( E ) E id
43
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Der LR(0)-Automat
E E + T | TT T * F | FF ( E ) | id
DragonBook S.294
44
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
GOTO(0,id) gibt uns Zustand 5 an
45
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Der LR(0)-Automat
E E + T | TT T * F | FF ( E ) | id
DragonBook S.294
46
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
(2) 05 $ id * id $ Reduzieren durch F → id
Gibt es keinen Folgezustand, weiß der Parser, dass er reduzieren soll.Bei einer Reduktion wird zunächst der Produktionsrumpf vom Stack entfernt und der Produktionskopf verschoben. Zustand 5 0 3
47
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Der LR(0)-Automat
E E + T | TT T * F | FF ( E ) | id
DragonBook S.294
48
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
(2) 05 $ id * id $ Reduzieren durch F → id
(3) 03 $ F * id $ Reduzieren durch T → F
49
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Der LR(0)-Automat
E E + T | TT T * F | FF ( E ) | id
DragonBook S.294
50
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
(2) 05 $ id * id $ Reduzieren durch F → id
(3) 03 $ F * id $ Reduzieren durch T → F
(4) 02 $ T * id $ Verschieben zu 7
51
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Der LR(0)-Automat
E E + T | TT T * F | FF ( E ) | id
DragonBook S.294
52
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
(2) 05 $ id * id $ Reduzieren durch F → id
(3) 03 $ F * id $ Reduzieren durch T → F
(4) 02 $ T * id $ Verschieben zu 7
(5) 027 $ T * id $ Verschieben zu 5
53
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Der LR(0)-Automat
E E + T | TT T * F | FF ( E ) | id
DragonBook S.294
54
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
(2) 05 $ id * id $ Reduzieren durch F → id
(3) 03 $ F * id $ Reduzieren durch T → F
(4) 02 $ T * id $ Verschieben zu 7
(5) 027 $ T * id $ Verschieben zu 5
(6) 0275 $ T * id $ Reduzieren durch F → id
55
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
(2) 05 $ id * id $ Reduzieren durch F → id
(3) 03 $ F * id $ Reduzieren durch T → F
(4) 02 $ T * id $ Verschieben zu 7
(5) 027 $ T * id $ Verschieben zu 5
(6) 0275 $ T * id $ Reduzieren durch F → id
(7) 02710 $ T * F $ Reduzieren durch T → T * F
56
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
(2) 05 $ id * id $ Reduzieren durch F → id
(3) 03 $ F * id $ Reduzieren durch T → F
(4) 02 $ T * id $ Verschieben zu 7
(5) 027 $ T * id $ Verschieben zu 5
(6) 0275 $ T * id $ Reduzieren durch F → id
(7) 02710 $ T * F $ Reduzieren durch T → T * F
(8) 02 $ T $ Reduzieren durch E → T
57
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Shift-Reduce-Parser mit Hilfe des LR(0)-Automaten
E E + T | TT T * F | FF ( E ) | id
Parsen von id * id
Zeile Stack Symbole Eingabe Aktion
(1) 0 $ id * id $ Verschieben zu 5
(2) 05 $ id * id $ Reduzieren durch F → id
(3) 03 $ F * id $ Reduzieren durch T → F
(4) 02 $ T * id $ Verschieben zu 7
(5) 027 $ T * id $ Verschieben zu 5
(6) 0275 $ T * id $ Reduzieren durch F → id
(7) 02710 $ T * F $ Reduzieren durch T → T * F
(8) 02 $ T $ Reduzieren durch E → T
(9) 01 $ E $ Akzeptieren DragonBook S.298
58
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
59
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parsertabellen
Jeder Parser besteht aus:
- Eingabe- Ausgabe- Stack- Treiberprogramm- Parsertabelle mit zwei Teilen (ACTION und GOTO)
60
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
ACTION(i,a)
Gibt dem Parser konkrete Entscheidungen an:
- Eingabe von Zustand i und Terminal a- Ergebnisse können sein:
- shift j - reduce- accept- error
61
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Agenda
BasicsCompileraufbauGrammatikenAbleitungenBeispiel Parse-BaumMehrdeutigkeit
Bottom-Up-ParsingShift-Reduce-Parser inkl. BeispielLR(0)-SyntaxanalyseItemsDie Funktionen CLOSURE(I) und GOTO(I,X)Der LR(0)-Automat inkl. BeispielParsertabellenBeispiel
62
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parsertabellen
Zustan
d
ACTION GOTO
- id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4 8 2 3
4 s5 s4
5 r6 r6 r6 r6 9 3
6 s5 s4 10
7 s5 s4
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5 DragonBook S.303
E E + T | TT T * F | FF ( E ) | id
63
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR-Parser mit Hilfe der Parsertabelle
Stack Symbole Eingabe Aktion(1) 0 id * id + id $ Verschieben zu 5
Parsen von id * id
E E + T | TT T * F | FF ( E ) | id
64
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parsertabellen
E E + T | TT T * F | FF ( E ) | id
Zustan
d
ACTION GOTO
- id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4 8 2 3
4 s5 s4
5 r6 r6 r6 r6 9 3
6 s5 s4 10
7 s5 s4
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
65
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR-Parser mit Hilfe der Parsertabelle
Parsen von id * id
E E + T | TT T * F | FF ( E ) | id
Stack Symbole Eingabe Aktion(1) 0 id * id + id $ Verschieben zu 5
(2) 05 id * id + id $ Reduzieren durch F → id
66
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parsertabellen
Zustan
d
ACTION GOTO
- id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4 8 2 3
4 s5 s4
5 r6 r6 r6 r6 9 3
6 s5 s4 10
7 s5 s4
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
E E + T | TT T * F | FF ( E ) | id
67
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR-Parser mit Hilfe der Parsertabelle
Parsen von id * id
E E + T | TT T * F | FF ( E ) | id
Stack Symbole Eingabe Aktion(1) 0 id * id + id $ Verschieben zu 5
(2) 05 id * id + id $ Reduzieren durch F → id
(3) 03 F * id + id $ Reduzieren durch T → F
68
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parsertabellen
Zustan
d
ACTION GOTO
- id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4 8 2 3
4 s5 s4
5 r6 r6 r6 r6 9 3
6 s5 s4 10
7 s5 s4
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
E E + T | TT T * F | FF ( E ) | id
69
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR-Parser mit Hilfe der Parsertabelle
Parsen von id * id
E E + T | TT T * F | FF ( E ) | id
Stack Symbole Eingabe Aktion(1) 0 id * id + id $ Verschieben zu 5
(2) 05 id * id + id $ Reduzieren durch F → id
(3) 03 F * id + id $ Reduzieren durch T → F(4) 02 T * id + id $ Verschieben zu 7
70
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parsertabellen
Zustan
d
ACTION GOTO
- id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4 8 2 3
4 s5 s4
5 r6 r6 r6 r6 9 3
6 s5 s4 10
7 s5 s4
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
E E + T | TT T * F | FF ( E ) | id
71
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR-Parser mit Hilfe der Parsertabelle
Parsen von id * id
E E + T | TT T * F | FF ( E ) | id
Stack Symbole Eingabe Aktion(1) 0 id * id + id $ Verschieben zu 5
(2) 05 id * id + id $ Reduzieren durch F → id
(3) 03 F * id + id $ Reduzieren durch T → F(4) 02 T * id + id $ Verschieben zu 7
(5) 027 T * id + id $ Verschieben zu 5
Weitere Tabellen
72
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parsertabellen
Zustan
d
ACTION GOTO
- id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4 8 2 3
4 s5 s4
5 r6 r6 r6 r6 9 3
6 s5 s4 10
7 s5 s4
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
E E + T | TT T * F | FF ( E ) | id
73
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR-Parser mit Hilfe der Parsertabelle
Parsen von id * id
E E + T | TT T * F | FF ( E ) | id
Stack Symbole Eingabe Aktion(1) 0 id * id + id $ Verschieben zu 5
(2) 05 id * id + id $ Reduzieren durch F → id
(3) 03 F * id + id $ Reduzieren durch T → F(4) 02 T * id + id $ Verschieben zu 7
(5) 027 T * id + id $ Verschieben zu 5
(6) 0275 T * id + id $ Reduzieren durch F → id
74
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR-Parser mit Hilfe der Parsertabelle
Parsen von id * id
E E + T | TT T * F | FF ( E ) | id
Stack Symbole Eingabe Aktion(1) 0 id * id + id $ Verschieben zu 5
(2) 05 id * id + id $ Reduzieren durch F → id
(3) 03 F * id + id $ Reduzieren durch T → F(4) 02 T * id + id $ Verschieben zu 7
(5) 027 T * id + id $ Verschieben zu 5
(6) 0275 T * id + id $ Reduzieren durch F → id
(7) 02710 T * F + id $ Reduzieren durch T → T * F
75
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
LR-Parser mit Hilfe der Parsertabelle
Parsen von id * id
E E + T | TT T * F | FF ( E ) | id
Stack Symbole Eingabe Aktion(1) 0 id * id + id $ Verschieben zu 5
(2) 05 id * id + id $ Reduzieren durch F → id
(3) 03 F * id + id $ Reduzieren durch T → F(4) 02 T * id + id $ Verschieben zu 7
(5) 027 T * id + id $ Verschieben zu 5
(6) 0275 T * id + id $ Reduzieren durch F → id
(7) 02710 T * F + id $ Reduzieren durch T → T * F
(8) 02 T + id $ Reduzieren durch E → T
(9) 01 E + id $ Verschieben
(10) 016 E + id $ Verschieben
(11) 0165 E + id $ Reduzieren durch F → id
(12) 0163 E + F $ Reduzieren durch T → F(13) 0169 E + T $ Reduzieren durch E → E + T
(14) 01 E $ Akzeptieren
76
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Parse-Baum
Reduktionsschritte:F idT FF idT T * FE TF idT FE E + T
F
id +id *
F
T
T
E T
E
F
id
77
Syntaxanalyse Bottom-Up und LR(0)
Daniel Matthey
Fragen?
