Re: Looking for existing research on a variation of CFGs

torbenm@diku.dk (Torben AEgidius Mogensen)
23 Feb 2001 00:04:03 -0500

          From comp.compilers

Related articles
Looking for existing research on a variation of CFGs tperry@stanford.edu (Todd Curtis Perry) (2001-02-17)
Re: Looking for existing research on a variation of CFGs torbenm@diku.dk (2001-02-23)
Re: Looking for existing research on a variation of CFGs huima@localhost.localdomain (Antti Huima) (2001-02-23)
| List of all articles for this month |

From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: comp.compilers
Date: 23 Feb 2001 00:04:03 -0500
Organization: Department of Computer Science, U of Copenhagen
References: 01-02-098
Keywords: parse, theory
Posted-Date: 23 Feb 2001 00:04:03 EST

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)


Post a followup to this message

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