The construction of more efficient parsing methods for context-free
grammars is a complicated matter that belongs to a course on compilers. We will
not pursue it here except for some isolated results.
Theorem 5.3
For every context-free grammar there exists an algorithm that parses any w ∈
L(G) in a number of steps proportional to |w| 3 .
There are several known methods to achieve this, but all of them are
sufficiently complicated that we cannot even describe them without developing
some additional results. In Section 6.3 we will take this question up again
briefly. More details can be found in Harrison 1978 and Hopcroft and Ullman
1979. One reason for not pursuing this in detail is that even these algorithms are
unsatisfactory. A method in which the work rises with the third power of the
length of the string, while better than an exponential algorithm, is still quite
inefficient, and a parser based on it would need an excessive amount of time to
analyze even a moderately long program. What we would like to have is a
parsing method that takes time proportional to the length of the string. We refer
to such a method as a linear time parsing algorithm. We do not know any linear
time parsing methods for context-free languages in general, but such algorithms
can be found for restricted, but important, special cases.
Definition 5.4
A context-free grammar G = (V, T, S, P) is said to be a simple grammar or sgrammar if all its productions are of the form
A → ax,
where A ∈ V, a ∈ T, x ∈ V * , and any pair (A, a) occurs at most once in P.
Example 5.9
The grammar
grammars is a complicated matter that belongs to a course on compilers. We will
not pursue it here except for some isolated results.
Theorem 5.3
For every context-free grammar there exists an algorithm that parses any w ∈
L(G) in a number of steps proportional to |w| 3 .
There are several known methods to achieve this, but all of them are
sufficiently complicated that we cannot even describe them without developing
some additional results. In Section 6.3 we will take this question up again
briefly. More details can be found in Harrison 1978 and Hopcroft and Ullman
1979. One reason for not pursuing this in detail is that even these algorithms are
unsatisfactory. A method in which the work rises with the third power of the
length of the string, while better than an exponential algorithm, is still quite
inefficient, and a parser based on it would need an excessive amount of time to
analyze even a moderately long program. What we would like to have is a
parsing method that takes time proportional to the length of the string. We refer
to such a method as a linear time parsing algorithm. We do not know any linear
time parsing methods for context-free languages in general, but such algorithms
can be found for restricted, but important, special cases.
Definition 5.4
A context-free grammar G = (V, T, S, P) is said to be a simple grammar or sgrammar if all its productions are of the form
A → ax,
where A ∈ V, a ∈ T, x ∈ V * , and any pair (A, a) occurs at most once in P.
Example 5.9
The grammar