Formula Sheets: Parsing | Compiler Design - Computer Science Engineering (CSE) PDF Download

 Page 1


Parsing F ormula Sheet
1. Context-Free Gr ammars (CFG)
• Definition : A CFG is a 4-tupleG = (V,T,P,S) , where:
– V : Set of variables (non-terminals).
– T : Set of terminals.
– P : Set of productions (A?a , whereA?V ,a? (V ?T)
*
).
– S : Start symbol.
• Leftmost Derivation : Alwa ys choose leftmost non-terminal to expand.
• Rightmost Derivation : Alwa ys choose rightmost non-terminal to expand.
• Parse Tree : Tree representation of derivation, root isS , leaves are terminals.
2. T op-Down Parsing
• Definition : Builds parse tree from root (S ) to leave s (terminals).
• Predictive Parsing (LL(1)) :
– First Set : First(a) ={a|a
*
?aß,a?T}?{?|a
*
??} .
– F ollow Set : F ollow(A) ={a|S
*
?aAaß,a?T}?{$|A is last symbol} .
– LL(1) Parsing T able : F or production A ? a , place in M[A,a] where a ?
First(a) ora? F ollow(A) if?? First(a) .
– Condition : No conflicts in M[A,a] (unique entry per cell).
– Time Complexity : O(|w|) , where|w| is input string length.
• Left F actoring : F orA?aß |a? , rewrite asA?aA
'
,A
'
?ß |? .
• Left Recursion Elimination : F orA?Aa|ß , r ewrite asA?ßA
'
,A
'
?aA
'
|? .
3. Bottom-Up Parsing
• Definition : Builds parse tree from leaves (terminals) to root (S ).
• Shift-Reduce Parsing :
– Shift : Push next input symbol onto stack.
– Reduce : Replace handle (rhs of production) on stack with lhs non-terminal.
– Handle : Substring matching right-hand side of a production.
– Time Complexity : O(|w|) for LR parsers.
• Oper ator Precedence Parsing :
– Precedence Relations : ·<· ,· =· ,·>· based on oper ator preceden ce.
1
Page 2


Parsing F ormula Sheet
1. Context-Free Gr ammars (CFG)
• Definition : A CFG is a 4-tupleG = (V,T,P,S) , where:
– V : Set of variables (non-terminals).
– T : Set of terminals.
– P : Set of productions (A?a , whereA?V ,a? (V ?T)
*
).
– S : Start symbol.
• Leftmost Derivation : Alwa ys choose leftmost non-terminal to expand.
• Rightmost Derivation : Alwa ys choose rightmost non-terminal to expand.
• Parse Tree : Tree representation of derivation, root isS , leaves are terminals.
2. T op-Down Parsing
• Definition : Builds parse tree from root (S ) to leave s (terminals).
• Predictive Parsing (LL(1)) :
– First Set : First(a) ={a|a
*
?aß,a?T}?{?|a
*
??} .
– F ollow Set : F ollow(A) ={a|S
*
?aAaß,a?T}?{$|A is last symbol} .
– LL(1) Parsing T able : F or production A ? a , place in M[A,a] where a ?
First(a) ora? F ollow(A) if?? First(a) .
– Condition : No conflicts in M[A,a] (unique entry per cell).
– Time Complexity : O(|w|) , where|w| is input string length.
• Left F actoring : F orA?aß |a? , rewrite asA?aA
'
,A
'
?ß |? .
• Left Recursion Elimination : F orA?Aa|ß , r ewrite asA?ßA
'
,A
'
?aA
'
|? .
3. Bottom-Up Parsing
• Definition : Builds parse tree from leaves (terminals) to root (S ).
• Shift-Reduce Parsing :
– Shift : Push next input symbol onto stack.
– Reduce : Replace handle (rhs of production) on stack with lhs non-terminal.
– Handle : Substring matching right-hand side of a production.
– Time Complexity : O(|w|) for LR parsers.
• Oper ator Precedence Parsing :
– Precedence Relations : ·<· ,· =· ,·>· based on oper ator preceden ce.
1
– T able : Precedence table guides shift/reduce decisions.
– Time Complexity : O(|w|) .
4. LR Parsing
• Definition : Bottom-up parsing using LR(0), SLR(1), LALR(1), or CLR(1) meth-
ods.
• LR(0) Items : Production with dot, e.g.,A?a·ß .
• LR(0) Parsing T able :
– States : Sets of LR(0) items.
– Closure : A dd itemsB ?·? forA?a·Bß .
– Goto : Goto(I,X) = Closure({A?aX·ß |A?a·Xß ?I}) .
– Conflicts : Shift-reduce or reduce-reduce.
• SLR(1) Parsing T able :
– ReduceA?a in stateI ifa? F ollow(A) for itemA?a· .
– Time Complexity :O(|w|) for parsing,O(|G|
3
) for table construction, where
|G| is gr ammar size.
• LALR(1) Parsing :
– Merge CLR(1) states with same LR(0) items, preserve loo kaheads.
– Ma y introduce reduce-reduce conflicts.
• CLR(1) Parsing :
– Uses LR(1) items: (A?a·ß,a) , wherea is lookahead.
– Most powerful, no conflicts for unambiguous gr ammars.
5. S yntax Trees
• Definition : Tree where internal nodes are non-terminals, leaves are termi-
nals, and edges represent productions.
• Construction : Derived from parse tree b y removing redundant nodes (e.g.,
single-child non-terminals).
• Use : Represents progr am structure for semantic analysis.
6. Time Complexities
• LL(1) Parsing : O(|w|) .
• LR Parsing : O(|w|) for parsing,O(|G|
3
) for table construction.
• Oper ator Precedence : O(|w|) .
2
Page 3


Parsing F ormula Sheet
1. Context-Free Gr ammars (CFG)
• Definition : A CFG is a 4-tupleG = (V,T,P,S) , where:
– V : Set of variables (non-terminals).
– T : Set of terminals.
– P : Set of productions (A?a , whereA?V ,a? (V ?T)
*
).
– S : Start symbol.
• Leftmost Derivation : Alwa ys choose leftmost non-terminal to expand.
• Rightmost Derivation : Alwa ys choose rightmost non-terminal to expand.
• Parse Tree : Tree representation of derivation, root isS , leaves are terminals.
2. T op-Down Parsing
• Definition : Builds parse tree from root (S ) to leave s (terminals).
• Predictive Parsing (LL(1)) :
– First Set : First(a) ={a|a
*
?aß,a?T}?{?|a
*
??} .
– F ollow Set : F ollow(A) ={a|S
*
?aAaß,a?T}?{$|A is last symbol} .
– LL(1) Parsing T able : F or production A ? a , place in M[A,a] where a ?
First(a) ora? F ollow(A) if?? First(a) .
– Condition : No conflicts in M[A,a] (unique entry per cell).
– Time Complexity : O(|w|) , where|w| is input string length.
• Left F actoring : F orA?aß |a? , rewrite asA?aA
'
,A
'
?ß |? .
• Left Recursion Elimination : F orA?Aa|ß , r ewrite asA?ßA
'
,A
'
?aA
'
|? .
3. Bottom-Up Parsing
• Definition : Builds parse tree from leaves (terminals) to root (S ).
• Shift-Reduce Parsing :
– Shift : Push next input symbol onto stack.
– Reduce : Replace handle (rhs of production) on stack with lhs non-terminal.
– Handle : Substring matching right-hand side of a production.
– Time Complexity : O(|w|) for LR parsers.
• Oper ator Precedence Parsing :
– Precedence Relations : ·<· ,· =· ,·>· based on oper ator preceden ce.
1
– T able : Precedence table guides shift/reduce decisions.
– Time Complexity : O(|w|) .
4. LR Parsing
• Definition : Bottom-up parsing using LR(0), SLR(1), LALR(1), or CLR(1) meth-
ods.
• LR(0) Items : Production with dot, e.g.,A?a·ß .
• LR(0) Parsing T able :
– States : Sets of LR(0) items.
– Closure : A dd itemsB ?·? forA?a·Bß .
– Goto : Goto(I,X) = Closure({A?aX·ß |A?a·Xß ?I}) .
– Conflicts : Shift-reduce or reduce-reduce.
• SLR(1) Parsing T able :
– ReduceA?a in stateI ifa? F ollow(A) for itemA?a· .
– Time Complexity :O(|w|) for parsing,O(|G|
3
) for table construction, where
|G| is gr ammar size.
• LALR(1) Parsing :
– Merge CLR(1) states with same LR(0) items, preserve loo kaheads.
– Ma y introduce reduce-reduce conflicts.
• CLR(1) Parsing :
– Uses LR(1) items: (A?a·ß,a) , wherea is lookahead.
– Most powerful, no conflicts for unambiguous gr ammars.
5. S yntax Trees
• Definition : Tree where internal nodes are non-terminals, leaves are termi-
nals, and edges represent productions.
• Construction : Derived from parse tree b y removing redundant nodes (e.g.,
single-child non-terminals).
• Use : Represents progr am structure for semantic analysis.
6. Time Complexities
• LL(1) Parsing : O(|w|) .
• LR Parsing : O(|w|) for parsing,O(|G|
3
) for table construction.
• Oper ator Precedence : O(|w|) .
2
• First/F ollow Computation : O(|G|) for simple gr ammars.
3