Hello! Im going to be coding a parser program soon but first i need to eliminate Left Recursive Rules from this Grammar - as i will be doing a recursive desent parser.
Ive looked for some tutorials on how to eliminate the problem, but to no avail - they are a wee bit confusing. Some say i may need to introduce a new terminal but im still not so sure how to do this.
Below is the grammer:
and the rules for the left recursive grammar:
The grammar as written is not LL(1); it has left-recursive rules of the form:
<X list> ::= <X> | <X list> separator <X>
and rules of the form:
<something> ::= α X β | α Y γ
where α, β and γ are strings of terminals and/or non-terminals (α non-null) and X and Y are different terminal symbols.
<program> ::= <procedure list>
<procedure list> ::= <procedure definition> |
<procedure list> ; <procedure definition>
<procedure definition> ::= <procedure heading> <block>
<procedure heading> ::= procedure identifier is |
procedure identifier ( <declaration list> ) is
<declaration list> ::= <declaration> |
<declaration list> ; <declaration>
<declaration> ::= <identifier list> : integer |
<identifier list> : float |
<identifier list> : string
<identifier list> ::= identifier |
<identifier list> , identifier
<block> ::= <declaration list> <statement part>
<statement part> ::= begin <statement list> end
<statement list> ::= <statement> |
<statement list> ; <statement>
<statement> ::= <assignment statement> |
<if statement> |
<while statement> |
<procedure statement> |
<until statement>
<assignment statement> ::= identifier := <expression> |
4
identifier := stringConstant
<if statement> ::= if <condition> then <statement list> end if |
if <condition> then <statement list> else <statement list> end if
<while statement> ::= while <condition> loop <statement list> end loop
<procedure statement> ::= call identifier (<argument list> )
<until statement> ::= do <statement list> until <condition>
<argument list> ::= identifier |
<argument list> , identifier
<condition> ::= identifier <conditional operator> identifier |
identifier <conditional operator> numberConstant |
identifier <conditional operator> stringConstant
<conditional operator> ::= > | >= | = | /= | < | <=
<expression> ::= <term> |
<expression> + <term> |
<expression> - <term>
<term> ::= <factor> |
<term> * <factor> |
<term> / <factor>
<factor> ::= identifier |
numberConstant |
( <expression> )I would appreciate it if someone could either point me towards a informative tutorial or could show me which of the above lines follow the second LR rule - i think i can find the ones which follow the first rule.
Thanks very much, if im asking to much just give me some pointers if thats ok :D Because i need to understand :)
