计算机代考程序代写 compiler AI Compiler Design Week 7 – cscodehelp代写
Compiler Design Week 7
Much of the materials on the slides were originally prepared by Prof. Engelen, FSU.
Detailed content
Weekly program
Week Week Week Week Week Week
Week
Week Week Week Week Week Week
1 – Introduction to Compiler Design 2 – Lexical Analysis
3 – CD Programming Language
4 – Syntax Analysis
5 – Top Down Parsing
6 – Symbol Table and Error Recovery
7 – Bottom-Up Parsing
8 – Stack Machine (SM) Architecture
9 – Semantic Analysis 10 – Code Generation 11 – Code Optimisation 12 – Revision
13 – Extra revision (if needed)
2
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
Week 07 Lecture Outline
Bottom Up Parsing
Bottom Up Parsing
Shift Reduce Parsing
Conflicts in Shift Reduce Parsing
LR(k) Parsing
Simple LR (SLR) Parser Table Construction LR(1) Parser Table Construction
LALR Parser Table Construction
3
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
Bottom-Up Parsing
• A process of “reducing” a string w to the start symbol of the grammar.
• At each reduction step, a specific substring matching the body of a
production is replaced by the nonterminal at the head of that production.
• LR methods (Left-to-right, Rightmost derivation in reverse)
– SLR, Canonical LR, LALR
Compare to top down parsing:
• Begins at the leaves (the bottom) and works up towards the root (the top).
• Traces the rightmost derivation in reverse.
• Uses the grammar rule to replace the rules’ body (RHS) with its head
(LHS).
• Key Decision: When to reduce and what production to apply
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
4
Reductions
Grammar:
S a A B e A A b c | b B d
These match
production’s right-hand sides
Reducing a sentence:
a b b c d e a A b c d e a A d e
a A B e
S
Shift-reduce corresponds to a rightmost derivation: S rm a A B e
rm a A d e rm a A b c d e rm a b b c d e
S
AAA AAABAB
abbcdeabbcdeabbcdeabbcde
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
5
Handles
A handle is a substring that matches the body of a production, and whose reduction represents one step along the reverse of a rightmost derivation.
Grammar:
a b b c d e a Ab c d e a Ad e
S a AB e
A A b c | b
Bd aABe
Handle
S
a b b c d e
a A b c d e
a A A c d e (result is not a sentential form) …?
∗
If 𝑆 ֜𝑟𝑚 𝛼𝐴𝑤 ֜𝑟𝑚 𝛼𝛽𝑤, then production A in the position
following is a handle of w
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
NOT a handle, because further reductions will fail
6
Handle Pruning
Suppose
S֜𝛾֜𝛾֜𝛾…֜𝛾 ֜𝛾=𝑤 𝑟𝑚 0 𝑟𝑚 1 𝑟𝑚 2 𝑟𝑚 𝑛−1 𝑟𝑚 𝑛
To reconstruct the derivation in the reverse order
• Locate the handle n in n
• Replace n in by An where An n to obtain n-1
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
7
Shift-Reduce Parsing
• Stack holds grammar symbols and a buffer holds the rest of the input
• The handle always appears at the top of the stack
• Starts with:
• Operations:
Stack Input $ w$
– Shift. Shift the next input symbol onto the top of the stack.
– Reduce. The right end of the string to be reduced must be at the top of the stack. Locate the left end of the string within the stack and decide with what nonterminal to replace the string.
– Accept. Announce successful completion of parsing.
– Error. Discover a syntax error and call an error recovery routine
• Accept when Stack Input $S $
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
8
Shift-Reduce Parsing
Stack
Input
Action
$
$id
$F
$T
$T * $T * id $T * F $T
$E
id*id$ *id$ *id$ *id$ id$ $ $ $ $
shift
reduce F id reduce T F shift
shift
reduce F id reduce T T * F reduce E T accept
Grammar:
E E+T |T TT*F|F F ( E ) | id
Find handles to reduce
• Handle will always appear on the top of the stack.
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
9
Conflicts in Shift-Reduce Parsing
Stack
Input
Action
$
$id
$E
$E+ $E+id $E+E $E+E* $E+E*id $E+E*E $E+E $E
id+id*id$ +id*id$ +id*id$ id*id$ *id$ *id$ id$ $ $ $ $
shift
reduce E id shift
shift
reduce E id shift (or reduce?) shift
reduce E id reduce E E * E reduce E E + E accept
Grammar:
EE+E EE*E E(E) E id
Find handles to reduce
How to resolve conflicts?
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
10
Conflicts
• For some CFGs shift-reduce parsing cannot be used.
– Every shift-reduce parser for such a grammar can face
• Shift/reduceconflictorreduce/reduceconflict
• knowing the entire stack contents and the next k input symbol,
cannot help
– These are non-LR grammars
• AnambiguousgrammarcanneverbeLR
• Shift-reduce and reduce-reduce conflicts are caused by
– The limitations of the LR parsing method (even when the grammar is unambiguous)
– Ambiguity of the grammar
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
11
Shift-Reduce Conflicts
Stack
$…
$…if E then S
Input
…$ else…$
Action
…
shift or reduce?
Ambiguous grammar:
S if E then S
| if E then S else S | other
Resolve in favor of shift, so else matches closest if
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
12
Reduce-Reduce Conflicts
Stack
Input
Action
$ $a
aa$ a$
shift
reduce A a or B a
Grammar:
CAB Aa Ba
Resolve in favor
of reduce A a, otherwise we’re stuck!
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
?
13
LR(k) Parsing
• Intuitively, a grammar is LR if a left-to-right shift-reduce parser be able to recognize handles of right-sentential forms when they appear on top of the stack.
• k = 0 or k=1 are of practical interest
– When (k) is omitted, k is assumed to be 1
• Advantages of LR parsers
– can be constructed to recognize virtually all context-free PL constructs
• Non-LRCFGsexistbutnotnecessaryforPLconstructs
– Most general non-backtracking shift reduce parsing method
– Can detect a syntactic error as soon as possible
– LR(k) grammars are proper superset of LL(k) grammars
• Drawback:
– Too much work to construct by hand
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
14
Use DFA for Shift/Reduce Decisions
• How does a shift-reduce parser know when to shift and when to reduce?
1
C 0A2
a a
3 Grammar:
SC CAB Aa Ba
goto(I0,a) COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
B4$
accept
start
5
goto(I0,C) goto(I0,A)
State I2: C A•B B •a
State I4: C A B•
goto(I2,B) goto(I2,a)
State I0: S •C C •A B A •a
31/08/2021
Can only reduce A a (not B a)
State I1: S C•
State I5: B a•
State I3: A a•
15
DFA for Shift/Reduce Decisions
Grammar:
SC CAB Aa Ba
goto(I0,a)
The states of the DFA are used to determine if a handle is on top of the stack
Stack
$0 $0 $0a3
$0A2 $0A2a5 $0A2B4 $0C1
Input
aa$ aa$ a$
a$ $ $ $
Action
start in state 0
shift (and goto state 3) reduce A a (goto 2)
shift (goto 5)
reduce B a (goto 4) reduce C AB (goto 1) accept [reduce S C]
State I0: S •C C •A B A •a
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
State I3: A a•
16
Model of an LR Parser
a1
a2
…
ai
…
an
$
input stack
LR Parsing Program (driver)
sm
sm-1
sm-2
…
…
$
Each state summarizes the information contained in the stack below it.
31/08/2021
Parsing Table
shift reduce accept
error
output
action
goto
DFA
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
17
LR Parsing
Configuration ( = LR parser state): (s0 s1 s2 …sm, ai ai+1 …an $)
stack input
If action[sm,ai] = shift s, then push s, and advance input:
(s0 s1 s2 …sm,s, ai+1 …an $)
If action[sm,ai] = reduce A and goto[sm-r,A] = s with r=|| then pop r symbols, and push s:
(s0 s1 s2 …sm-r,s, ai ai+1 …an $) If action[sm,ai] = accept, then stop
If action[sm,ai] = error, then attempt recovery
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
18
Example LR Parse Table
ACTION
GOTO
id + * ( ) $
ETF
123
823
93 10
state
Grammar:
1. E E + T 2. E T
3. T T * F 4. T F
5. F ( E ) 6. F id
Shift & goto 5
Reduce by
production #1
31/08/2021
0 s5 s4 1s6 acc
2
3
4 s5 5
6 s5 7 s5 8
9
10
r2 s7
r2 r2 r4 r4
r6 r6
r4 r6
r4 r6
s4
s4
s4
s6 s11
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
11r5r5
r1 s7
r3 r3
r1 r1 r3 r3 r5 r5
19
Example LR Parsing
Grammar:
1. E E + T 2. E T
3. T T * F 4. T F
5. F ( E ) 6. F id
Stack
Input
Action
$0
$05 $03 $02 $027
$ 0 27 5 $ 0 2 7 10 $02 $01 $016
$ 0 16 5 $ 0 16 3 $ 0 16 9 $01
id*id+id$ *id+id$ *id+id$ *id+id$ id+id$ +id$ +id$ +id$ +id$ id$ $ $ $ $
shift 5 reduce reduce shift 7 shift 5 reduce reduce reduce shift 6 shift 5 reduce reduce reduce accept
6 goto 3 4 goto 2
6 goto 10 3 goto 2 2 goto 1
6 goto 3 4 goto 9 1 goto 1
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
20
SLR Grammars
• •
SLR (Simple LR): a simple extension of LR(0) shift-reduce parsing SLR eliminates some conflicts by populating the parsing table with
S E
E id + E E id
goto(I0,id)
Shift on + goto(I3,+)
FOLLOW(E)={$} thus reduce on $
reductions A on symbols in FOLLOW(A)
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
State I0:
S •E
E •id + E E •id
State I2:
E id•+ E E id•
21
SLR Parsing Table
• Reductions do not fill entire rows
• Otherwise the same as LR(0)
1. S E
2. E id + E 3. E id
Shift on + FOLLOW(E)={$}
thus reduce on $ COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
0 1 2 3 4
id + $
s2
acc
E
1
4
s3 r3
s2
r2
31/08/2021
22
LR(0) items and Automaton
LR(0) automaton state: a set of items
accept
goto(I0,C) goto(I0,A)
goto(I0,a) Transitions: directs
shift/reduce operations
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
goto(I2,B) goto(I2,a)
LR(0) item
State I0: S •C C •A B A •a
State I1: S C•
$
State I4: C A B•
State I2: C A•B B •a
State I5: B a•
State I3: A a•
LR(0) automaton
23
LR(0) items and Automaton
• An LR parser makes shift-reduce decisions by maintaining states to
keep track of where we are in a parse.
• States: a set of LR(0) items
• LR (0) Item (item) of a grammar G is a production of G with a dot at some position of the body.
– Thus, production AXYZ yields the four items A•XYZ
AX•YZ AXY•Z AXYZ•
– Note that production A has one item [A •]
• An item indicates how much of a production we have seen at a given
point in the parsing process.
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
24
LR(0) items and Automaton
• Canonical LR(0) collection: Collection of sets of LR(0) items,
• LR (0) automaton: A DFA constructed from canonical LR(0) collection,
– used to make parsing decisions
– Each state of LR(0) automaton represents a set of items in the canonical LR(0) collection.
• Augmented grammar: If G is a grammar with start symbol S, then G’ , the augmented grammar for G, is G with a new start symbol S’ and production S’S.
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
25
LR(0) items and Automaton
• Given, I is a set of items
• Closure of (I):
1. add every item in I to CLOSURE(I).
2. If A ·B is in CLOSURE(I) and B is a production, then add the item
Bto CLOSURE(I) if it is not already there.
3. Repeat Step 2 until no more new items can be added
Example
CLOSURE({[E’ •E]}) =
{ [E’ • E] } { [E’ • E]
[E • E + T]
[E • T] } Add [E•]
{ [E’ • E]
[E • E + T] [E • T]
{ [E’ • E]
[E • E + T] [E • T] [T•T*F] [T • F]
[F • ( E )] [F • id] }
Augmented Grammar E’ E
E E+T | T TT*FIF
F (E) I id
Add [F•]
• Kernel item: , S’ S, and all items whose dots are not at the left end
• Nonkernel item: all items with their dots at the left end, except for S’ S
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
Add[T•] [T•T*F] [T • F] }
26
LR(0) items and Automaton
• GOTO function is used to define the transitions in the LR(0) automaton
• Given, I is a set of items and X is a grammar symbol
• GOTO(I,X): is defined to be the closure of the set of all items [A X·] such that [A ·X] is in I.
Example
Augmented Grammar E’ E
E E+T | T
TT* F I F
F (E) I id
I = {E’ E, E E+T}
GOTO(I,+) = CLOSURE(E E+T} ) = {E E+T
T T* F TF
F (E) F id }
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
27
Constructing the set of LR(0) Items of a Grammar
1. The grammar is augmented with a new start symbol S’ and production S’S
2. Initially, set C = CLOSURE({[S’•S]}) (this is the start state of the DFA)
3. For each set of items I C and each grammar symbol X (NT) such that GOTO(I,X) C and GOTO(I,X) , add the set of items GOTO(I,X) to C
4. Repeat 3 until no more sets can be added to C
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
28
Example SLR Grammar and LR(0) Items
Augmented grammar: 1. C’ C 2. C A B 3. A a
4. B a
start
GOTO(I0,a) COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
I0 = CLOSURE({[C’ •C]})
I1 = GOTO(I0,C) = CLOSURE({[C’ C•]}) …
final
31/08/2021
GOTO(I0,C) GOTO(I0,A)
GOTO(I2,B) GOTO(I2,a)
State I0: C’ •C C •A B A •a
State I1: C’ C•
State I4: C A B•
State I2: C A•B B •a
State I5: B a•
State I3: A a•
29
Constructing SLR Parsing Tables
1. Augment the grammar with S’S
2. Construct the set C={I0,I1,…,In} of LR(0) items
3. ACTION part of the table for state i is determined as follows:
I. If [A•a] Ii and GOTO(Ii,a)=Ij then set ACTION[i,a]=shift j . [a is a terminal]
II. If [A•] Ii then set ACTION[i,a]=reduce A for all a FOLLOW(A) [apply only if AS’]
III. If [S’S•] is in Ii then set ACTION[i,$]=accept
4. GOTO part of the table for state j is determined as follows:
5. 6. 7.
I. If GOTO(Ii,A)=Ij then set GOTO[i,A]=j [A is a nonterminal] Repeat 3-4 until no more entries added
The initial state i is the Ii holding item [S’•S]
All entries not defined by above rules are made “error”
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
30
Example SLR Parsing Table
State I0: C’ •C C •A B A •a
State I1: C’ C•
State I3: A a•
State I5: B a•
Grammar: 1. C’ C 2. C A B 3. A a 4. B a
FOLLOW(A) = {a} FOLLOW(B) = {$} FOLLOW(C) = {$}
0 1 2 3 4 5
a$
s3
acc
s5 r3
r2 r4
CAB
12
4
C 0A2
B
4
1
start
a a
5 3
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
State I2: C A•B B •a
State I4: C A B•
31
SLR Parsing Table Construction: Example 2
Grammar E E+T ET TT*F TF
F (E) F id
Parsing Table on Slide 20
LR(0) Automata
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
32
SLR and Ambiguity
• Every SLR grammar is unambiguous, but not every
unambiguous grammar is SLR
• Consider for example the unambiguous grammar SL=R|R
L * R | id RL
I0:
S’ •S
S •L=R S •R
L •*R
L •id
R •L
I1:
S’ S•
I2:
S L•=R R L•
I3:
S R•
I4:
L *•R R •L L •*R L •id
I5:
L id•
I6:
S L=•R R •L
L •*R
L •id
I7:
L *R•
I8:
R L•
action[2,=]=s6no Has no SLR action[2,=]=r5 parsing table
I9:
S L=R•
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
33
LR(1) Grammars
• SLR too simple
• LR(1) parsing uses lookahead to avoid unnecessary conflicts in parsing table
• LR(1) item = LR(0) item + lookahead
LR(0) item: [A•]
LR(1) item: [A•, a]
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
34
SLR Versus LR(1)
• Split the SLR states by adding LR(1) lookahead
• Unambiguous grammar S L = R| R
L * R | id RL
split
I2:
S L•=R
R L•
31/08/2021
S L•=R
action[2,=]=s6
Should not reduce, because no
right-sentential form begins with R= COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
R L•
35
LR(1) Items
• An LR(1) item [A•, a]
contains a lookahead terminal a, meaning already on top of the stack, expect to see a
• For items of the form [A•, a]
the lookahead a is used to reduce A only if the next input is a
• For items of the form [A•, a]
with the lookahead has no effect
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
36
The Closure Operation for LR(1) Items
1. Start with CLOSURE(I) = I
2. If [A•B, a] CLOSURE(I) then for each production B in the grammar and each terminal b FIRST(a), add the item [B•, b] to I if not already in I
3. Repeat 2 until no new items can be added
Example:
S S SL=R|R L * R | id RL
CLOSURE([S •S, $])
[S •S, $]
[S •L=R, $] [S •R, $] [L •*R, =] [L •id, =] [R •L, $] [L •*R, $] [L •id, $]
[S •S, $] [S •L=R, $] [S •R, $] [L •*R, =/$] [L •id, =/$] [R •L, $]
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
37
The GOTO Operation for LR(1) Items
1. For each item [A•X, a] I, add the set of items CLOSURE({[AX•, a]}) to GOTO(I,X) if not already there
2. Repeat step 1 until no more items can be added to GOTO(I,X)
Example:
I0:
[S’ •S, [S •L=R, [S •R,
[L •*R, [L •id, [R •L,
$] GOTO(I0,S)=I1 $] GOTO(I0,L)=I2 $] GOTO(I0,..)=.. =/$] GOTO(I0,..)=..
=/$] GOTO(I0,..)=.. $] GOTO(I0,..)=..
I1: I2:
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
[S L•=R, $] GOTO(I2,..)=.. [R L•, $]
31/08/2021
[S’ S•, $]
38
Constructing the set of LR(1) Items of a Grammar
1. Augment the grammar with a new start symbol S’ and production S’S
2. Initially, set C = closure({[S’•S, $]}) (this is the start state of the DFA)
3. For each set of items I C and each grammar symbol X (NT) such that goto(I,X) C and goto(I,X) , add the set of items goto(I,X) to C
4. Repeat 3 until no more sets can be added to C
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
39
Example Grammar and LR(1) Items
• Unambiguous LR(1) grammar: SL=R|R
L * R | id RL
• Augment with S’ S
• LR(1) items (next slide)
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
40
I0:
I6:
[S’ •S, [S •L=R, [S •R,
[L •*R, [L •id, [R •L,
$] GOTO(I0,S)=I1 $] GOTO(I0,L)=I2 $] GOTO(I0,R)=I3 =/$] GOTO(I0,*)=I4
=/$] GOTO(I0,id)=I5 $] GOTO(I0,L)=I2
I1: I2:
I3: I4:
I7: I8:
I9: I10:
I11:
[S L•=R, $] GOTO(I0,=)=I6 [R L•, $]
[L *•R, [R •L, [L •*R, [L •id,
$] GOTO(I11,R)=I13 $] GOTO(I11,L)=I10 $] GOTO(I11,*)=I11 $] GOTO(I11,id)=I12
[L *•R, [R •L, [L •*R, [L •id,
=/$] GOTO(I4,R)=I7 =/$] GOTO(I4,L)=I8 =/$] GOTO(I4,*)=I4 =/$] GOTO(I4,id)=I5
I5:
31/08/2021
I12: I13:
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
[L *R•, =/$]
[S’ S•, $]
[R L•, =/$]
[S L=R•, $]
[R L•, $]
[S R•, $]
[L id•, $]
[L id•, =/$]
[L *R•, $]
[S L=•R, [R •L,
[L •*R, [L •id,
$] GOTO(I6,R)=I4 $] GOTO(I6,L)=I10 $] GOTO(I6,*)=I11 $] GOTO(I6,id)=I12
41
Constructing Canonical LR(1) Parsing Tables
1. 2. 3.
4.
5. 6. 7.
Augment the grammar with S’S
Construct the set C={I0,I1,…,In} of LR(1) items
ACTION part of the table for state i is determined as follows:
If [A•a, b] Ii and GOTO(Ii,a)=Ij then set action[i,a]=shift j
I.
II. If [A•, a] Ii then set ACTION[i,a]=reduce A (only if AS’)
III. If [S’S•, $] is in Ii then set ACTION[i,$]=accept
I.
GOTO part of the table for state j is determined as follows: If GOTO(Ii,A)=Ij then set GOTO[i,A]=j
Repeat 3-4 until no more entries added
The initial state i is the Ii holding item [S’•S,$]
All entries not defined by above rules are made “error”
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
42
Example LR(1) Parsing Table
Grammar:
1. S’ S
2. S L = R 3. S R
4. L * R
5. L id
6. R L
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
43
LALR(1) Grammars
• LR(1) parsing tables have many states
• LALR(1) parsing (Look-Ahead LR) combines LR(1) states to reduce table size
• Less powerful than LR(1)
– Will not introduce shift-reduce conflicts, because shifts do not use lookaheads
– May introduce reduce-reduce conflicts, but seldom do so for grammars of programming languages
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
44
Constructing LALR(1) Parsing Tables
1. Construct sets of LR(1) items
2. Combine LR(1) sets with sets of items that share the same first part
I4: [L *•R, =] [R •L, =] [L •*R, =] [L •id, =]
I11: [L *•R, $] [R •L, $] [L •*R, $] [L •id, $]
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
[L *•R, =/$] [R •L, =/$] [L •*R, =/$] [L •id, =/$]
Shorthand for two items in the same set
45
Example LALR(1) Grammar
• Unambiguous LR(1) grammar: SL=R|R
L * R | id RL
• Augment with S’ S
• LALR(1) items (next slide)
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
46
[S’ •S, [S •L=R, [S •R,
[L •*R, [L •id, [R •L,
$] GOTO(I0,S)=I1 $] GOTO(I0,L)=I2 $] GOTO(I0,R)=I3 =] GOTO(I0,*)=I4 =] GOTO(I0,id)=I5 $] GOTO(I0,L)=I2
[S’ S•, $]
I0:
I1: I2:
I3: I4:
I5:
I7: I8: I9:
I6:
[S L•=R, $] GOTO(I0,=)=I6 [R L•, $]
[S R•, $]
[L *•R, [R •L, [L •*R, [L •id,
=/$] GOTO(I4,R)=I7 =/$] GOTO(I4,L)=I9 =/$] GOTO(I4,*)=I4 =/$] GOTO(I4,id)=I5
[L id•, =/$]
[S L=•R, [R •L,
[L •*R, [L •id,
$] GOTO(I6,R)=I8 $] GOTO(I6,L)=I9 $] GOTO(I6,*)=I4 $] GOTO(I6,id)=I5
[L *R•, =/$]
[S L=R•, $]
[R L•, =/$]
47
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
Example LALR(1) Parsing Table
0 1 2 3 4 5 6 7 8 9
id * = $
s5 s4
acc
s6 r6 r3
s5 s4
r5 r5
s5 s4
r4 r4
r2 r6 r6
SLR
123
97 98
Grammar:
1. S’ S
2. S L = R 3. S R
4. L * R
5. L id
6. R L
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
48
LL, SLR, LR, LALR Summary
• LL parse tables computed using FIRST/FOLLOW – Nonterminals terminals productions
• LR parsing tables computed using CLOSURE/GOTO – LR states terminals shift/reduce actions
– LR states nonterminals goto state transitions
• A grammar is
– LL(1) if its LL(1) parse table has no conflicts
– SLR if its SLR parse table has no conflicts
– LALR(1) if its LALR(1) parse table has no conflicts – LR(1) if its LR(1) parse table has no conflicts
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
49
LL, SLR, LR, LALR Grammars
LR(1)
LALR(1) LL(1) SLR
LR(0)
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
50
References
• Compilers: Principles, Techniques, and Tools (2nd Edition)
– By A.V. Aho, Lam, R. Sethi, . Ullman
• Chapter 4
31/08/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
51
