|Looking for existing research on a variation of CFGs firstname.lastname@example.org (Todd Curtis Perry) (2001-02-17)|
|Re: Looking for existing research on a variation of CFGs email@example.com (2001-02-23)|
|Re: Looking for existing research on a variation of CFGs firstname.lastname@example.org (Antti Huima) (2001-02-23)|
|From:||email@example.com (Torben AEgidius Mogensen)|
|Date:||23 Feb 2001 00:04:03 -0500|
|Organization:||Department of Computer Science, U of Copenhagen|
|Posted-Date:||23 Feb 2001 00:04:03 EST|
Todd Curtis Perry <firstname.lastname@example.org> writes:
>Could someone point me towards research that has done on the properities
>of grammars made up of productions of the form A -> B where _both_ A and B
>are strings of terminals or non-terminals.
>[Those are context sensitive grammars. Look in books about compiler theory
>and linguistics. -John]
Actually, in the form Todd describes them, they are unrestricted
(Chomsky type-0) grammars. You get context-sensitive (Chomsky type-1)
grammers if you restrict the left-hand side to be no longer than the
A brief summary of decidability/complexity properties of these and
context-free (Chomsky type-2) grammars are found below:
Type 0 Type 1 Type 2
Parsing (w in L(G)) undec. PSPACE <O(n^3)
Emptyness og L(G) undec. undec. O(|G|)
Equivalence og G and G' undec. undec. unknown
Ambiguity of G undec. undec. undec.
where "undec." means "undecidable". "unknown" means that the
decidability question is still open (AFAIK).
Most parsers use a subset of context-free grammars that can be parsed
on a deterministic stack automaton. This guarantees nonambiguity,
makes parsing linear-time and equivalence decidable. The latter is a
fairly new result.
Torben Mogensen (email@example.com)
Return to the
Search the comp.compilers archives again.