Syntax-Directed Translation for
Top-Down Parsing
Copyright By PowCoder代写 加微信 powcoder
Midterm next week – during class online
Covers everything up to and incl today’s class
Sample questions be posted on website
Exam is multiple choice.
Last Time: Built LL(1) Predictive Parser
FIRST and FOLLOW sets define the parse table
If the grammar is LL(1), the table is unambiguous
• i.e., each cell has at most one entry
If the grammar is not LL(1) we can attempt a
transformation sequence:
1. Remove left recursion
2. Left-factoring
Grammar transformations affect the structure of the
parse tree. How does this affect syntax-directed
translation (in particular, parse tree → AST)?
Review parse-table construction
– 2 examples
Show how to do syntax-directed translation using
an LL(1) parser
FOLLOW(A) for X⟶ α A β
If A is the start, add eof
Add FIRST(β) – {ε}
Add FOLLOW(X) if ε in FIRST(β) or β empty
S ⟶ B c | D B
B ⟶ a b | c S
FIRST (D) { d, ε }
{ a, c, d }
FIRST (D B) { d, a, c }
FIRST (B c) { a, c }
FIRST (a b) { a }
FIRST (c S) { c }
FIRST(α) for α = Y1 Y2 … Yk
Add FIRST(Y1) – {ε}
If ε is in FIRST(Y1 to i-1): add FIRST(Yi) – {ε}
If ε is in all RHS symbols, add ε
for each production X ⟶ α
for each terminal t in FIRST(α)
put α in Table[X][t]
if ε is in FIRST(α){
for each terminal t in FOLLOW(X){
put α in Table[X][t]
Table[X][t]
a b c d eof
B c B c D B
FOLLOW (S) { eof, c } =
FOLLOW (B) { c, eof }=
FOLLOW (D) { a, c } =
FIRST (d) { d }
FIRST (ε) { ε }
FOLLOW(A) for X⟶ α A β
If A is the start, add eof
Add FIRST(β) – {ε}
Add FOLLOW(X) if ε in FIRST(β) or β empty
FIRST (S) { { , ( , ε } =
FIRST(α) for α = Y1 Y2 … Yk
Add FIRST(Y1) – {ε}
If ε is in FIRST(Y1 to i-1): add FIRST(Yi) – {ε}
If ε is in all RHS symbols, add ε
for each production X ⟶ α
for each terminal t in FIRST(α)
put α in Table[X][t]
if ε is in FIRST(α){
for each terminal t in FOLLOW(X){
put α in Table[X][t]
Table[X][t]
S → ( S ) | { S } | ε
FIRST ( ( S ) ) { ( } =
FIRST ( { S } ) { { } =
FIRST ( ε ) { ε } =
FOLLOW ( S ) { eof, ), } } =
( S ) { S }ε ε ε
FOLLOW(A) for X⟶ α A β
If A is the start, add eof
Add FIRST(β) – {ε}
Add FOLLOW(X) if ε in FIRST(β) or β empty
FIRST (S) { +, ε } =
FIRST(α) for α = Y1 Y2 … Yk
Add FIRST(Y1) – {ε}
If ε is in FIRST(Y1 to i-1): add FIRST(Yi) – {ε}
If ε is in all RHS symbols, add ε
for each production X ⟶ α
for each terminal t in FIRST(α)
put α in Table[X][t]
if ε is in FIRST(α){
for each terminal t in FOLLOW(X){
put α in Table[X][t]
Table[X][t]
S → + S | ε
FIRST ( + S ) { + } =
=FIRST ( ε ) { ε }
FOLLOW ( S ) { eof } =
How’s that Compiler Looking?
Tokens via RegEx table
Parse Tree via Recursive Descent
TODO: SDT on
transformed CFG
IR Codegen
MC Codegen
Implementing SDT for LL(1) Parser
So far, SDT shown as second (bottom-up) pass
over parse tree
The LL(1) parser never needed to explicitly build
the parse tree (implicitly tracked via stack)
Naïve approach: build the parse tree
Semantic Stack
Instead of building the parse tree, give parser
second, semantic stack
– Holds nonterminals’ translations
SDT rules converted to actions on semantic stack
– Pop translations of RHS nonterms off
– Push computed translation of LHS nonterm on
| ( Expr )
| [ Expr ]
Expr.trans = 0
Expr.trans = Expr2.trans + 1
Expr.trans = Expr2.trans
Expr2.trans = pop; push Expr2.trans + 1
Expr2.trans = pop; push Expr2.trans
CFG SDT Rules SDT Actions
Translation goal:
• Count the number of occurrences of
matched pairs of rounded parens: “( … )”
• Ignore occurrences of matched pairs of
square brackets: “[ … ]”
Action Numbers
Need to define when to fire the SDT Action
– Not immediately obvious since SDT is bottom-up
– Number actions and put them on the symbol stack!
– Add action number symbols at end of the
productions
CFG SDT Actions
Expr2.trans = pop; push Expr2.trans + 1
Expr2.trans = pop; push Expr2.trans
| ( Expr )
| [ Expr ]
Action Numbers: Example 1
CFG SDT Actions: Counting Max Parens Depth
Expr2.trans = pop; push(Expr2.trans + 1)
Expr2.trans = pop; push(Expr2.trans)
| ( Expr )
| [ Expr ]
( Expr ) #2 [ Expr ] #3
Work Stack SemanticStack
currentcurrentcurrent0 current
Root translation
No-op SDT Actions
CFG SDT Actions: Counting Max Parens Depth
Expr2.trans = pop; push(Expr2.trans + 1)
Expr2.trans = pop; push(Expr2.trans)
| ( Expr )
| [ Expr ]
Useless rule
CFG SDT Actions: Counting Max Parens Depth
Expr2.trans = pop; push(Expr2.trans + 1)
| ( Expr )
| [ Expr ]
Placing Action Numbers
• Action numbers go after their corresponding
nonterminals, before their corresponding terminal
• Translations popped from action stack right-to-left
CFG SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Expr + Term
| Term
Term ⟶ Term * Factor
| Factor
Factor ⟶ intlit
A terminal symbol’s value is available
during the parse only when it is the
“current token.” We need to access
the terminal symbol’s value before it
is popped from the work stack
The predictive parser does a leftmost derivation, so the
translation of Expr is performed first and pushed on the
semantic stack. The translation of Term is done later, so
its translation is pushed more recently than that of Expr
Translation goal:
• Evaluate the expression
• E.g., 5 + 3 * 2 produces 11
Placing Action Numbers
• Action numbers go after their corresponding
nonterminals, before their corresponding terminal
CFG SDT Actions
#3 push(intlit.value) #3
Factor ⟶ intlit
A terminal symbol’s value is available
during the parse only when it is the
“current token.” We need to access
the terminal symbol’s value before it
is popped from the work stack
Work Stack Semantic Stack
Input: … intlit:17 …
Problem: The push action can no
longer access intlit.value; i.e., it cannot
push 17 onto the semantic stack!Let’s try putting the
action after intlit
Placing Action Numbers
• Action numbers go after their corresponding
nonterminals, before their corresponding terminal
CFG SDT Actions
#3 push(intlit.value) #3
Factor ⟶ intlit
A terminal symbol’s value is available
during the parse only when it is the
“current token.” We need to access
the terminal symbol’s value before it
is popped from the work stack
Work Stack Semantic Stack
Input: … intlit:17 …
Correct! The push action can
access intlit.value, and pushes 17
onto the semantic stack!Let’s try putting the
action before intlit
Placing Action Numbers: Example
Write SDT Actions and place action numbers to
get the product of a ValList (i.e., multiply all
CFG SDT Actions
LTrans = pop ; vTrans = pop ; push(LTrans * vTrans)
LTrans = pop; vTrans = pop ; push(LTrans * vTrans)
push(intlit.value)
List ⟶ Val List’
List’ ⟶ Val List’
Val ⟶ intlit
| ε
#3 push(1)
Action Numbers: Benefits
Plans SDT actions using the work stack
Robust to previously introduced grammar
transformations!
Expr ⟶ Expr + Term #1
Term ⟶ Term * Factor #2
| Factor
Factor ⟶ #3 intlit
| ( Expr )
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
• Define the SDT using the original grammar (define
translation rules; convert to actions that push/pop using
the semantic stack; incorporate action numbers into the
grammar rules).
• Then transform the grammar to be LL(1), treating the
action numbers just like terminal symbols!
• But treat all action numbers as ε when computing FIRST
and FOLLOW sets. (An action number is not actually a
terminal symbol in the input stream of tokens.)
Example: SDT on Transformed Grammar
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
Example: SDT on Transformed Grammar
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
First(Factor) = { intlit, ( }
First(Term’) = { *, ” }
First(Term) = { intlit, ( }
First(Expr’) = { +, ” }
First(Expr) = { intlit, ( }
First(Term Expr’) = { intlit, ( }
First(+ Term #1 Expr’) = { + }
First(“) = { ” }
First(Factor Term’) = { intlit, ( }
First(* Factor #2 Term) = { * }
First(“) = { ” }
First(#3 intlit) = { intlit }
First( ( Expr ) ) = { ( }
Follow(Expr) = { eof, ) }
Follow(Expr’) = { eof, ) }
Follow(Term) = { +, eof, ) }
Follow(Term’) = { +, eof, ) }
Follow(Factor) = { *, +, eof, ) }
Example: SDT on Transformed Grammar
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
+ * ( ) intlit eof
Expr Term Expr’ Term Expr’
Expr’ + Term #1 Expr’ ε ε
Term Factor Term’ Factor Term’
Term’ ε * Factor #2 Term’ ε ε
Factor ( Expr ) #3 intlit
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
Work Stack Semantic Stack
Input: 5 + 3 * 2 eof
+ * ( ) intlit eof
Expr Term Expr’ Term Expr’
Expr’ + Term #1 Expr’ ε ε
Term Factor Term’ Factor Term’
Term’ ε * Factor #2 Term’ ε ε
Factor ( Expr ) #3 intlit
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
Work Stack Semantic Stack
Input: 5 + 3 * 2 eof
+ * ( ) intlit eof
Expr Term Expr’ Term Expr’
Expr’ + Term #1 Expr’ ε ε
Term Factor Term’ Factor Term’
Term’ ε * Factor #2 Term’ ε ε
Factor ( Expr ) #3 intlit
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
Work Stack Semantic Stack
Input: 5 + 3 * 2 eof
+ * ( ) intlit eof
Expr Term Expr’ Term Expr’
Expr’ + Term #1 Expr’ ε ε
Term Factor Term’ Factor Term’
Term’ ε * Factor #2 Term’ ε ε
Factor ( Expr ) #3 intlit
Factorintlit
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
Work Stack Semantic Stack
Input: 5 + 3 * 2 eof
+ * ( ) intlit eof
Expr Term Expr’ Term Expr’
Expr’ + Term #1 Expr’ ε ε
Term Factor Term’ Factor Term’
Term’ ε * Factor #2 Term’ ε ε
Factor ( Expr ) #3 intlit
currentcurrent
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
Work Stack Semantic Stack
Input: 5 + 3 * 2 eof
+ * ( ) intlit eof
Expr Term Expr’ Term Expr’
Expr’ + Term #1 Expr’ ε ε
Term Factor Term’ Factor Term’
Term’ ε * Factor #2 Term’ ε ε
Factor ( Expr ) #3 intlit
Factorintlit
current2 current
SDT Actions
tTrans = pop ; eTrans = pop ; push(eTrans + tTrans)
fTrans = pop; tTrans = pop ; push(tTrans * fTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ Factor Term’
Term’ ⟶ * Factor #2 Term’
Factor ⟶ #3 intlit
| ( Expr )
Work Stack Semantic Stack
Input: 5 + 3 * 2 eof
+ * ( ) intlit eof
Expr Term Expr’ Term Expr’
Expr’ + Term #1 Expr’ ε ε
Term Factor Term’ Factor Term’
Term’ ε * Factor #2 Term’ ε ε
Factor ( Expr ) #3 intlit
Root translation
What about ASTs?
Push and pop AST nodes on the stack
Keep field references to nodes that we pop
Expr ⟶ Expr + Term #1
Term ⟶ #2 intlit
“AST-creation” SDT Actions
tTrans = pop ;
eTrans = pop ;
push(new PlusNode(tTrans, eTrans))
push(new IntLitNode(intlit.value))
“Evaluation” SDT Actions
tTrans = pop ;
eTrans = pop ;
push(eTrans + tTrans)
push(intlit.value)
Expr ⟶ Term Expr’
Expr’ ⟶ + Term #1 Expr’
Term ⟶ #2 intlit
Transformed CFG
AST Example
“AST” SDT Actions
tTrans = pop ;
eTrans = pop ;
push(new PlusNode(tTrans, eTrans))
push(new IntLitNode(intlit.value))
E’ ⟶ + T #1 E’
T ⟶ #2 intlit
Transformed CFG T E’
intlit + EOF
Work Stack Semantic Stack
IntLitNode
IntLitNode
IntLitNode
#2 currentcurrentcurrentcurrentcurrent current
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com