10 Top Down Parser – FIRST(), FOLLOW(), Parsing Table

Rajeswari Sridhar

In the previous module, we discussed the pre-processing steps that need to be carried out to convert a grammar to be parsed by a top-down parser. In this module, we will discuss how to compute the functions first () and follow(). Using these functions the LL(1) parsing table is constructed. This parsing table will be subsequently used by the parsing algorithm to verify whether an input string belongs to a grammar or not.

10.1 Top-Down Parsing

The input grammar is to be pre-processed and should be free of left-recursion and need to be left factored. This grammar is considered for computing the two functions FIRST(k) and FOLLOW(k). The ‘k’ within the parenthesis indicates the number of input symbols to be considered during parsing. So, if we are to consider only ‘1’ input symbol as look ahead, then we need to compute FIRST(1) and FOLLOW(1) and this is required for a LL(1) parser. We have already indicated in the previous module that LL(1) parser is a type of top-down parser that avoids backtracking. The first ‘L’ indicates that the input is scanned from left to right, the second ‘L’ denotes that the left derivation is to be applied, and the ‘(1)’ indicates looking at 1 input symbol at any point of time. This parser predicts what the input string would look like and hence is called predictive parser. This predictive parser avoids backtracking by constructing a parsing table. To construct this LL(1) parsing table, computation of FIRST(1) and FOLLOW(1) are necessary.

A grammar G is LL(1) if A → α | β are two distinct productions of G:

• For no terminal a, both α and β derive strings beginning with a.
• At most one of α and β can derive empty string.
• If β → ε, then α does not derive any string beginning with a terminal in FOLLOW(A).

  The interaction of the various modules is shown in figure 10.1. From figure 10.1, a parsing table is to be constructed which requires the functions FIRST() and FOLLOW(). The parsing algorithm considers the current input symbol and the symbol on the top of the stack and looks into the parsing table for an action. Based on the action, the parser pushes/pops the stack symbol. The output of the parser will be a “YES” or a “NO” indicating success or failure of the parsing action. The parser accepts the string and outputs a “YES” if the stack is empty and the input is completely processed. Any other state of the input or the stack is to be termed as incorrect string for a given grammar.