next up previous
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$ For a symbol X $ \in$ VT  $ \cup$ VN 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 up previous
Next: Annexe 2. Up: Final-13-04-2004 Previous: Exercise 10.
Marc Moreno Maza
2004-12-02