Re: Trouble understanding LL(k) vs. LALR(k) etc.

# Of course, the *best* way to parse either of the above is with a regular
# expression (i.e. a finite automaton), and not a stack-based machine (LL
# or LR) at all. Any decent recursive-descent parser generator allows
# regular expressions in its grammar specification, eliminating the need
# for much recursion - and leading to a nicer shape abstract syntax tree.


The issue isn't regular expressions, but whether the implementation is a
DFA or DPDA. It's usually not that hard to convert left recursion LR
state machine from DPDA to a DFA. (In a reduction state, back track
the state graph to find out what state will be the next after the
reduction and then add a link to go to that directly instead of popping
a goto table off a stack.)


The grammar should be presented in the most natural form, since most
transformations like left recursion removal or production factorring
can be automated. Unfortunately this is rarely done.


--
Derk Gwen http://derkgwen.250free.com/html/index.html

Return to the comp.compilers page.
Search the comp.compilers archives again.