Grammar Transformations

This paper is about how you sometimes have to re-write a grammar in order to write a parser.

Before reading this section, you should already be able to answer these questions:

• What is a grammar, and how does it work?
• What do the terms terminal, non-terminal and production mean?
• What does parsing mean?
• What is meant by source program, source language and parse trees?
• What is a parser?
• What is meant by current token (in Sweidsh: aktuell token)?
• What is a recursive-descent parser? How does it work?
• What is a FIRST() conflict, and why is it bad?
• What is a predictive recursive-descent parser? How does it work?
• How do you write a predictive recursive-descent parser based on a grammar?
• What does it mean that a grammar is ambiguous?
• What is a syntax-directed translation scheme?

To write a predictive recursive-descent parser

The steps in summary:

1. Write a grammar that describes the source language that you want to parse.
2. Is the grammar ambiguous? In that case, you must first determine which of the meanings is the right one, and then re-write the grammar so that it only allows that meaning. (Example: Should 3-4-5 be interpreted as (3-4)-5, which is -6, or as 3-(4-5), which is 4?)
3. If the parser is going to do anything more than just check that the source program follows the grammar, you must insert semantic actions that do the things that you want to be done. It could be to calculate the value of expressions, to generate code, or something else.
4. Does the grammar have any FIRST() conflicts? In that case, you must rewrite the grammar so that the FIRST() conflicts disappear.
5. Does the grammar contain left recursion (what that is will be explained later)? In that case, you have to rewrite the grammar so that the left recursion is removed.
6. Construct a predictive recursive-descent parser based on your (possibly re-written) grammar.

What is left recursion, and why is it bad?

expression -> expression + term | term term -> id | num

expression -> expression + term

void expression() {
  if (lookahead == num or lookahead == id) {
    expression(); match('+'); term();
  }
  else
...  

Assume the following source program:

2 + 2 + 2;

num + num + num ;

When entering the function expression it turns out that lookahead is equal to num. Thus, we enter the first branch of the if statement, and we call the function expression.

When entering the function expression it turns out that lookahead is equal to num. Thus, we enter the first branch of the if statement, and we call the function expression.

When entering the function expression it turns out that lookahead is equal to num. Thus, we enter the first branch of the if statement, and we call the function expression.

...

Because no tokens are consumed, the parser will be stuck on the first num. No tokens are consumed, and therefore the program is stuck in an endless recursion.

Other types of parsers, such as those created by the Yacc tool, can handle left-recursive productions, but a recursive-descent parser of the type we see here can't. So you have to write about the grammar.

Elimination of left recursion recursion

A left-recursive production can easily be rewritten as a couple of other rules that are not left-recursive. Suppose the grammar looks like this:

A -> A x | y

The rule is replaced by the following two rules, which describe the same language but are not left recursioned:

A -> y R
R -> x R | empty

Example: This left-recursive grammar,

expression -> expression + term | term

expression -> term rest
rest -> + term rest | empty

• A = expression
• x = + term
• y = term
• R = rest

Expansion of non-terminals using the grammar productions

A -> A x | y

We assume that A is the start symbol. We can generate all allowed programs by repeatedly expanding the non-terminals. There will be a tree that looks like this (but note that this is not a parse tree or a syntax tree, but it is a tree that shows what the grammar allows):

The underlined expressions can not be expanded. We see a pattern: What this grammar describes are programs consisting of a y followed by zero, one or more x .

In the previous section we said that we could write the left recursion grammar to the following grammar, which describes the same language but is not left-recursive:

A -> y R
R -> x R | empty

An example of elimination of left recursion

For example, the following source programs should be allowed: 2, 2+3, 2-3, 2-3+4+5-6

ASU-86 Figure 2.13 / 2.19 shows the translation scheme (ie a grammar of semantic inputs) based on:

expression -> expression + term { print('+') }
expression -> expression - term { print('-') }
expression -> term
term -> 0 { print('0') }
term -> 1 { print('1') }
term -> 2 { print('2') }
...
term -> 9 { print('9') }

Now we re-write the grammar to eliminate the left recursion.
Important: You should handle the semantic actions as part of the grammar, as you re-write it according to the above technique for eliminating left recursion! Otherwise, the prints will end up in the wrong place.

The result will look like this:

expression -> term rest
rest -> + term { print('+') } rest
rest -> - term { print('-') } rest
rest -> empty
term -> 0 { print('0') }
term -> 1 { print('1') }
term -> 2 { print('2') }
...
term -> 9 { print('9') }

• A = expression
• x = + term {print ('+')}
• y = term
• R = rest

• A = expression
• x = - term {print ('-')}
• y = term
• R = rest

void term () {
  if (isdigit(lookahead)) {
    putchar(lookahead);
    match(lookahead);
  }
  else
    error();
}

void rest() {
  if (lookahead == '+') {
    match('+'); term(); putchar('+'); rest();
  }
  else if (lookahead == '-') {
    match('-'); term(); putchar('-'); rest();
  }
  else
    ;
}

void expression() {
  term(); rest();
}

What is a FIRST() conflict, and why is it bad?

Suppose, for example, that a captain can call four different commands to her soldiers: "halt", "forward march", "fire" and "fire cease". It can be described with the following grammar:

command -> halt
command -> forward march
command -> fire
command -> fire cease