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.