-
Notifications
You must be signed in to change notification settings - Fork 0
/
LR-table.txt
132 lines (94 loc) · 3.94 KB
/
LR-table.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
Grammar
-------
EProd. Exp ::= Exp1;
EAdd. Exp ::= Exp "+" Exp1;
EInt. Exp1 ::= Integer;
EMul. Exp1 ::= Exp1 "*" Integer;
LInt. Integer ::= int;
%start. S ::= Exp eof;
Generated parse table (in Happy-info layout)
--------------------------------------------
State 0
int shift to state 1
Exp goto state 2
Exp1 goto state 3
Integer goto state 4
State 1
eof reduce with rule LInt
'*' reduce with rule LInt
'+' reduce with rule LInt
State 2
eof reduce with rule %start
'+' shift to state 5
State 3
eof reduce with rule EProd
'*' shift to state 7
'+' reduce with rule EProd
State 4
eof reduce with rule EInt
'*' reduce with rule EInt
'+' reduce with rule EInt
State 5
int shift to state 1
Exp1 goto state 6
Integer goto state 4
State 6
eof reduce with rule EAdd
'*' shift to state 7
'+' reduce with rule EAdd
State 7
int shift to state 1
Integer goto state 8
State 8
eof reduce with rule EMul
'*' reduce with rule EMul
'+' reduce with rule EMul
States
------
State 0
S → . Exp eof
Exp → . Exp "*" Exp1
Exp → . Exp1
Exp1 → . Exp1 "*" Integer
Exp1 → . Integer
Integer → . int
| State | Parse item 1 | Parse item 2 |
|-------|---------------------------|---------------------------|
| 0 | S → . Exp eof | |
| 1 | Integer → int . | |
| 2 | S → Exp . eof | Exp → Exp . "+" Exp1 |
| 3 | Exp → Exp1 . | Exp1 → Exp1 . "*" Integer |
| 4 | Exp1 → Integer . | |
| 5 | Exp → Exp "+" . Exp1 | |
| 6 | Exp → Exp "+" Exp1 . | Exp1 → Exp1 . "*" Integer |
| 7 | Exp1 → Exp1 "*" . Integer | |
| 8 | Exp1 → Exp1 "*" Integer . | |
Parse table
-----------
| State | eof | + | * | int | Exp | Exp1 |Integer|
|-------|-------|-------|-------|-------|-------|-------|-------|
| 0 | | | | s1 | g2 | g3 | g4 |
| 1 | LInt | LInt | LInt | | | | |
| 2 | %start| s5 | | | | | |
| 3 | EProd | EProd | s7 | | | | |
| 4 | EInt | EInt | EInt | | | | |
| 5 | | | | s1 | | g6 | g4 |
| 6 | EAdd | EAdd | s7 | | | | |
| 7 | | | | s1 | | | g8 |
| 8 | EMul | EMul | EMul | | | | |
Parser run on 1+2*3
-------------------
ε . '1' '+' '2' '*' '3' -- shift
int(1) . '+' '2' '*' '3' -- reduce with rule LInt
Integer . '+' '2' '*' '3' -- reduce with rule EInt
Exp1 . '+' '2' '*' '3' -- reduce with rule EProd
Exp . '+' '2' '*' '3' -- shift
Exp '+' . '2' '*' '3' -- shift
Exp '+' int(2) . '*' '3' -- reduce with rule LInt
Exp '+' Integer . '*' '3' -- reduce with rule EInt
Exp '+' Exp1 . '*' '3' -- shift
Exp '+' Exp1 '*' . '3' -- shift
Exp '+' Exp1 '*' int(3) . -- reduce with rule LInt
Exp '+' Exp1 '*' Integer . -- reduce with rule EMul
Exp '+' Exp1 . -- reduce with rule EAdd
Exp . -- halt