16 May 2004 23:29:44 -0400

Related articles |
---|

DFA's and LR machine (was Re: Trouble understanding...) cdc@maxnet.co.nz (Carl Cerecke) (2004-04-21) |

Re: DFA's and LR machine (was Re: Trouble understanding...) wyrmwif@tsoft.com (SM Ryan) (2004-04-28) |

Re: DFA's and LR machine (was Re: Trouble understanding...) cdc@maxnet.co.nz (Carl Cerecke) (2004-05-08) |

Re: DFA's and LR machine (was Re: Trouble understanding...) cfc@shell01.TheWorld.com (Chris F Clark) (2004-05-09) |

Re: DFA's and LR machine (was Re: Trouble understanding...) wyrmwif@tsoft.com (SM Ryan) (2004-05-16) |

From: | SM Ryan <wyrmwif@tsoft.com> |

Newsgroups: | comp.compilers |

Date: | 16 May 2004 23:29:44 -0400 |

Organization: | Quick STOP Groceries |

References: | 04-05-041 |

Keywords: | parse |

Posted-Date: | 16 May 2004 23:29:44 EDT |

# 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/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.