Controlled grammar

Controlled grammars are a class of grammars that extend, usually, the context-free grammars with additional controls on the derivations of a sentence in the language. A number of different kinds of controlled grammars exist, the four main divisions being Indexed grammars, grammars with prescribed derivation sequences, grammars with contextual conditions on rule application, and grammars with parallelism in rule application. Because indexed grammars are so well established in the field, this article will address only the latter three kinds of controlled grammars.

Control by prescribed sequences

Grammars with prescribed sequences are grammars in which the sequence of rule application is constrained in some way. There are four different versions of prescribed sequence grammars: language controlled grammars (often called just controlled grammars), matrix grammars, vector grammars, and programmed grammars.

In the standard context-free grammar formalism, a grammar itself is viewed as a 4-tuple,

G

=

(

N

,

T

,

S

,

P

)

{\displaystyle G=(N,T,S,P)}

, where N is a set of non-terminal/phrasal symbols, T is a disjoint set of terminal/word symbols, S is a specially designated start symbol chosen from N, and P is a set of production rules like

X

→

α

{\displaystyle X\to \alpha }

, where X is some member of N, and

α

{\displaystyle \alpha }

is some member of

(

N

∪

T

)

∗

{\displaystyle (N\cup T)^{*}}

.

Productions over such a grammar are sequences of rules in P that, when applied in order of the sequence, lead to a terminal string. That is, one can view the set of imaginable derivations in G as the set

{

p

1

p

2

.

.

.