15 Nov 1998 13:26:28 -0500

Related articles |
---|

[2 earlier articles] |

Re: Is a contextfree Grammar ambiguous ? mickunas@cs.uiuc.edu (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? mickunas@cs.uiuc.edu (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? aycock@csc.uvic.ca (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? dmr@plan9.bell-labs.com (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? cfc@world.std.com (Chris F Clark) (1998-11-07) |

Re: Is a contextfree Grammar ambiguous ? cfc@world.std.com (Chris F Clark) (1998-11-12) |

Re: Is a contextfree Grammar ambiguous ? jmlake@unity.ncsu.edu (1998-11-15) |

From: | jmlake@unity.ncsu.edu (John M Lake) |

Newsgroups: | comp.compilers,comp.theory |

Date: | 15 Nov 1998 13:26:28 -0500 |

Organization: | North Carolina State University |

Distribution: | inet |

References: | 98-10-172 98-11-037 98-11-052 98-11-073 |

Keywords: | parse |

*>One variation on this is the LR-regular languages where the unbounded*

*>lookahead has to be recognizable by a regular expression.*

Determining whether a grammar is LR-regular is undecidable in general.

An interesting decidable subset is characterized in

Bermudez, Manuel E. and Schimpf, Karl M. 1990. Practical

Arbitrary Lookahead LR Parsing. J. Comp. Sys. Sciences, 41,

230-250.

Their algorithm constructs the LR(0) machine, then constructs one finite

state machine for each state with conflicts. The FSM is generated

by a modified LR(0) construction limited to the subgrammar involved

in the conflict. They achieve decidability by limiting the depth of

the stack the lookahead machine manipulates rather than the number of

lookahead symbols. The amount of lookahead actually used depends upon

the topology of the lookahead LR(0) machine: a dag-structured machine

has finite lookahead, a cyclic machine has arbitrary lookahead, and

a lookahead machine with conflicts itself cannot resolve the original

grammar's conflicts. Naturally, this can lead to quadratic time parsing.

Empirically, two symbols of lookahead almost always suffice.

Mike

--

Mike Lake jmlake@adm.csc.ncsu.edu 320 Research I

Computer Science North Carolina State University (919) 515-4521

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.