Implementing parsers

Introduction

Once we have tokenized some program text, we need to check whether the tokens are in the correct sequence. For example, which of the following token sequences are valid?

1. Tokenization of “32 + 4”: “<number, 32>, <+, +>, <number, 4>”.
2. Tokenization of “+ 32 4”: “<+, +>, <number, 32>, <number, 4>”.

Regular expressions are not powerful enough to make the choices like these. The rules about which token sequences are valid constitute the syntax of a programming language. In this article, we will develop the concepts and techniques of checking syntactic correctness of a program text.

We will assume that the program text is already tokenized. Thus, our input is going to be a sequence of tokens. The tokens we will be dealing with in this article are as follows.

1. The token “number” represents positive integers.
2. The token “id” represents identifiers.
3. The symbols “+”, “-”, “*”, “/”, “=”, “==”, “)”, and “(” represent themselves.

Here are some examples of raw inputs along with their tokenized represenations.

For brevity, we will call a sequence of tokens a string.

Context-free grammars

We need a way to represent programming language syntax. Let’s start with a simple example. Suppose we want to represent those arithmetic expressions where two positive integers are separated by a “+” sign. We can represent this idea using the following notation.

This is an example of a production. There are two parts separated by an arrow. The symbol “expr” on the left of the arrow is the head of this production. The symbols “number”, “+”, and “number” on the right are collectively the body of this production. The underlined symbols appear in the input and are called the terminals. Symbols that are not terminals are called the non terminals.

Only “number + number” conforms to the above production. To represent “number + number + number”, we need to write a new production.

What if we want to represent an unbounded number of “number” tokens separated by “+” signs? The phrase “an unbounded number” suggests induction. We need atleast two productions to represent an inductive definition.

In the above set of productions, the second production is the basis case and the first production is the inductive case. Before we can use this set of productions to represent something like “number + number + number”, we need to define a new concept.

In a set of productions, if we designate a non terminal as a start symbol, we have a context-free grammar.

We can thus use our above pair of productions to create a context-free grammar.

In the above grammar:

1. $V = \{expr\}$,
2. $\Sigma = \{number, +\}$,
3. $P$ is the set of productions, and
4. $S = expr$.

A string is a member of a grammar if it can be derived using that grammar. Let us derive “number + number + number” using our addition grammar. We start with the start symbol.

The above derivation of “number + number + number” is this.

Context-free grammars describe languages. The langauges defined by context-free grammars are called context-free languages.

With context-free grammars, we have a notation to represent the syntactic elements of a programming language.

Reductions

In syntax checking, we are given a grammar and a string and we want to check whether the string is in the language of that grammar. We need to find the derivation of that string using the grammar.

A more convinient way to look into this problem is to look at derivations in reverse. The above derivation of “number + number + number” in reverse looks like this.

We are finding instances of production bodies in the string and replacing them with production heads. This process of replacing an instance of a production body with a production head is called reduction. Reduction is the opposite of the application of a production. We can now state the condition under which a string belongs to a context-free language.

Extending context-free grammars

The addition grammar is contrived. Because of that, we have not uncovered the full complexity of derivations and reductions. Before moving further, we should learn about extending context-free grammars.

Context-free grammars are defined inductively. Thus, we can extend a context-free grammar by adding more inductive cases as productions. Let’s try to extend our arithemtic grammar. Right now, it can only handle the “+” operator.

We now want to add support for the “*” operator. We can do that by adding more productions to our addition grammar.

One way to add more induction cases is to introduce new non terminals. This is what led us from addition grammar to addition and multiplication grammar. Let us look at another example. If we want to handle parenthesized expressions like “(123 + 12) * 3”, we can extend our addition and multiplication grammar like this.

We can add inductive cases to our grammar without introducing new non terminals by changing the way non terminals are arranged in production bodies. Let us extend our grammar to handle “" and “-” operators.

The complete arithmetic grammar is realistic enough for us to elucidate points we would otherwise have missed had we continued with our original addition grammar.

Implementing reductions

Let us go back to the problem of implementing reductions. The implementations of reductions, and of grammars, are called parsers. The process of reducing a string of tokens to the start symbol of a grammar is called parsing.

Let us reduce “(number - number) * (number / number)” using the complete arithmetic grammar. To get started, here is the derivation of “(number - number) * (number / number)” using the complete arithmetic grammar. Notice that at each step, we apply a production to the rightmost terminal. This technique is called the rightmost derivation.

Doing the derivation in reverse results in the reduction of the input to the start symbol.

Because we already know how this particular input is reduced, we can use the above steps as our guide and focus on the data structures and the algorithms we can use to represent this process. We will then use those techniques to parse new inputs.

Suppose the input is an array of tokens and we have an empty stack. In the following illustrations, the top of the stack is on the right. The initial state looks like this.

We will apply one of the following two operations at each step.

1. We shift a token onto the stack. This is called performing a shift.
2. We identify the stack contents with a production body and perform a reduction on part or all of the stack. This is called performing a reduce.

The parser variant we are considering is called a shift-reduce parser.

Let us shift one more token on to the stack.

We now do two shifts.

We shift again.

In the steps we have executed so far, we notice two things.

1. We need to decide whether to shift or to reduce at each step.
2. We need to select a production whenever we perform a reduce.

We continue executing actions similar to above till we have only the start symbol on the stack. We add a new column of explanations for each of these steps. On each row, the explanation is the action we do to get the next row.

We now have the mechanism to implement parsing. We either do a shift or a reduce using a stack and an array of tokens. But the above implementation makes decisions at each step and we don’t yet know how to make those decisions. The decisions are:

1. Should we shift or should we reduce?
2. If we are reducing, which production should we use?

In other words, we have the mechanisms in place but not the policies to drive those mechanisms. We will focus next on changing our above implementation so that it can make those decisions.

Implementing parsing decisions

What are the decision inputs at each step? We have two pieces of information.

1. The entire stack that is read from right to left.
2. The next token in the array of tokens that we are parsing. In other words, we have a lookahead of one symbol.

To see how these information pieces can be used to make a decision, let’s look at the reduction of “number + number * number”.

Therefore, to make progress with the parser implementation, we need to find the terminals that can follow each non terminal of a grammar during a derivation.

What happens if a non terminal is followed by another non terminal in a parser state? That’s not possible in our arithmetic grammar above because all non terminals are followed by terminals so let’s create a new grammar to answer this question.

Suppose we want to express C-like declaration statements like “int foo, bar;” or “float temperature;”. Here’s a grammar to represent declaration statements.

We can now define the concept of the first set of a grammar symbol.

Let us look at a couple of examples to make this clear.

We can now design an algorithm to compute the first sets. The definition suggests a recursive algorithm. The basis case is when the grammar symbol we are computing the first set of is a terminal. The recursive case is when the grammar symbol is a non terminal.

• Because the non terminal $type$ derives two single length strings, $int$ and $f\!loat$, and nothing else, the first set of $type$ is $\{int, f\!loat\}$.
• Because of the production $declaration \rightarrow type \space variables\_list\underline{;}$, every string derivable from $declaration$ must start with something that is derived from $type$. Thus, the first set of $type$ is a subset of the first set of $declaration$. Since there are no other productions with $declaration$ as the head, the first set of $declaration$ equals the first set of $type$.

We are now in a position to write down a recursive algorithm to compute first set.

def compute_first_set(grammar_symbol):
  if grammar_symbol is a terminal:
    # Basis case
    return {grammar_symbol}
  else:
    # Recursive case
    first_set = {}
    productions_of_grammar_symbol = get_all_productions_of_grammar_symbol(grammar_symbol)
    for production in productions_of_grammar_symbol:
      first_symbol_of_production_body = get_first_symbol_of_production_body(production)
      if first_symbol_of_production_body != grammar_symbol:
        # Recurse
        first_set_of_body_symbol = compute_first_set(first_symbol_of_production_body)
        first_set.union_with(first_set_of_body_symbol)
    return first_set
}

The execution looks like this.

Let us do another example, this time with our arithmetic grammar.

The execution looks like this.

We can now go back to designing an algorithm for computing follow sets. There are two scenarios under which a terminal can be in the follow set of a non terminal.

We now have enough information to write an algorithm to compute follow sets.

def compute_follow_set(non_terminal):
{
  follow_set = {}

  for production in productions {
    production_body = production.get_body()
    if the given non terminal does not appear in the production body:
      continue

    if the given non terminal is not the last symbol of the production_body:
      follow_set.union_with(compute_first_set(symbol following the given non terminal))
    else:
      production_head = production.get_head()
      follow_set.union_with(compute_follow_set(production_head))

  return follow_set
}

Let us try the above algorithm on our arithmetic grammar which is repeated below.

Here is the execution of “compute_follow_set(factor)”.

We can now go back to making decisions at parsing steps. We can now answer both questions we posed earlier. The statements below cannot be justified in a formal way and hence we will call them heuristics. These heuristics will always work for the grammars we will consider and they work for grammars that common occur in programming language syntax specifications.

1. The first question was about deciding whether to shift or to reduce at each parsing step. The answer is this. If we reduce the top stack contents and the resulting non terminal has the following token in its follow set, we reduce. Otherwise, we shift.
2. If we can choose between multiple productions, we choose the one which reduces the maximum of the stack contents.

Let’s see an example of how these heuristics can be applied in practice. We will parse “(number - number) * number” using our arithmetic grammar. Before we do our parsing, we should write down the follow sets of each non terminal.

The initial state of the parser is this.

There is nothing on the stack so we do a shift.

We cannot do any more reductions so we do a shift.

We cannot do any more reductions so we shift.

We cannot do any more reductions so we do a shift.

We are stuck now. We cannot do any more moves but we still haven’t reduced the stack contents to the start symbol. We need to introduce more features into our parser to get past this stuck state.

We introduce the convention that every input is ended by $$$. The $$$ symbol is not a part of the grammar and is introduced to mark the end of the inputs we will be parsing.

Suppose we start with the input $number + number$. With our arithmetic grammar, it will be reduced to $expr \$$. In general, every start symbol is going to have $\$$ in its follow set. Thus, the follow sets of arithmetic grammar that we computed above need revision.

We now replay all the parsing steps we did above.

Since we have reduced the input to the start symbol, our parsing has finished succesfully.

We now have a definite framework to execute parsing actions and make parsing decisions. But we need to make the above mechanisms and policies more amenable to implementation. In the next section, we will recast the above framework as a graph problem.

Implementing parsers using automata

In the last section, we arrived at a framework for making parsing decisions. We now have all the ingredients we need to construct a parser programmatically given a context-free grammar. In this section, we will implement context-free grammars using a specific type of automaton.

Let us start by doing a quick review of the basics of finite automata. A finite automaton is a labelled directed graph where the vertices of the graph are called the states and the edges are called the transitions. Each finite automaton has:

1. A set of states.
2. A state identified as a start state.
3. A set of states identified as final states.
4. An alphabet which is the set of symbols that can label transitions.
5. A transition function which takes a state and an alphabet symbol as inputs and outputs a set of states.

Here is an example.

The automaton makes moves on a given string. For example, for string “ab”, the above automaton makes the following moves.

How can we use finite automata to track parser state? To examine that, let us go back to the simplest grammar we had at the beginning.

We can construct a finite automaton that recognises the body of the production.

We can also construct a finite automaton to recognise the head of the production.

When we are scanning some input from left to right, we can use the body automaton to keep track of where we are in the input. After we have reduced the input to the production head, we can use our head automaton to see if the reduced string is correct.

We can track where we are in a production with a dot in the production body. Here are some examples.

It is formally defined like this.

We can now redraw our body automaton using production items.

We can now make an automaton to recoginse the string “expr”. Let us call it the head automaton.

The sequence of things that need to happen for our addition grammar to accept a string is this.

1. The string takes the body automaton to state 3.
2. Once we reach the state 3, we reduce using the addition grammar production.
3. We now have the head of the production as the input string. We confirm that by executing the head automaton using the reduced string and checking whether it goes to state 1.

There are gaps between these steps that we need to fill. How can we construct a single automaton to execute the above steps. We somehow have to do this.

1. We traverse the body automaton using the input string.
2. Once the body automaton scans the input string corresponding the body of a production, we do a reduction.
3. We traverse the head automaton using the reduced string.

The way to achieve this is by pushing the current state of the automaton on a stack after each transition. Earlier, we implicitely tracked our current state using a single variable. If we push the current state after each transition to a stack, it would enable us to “revert” the steps the automaton took.

Let us now see how can we construct an automaton for a grammar. We start with the start symbol production.

Let us try to parse “number + number” using the above automaton and a stack. We represent the stack contents by writing down the elements of the stack seperated by commas such that the top of the stack is on the right. Initially, the stack consists of the start state of the automaton.

After reading “number”, the automaton goes to state 3. We push that state on to the stack.

After reading “+”, we push state 4 onto the stack.

Finally, we ready “number” and the new stack state looks like this.

We have reduced the string to “expr”. We now restart the automaton with “expr” as the input. The stack looks like this after reading “expr”.

The current state of the automaton corresponds to the input reduced to the start symbol. Hence, the automaton has parsed “number + number” succesfully.

Let us try a slightly more complex grammar. We augment our original complete addition grammar with a new start symbol.

As above, we start with the start symbol production state.

Starting from state 1, we can include all the states to process “expr + number”.

We can similarly add the states to process “number” from state 2, and to process “expr” from state 0.

Let’s parse “number + number + number” using our above automaton. We will write the stack states on the left and the input that remains to be parsed on the right. The start state looks like this.

After reading the first token, we reach state 6. The parser state now looks like this.

Let us continue processing our string using the automaton. There is nothing we can do from state 7 but from state 3, we can follow a transition to state 4 using “+”.

From 4, we can go to 5 following “number” transition.

Like above, we can read “+” and “number” in succession. The state after reading the next two tokens is this.

Let’s compare the automaton framework that we just discussed with the stack framework that we discussed before. We can do a side-by-side comparison of parsing “number + number + number” using addition grammar.

The symbols on the framework stack are exactly those that drive the automaton. Hence, the automaton framework is equivalent to the stack framework. And because the automaton is a directed graph, we can use the standard graph data structures and algorithms to implement it.

Let us try a slightly more complicated example. Here is the augmented addition and multiplication grammar.

compute_epsilon_closure(item, grammar):
  epsilon_closure_set = {item}
  queue.enqueue(item)
  
  while queue is non-empty {
    current_item = queue.dequeue()
    if current_item has dot before a non terminal:
      for production in productions of non terminal:
        next_item = construct item for the production with dot on the left side of the body
        if next item is not already in the epsilon closure set
          epsilon_closure_set.add(next_item)
          queue.enqueue(next_item)

To make the illustrations concise, we collect all the items that belong to the same closure set into item sets. The above closure set looks like this.

We can continue in breadth-first search fashion. Let us now look at the state 1. There is only one transition out of that state, the one with the label +. We compute the epsilon closure of the new state; it looks like this.

Continuing with our breadth first search, we next look at state 2. There is one transition out of that state with label *.

We can keep expanding the transition graph using the breadth first search. The complete automaton looks like this.

The above graph can be represented by the following adjacency list.

{
  0: {"expr": 1, "term": 2, "factor": 3, "number": 4},
  1: {"+": 5},
  2: {"*": 6},
  5: {"term": 7, "factor": 3, "number": 4},
  6: {"factor": 8, "number": 4},
  7: {"*": 6}
}

However, there are some differences between directed graphs and the above automaton.

1. When we reach a new state, we push that state on to the stack. That is, we do a shift.
2. When we reach a state where any of the items has the dot on the right side of the body, we do a reduce using that production, depending on the next input token.

We need to modify our above representation to handle shift and reduce actions. To support shift, we add a prefix “s” to each state that is the result of a state and a transition symbol.

{
  0: {"expr": "s1", "term": "s2", "factor": "s3", "number": "s4"},
  1: {"+": "s5"},
  2: {"*": "s6"},
  5: {"term": "s7", "factor": "s3", "number": "s4"},
  6: {"factor": "s8", "number": "s4"},
  7: {"*": "s6"}
}

To add support for reduce, we first number all the productions so that we can refer to them.

Next, we compute the follow set of each non terminal.

{
  0: {"expr": "s1", "term": "s2", "factor": "s3", "number": "s4"},
  1: {"+": "s5"},
  2: {"*": "s6"},
  5: {"term": "s7", "factor": "s3", "number": "s4"},
  6: {"factor": "s8", "number": "s4"},
  7: {"*": "s6","+", "r2", "$", "r2"}
}

In general, to fill in the reduce moves in our above data structure, we need to do these things:

1. We look at each state and select those that have at least one item with the dot on the right side.
2. For each symbol in the follow set of the head of the reducible item, we add entries for that state and that symbol for the correponding reduction.

The above data structure called a parsing table. It can be constructed by doing a breadth first search.

def construct_parsing_table(grammar):
  productions_list = grammar.get_productions()
  
  start_production = grammar.get_start_production()
  start_item_set = construct_item_set(start_production)
  
  queue.enqueue(start_production)

  parsing_table = {}
  # BFS to compute shift moves.
  while !queue.empty():
    current_state = queue.dequeue()
    for transition_symbol in current_state.get_transition_symbols():
      next_state = current_state.compute_next_state(transition_symbol)
      parsing_table.add_entry(current_state, transition_symbol, next_state)
  
  # Compute reduce moves by scanning all the states.
  for item_set in all_item_sets():
    for item in item_set.get_reducible_items():
      if item has dot on the right hand side: 
        production = item.get_production()
        production_head = production.get_head()
        production_number = production.get_number()
        for symbol in follow_set(production_head)
          state = item_set.get_state()
          parsing_table.add_entry(state, symbol, "r production_number")

  return parsing_table
}

Using the above algorithm, the parsing table of the addition and multiplication grammar looks like this.

{
  0: {"expr": "s1", "term": "s2", "factor": "s3", "number": "s4"},
  1: {"+": "s5", "$": "r1"},
  2: {"*": "s6", "+": "r3", "$": "r3"},
  3: {"+": "r5", "*": "r5", "$": "r5"},
  4: {"+": "r6", "*": "r6", "$": "r6"},
  5: {"term": "s7", "factor": "s3", "number": "s4"},
  6: {"factor": "s8", "number": "s4"},
  7: {"*": "s6", "+", "r2", "$", "r2"},
  8: {"+": "r4" "*": "r4", "$": "r4"}
}

Let us do an example run of the above parsing table on the input “number + number * number”. We add a column for explanations.

Notice that all the information we need to make parsing moves is contained in the parsing table. We no longer need to look at a production list or follow sets to execute parsing actions. We thus have solved the main problem we were pursuing. Parsing tables are the implementations for context-free grammars.

Conclusion

What is the output of a parser? We can return a boolean indicating whether the input is parseable. But we need to return more information. Specifically, the reduce moves we did might be interesting to the later phases of the compiler.

We need to define more concepts before we can discuss the output of a parser. Specifically, we need to execute actions whenever a reduction happens. This subject will be treated in the next article.