Computer Science

Computer Science RSS

Eliminate Left Recursive Grammar

Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.

•

Join Date: Nov 2004

Posts: 89

Reputation: MrScruff is an unknown quantity at this point

Solved Threads: 0

MrScruff

Offline

Junior Poster in Training

Eliminate Left Recursive Grammar

Nov 28th, 2004

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.

Help with Code Tags

(Toggle Plain Text)

<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

Because i need to understand

Blackdrop Online Music Community... Love your music.. bitch! |

•

Join Date: Dec 2004

Posts: 207

Reputation: Real-tiner is an unknown quantity at this point

Solved Threads: 7

Real-tiner Real-tiner is offline

Offline

Posting Whiz in Training

Re: Eliminate Left Recursive Grammar

Jan 19th, 2005

It depends on whether or not this is considered left-recursive:

<procedure list> ::= <procedure definition> |
<procedure rdc> ; <procedure definition>
<procedure rdc> ::= <procedure list>