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]

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

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