Recursive Descent Parsing

Recall that we have a grammar (set of production rules) and a sentence; our job is to show how the production rules can be applied to the start symbol in order to derive the sentence.

The simplest way to construct a top-down parser is to regard:

• each production rule as defining a function, where:
  • the name of the function is the non-terminal on the l.h.s. of the rule
  • each instance of a non-terminal on the r.h.s. is a call to the corresponding function,
  • each instance of a terminal on the r.h.s. tells us to match it with the input symbol

This is fairly easy to do if each r.h.s. starts with a different terminal symbol - this means that we needed only to read one character from the input in order to know which rule to pick.

Suppose we were given the following production rules:

$$\begin{array}{ccccccccc} X &\rightarrow & AB & \mid & {\bf a}A{\bf b} & \mid & C{\bf c} & \mid & \varepsilon \\ \end{array}$$

Since we can't make easy predictions, the simplest approach here is to try the first rule; if that doesn't work, try the second, and so on. Really, this type of algorithm is more suitable for implementation in a goal-directed language such as Prolog (where we can backtrack after a failure), rhather than a conventional one like C. Note that if we used a Prolog version with an ambiguous grammar, then the program should respond with an answer for each possible derivation (since Prolog will try to find all ways of satisfying its goal).