Re: Looking for existing research on a variation of CFGs

Todd Curtis Perry <tperry@stanford.edu> 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
right-hand side.


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 (torbenm@diku.dk)

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