|CFL < ? < CSL firstname.lastname@example.org (1991-06-25)|
|Re: CFL < ? < CSL email@example.com (1991-07-04)|
|From:||firstname.lastname@example.org (Aaron Emigh)|
|Keywords:||parse, indexed languages|
|Organization:||University of California, Santa Cruz|
|Date:||4 Jul 91 09:40:30 GMT|
Amr Sabry writes:
>My question is whether there exists a class of languages lying properly
>between context-free languages and context-sensitive languages and that is
It depends on what you mean by "efficiently" -- most people would say
that context-free languages cannot be recognized efficiently enough to
use, for example, a general context-free parser in a compiler.
The most noteworthy class of languages lying properly between CFLs and
CSLs with which I am aware is the class of indexed grammars. The basic
reference on this is Aho '68; there are some others too (and I'm sure I
don't have them all here).
Alfred Aho, "Indexed Grammars," JACM 15:4 (1968), 647-671.
Alfred Aho, "Nested Stack Automata," JACM 16:3 (1969), 383-406.
S. A. Greibach, "Full AFL's and Nested Iterated Substitution,"
Information and Control 16:1 (1970), 7-35.
Takeshi Hayashi, "On Derivation Trees of Indexed Grammars..." Pub. RIMS
(Kyoto University) 9:1 (1973), 61-92.
T. S. E. Maibaum, "A Generalized Approach to Formal Languages," J.
Computer and Systems Science 8:3 (1974), 409-439.
Parchmann, Duske, Specht, "On Deterministic Indexed Languages,"
Information and Control 45 (1980), 48-67.
Parchmann, Duske, Specht, "Closure Properties of Deterministic Indexed
Languages," Information and Control 46 (1980), 200-218.
Aaron Emigh email@example.com ...!ucscc!oak!aaron
Return to the
Search the comp.compilers archives again.