Related articles 

Seamlessly parsing leftrecursive grammars with LL parsers ? louis@mulliemedia.com (Louis Mullie) (20050320) 
Re: Seamlessly parsing leftrecursive grammars with LL parsers ? angagon@earthlink.net (Matt O'Connor) (20050327) 
Re: Seamlessly parsing leftrecursive grammars with LL parsers ? branco.medeiros@gmail.com (20050331) 
Re: Seamlessly parsing leftrecursive grammars with LL parsers ? louis@mulliemedia.com (Louis Mullie) (20050402) 
From:  "Louis Mullie" <louis@mulliemedia.com> 
Newsgroups:  comp.compilers 
Date:  2 Apr 2005 19:37:44 0500 
Organization:  Compilers Central 
References:  0503079 0503127 
Keywords:  parse, LL(1) 
PostedDate:  02 Apr 2005 19:37:44 EST 
Hello,
Thanks a lot for your replies.
Mr. O'Connor :
There's, as noted by Mr. Medeiros, an error in my above grammar : "add :=
add '+' term" should be "add := add '+' term  term", and I unwillingly
tried to fix it in my code: reverseOrder(symbol.rule) + '' + symbol;
should simply be reverseOrder(symbol.rule);
Don't forget that the input is also reversed, so add "'+' '*' term" would
become "term '*' '+' add", but "4 +* 5" would also be flipped to "5 *+ 4",
which stays correct.
Mr. Medeiros :
When I wrote "seamlessly", I meant without the parse tree being changed:
this would have to occur behind the scenes, the end user not 'knowing' the
tool transformed the grammar. The tool is a recursive descent parser that
dynamically accepts any grammar. I have (unsuccessfully) tried to
implement a nontabledriven LALR parser; I am looking into recursive
ascentdescent and recursive ascent parsing as an alternative, but it
still involves computing states.
Since I wrote this, I've read up a lot on leftrecursion, and I've
questionned myself if, on a parse tree T generated by a grammar G`
(created from G in which leftrecursion was removed with the standard
(Ullman's) method), it was possible to apply a set of transformations such
that T` would've been the same tree as the one generated by G (G` => T and
G => T`). Mathematically, it looked perfectly possible, and I've come up
with another (simple) algorithm, which also restores the left
associativity of the operators :
For each child of node N {
if child is a newly created nonterminal (i.e., of the form A`) :
for each subchild of child {
if child is a newly created nonterminal (i.e., of the form
A`) : store in variable 'rest' and break the loop
apply algorithm on subchild;
add subchild to N;
}
create new node N` with the same type as N;
add N to N`;
if rest is ε then continue;<>
apply algorithm to rest;
add each child of rest to N;
}
1. Original tree
Expr 
/ \
Term Expr' 
 /  \
Factor + Term Expr' 
   \ \
Int Factor + Term Expr'
 
Factor ε

Int
==========================================================
2. Added subchild to N
Expr 
/ \
Term Term
  (Rest)
Factor Factor Expr' 
   \ \
Int Factor + Term Expr'
 
Factor ε

Int
3. Added rest
Expr 
/  
/  
Expr  + Term
/ \ 
Term Term Factor
  
Factor Factor Int
 
Int Factor
4. The above tree is the same tree as the one produced by an LR parser :
Expr
/ \
Expr + Term
/  \ \
Expr + Term Factor
  
Term Factor Int
 
Factor Int

Int
Any thoughts on this approach to the problem ?
Regards,

Louis Mullie <louis@mulliemedia.com>
Return to the
comp.compilers page.
Search the
comp.compilers archives again.