KindCons: Kind Grammars
Kind grammars are deterministic context-free grammars satisfying following
conditions:
-
For any two A-productions being both left recurive or both non-left-recursive
must hold that after some common prefix they must be ditinguishable using
some fixed (currently 1) lookahead.
-
Lookahead into left recursion has to differ from the lookeahead after the
nonterminal outside its left recursion.
Practically they are deterministic grammars that allow left recursion and
groups of productions with common prefixes - but at the point where the common
prefix ends, they must be distinguishable using fixed lookeahed (in this case
one terminal).
More information (and definitions, theorems and proofs) are available e.g. in
following papers:
- Zemlicka, M.: Extensible LL(1) Parsing.
Poster. SOFSEM'95. Milovy, 1995.
- Zemlicka, M.: Rozsiritelna syntakticka analyza
Technical report. MFF UK. Praha, 1996. (in Czech only)
- Zemlicka, M., Kral, J.:
Run-Time Extensible (Semi-)Top-Down Parser
In: Matousek, V., Mautner, P., Ocelikova, J., Sojka, P. (Eds.):
Text, Speech and Dialogue.
Edice Lecture Notes in Artificial Intelligence (LNAI) 1692, pp.
121-126, Springer Verlag, 1999.
- Zemlicka, M., Kral, J.:
Run-time Extensible Deterministic Top-Down Parsing.
In Grammars 2: 283-293, 1999, Kluwer Academic
Publishers. ISSN 1386-7393.
A prototype of a run-time extensible compiler based on this technique was
written in 1992-1994 as my Master Theses.