Predictive parsing

THE IDEA. Predictive parsing relies on information about what first symbols can be generated by the right side of a production. The lookahead symbol guides the selection of the production A $\longmapsto$ $\alpha$ to be used:

• if $\alpha$ starts with a token, then the production can be used when the lookahead symbol matches this token
• if $\alpha$ starts with a nonterminal B, then the production can be used if the lookahead symbol can be generated from B.

THE METHOD.

(1)

For each nonterminal A for each production A $\longmapsto$ $\alpha$ let FIRST($\alpha$) be the subset of V_T  $\cup$  {$\varepsilon$} defined by the following rules

• for every a $\in$ V_T we have

  $$\in \mbox{{\sc FIRST}(${\alpha}$)} \iff \exists \beta \in \cup \alpha \;\stackrel{{\ast}}{{\Longrightarrow}}\; \beta$$ (40)

  
  

• $\varepsilon$ $\in$ FIRST($\alpha$)  $\iff$  $\alpha$$\;\stackrel{{\ast}}{{\Longrightarrow}}\;$$\varepsilon$

In other words the token a belongs to FIRST($\alpha$) iff there exists a string $\gamma$ deriving from $\alpha$ such that a is the first symbol of $\gamma$. Moreover $\varepsilon$ belongs to FIRST($\alpha$) iff $\varepsilon$ derives from $\alpha$.

(2)

Consider the following procedure in pseudo-code of Algorithm 1.

Algorithm 1  

So match(a) moves the cursor lookahead one symbol forward iff lookahead points to a. Otherwise an error is produced.

(3)

A procedure proc$\_A$ (given by Algorithm 2) is associated with every nonterminal A.

Algorithm 2  

In other words, given a nonterminal A the call proc$\_A$ chooses an A-production A  $\longmapsto$  $\alpha$ such that lookahead belomgs to FIRST($\alpha$). If such a production exists then for each symbol X in $\alpha$ (reading $\alpha$ from left to right)

• if X is a terminal, then call match(X)
• if X is a nonterminal, then call proc$\_X$

If no A-production A  $\longmapsto$  $\alpha$ satisfies lookahead $\in$ FIRST($\alpha$) then either A  $\longmapsto$  $\varepsilon$ is a production and the procedure terminates normally, or an error is produced.

(4)

Initially lookahead is the first symol of the input string and we run procS where S is the start symbol.

Observations:

• In Algorithm 2 return is an escape statement without error whereas error is an interruption with error.
• The grammar must have no left recursive derivations, otherwise the parsing may lead to an infinite loop.
• Back-tracking is avoided provided that for every nonterminal A and for every string of symbols $\alpha$, $\beta$

  $$\left\{\vphantom{ \begin{array}{lll} A & \longmapsto & {\alpha} \... ...\ {\sc FIRST}({\alpha}) \ \cap {\sc FIRST}({\beta}) \ = \ {\emptyset}. }\right. \begin{array}{lll} A & \longmapsto & {\alpha} \\ A & \longmapsto & {\beta} \\ \end{array} \Rightarrow \alpha \cap \beta \emptyset$$ (41)

  
  

• The last statement of Algorithm 2 means that the A-production A $\longmapsto$ $\varepsilon$ can be chosen if the lookahead symbol is not in any of the FIRST($\alpha$) for A $\longmapsto$ $\alpha$ with $\alpha$ $\neq$ $\varepsilon$.

Hint: You should understand the production A $\longmapsto$ $\varepsilon$ as a way to say that the nonterminal A can be canceled (if no other A-production is convenient to use).

Example 15   Consider the following grammar (with terminals a, b, c, d and nonterminals S, A)

S	$\longmapsto$	cAd
A	$\longmapsto$	ab  | a

Here we have FIRST(cAd) = {c}, FIRST(ab) = {a} and FIRST(a) = {a}. Unfortunately, if we have lookahead = a we cannot tell each A-production to use. So left factoring would be needed to process this example further (what we will not do).

Example 16   The following grammar generates a subset of the types in the PASCAL language.

type	$\longmapsto$	simple | $\uparrow$id | array[simple] of type
simple	$\longmapsto$	integer | char | num dotdot num

where

• all bold names and the characters $\uparrow$ ,, [, ] are tokens,
• type and simple are nonterminals,
• dotdot stands for ^...
• and num for a type of small integers.

Here's a string of tokens generated by the above grammar.

array [ num dotdot num ] of integer

We give now the FIRST sets of every left side of the above productions.

FIRST(simple)	=	{ integer, char, num }
FIRST($\uparrow$id)	=	{ $\uparrow$ }
FIRST(array[simple] of type)	=	{ array }
FIRST(integer)	=	{ integer }
FIRST(char)	=	{ char }
FIRST(num dotdot num)	=	{ num }

Algorithms 3 and 4 define the procedures proc_simple and proc_type.

Algorithm 3  

Algorithm 4