Compilers hw help geting rid of left recursion using top down parsing R1. <Rat18
ID: 3730842 • Letter: C
Question
Compilers hw help geting rid of left recursion using top down parsing
R1. <Rat18S> ::= <Opt Function Definitions> %% <Opt Declaration List> <Statement List>
R2. <Opt Function Definitions> ::= <Function Definitions> | <Empty>
R3. <Function Definitions> ::= <Function> | <Function> <Function Definitions>
R4. <Function> ::= function <Identifier> [ <Opt Parameter List> ] <Opt Declaration List> <Body>
R5. <Opt Parameter List> ::= <Parameter List> | <Empty>
R6. <Parameter List> ::= <Parameter> | <Parameter> , <Parameter List>
R7. <Parameter> ::= <IDs > : <Qualifier>
R8. <Qualifier> ::= int | boolean | real
R9. <Body> ::= { < Statement List> }
R10. <Opt Declaration List> ::= <Declaration List> | <Empty>
R11. <Declaration List> := <Declaration> ; | <Declaration> ; <Declaration List>
R12. <Declaration> ::= <Qualifier > <IDs>
R13. <IDs> ::= <Identifier> | <Identifier>, <IDs>
R14. <Statement List> ::= <Statement> | <Statement> <Statement List>
R15. <Statement> ::= <Compound> | <Assign> | <If> | <Return> | <Print> | <Scan> | <While>
R16. <Compound> ::= { <Statement List> }
R17. <Assign> ::= <Identifier> = <Expression> ;
R18. <If> ::= if ( <Condition> ) <Statement> endif |
if ( <Condition> ) <Statement> else <Statement> endif
R19. <Return> ::= return ; | return <Expression> ;
R20. <Print> ::= put ( <Expression>);
R21. <Scan> ::= get ( <IDs> );
R22. <While> ::= while ( <Condition> ) <Statement>
R23. <Condition> ::= <Expression> <Relop> <Expression>
R24. <Relop> ::= == | ^= | > | < | => | =<
R25. <Expression> ::= <Expression> + <Term> | <Expression> - <Term> | <Term>
R26. <Term> ::= <Term> * <Factor> | <Term> / <Factor> | <Factor>
R27. <Factor> ::= - <Primary> | <Primary>
R28. <Primary> ::= <Identifier> | <Integer> | <Identifier> ( <IDs> ) | ( <Expression> ) |
<Real> | true | false
R29. <Empty> ::= e
Explanation / Answer
#LEFT RECURSION
Left recursion in the grammar is the recursive expansion of the grammar from the leftmost part of the production that makes it diificult to guess the starting terminal of the sentence to be derived from the productions of grammars.
Basically when the left hand side non terminal appears on the left most part of the production's right hand side then this results in left recursion.
Left recursion is of the form as shown below
A ::= A b | A d | A f | ................ | C
now on deriving a string from this prodcution, A will be recursively expanded to give another A resulting in left recursion.
For each left recursive production of the grammar of the form as shown above, we write a right recursive production in the following way
A ::= A b | C
now becomes
A ::= C A'
A' ::= b A' | e
and for multiple left hand side derivation in the same production of the form
A ::= A b | Ad | C
now becomes
A ::= C A'
A' ::= b A' | d A' | e
here A' is another non-terminal taken to get rid of the left recusrion and 'e' is the empty symbol.
#QUESTION
Now coming to your question, we can see that not all the productions of the given grammar are left - recursive in nature.
First we have to identify which are the left-recursive productions.
R25. <Expression> ::= <Expression> + <Term> | <Expression> - <Term> | <Term>
R26. <Term> ::= <Term> * <Factor> | <Term> / <Factor> | <Factor>
These are the two productions which are left recursive in nature .
REMOVING LEFT RECURSION
R25. <Expression> ::= <Expression> + <Term> | <Expression> - <Term> | <Term>
In this production we can see that non terminal <Expression> is left recursively expanded.
Comapring this production to the form of left-recursion production
A ::= A b | Ad | C
here A is <Expression> , b is + <Term>, d is - <Term>, C is <Term>
so equivalent no-left recursive form will be
A ::= C A'
A' ::= b A' | d A' | e
that is
<Expression> ::= <Term> <Expression'>
<Expression'> ::= + <Term> <Expression'> | - <Term> <Expression'> | e
where <Expression'> is the new non terminal taken to make the production non -left recusrive
R26. <Term> ::= <Term> * <Factor> | <Term> / <Factor> | <Factor>
This production is same as the previous production, we have this production in the form as shown below
A ::= A b | Ad | C
where A is <Term>, b is * <Factor> , d is / <Factor>, C is <Factor>
the equiavlent non-left recursive form will be
A ::= C A'
A' ::= b A' | d A' | e
so equiavlent non-left recursive production is
<Term> ::= <Factor> <Term'>
<Term'> ::= * <Factor> <Term'> | / <Factor> <Term'> | e
where <Term'> is the new non terminal taken to make the production non-left recusrive
so apart from these two productions , all the productions in the grammar will remain same. Just replace the R25 and R26 productions with the above equivalent non-left recursive productions.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.