Re: Is a contextfree Grammar ambiguous ?

>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

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