Re: DFA's and LR machine (was Re: Trouble understanding...)

# One could find an even better encoding quite easily. Of course, all
# I've done is translate the stack into integer operations, but that's
# the idea behind counters anyway. I'm sure there some nice proof by
# Church, Turing, Goedel, Post or someone that shows that one can do
# this completely generally--my automata theory is quite rusty these
# days.


Congratulations on rediscoverring a Godel numberring of a Turing machine
tape.


# Note, your original idea of using a simple counter to handle pure
# left or right recursion is equivalent to using run-length encoding for
# that part of the grammar. However, I think if you do the arithmetic


You don't need a counter for left recursion, just right and embedding
recursion.


If you don't want the solution but just hints to the solution, here's
a hint: come up a number of small grammars that exhibit various types
of recursion and recursion within recursion. Create the LR(k) states
and draw the LR(k) state machines; examine the items in the states
including lookahead sets, especially what happens to lookahead sets
when there's a cycle in the state machine. You should be able derive
properties of the LR(k) state machines about when they can be
converted to DFAs, DFAs with counters, and left as PDAs. (Ancona's
derivation of LR(k) states defers expanding nonterminals in lookahead
sets and makes it easier to understand how they contribute to cyclic
graphs.)


--
SM Ryan http://www.rawbw.com/~wyrmwif/

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