6-Role of Parser, Construction of Parse Tree and Elimination of Ambiguity-06-05-2023.pptx

Good

1. Role of Parser, Construction of Parse Tree and Elimination of Ambiguity Dr. S K Somasundaram Assistant Professor Senior Grade 2 School of Computer Science and Engineering, Vellore Institute of Technology, Vellore – 632014 Phone No: [phone] Mail ID: [email protected] Location : PRP Block – 218D BCSE307L – Compiler Design

2. Contents Role of Parser Parse Tree Elimination of Ambiguity Top Down Parsing Recursive Descent Parsing LL (1) Grammars Shift Reduce Parsers Operator Precedence Parsing LR Parsers Construction of SLR Parser Tables and Parsing CLR Parsing LALR Parsing

3. Role of parser Parser obtains a string of token from the lexical analyzer and reports syntax error if any otherwise generates syntax tree . There are two types of parser: Top-down parser Bottom-up parser Rest of front end Parse tree Token IR Lexical analyzer Symbol table Parser Get next token Source program Parse tree

4. Context free grammar A context free grammar (CFG) is a 4-tuple where, is finite set of non terminals, is disjoint finite set of terminals, is an element of and it’s a start symbol, is a finite set formulas/productions of the form where and   Nonterminal symbol: The name of syntax category of a language, e.g., noun, verb, etc. The It is written as a single capital letter , or as a name enclosed between < … >, e.g., A or <Noun> <Noun Phrase> → <Article><Noun> <Article> → a | an | the <Noun> → boy | apple

5. Context free grammar A context free grammar (CFG) is a 4-tuple where, is finite set of non terminals, is disjoint finite set of terminals, is an element of and it’s a start symbol, is a finite set formulas of the form where and   Terminal symbol: A symbol in the alphabet. It is denoted by lower case letter and punctuation marks used in language. <Noun Phrase> → <Article><Noun> <Article> → a | an | the <Noun> → boy | apple

6. Context free grammar A context free grammar (CFG) is a 4-tuple where, is finite set of non terminals, is disjoint finite set of terminals, is an element of and it’s a start symbol, is a finite set formulas of the form where and   Start symbol: First nonterminal symbol of the grammar is called start symbol. <Noun Phrase> → <Article><Noun> <Article> → a | an | the <Noun> → boy | apple

7. Context free grammar A context free grammar (CFG) is a 4-tuple where, is finite set of non terminals, is disjoint finite set of terminals, is an element of and it’s a start symbol, is a finite set formulas of the form where and   Production: A production, also called a rewriting rule, is a rule of grammar. It has the form of A nonterminal symbol → String of terminal and nonterminal symbols <Noun Phrase> → <Article><Noun> <Article> → a | an | the <Noun> → boy | apple

8. Example: Grammar Write terminals, non terminals, start symbol, and productions for following grammar. E  E O E| (E) | -E | id O  + | - | * | / | ↑ Terminals: id + - * / ↑ ( ) Non terminals: E, O Start symbol: E Productions: E  E O E| (E) | -E | id O  + | - | * | / | ↑

9. Derivation & Ambiguity

10. Derivation Derivation is used to find whether the string belongs to a given grammar or not. Types of derivations are: Leftmost derivation Rightmost derivation

11. Leftmost derivation A derivation of a string in a grammar is a left most derivation if at every step the left most non terminal is replaced. Grammar: S  S+S | S-S | S*S | S/S | a Output string: a*a-a S  S-S  S*S -S  a *S-S  a* a -S  a*a- a   a S - S a a S * S S Parse tree represents the structure of derivation Leftmost Derivation Parse tree

12. Rightmost derivation A derivation of a string in a grammar is a right most derivation if at every step the right most non terminal is replaced. It is all called canonical derivation . Grammar: S S+S | S-S | S*S | S/S | a Output string: a*a-a S  S*S  S* S-S  S*S- a  S* a -a  a *a-a   a S * S a a S - S S Rightmost Derivation Parse Tree

13. Exercise: Derivation Perform leftmost derivation and draw parse tree. S A1B A0A | 𝜖 B0B | 1B | 𝜖 Output string: 1001 Perform leftmost derivation and draw parse tree. S0S1 | 01 Output string: 000111 Perform rightmost derivation and draw parse tree. EE+E | E*E | id | (E) | -E Output string: id + id * id

14. Ambiguity Ambiguity, is a word, phrase, or statement which contains more than one meaning . Chip A long thin piece of potato A small piece of silicon

15. Ambiguity In formal language grammar, ambiguity would arise if identical string can occur on the RHS of two or more productions. Grammar: can be derived from either N1 or N2         Replaced by or ?  

16. Ambiguous grammar Ambiguous grammar is one that produces more than one leftmost or more than one rightmost derivation for the same sentence. Grammar: S S+S | S*S | (S) | a Output string: a+a *a S S S*S S+S S+S*S  a+S  a+S *S  a+S *S  a+a *S  a+a *S  a+a *a  a+a *a Here, Two leftmost derivation for string a+a *a is possible hence, above grammar is ambiguous. a S * S a a S S + S a S + S a a S * S S

17. Exercise: Ambiguous Grammar Check Ambiguity in following grammars: S  aS | Sa | 𝜖 ( output string: aaaa ) S  aSbS | bSaS | 𝜖 ( output string: abab ) S  SS+ | SS* | a ( output string: aa+a *) <exp> → <exp> + <term> | <term> <term> → <term> * <letter> | <letter> <letter> → a|b|c |…|z ( output string: a+b *c) Prove that the CFG with productions: S  a | Sa | bSS | SSb | SbS is ambiguous (Hint: consider any output string)

18. Reasons for Ambiguity in Grammars Sequence of identical operators can group either from left or from right [ Associativity problem ] The precedence of the operators is not considered

19. 1. Associativity If the same precedence operators are in production, then we will have to consider the associativity . If the associativity is left to right , then we have to prompt a left recursion in the production. The parse tree will also be left recursive and grow on the left side. +, -, *, / are left associative operators. If the associativity is right to left , then we have to prompt the right recursion in the productions. The parse tree will also be right recursive and grow on the right side. ^ is a right associative operator.

20. Example 1: Consider the ambiguous grammar E -> E-E | id Derive the string id-id-id and consider id=3. Soln :

21. Cont … To make the above grammar unambiguous, simply make the grammar Left Recursive by replacing the left most non-terminal E in the right side of the production with another random variable, say P . The grammar becomes : E -> E – P | P P -> id

22. Note: Similarly, the unambiguous grammar for the expression : 2^3^2 E -> P ^ E | P // Right Recursive as ^ is right associative . P -> id

23. Example 2: Show that the following grammar is ambiguous grammar for the given string and remove ambiguity from the given grammar: S  S * S | a String, w = a * a * a Soln : LMD1 : S  S * S  a * S  a * S * S  a * a * a LMD2 : S  S * S  S * S * S  a * S * S  a * a * S  a * a * a Reconstructed grammar: S  S * a | a S S * a S * a a Left Recursion

24. 2. Precedence If different operators are used, consider the precedence of the operators. The characteristics: The level at which the production is present denotes the priority of the operator used . The production at higher levels will have operators with less priority . In the parse tree, the nodes which are at top levels or close to the root node will contain the lower priority operators. The production at lower levels will have operators with higher priority . In the parse tree, the nodes which are at lower levels or close to the leaf nodes will contain the higher priority operators.

25. Example Consider the grammar shown below, which has two different operators : E -> E + E | E * E | id Derive the string “ id+id *id” Soln Two parse trees for the string “ id+id *id”

26. Cont … The unambiguous grammar will contain the productions having the highest priority operator (“*” in the example) at the lower level and vice versa . The “+” having the least priority has to be at the upper level and has to wait for the result produced by the “*” operator which is at the lower level. The associativity of both the operators are Left to Right. So, the unambiguous grammar has to be left recursive. The unambiguous grammar for the given grammar: E -> E + P // + is at higher level and left associative E -> P P -> P * Q // * is at lower level and left associative P -> Q Q -> id (or) E -> E + P | P P -> P * Q | Q Q -> id Note : E is used for doing addition operations and P is used to perform multiplication operations. They are independent and will maintain the precedence order in the parse tree. E -> E + E | E * E | id

27. Note: The unambiguous grammar for an expression having the operators -,*,^ is : E -> E – P | P // Minus operator is at higher level due to least priority and left associative. P -> P * Q | Q // Multiplication operator has more priority than – and lesser than ^ and left associative. Q -> R ^ Q | R // Exponent operator is at lower level due to highest priority and right associative. R -> id

28. Example 2 Convert the following ambiguous grammar into unambiguous grammar- bexp → bexp or bexp / bexp and bexp / not bexp / t / f where bexp represents Boolean expression, t represents True and f represents False. Soln : bexp → bexp or A / A A → A and B / B B → not B / G G → t / f

29. Dangling else problem

30. Two possible parse trees

31. Unambiguous Grammar Matchedstmt Openstmt

32. Left recursion & Left factoring

33. Left recursion A grammar is said to be left recursive if it has a non terminal such that there is a derivation for some string              𝜖   Left recursion elimination

34. Examples: Left recursion elimination E  E+T | T E  TE’ E’  +TE’ | ε T  T*F | F T  FT’ T’  *FT’ | ε XX%Y | Z X Z X’ X’ %YX ’ | ε

35. Exercise: Left recursion A Abd | Aa | a BBe | b AAB | AC | a | b SA | B AABC | Acd | a | aa BBee | b ExpExp+term | Exp-term | term

36. Left factoring Left factoring is a grammar transformation that is useful for producing a grammar suitable for predictive parsing. S aAB | aCD S aS ’ S’AB | CD A  xByA | xByAzA | a A  xByAA ’ | a A’  𝜖 | zA A aAB | aA |a A aA ’ A’AB | A | 𝜖 A’AA’’ | 𝜖 A’’ B | 𝜖

37. Exercise S iEtS | iEtSeS | a A ad | a | ab | abc | x