Context Free Parser

A parser for a Context Free language converts a linear string of input tokens into a parse tree.

Any program that deals with a tree needs a stack to maintain the list of ancestors of the current node, either as:

• a recursive program: e.g., expression parser calls itself as a subroutine

• a program that maintains a stack.

These are equivalent: as we shall see, a recursive program is implemented using a runtime stack.