23 Feb 2001 00:04:03 -0500

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) |

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.