Annexe 1.

Next: Annexe 2. Up: Final-13-04-2004 Previous: Exercise 10.

Annexe 1.

Recall that for any string $\alpha$ of symbols the set FIRST( $\alpha$ ) satisfies the following conditions for every terminal a and every string of symbols $\beta$

FIRST( $\alpha$ ) $\subseteq$ V_T $\cup$ { $\varepsilon$ }
$\alpha$ $\;\stackrel{{\ast}}{{\Longrightarrow}}\;$ a $\beta$ iff a $\in$ FIRST( $\alpha$ )
$\alpha$ $\;\stackrel{{\ast}}{{\Longrightarrow}}\;$ $\varepsilon$ iff $\varepsilon$ $\in$ FIRST( $\alpha$ ).

For a symbol X $\in$ V_T $\cup$ V_N the set FIRST(X) can be computed as follows

Algorithm 1

$\fbox{ \begin{minipage}{13 cm} \begin{description} \item[{\bf Input:}] $X \in V_... ...) := {\sc FIRST}($X$) ${\cup} \ \{ {\varepsilon} \}$\end{tabbing}\end{minipage}}$

Algorithm 2

$\fbox{ \begin{minipage}{10 cm} \begin{description} \item[{\bf Input:}] $X = X_1 ... ...) := {\sc FIRST}($X$) ${\cup} \ \{ {\varepsilon} \}$\end{tabbing}\end{minipage}}$

Recall that FOLLOW(A) is the set of the terminals that can appear immediately to the right of the nonterminal A in some sentential form. Moreover $ belongs to FOLLOW(A) if A is the rightmost symbol in some sentential form.

Algorithm 3

$\fbox{ \begin{minipage}{13 cm} \begin{description} \item[{\bf Input:}] $G = (V_T... ...} \\ \> \> \> \> \> \> \> $M[A,a]$\ := {\em error} \end{tabbing}\end{minipage}}$

Next: Annexe 2. Up: Final-13-04-2004 Previous: Exercise 10.

Marc Moreno Maza
2004-12-02