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 :)