IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

LL(K) PARSING
BY A CANONICAL P.D.A.
USING
BOUNDED CONTEXT TECHNIQUE

Gérard TERRINE
Anne-Marie COUHAULT

Rapport de Recherche N° 222

Mars 1977
LL(K) PARSING BY A CANONICAL P.D.A. USING
BOUNDED CONTEXT TECHNIQUE

Gérard Terrine*, Anne-Marie Couhault**

Résumé :

Presque tous les langages LL(k) peuvent être analysés de manière déterministe par un p.d.a. clas-
sique (sans états) en utilisant des chaînes de regard en avant de longueurs $\le k$ et des chaînes
de regard en arrière de longueurs $\le (n_\epsilon + 1)(k-1)$, $n_\epsilon$ étant le nombre de non-terminaux
dont le langage contient la chaîne vide $\epsilon$.

Abstract :

Almost all the LL(k) languages can be deterministically analyzed by a classical p.d.a. (without states) using look-ahead strings of lengths $\le k$ and look-backward strings of lengths $\le (n_\epsilon+1)(k-1)$ where $n_\epsilon$ is the number of non-terminals whose language contains the empty string $\epsilon$.

* LABORIA

** SESORI
## LL(k) parsing by a canonical p.d.a. using bounded-context technique

Top-down deterministic parsing is appreciated by the compilers writers ; there are more languages generated by LL(k+1) grammars than by LL(k) grammars (contrary to what happens with LR(k) grammars) ; empty productions are generally considered as very useful in practice ; as far as we know, only LL(1) parsers have been actually implemented (since LL(1) = strong-LL(1), besides the minimal look-ahead of one symbol, no states have to be computed and managed) ; implementations so far proposed for LL(k) parsers with k≥1 seem quite complex and to require large amounts of space. These five preliminary statements indicate a gap that we try to palliate in the sequel.

We define a deterministic top-down parser that has no explicit states but uses couples of look-ahead and look-backward strings to make its decisions ; whenever a non-terminal A is on the top of the stack, the p.d.a. has to decide by which, among its productions, A must be replaced ; for that purpose it uses a look-ahead string of length $k_A$ and a look-backward string of length $h_A$ (the $h_A$ first symbols on the stack below A) to search a parsing table $PT(A)$ divided in subtables corresponding to the significantly different (implicit) states ; having defined upper bounds $k$ and $h$ for the lengths of the look-ahead and look-backward strings, we will select for $k_A$ and $h_A$ the least values still insuring the deterministic replacement of A by one of its productions ; this locality of the values $k_A$ and $h_A$ is made possible by the absence of explicit states which, depending on each other, should be computed globally.

We will show, among other results, that for non-ambiguous reduced grammars in which no non-terminal generates a language equal to the empty string (this does not prohibit empty string productions), for all non-terminal A, $0 \le k_A \le k$ and $0 \le h_A \le h = (n_e+1)(k-1)$ (when the p.d.a. is deterministic), where $n_e$ is the number of non-terminals whose language contains the empty string ; if we denote by LL'(h,k) the set of grammars analysed by this (top-down) bounded-context parser, we will prove that LL'((n_e+1)(k-1),k) = LL(k) in the subset of the reduced grammars in which no non-terminal generates a language equal to the empty string. Practically speaking, this bounded-context parser accepts most of the LL(k) languages.

To conclude with another practical point, we will say that, because of the locality of parameters $h_A$ and $k_A$, we will be able to take advantage of situations where G is LL(k) with $k>1$ while most of the parameters $k_A$ and $h_A$ have lower values (typically $k_A=1$, $h_A=0$ or $k_A>1$ and $h_A=0$ where A can be termed strong-LL'(0,$k_A$)).
## Dictionary

As far as possible, we have used notations close to those used in [KNU 71] and [AHO 72]; the abbreviations used are as follows:

* c.f.g. : context-free grammar

* r.c.f.g. : reduced c.f.g.

* CFG : set of the c.f.g.

* RCFG : set of the r.c.f.g.

* NARCFG : set of the non-ambiguous r.c.f.g.

* ε:empty string

* subscript $ε$: when applied to any subset of non-terminal s of a r.c.f.g., indicates that all the languages generated by these non-terminal s contain $ε$.

* subscript $\$$: when applied to any subset of non-terminal s of a r.c.f.g., indicates that none of the languages generated by these non-terminal s is $\{ε\}$

* when applied to any r.c.f.g. (or any set of r.c.f.g.), indicates that no non-terminal of this (or these) r.c.f.g. generates the language $\{ε\}$

* $G = (N,T,R,Z)$ : r.c.f.g. defined by four objects N,T,R,Z

* N : set of non-terminal symbols (not including Z)

* T : set of terminal symbols

* R : set of production rules

* Z : initial non-terminal symbol whose rule is bound to be $Z S^{+h}$, where S is in N and $S^{+h}$ stands for an arbitrary number ($\ge 1$) of markers occurring in no other production.

* V : union of N and T

* $|\theta|$: if $\theta$ is a string in $V^*$, $|\theta|$ denotes its length

* $L(\theta)$ : if $\theta$ is in $V^*$, $L(\theta)$ is the language that can be generated from $\theta$ by using the set $R$; if $\theta$ is in $T^*$ then $L(\theta) = \theta$.

* $\llbracket L(\theta) \rrbracket$ : length of the shortest sentence in $L(\theta)$

* $L(G)$ : is $L(Z)$

* $N_\epsilon$ : $\{A \mid A \text{ in } N \text{ and } \llbracket L(A) \rrbracket = 0\}$

* $n_\epsilon$ : is Card $(N_\epsilon)$

* LSF(G) : set of left sentential forms $\{\theta \mid Z \xrightarrow{L^+} \theta\}$

* $yA\lambda$ : typical writing of a left sentential form in $T^*NV^*$ where y is in $T^*$, A is in N and $\lambda$ is in $V^*$

* FLSF(G) : set of factors (substrings) of the strings in LSF(G)
* RCFG'(k) : subset of RCFG, where all substrings of length = (n_ε+1)k of the left sentential forms generate languages whose sentences are of lengths ≥k

* LL'(k) : subset of LL(k) generating languages that can be parsed by a bounded-context (≤k, ≤(n_ε+1)(k-1)) p.d.a.

* LL'(h,k) : subset of LL(k) generating languages that can be parsed by a bounded-context (≤k, ≤h) p.d.a.
We have in mind to characterize subsets of CFG such that a top-down parser could perform deterministic computations by using a look-ahead string of k terminal symbols from the input tape and a "look-backward" string of h = 0(k) symbols from the stack; provided that the terminal strings of the language generated by these h symbols be of lengths >k, the look-backward string represents the prediction of the look-ahead string derived from the parsing so far performed.

**Definition 1 :** the sets RCFG'(k)

For all G in RCFG, G is in RCFG'(k) iff
for all θ in FLSF(G), if |θ|=(n_ε +1)k then ⌊L(θ)⌋ ≥k

comment : we have chosen h=(n_ε +1)k because such a value complies with
Definition 1 on the set NARCFG<sub>‡</sub> (see Result 1).

Result 1

RCFG'(k) is strictly included in RCFG and strictly includes NARCFG<sub>‡</sub>

Proof :

. let us give a short example : the following grammar is in RCFG while not in
RCFG' :

$$
\begin{align*}
Z & \to S \xrightarrow{h} \\
S & \to aSE|s \\
E & \to b|\epsilon
\end{align*}
$$

a^{|n|}SE^n \xrightarrow{h} is in LSF(G) for all n>1 and thus E^n is in FLSF(G) but |E^n| = n
while ⌊L(E^n)⌋ = 0.

Therefore, the inclusion of RCFG' in RCFG is strict.

. Now we consider G in NARCFG<sub>‡</sub> and θ in FLSF(G) such that

$$
|\theta| \ge n_{\epsilon} + 1 \text{ while } \lfloor L(\theta) \rfloor = 0
$$

we will write

$$
\theta = \theta_1 \theta_2 \dots \theta_l \quad \text{where} \quad 1 = |\theta|
$$
Since $\lfloor L(\theta) \rfloor = 0$ we have

$\theta_i$ is in $N_\epsilon$ for $i=1$ to $1$

But $1 \ge n_\epsilon + 1$ so that for some $t$, $t'$ and $A$ in $N_\epsilon$ we must have

$1 \le t < t' \le 1$ and $\theta_t = \theta_{t'} = A$

Since $G$ is also in $RCFG_\ddag$ then there is at least one terminal string $u$ in $L(A)$ which is also in $L(\theta)$; $u$ is generated by two distinct left-derivation sequences :

$\theta_i \xrightarrow{L \to \epsilon} u$ for $i=1$ to $t-1$, $t+1$ to $1$ and $\theta_t \xrightarrow{L \to \epsilon} u$

$\theta_i \xrightarrow{L \to \epsilon} u$ for $i=1$ to $t'-1$, $t'+1$ to $1$ and $\theta_t \xrightarrow{L \to \epsilon} u$

which makes $G$ ambiguous and contradicts the hypothesis.

Therefore $RCFG_\ddag$ is included in $RCFG'(1)$.

Let us now consider $k>1$ and $G$ in $NARCFG_\ddag$; we still use a string $\theta$ in $FLSF(G)$

$\theta = \theta_1 \theta_2 \dots \theta_1$ where $1 = |\theta|$ is unknown for the time being.

and we assume that

$\lfloor L(\theta) \rfloor \ge k$

We know that no more than $n_\epsilon$ adjacent $\theta_i$ can be in $N_\epsilon$ otherwise $G$ would be ambiguous; thus the longest string $\theta$ such that

$\lfloor L(\theta) \rfloor \ge k$ and $G$ is in $NARCFG_\ddag$

must be in

$(N_\epsilon^\nabla \epsilon V_\ddag)^k$ where $V_\ddag = V - N_\epsilon$

so that its length would in that (worst) case be

$1 = (n_\epsilon + 1)k$

Therefore $NARCFG_\ddag$ is included in $RCFG' = \bigcup_{k>1} RCFG'(k)$

Finally, we give an example of a grammar in $RCFG'$ while not in $NARCFG_\ddag$

$Z \to S \xrightarrow{h} S \to aTb|\epsilon$

$S \to aTb|\epsilon$

$T \to \epsilon$

$L(T) = \{\epsilon\}$ but there is at most one occurrence of $T$ in any left-sentential form of that grammar.

Therefore the inclusion of $NARCFG_\ddag$ in $RCFG'$ is strict.

**End of proof of Result 1**

We can now propose a definition of a so-called $LL'(k)$ set; this definition strongly resembles the Lewis-Stearns theorem on $LL(k)$ grammars, which is :
## Lewis-Stearns theorem on LL(k) grammars.

For all c.f.g. G in RCFG, G is in LL(k) iff :
for all yAλ in LSF(G), for all productions Ψ and Ψ' of A
if Ψ ≠ Ψ' then k : L(Ψλ) ∩ k : L(Ψ'λ) = ∅

## Definition 2 : the sets LL'(k)

For all c.f.g. G in RCFG, G is in LL'(k) iff :
G is in RCFG'(k) and
for all yAλ in LSF(G), for all productions Ψ and Ψ' of A,
for some k_A and h_A such that 1<k_A<k and 0<h_A≤(n_ε+1)k_A-1 = h
if Ψ ≠ Ψ' then k_A : L(Ψ(h_A:λ)) ∩ k_A:L(Ψ'(h_A:λ)) = ∅

**comment** : the only difference lies in the fact that h_A:λ is used instead of λ ;
this makes sense because G is in RCFG'(k).

.h_A is such that ⌊L(A(h_A:λ))⌋≥k_A

## Result 2

LL'(k) is strictly included in LL(k) and strictly includes LL<sub>‡</sub>(k)

## Proof :

We will merely prove inclusions ; strict inclusion could be derived from trivial examples :

. Assume that G is in LL'(k) ; thus it is in RCFG'(k) so that for all productions of any A in N, for all yAλ in LSF(G), we have

$k : L(A(\lambda)) = k : L(A(h(\lambda)))$

because |A(h:λ)|=(n_ε+1)k so that ⌊L(A(h:λ))⌋ ≥k by Definition 1.
Therefore LL'(k) is included in LL(k).

. Assume that G is in LL<sub>‡</sub>(k) ; thus it cannot be ambiguous so that it is also in NARCFG<sub>‡</sub> and consequently in RCFG'(k) and thus, for all left sentential forms yAλ and h=(n_ε+1)k-1, we have

$k : L(A(h:λ)) = k : L(A(λ))$

because |A(h:λ)|=(n_ε+1)k, so that ⌊L(A(h:λ))⌋≥k by Definition 1.
Therefore LL<sub>‡</sub>(k) is included in LL'(k).

## End of proof of Result 2

**comment** : from a practical viewpoint, LL'(k) is "nearly equal" to LL(k).
## Result 3

If a c.f.g. G is in RCFG'(k) while not in LL'(k) then it is not in LL(k).

**comment**: this is just an obvious consequence of the previous proof ; an algorithm to decide whether G is in LL'(k) or not will first decide whether G is in RCFG'(k) or not ; if it succeeds, but fails on the empty-intersection condition, it will be of no use to try to construct a LL(k) parser for L(G).

## Result 4

If a c.f.g. G is in LL'(k), then the top-down deterministic parser of L(G) only needs for his computations (besides terminal symbols matching) :

* the name of the non-terminal on the top of the stack, say A.

* the input tape look-ahead string of length $k_A$ with $O<k_A\le k$.

* the stack look-backward string of length $h'_A$ with $O\le h'_A \le (n+1)(k_A-1)\le h'$.
  $k_A$ and $h'_A$ are the minimal values still insuring the determinism of the
  parsing table $\text{PT}(A)$ ; $h' = (n+1)(k-1)$.

**comment**: the upper bound for $h'_A$ is $O(k-1)$, while in Definition 2 the upper bound for $h_A$ was $O(k)$ ; this means that, provided that G be in RCFG'(k), we need at most $h$ symbols after A to generate terminal strings of lengths greater or equal to $k$ while we do not need more than $h'$ symbols after A to have a deterministic parsing table $\text{PT}(A)$ ; we prove now that result about $h'$.

## Proof.

Let us assume that G is in LL'(k) ; we consider a non-terminal A with p production $\Psi_1, \Psi_2, \dots, \Psi_p$ ; there are two cases :

* $[L(A)] > 0$: in that case, $h_A=O(k-1)$ so that $h'_A=h_A$.

* $[L(A)] = 0$: only one production, say $\Psi_1$, is such that $[L(\Psi_1)] = 0$ ; (if there is more than one such production then G is ambiguous).

All the empty-intersection conditions among the $\Psi_i$ for $i \ge 2$ hold with $h_A=O(k-1)$, thus we are only interested in those conditions between $\Psi_1$ and $\Psi_i$ for $i \ge 2$ ; for all $\lambda$, for some $k_A$, $h_A$ and $h'_A$ such that $1 \le k_A \le k$, $0 \le h_A \le (n_\epsilon+1)k-1$, $0 \le h'_A \le (n_\epsilon+1)(k-1)$, for all $i$ such that $2 \le i \le p$,

$$k_A : L(\Psi_1 h_A : \lambda) \cap k_A : L(\Psi_2 h'_A : \lambda) = \emptyset$$

Let us assume that there are $\lambda$ and $\lambda'$ such that
$h_A : \lambda \neq h_A : \lambda'$ and $h'_A : \lambda = h'_A : \lambda'$

Considering look-backward strings of length $h'_A$ instead of $h_A$ will not allow to distinguish $\lambda$ from $\lambda'$; therefore the conditions for $\lambda$ and $\lambda'$ must be merged; let $E_1 = k_A : L(\Psi_1 h_A : \lambda) ; E'_1 = k_A : L(\Psi'_1 h'_A : \lambda') ;$

$E_i = k_A : L(\Psi_i h'_A : \lambda) ; E'_i = k_A : L(\Psi'_i h'_A : \lambda')$ for $i = 2$ to $p$;

The two sets of conditions for $\lambda$ and $\lambda'$ are

$E_1 \cap E_i = \emptyset$ and $E'_1 \cap E'_i = \emptyset$ for $i = 2$ to $p$; and merging them yields

$(E_1 \cup E'_1) \cap (E_i \cup E'_i) = \emptyset$ ? for $i = 2$ to $p$

If we notice that $E_i = E'_i$ for $i = 2$ to $p$ because $h'_A : \lambda = h'_A : \lambda'$, we obtain

$(E_1 \cap E_i) \cup (E'_1 \cap E'_i) = \emptyset$ ? for $i = 2$ to $p$;

which is obviously true.

### End of proof of Result 4

### Definition 3: the sets SLL'(k)

For a c.f.g. G in LL'(k), if for a non-terminal A, $h'_A=0$ then A is said to be SLL'(k_A), S standing for strong; if $h'_A=0$ for all A in N then G is said to be SLL'(k).

### Result 5

SLL(1) = LL'(1)

**comment**: it is easy to prove that SLL'(k) is included in strong-LL(k) and strictly includes strong-LL<sub>‡</sub>(k); it is well known that strong-LL(1) = LL(1) and it is no surprise that $h_A=0(k-1)$ directly gives an equivalent result for LL'(1) and SLL'(1).

On the basis of our definition of LL'(k) grammars and of Result 4, we now propose a different formulation of that definition.
**Definition 4 :** second definition of LL'(k)

For all c.f.g. G in RCFG, G is in LL'(k) iff G is in RCFG'(k) and for all yAλ and y'Aλ' in LSF(G), for all productions Ψ and Ψ' of A, for some k<sub>A</sub>, h'<sub>A</sub> and h<sub>A</sub> such that 1<k<sub>A</sub>≤k, 0≤h'<sub>A</sub> <(n<sub>ε</sub>+1)(k<sub>A</sub>-1) and 0≤h<sub>A</sub>≤(n<sub>ε</sub>+1)k<sub>A</sub>-1, if Ψ≠ Ψ' then h'<sub>A</sub>:λ≠h'<sub>A</sub>:λ' or k<sub>A</sub>:L(Ψ(h<sub>A</sub>:λ))∩k<sub>A</sub>:L(Ψ'(h<sub>A</sub>:λ'))=Ø

**comment** : If we assume that λ=λ' then we find again our first definition ; now, if λ≠λ', this new definition gives account of the fact that (may be) the intersection of the two languages is empty, of what, if so, we must take advantage.

. for instance, if for all λ and λ', ψ and ψ',

k_A : L(Ψ(h_A : λ)) ∩ k_A : L(Ψ'(h_A : λ')) = ∅
then h_A', length of the requested look-backward strings can be set to zero

. another instance : if the empty intersection condition is only satisfied for λ=λ' and the strings λ can be distinguished by inspecting their first symbol while we need their two first symbols so that ⌊L(ψ(h<sub>A</sub>:λ))⌋>k<sub>A</sub> for all ψ and λ, then h'<sub>A</sub> will be set to one.

It should be clear that, for every non-terminal A :

k_A is the minimal length of the look-ahead strings insuring the empty-intersection condition for every Ψ, Ψ' and λ=λ'.

. $h_A$ is the minimal length of the strings $h_A:λ$ insuring that $\lfloor L(\Psi(h_A:λ)) \rfloor \geq k_A$ for all $\Psi$ and $λ$.

. h' is the minimal length of the look-backward strings needed to distinguish the different languages of the useful empty-intersections conditions (by useful, we mean : after merging empty-intersection conditions corresponding to a minimal partition of the λ, as seen in the proof of Result 4).

It is still possible to generalize the second definition of LL'(k) in order to obtain a bounded-context definition of a so-called LL'(h,k) set ; the term bounded-context should not be confusing : here it is used with regard to top-down parsing.

**Definition 5 :** the sets LL'(h,k)

For all c.f.g. G in RCFG, G is in LL'(h,k) iff
for all yAλ and y'Aλ' in LSF(G), for all productions Ψ and Ψ' of A,
for some k_A and h_A' such that 1<k_A≤k and 0≤h_A'≤h,
if Ψ≠Ψ' then h_A':λ≠h_A':λ' or k_A:L(Ψλ)∩k_A:L(Ψ'λ')=Ø
**Comment** : We have suppressed the obligation for G to be in RCFG'(k);
thus, if G happens to be in RCFG'(k) then Definition 5 will work for
$h=(n_\epsilon+1)(k-1)$ else it will sometimes work and yield deterministic parsing
tables for L(G). Since it is not guaranteed that G be in RCFG'(k), we can
only rely on the fact that $LL(\Psi\lambda)\supset k$ for all $\Psi$ and $\lambda$, as indicated in the
Lewis-Steams theorem. We shall merely indicate the following result
without proof.

Result 6

LL'((n_ε+1)(k-1),k) includes LL'(k) and is included in LL(k).

**Comment** : For implementation purposes, it seems sensible to use the
definition of LL'(h,k) because it is the less restrictive one.

We will now look at the LL'(k) grammars from a seemingly different viewpoint :
the LL'(k) parser can obviously work through bounded-context techniques but
we will show that it can as well work with a finite-state control ; every
non-terminal A in the stack is appended by a state number s indicating which
parsing table PT($A_s$) must be looked up to find the terminal look-ahead
string. We will see now how to proceed from one approach to the other one.

Result 7

For all c.f.g. G in LL'(h,k), it is possible to build a finite-state grammar G'
whose language is the set of all the couples of look-ahead and look-backward
strings met during the computations of the LL'(k) parser on all the sentences
in L(G).

Proof :

It follows about the same principle as in [KNU 65] p. 614 ; let us build the
rules and non-terminals of G' from the rules and non-terminals of G ; we
assume that the square brackets and the slash are not in T.

. Initial non-terminal :

if Z is the initial non-terminal of G, then [Z ; ε] is the initial non-
terminal of G'

. For all rules $A \to \Psi_1|\Psi_2|\dots|\Psi_{p_A}$ where $\Psi_i=X_{i,1}, X_{i,2},\dots,X_{i,li}$, for all $[A; \beta]$ already created,

. if $A \neq Z$ then create the following rules (whose right hand side is termi-
nal) : $[A; \beta] \to u/A_i/\beta$, for $i=1$ to $p$,
where $i$ is a production number of $A$, $u$ is a look-ahead string in $k:L(\Psi_i, \beta)$
and $\beta$ is a look-backward string

* for all $X_{i,j}$ in $N$ such that $X_{i,li} \neq A$, create the following rules :
  $[A; \beta] \to [X_{i,j}; \gamma]$, for $i=1$ to $p_A$,
  where $\gamma$ is in $h:(X_{i,j+1} \cdots X_{i,li} \beta)$

The language $L(G')$ is the set of all the $u/A_i/\beta$ which for all $A$ in $N$ and all its productions $\psi_i$, $i=1, \dots, p_A$ are the triples (with slash separators)

* look-ahead string : $u$

* name of non-terminal subscripted by the number of the production that will replace it : $A_i$

* look-backward string : $\beta$

$G'$ is a "degenerate" linear grammar whose language is a (finite) set of strings of bounded lengths.

End of proof of Result 7

**comment**: if a c.f.g. $G$ is in $LL'(h,k)$ for some finite $h$ and $k$, the grammar $G'$ built as shown in the proof of Result 7 allows to construct a parser with finite control for $L(G)$.

**Algorithm 1**: to construct a parser with finite control for $L(G)$ with $G$ in $LL'(h,k)$.

We will build a new grammar $G''$ from $G$ and $G'$; $G''$ is very similar to $G$ but has much more rules corresponding to the states indicated by $G'$:

* for all $[A; \beta]$ in $N'$ create $A_t$ in $N''$ by subscripting the strings $\beta$

* for all rules of $G$, $A \to \psi_1|\psi_2|\dots|\psi_{pA}$ where $\psi_i = X_{i,1} X_{i,2} \cdots X_{i,li}$, for all $\beta$ in $V^h$ such that $[A; \beta]$ is in $N'$ and $\beta$ has subscript $t$, create new rules of $G'$ such as

$A_t \to \psi_1''|\psi_2''|\dots|\psi_{pA}''$, for $t=1$ to $Card(\{\beta\})$,

where $\psi_i'' = X_{i,1}'' X_{i,2}'' \cdots X_{i,li}''$ for $i=1$ to $pA$

and where the $X_{i,j}''$ are computed as follows

* if $\psi_i'' = \epsilon$ then $\psi_i'' = \epsilon$

* if $X_{i,j}$ is in $T$ then $X_{i,j}'' = X_{i,j}$

* if $X_{i,j}$ is in $N$, then look for the rule of $G'$ $[A;\beta] \to [X_{i,j};\gamma]$

where $\beta$ has subscript $t$ and $\gamma$ has subscript $t'$ and, assuming that the name of $X_{i,j}$ is $B$, construct $X_{i,j}'' = B_{t'}$; if such a rule does not exist then :

* if $X_{i,li}'' = A$ then $X_{i,li}'' = A_t''$
The parsing tables $\text{PT}(A_t)$ are constructed as follows

for all $A_t$ in $N''$ where $t$ is the subscript of some $\beta$ in $V^h$, look for
all the production $u/A_i/\beta$ in $G'$ and include the couples $(u,i)$ in $\text{PT}(A_t)$

**comment** : The parser with finite control for L(G) is actually a classical p.d.a. with regard to G" ; whenever a non-terminal $A_t$ occurs on the top of the stack, the look-ahead string is searched for in the parsing table $\text{PT}(A_t)$ and, when found, yields the number i of the production $\psi_i$ by which $A_t$ must be replaced. This is obviously faster than using look-ahead and look-backward strings but needs more space since G" must be stored instead of G ; the overall size of the parsing tables is about the same in both cases.

Estimating the size of G" compared to G is not easy ; a grossly over estimated upper bound can be obtained as follows:for every A in N,there are at most $n_A=(\text{Card}(V))^h$ non-terminals $A_t$ in N" because there are at most $n_A$ such strings in $V^h$ ; actually, it is unnecessary to store all the rules of left hand side $A_t$ (in G") for $1 \le t \le n_A$ : it is enough to store the rule of left hand side A (in G) and some representation of the correspondance between the state numbers associated with A and the state numbers of the non-terminals occuring in the productions of A.
Examples

Definition 1 :

$$
G1 : \begin{aligned}[t]
    & Z \to S^{-1} \stackrel{\rho}{\to} S \\
    & S \to aSA \mid \varepsilon \\
    & A \to bb
\end{aligned}
\qquad
\begin{array}{l@{\qquad}l@{\qquad}l}
\lfloor L(S) \rfloor = 0 & n_{\varepsilon} = 1 & \\
\lfloor L(A) \rfloor = 2 & &
\end{array}
$$

$G_1$ is in RCFG', because there is at most one S in every string of LSF($G_1$) ;
thus for all $\theta$ in FLSF($G_1$) $|\theta| = k+1$ (instead of 2k) insures $\lfloor L(\theta) \rfloor \ge k$

Definition 2 :

$$
G2 : \begin{array}{r@{\quad}l@{\quad}l@{\quad}l@{\quad}l}
 & Z \to S^{-1} \stackrel{\rho}{\to} S & \multicolumn{1}{l}{\text{S} \to \text{xAa} \mid \text{yA}} & \multicolumn{1}{l}{\text{\lceil L(S) \rceil} = 2} & \multicolumn{1}{l}{n_{\epsilon}=0} & \multicolumn{1}{l}{h \le k-1} \\
 & A \to aA \mid a & \multicolumn{1}{l}{\text{A} \to \text{aA} \mid \text{a}} & \multicolumn{1}{l}{\text{\lceil L(A) \rceil} = 1} & &
\end{array}
$$

$G_2$ is in LL'(3) : it is in RCFG'(k) for all $k \ge 0$ ; $h \le 2$ :

$$
k_S = 1 ; h_S = 0 ; k_S : L(xAa) \cap k_S : L(yA) = \{x\} \cap \{y\} = \emptyset
$$

$$
k_A = 3 ; h_A = 2 ;
$$

$$
h_A : \lambda = \{a \searrow, \nearrow \}
$$

$$
k_A : L(aAa \searrow) \cap k_A : L(aa \searrow) = \{aaa\} \cap \{aa \searrow\} = \emptyset
$$

$$
k_A : L(aA \searrow \searrow) \cap k_A : L(a \searrow \searrow) = \{aa \searrow, aaa\} \cap \{a \searrow \searrow\} = \emptyset
$$

Result 4

Let us consider $G_2$ ; $n_\epsilon=0$ ; $k=3$ ; $h\le2$ ; $h'\le2$ ;

$$
k_S = 1 ; h_S = h_S' = 0 ;
$$

$k_A=3$ ; $h_A=2$ ; $h'_A=1$ because the two possible $\lambda$ following A are $a\searrow$ and $\searrow\searrow$

which can be discriminated by their initial symbols and because both empty
intersection conditions cannot be merged because of the look-ahead string
aa-

Result 4

$$
G3 : \begin{array}{r@{\quad}l@{\quad}l@{\quad}l@{\quad}l}
 & Z \to S^{-1} \stackrel{\rho}{\to} S & \multicolumn{1}{l}{\text{S} \to \text{xAa} \mid \text{yAb}} & \multicolumn{1}{l}{\text{\lceil L(S) \rceil} = 1} & \multicolumn{1}{l}{n_{\epsilon}=1} & \multicolumn{1}{l}{h \le 2k-1} \\
 & A \to aA \mid \varepsilon & \multicolumn{1}{l}{\text{A} \to \text{aA} \mid \varepsilon} & \multicolumn{1}{l}{\text{\lceil L(A) \rceil} = 0} & & h' \le 2k-2
\end{array}
$$

$G_3$ is LL'(2) ; $n_\epsilon=1$ ; $k=2$ ; $h\le3$ ; $h'\le2$ ;

$$
k_S = 1 ; h_S = 0 ; h'_S = 0 ;
$$

$$
k_A = 2 ; h_A = 2 ; h'_A = 0 ;
$$

$$
h_A : \lambda = \{a \searrow, b \searrow\}
$$

$$
k_A : L(aAa \searrow) \cap k_A : L(a \searrow) = \{aa\} \cap \{a \searrow\} = \emptyset
$$

$$
k_A : L(aAb \searrow) \cap k_A : L(b \searrow) = \{ab, aa\} \cap \{b \searrow\} = \emptyset
$$
we see that both empty intersections can be merged, which yields
{aa,ab} ∩ {a→,b-} = ∅
thus there is no need to distinguish a- from b- so that h'_A=0

**Definition 3**

Let us consider G3 ; S is SLL'(1), A is SLL'(2) and G₃ is SLL'(2)

Definition 4

Let us consider G3 and the non-terminal A such that k<sub>A</sub>=2 ; h<sub>A</sub>=2

h'<sub>A</sub>:a- =h'<sub>A</sub>:a- or k<sub>A</sub>:L(aAa-) ∩ k<sub>A</sub>:L(a-) =Ø ?

h'<sub>A</sub>:a- =h'<sub>A</sub>:b- or k<sub>A</sub>:L(aAa-) ∩ k<sub>A</sub>:L(b-) =Ø ?

h'<sub>A</sub>:b- =h'<sub>A</sub>:a- or k<sub>A</sub>:L(aAb-) ∩ k<sub>A</sub>:L(a-) =Ø ?

h'<sub>A</sub>:b- =h'<sub>A</sub>:b- or k<sub>A</sub>:L(aAb-) ∩ k<sub>A</sub>:L(b-) =Ø ?

Since the second part of these conditions is always true, the first part
can be false and thus h'<sub>A</sub>=0.

Definition 5

$$
G4 : \begin{array}{rcl@{\quad}l}
 & Z \to S- & \multicolumn{2}{l}{\mathbb{L}} \\
 & S \to A & aBd & [L(S)]=0 \\
 & A \to d & \varepsilon & [L(A)]=0 \\
 & B \to aBC & A & [L(B)]=0 \\
 & C \to \varepsilon & & [L(C)]=0
\end{array}
$$

G₄ is not in RCFG'(k) for any k≥1 because L(C)={ε} and left sentential forms
such as a<sup>n+1</sup><sub>B</sub>C<sup>n</sup><sub>d</sub>·<sup>h</sup><sub>A</sub> with n≥1.

Nevertheless G₄ is in LL'(1,2) as we shall see now :

$$
k_S = 1 ; h_S = 1 ; h'_S = 0 ;
$$

$k_S : \lambda = \{ \mathbf{-} \}$

$$
k_S : L(A \mathbf{-} ) \cap k_S : L(aBd \mathbf{-} ) = \{d, \mathbf{-} \} \cap \{a\} = \emptyset
$$

$k_A = 2 ; h_A \text{ unbounded} ; h'_A = 1 ;$

$$
h_A : \lambda = \lambda = \{ \mathbf{-}^h, C^* d \mathbf{-}^h \} ; h'_A : \lambda = \{ \mathbf{-} , C , d \}
$$

$$
k_A : L(d \mathbf{-}^h) \cap k_A : L(\mathbf{-}^h) = \{d \mathbf{-} \} \cap \{ \mathbf{-} \mathbf{-} \} : \emptyset
$$

$$
k_A : L(dC^*d \mathbf{-}^h) \cap k_A : 1(C^*d \mathbf{-}^h) = \{dd\} \cap \{d \mathbf{-} \} = \emptyset
$$

$k_B = 1 ; h_B \text{ unbounded} ; h'_B = 0 ;$

$$
h_B : \lambda = \lambda = \{ C^* d \mathbf{-}^h \} ;
$$

$$
k_B : L(abcc^*d \mathbf{-}^h) \cap k_B : L(ac^*d \mathbf{-}^h) = \{a\} \cap \{d\} = \emptyset
$$
## Result 7 and algorithm

Let us consider $G_2$

$$G'_2 : [Z;\epsilon] \rightarrow [S;\text{---}] \\ [S;\text{---}] \rightarrow [A;a\text{---}] | [A;\text{---}] | \begin{array}{l} \text{xaa}/S_1/\text{---} \\ \text{yaa}/S_2/\text{---} \end{array} \\ [A;a\text{---}] \rightarrow \text{aaa}/A_1/a\text{---} | \begin{array}{l} \text{aa\text{---}}/A_2/a\text{---} \\ \text{a\text{---}\text{---}}/A_2/\text{---} \end{array} \\ [A;\text{---}] \rightarrow \text{aa}/A_1/\text{---} | \begin{array}{l} \text{aaa}/A_1/\text{---} \\ \text{a\text{---}\text{---}}/A_2/\text{---} \end{array} $$

$$G_2'' : Z_1 \rightarrow S_1 \text{---} \\ S_1 \rightarrow xA_1A \mid yA_2 \\ A_1 \rightarrow aA_1 \mid a \\ A_2 \rightarrow aA_2 \mid a$$

Tables of the bounded-context parser for $L(G_2)$ $h_S'=0$; $h_A'=1$

$\text{PT}(S) = (x,1), (y,2)$

$\text{PT}(A) = \begin{array}{l} \text{SPT}(a) = (aaa,1), (aa\text{---},2) \\ \text{SPT}(\text{---}) = (aa\text{---},1), (aaa,1), (a\text{---}\text{---},2) \end{array}$

This parser also needs grammar $G_2$ to be stored.

## Tables of the parser with finite state control for L(G2)

This parser needs $G_2$ plus a representation of the state numbers derived from $G_2''$; for instance $G_2$ plus states vectors as follows

$$\begin{array}{l} Z \rightarrow S \text{---} \\ S(1) \rightarrow xA(1) \mid yA(2) \\ A\begin{pmatrix} 1 \\ 2 \end{pmatrix} \rightarrow aA\begin{pmatrix} 1 \\ 2 \end{pmatrix} \mid a \\ \text{PT}(S_1)=(x,1), (y,2) \\ \text{PT}(A_1)=(aaa,1), (aa\text{---},2) \\ \text{PT}(A_2)=(aa\text{---},1), (aaa,1), (a\text{---}\text{---},2) \end{array}$$
## Conclusion

For almost all LL(k) languages it is possible to build a bounded-context parser using look-ahead strings of lengths ≤k and look-backward strings of lengths ≤h; we have characterized a subset of LL(k) on which $h \le (n_e + 1)(k-1)$, that is $LL_{\oplus}^t(k)$. The advantages of this approach are: it is easy to understand and the parameters h and k are locally, i.e. for each non-terminal, adjusted to the minimal values still insuring the determinism; thus, the parsing tables are also minimized in terms of space. The drawback is some loss of time compared to a parser with finite control, ponderated by the fact that the computation of the states is global and sometimes creates locally useless states and possible table duplications.
Acknowledgments

Our thanks to Prof. C. PAIR for his helpful criticism, to P. BOULLIER, M.C. GAUDEL and B. LORHO for useful discussions.

References

[KNU 71] : Donald E. Knuth, Top-down syntax analysis, Acta Informatica 1 (1971) 79-110.

[AHO 72] : Alfred V. Aho and Jeffrey D. Ullman, The theory of Parsing, Translation and Compiling, Vol. 1 : Parsing, Prentice Hall, Englewood Cliffs, N.J., 1972.

Philip M. Lewis II and Richard E. Stearns, Syntax directed transduction, J. ACM 15, 3(July 68) 464-488.

Daniel J. Rosenkrantz and Richard E. Stearns, Properties of deterministic top-down grammars, Information and Control 17,3(Oct. 70) 226-256.

Donald B. Johnson and Ravi Sethi, A Characterization of LL(1) grammars
Bit 16(1976), 275-280.