23 Feb 2001 00:08:24 -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: | Antti Huima <huima@localhost.localdomain> |

Newsgroups: | comp.compilers |

Date: | 23 Feb 2001 00:08:24 -0500 |

Organization: | KPNQwest Finland customer news service |

References: | 01-02-098 |

Keywords: | parse, theory |

Posted-Date: | 23 Feb 2001 00:08:24 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]*

If X, Y, ... range over non-terminals and a, b, ... range over

terminals, and S ranges over all symbols, then

(1) If every production is of the form

X -> aY or X -> Y

the grammar is `regular'.

(2) If every production is of the form

X -> S+

the grammar is `positive context-free'. (`Positive' corresponds

to the requirement that the right-hand side of a production is not

allowed to be empty.)

(3) If every production is of the general form

S* -> S*

but so that the length of the right-hand side is not smaller than

that of the left-hand side, then the grammar is `context

sensitive'.

(4) Otherwise, if every production is of the general form

S* -> S*

without restrictions, the grammar is a `phrase structure grammar'

and the language can be whatever accepted by some algorithm.

The corresponding languages are

(1) regular languages

(2) context-free languages

(3) context-sensitive languages

(4) recursively enumerable languages

and correspond to the types 3, 2, 1 and 0 in what is known the Chomsky

Hierarchy.

The corresponding automata classes are

(1) finite-state automata

(2) finite-state push-down automata

(3) linear bounded automata (non-deterministic Turing machines with

a linear bound on the amount of tape to be used)

(4) Turing machines

Thus, Todd's question is a bit too general, as there are different

classes of grammars that all have strings of symbols on the both sides

of a production. Parsing is decidable for context-sensitive grammars

but not for phrase structure grammars, and both grammars fit Todd's

description.

My two cents...

--

Antti Huima

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.