# What information do we get from a compiler's parse tree?

In the compiler course by Alex Aiken on Coursera, more specifically lecture 05-02 Context Free Grammars, the professor says that CFGs give answers of the type yes/no, i.e. whether the given string of tokens is valid or not. He adds that it is also desirable to know how a particular string of tokens is in the language; for this purpose he introduces parse trees.

Why is the "how" part important?

Prelude It might be useful to be pedantic and start with a surprising fact: compilers do not use context free grammars, contrary to what you've been told. Instead they use something closely related but subtly different, which might be termed context-free transducers (please let me know if there's an official name for it). They relate to context free grammars as Mealy-machines do to finite state machines.

The reason why CFGs are not used is that CFGs only give a yes/no answer. That's not enough for the subsequent stages of a compiler. Instead, subsequent stages need a good representation of the input program to work with. This representation is the abstract syntax tree (AST). Something similar happens in lexical analysis: contrary to what most compiler courses tell you, the lexer does not use a finite state machine or regular expression to nail down the lexical structure of a language, because regular expressions and finite state machines also only give a yes/no answer. We want the output of the lexical stage to be a token-list for consumption by the parser. Mealy machines deliver token lists.

If this is the case, why do compiler courses usually use regular expressions and finite state machines for the lexical analysis and CFGs for parsing? Do compiler teachers lie to us? No, they want to help us understand:

1. The concepts are really similar, e.g. a Mealy machine is just a finite state machine where every transition carries not just an input action (as they do with finite state machines) but also a corresponding output action. Likewise context free transducers are just CFGs where every production is also associated with an output.

2. Teachers don't want to be overly formal, and expect the students to bridge the gap between finite state machines and lexer / CFG and parser themselves. In practise students almost always do.

Main point. With this pedantic caveat we can come to the original question: what is the parse tree used for?

The parse tree contains the "how a string is in the CFG". The parse tree is used to construct the abstract syntax tree (AST) which is a concise representation of the program that is used by later phases in the compiler, in particular the type checker (for statically typed languages) and the code generator. The advantage of ASTs over other program representations such as strings is that ASTs make access to the immediate sub-programs of a program easy, e.g. the program

if C then P else Q


has three immediate sub-programs namely C, P and Q. The AST for the program has three pointers to the sub-programs:

Both, code-generation and type-checking, involve the recursive invocation of code-generation/type-checker on the immediate sub-programs (plus some glue-code). Hence ASTs provide exactly the information needed for efficient type-checking and code generation.

The relationship between parse trees and ASTs is simple. The parse tree contains the exact information about how a string 'fits' into the CFG. Every production applied when consuming the input string is noted down in the order used. This information has a natural tree shape, whence the name "parse tree". An AST is a parse-tree with redundant information removed. An example of redundant information are properly balanced brackets. Another example is the node labelling that gives the aforementioned information about what productions were used to derive the string. Such information is important for checking if the input string (or more precisely token-list) is syntactically valid, but once that has been acertained, this information is no longer needed for compilation and hence discarded.

Let us look at an example. Consider the arithmetic expression $4 *(3+17)$ in the obvious grammar of arithmetic expressions: $$E \ \ \rightarrow\ \ E + E \ |\ E * E \ |\ ( E ) \ |\ 0 \ |\ 1 \ |\ 2 \ |\ ...$$ Let's ignore the ambiguity and left-recursion in that grammar. Here is a plausible parse tree for $4 *(3+17)$

(Note that the parse tree is usually not constructed explicitly, but is implicity in the structure of the recursion throughout the parsing process.) The corresponding AST is simpler, but still contains all relevant information, including precedence of the addition over the multiplication, in its pointer structure:

Summary: compilers construct ASTs (good representation of the program for future compiler stages) from parse trees (which tell "how" the program is in the CFG).

The parse tree will also give the meaning of the program. For example $7 + 5 * 3$ will be mapped to $7 + (5 * 3)$ because of precedence rules, and in complicated nested if-then-else statements it will be determined which else maps to which then.

In the abstract world, any derivation of a context-free grammar corresponds to a derivation tree; this is what compiler people call parse or syntax tree. These trees capture the structure of the word in some sense.

However, a compiler does not have to utilise it. Compiler generators like yacc allow you to specify actions that are execute upon reduction; the parse tree remains implicit.

However, we often tie semantics to the structure of words. For programming languages, this seems obvious: arithmetic expressions are for all intents and purposes trees, variable visibility and scopes are organised along tree structures, and so on. It can therefore be useful to make syntax trees explicit in a reduced form, that is as abstract syntax trees.

Once you have such a tree, static analysis, optimisations and, finally, code generation are easy to express -- because our semantics fit exactly. Attribute grammars can be used here.

A tool that focuses on AST rewriting is Antlr; here you can even specify tree grammars for AST manipulation.

• In practise the actions while parsing (and implicitly constructing the derivation/parse tree) that you can specify in a tool like yacc are used for the construction of an AST which is used in subsequent compiler phases. – Martin Berger Nov 2 '13 at 16:24
• @MartinBerger: I would sincerely hope so if the source language has a reasonable level of abstraction, but one can certainly output target code directly. When compiling, say, assembly language to binary, more is not necessary. – Raphael Nov 2 '13 at 17:35
• OK, I agree, for very simple compilation tasks, you don't need a fully blown compiler pipeline. I doubt you even need a parser to go assembly -> binary. – Martin Berger Nov 2 '13 at 17:38

Note that a context-free grammar can be ambiguous. Context-free does not mean "unambiguous".

Therefore, when the CFG gives us a yes-or-no answer, it is possible that the given string of symbols is in the language in more than one way: two or more different parses are possible using the same CFG, both of which confirm that the string is valid syntax.

To know which parse was used, we need the abstract syntax tree. (Or some other object, such as information representing the detailed trace of the parsing steps.)

Of course, we need the syntax tree for other purposes also, but the first thing that it gives us is how the syntax was interpreted: how the symbols group together and subordinate. If the string was A + B * C, the parse tree tell us whether the interpretation was (A + B) * C or A + (B * C).

Before we can interpret meaning, we must interpret syntax. (However, we don't have to interpret all the syntax before interpreting any of the meaning. Compilers do some interpretation of meaning on what was already parsed, which guides the parsing decisions for what is yet to come.)

Note that parse tree and abstract syntax tree are two related but different ideas. A parse tree is concerned with the raw syntax, and so it includes punctuation tokens. Parse trees are relatively uninteresting in compilers for programming languages; it is not useful for a compiler's parser to output a parse tree, other than for debugging the low level actions of the parser: is it doing the right things with semicolons, commas, parentheses, and such. What we want is an abstract syntax tree. (In fact, some of the syntax will even disappear before tokenization: for instance, comments may disappear, and serve only to divide two tokens, like a/*...*/b in the C language, producing two tokens. So parse trees, chock full of irrelevant details though they be, do not have all the irrelevant details.)

The abstract syntax tree identifies the meaningful symbols in the utterance and their relation to each other: which feature of the sentence is the major constitutent, and which are its subordinates. For instance, the abstract syntax tree of A * (B + C) will tell us that this is a multiplicative expression: the root node is the * operator, and its children are A, which is a leaf-node, and (B + C) which is subtree consisting of the + node and the children B and C. The semantic actions in the parser know which parts of a phrase carry meaning and which are just punctuation marks; they pull out the meaningful pieces out of the syntax to build the tree.

In an abstract syntax tree, furthermore, what used to be raw tokens in the syntax may be replaced by richly typed objects. In a given language, a token whose lexeme looks like 123 may become an integer object in the tree; a token which looks like abc may turn into a symbol object, and "xyz" into a string and so forth.

• You don't want an ambiguous CFG for your programming language. Because if the grammar is ambiguous, how's the compiler to know which possible parse tree to use? That's why compiler writers usually transform the language's CFG into an equivalent one (= accepting the same language) that is not ambiguous. Where this can be done at all (some languages are inherently ambiguous, but typically not those programming languages people are interested in), this can be done in various ways. With parser generators like Yacc, precedence declarations are popular for this purpose. – Martin Berger Nov 2 '13 at 15:35
• @MartinBerger The question doesn't say anything about a programming language, other than alluding to a compiler course. If a grammar is ambiguous then it cannot even be transformed into a parser (with a tool like Yacc). That tool will run into conflicts which then have to be resolved, and when they are resolved, you get an unambiguous behavior. Even if you don't put %prec and %assoc declarations into Yacc, it will output something anyway, just not necessarily with the behavior you want. – Kaz Nov 2 '13 at 15:50
• I think the context makes it clear that the question is about PLs. Moreover, some approaches to parsing happily accept ambiguous grammars, e.g. Earley parsers. It's also trivial to write top-down parsers in a way that simply return all possible ASTs. But this pushes the problem of disambiguation only towards laters compilation stages. Anyway, in practise, CFGs that are being used for parsing programming languages are not ambiguous, and hence the parse tree is not used for disambiguation. It is used for deciding if the input is syntactically well formed and for building ASTs. – Martin Berger Nov 2 '13 at 16:21