Introduction to Grammars and Parse Trees

TL;DR

Grammars define the valid structure of a language using rules, much like how English grammar defines correct sentences. When a compiler processes code, it uses these grammar rules to build a parse tree, which is a visual representation of the code's structure. This tree helps the compiler understand if your code is correctly formed and what each part means.

1. The Mental Model

Think of a grammar as a recipe book for a language. It tells you exactly how to combine ingredients (words/symbols) to make valid dishes (programs/statements). A parse tree is like the assembled dish itself, showing all the ingredients and how they fit together according to the recipe.

2. The Core Material

In compiler construction, a grammar is a formal system that describes the syntax of a programming language. It's a set of rules, called production rules, that dictate how valid strings (like code) can be formed. We usually use a notation called Context-Free Grammars (CFGs).

A CFG has four main components:
1. Non-terminal symbols (V): These are abstract concepts that can be broken down further, like Statement, Expression, or IfElseBlock.
2. Terminal symbols (T): These are the basic building blocks of the language—the actual words, numbers, or symbols that appear in your code, like if, else, while, ID (for identifier), NUM (for number), +, *, ;, {, }.
3. Production rules (P): These are the core of the grammar. They show how non-terminals can be replaced by sequences of other non-terminals and terminals. They usually look like A -> B C meaning "A can be replaced by B followed by C."
4. Start symbol (S): A special non-terminal that represents the highest-level structure in the language (e.g., Program).

Let's look at a very simple grammar for arithmetic expressions:

E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> ID

Here:
- E, T, F are non-terminals (representing Expression, Term, Factor).
- +, *, (, ), ID are terminals (representing addition, multiplication, parentheses, and an identifier/variable name).
- E is usually the start symbol.

When a compiler reads your code, it uses these rules to check if the code is syntactically correct. If it is, it can construct a parse tree. A parse tree (also known as a derivation tree) is a hierarchical structure that visually represents how a string of terminals (your code) is derived from the start symbol of the grammar using the production rules.

Key characteristics of a parse tree:
- The root of the tree is always the start symbol of the grammar.
- Internal nodes are non-terminal symbols.
- Leaf nodes are terminal symbols.
- Each internal node A with children X1, X2, ..., Xn corresponds to a production rule A -> X1 X2 ... Xn used in the derivation.
- Reading the leaf nodes from left to right gives you the original input string (the code).

Parse trees are fundamental because they give structure to the flat stream of tokens from the lexer. This structure helps later phases of the compiler, like semantic analysis and code generation, understand the meaning and intent of the code. For example, in an arithmetic expression, the parse tree naturally shows operator precedence (e.g., multiplication before addition).

Here's an example of how a parser might use grammar rules to build a parse tree:

graph TD
    A[Program] --> B[StatementList]
    B --> C[Statement]
    C --> D["ID = Expression ;"]
    D --> E[ID]
    D --> F["="]
    D --> G[Expression]
    D --> H[";"]
    G --> I[Term]
    I --> J[Factor]
    J --> K[ID]
    K --> L["x"]
    G --> M["+"]
    G --> N[Term]
    N --> O[Factor]
    O --> P[ID]
    P --> Q["y"]

This diagram shows a very simple parse tree for the statement x = x + y;. You can see how the Program breaks down into a StatementList, then a Statement, which is an ID = Expression ;. The Expression then breaks down further into Term + Term, and finally to the actual x and y identifiers.

Derivations

Building a parse tree implicitly involves a derivation. A derivation is a sequence of rule applications that transform the start symbol into the input string.
For ID + ID * ID using our simple arithmetic grammar, a leftmost derivation (always expanding the leftmost non-terminal first) would be:

1. E (Start symbol)
2. E + T (Using E -> E + T)
3. T + T (Using E -> T)
4. F + T (Using T -> F)
5. ID + T (Using F -> ID)
6. ID + T * F (Using T -> T * F)
7. ID + F * F (Using T -> F)
8. ID + ID * F (Using F -> ID)
9. ID + ID * ID (Using F -> ID)

Each step here corresponds to applying a production rule and eventually forms the parse tree.

3. Worked Example

Let's use our simple grammar to parse the expression a * b + c and build its parse tree.

Grammar:

E -> E + T | T
T -> T * F | F
F -> ( E ) | ID

Input String: a * b + c

Derivation (Leftmost):

1. E (Start)
2. E + T (Using E -> E + T to prepare for +)
3. T + T (Using E -> T for the leftmost E)
4. T * F + T (Using T -> T * F for the leftmost T)
5. F * F + T (Using T -> F for the leftmost T)
6. ID * F + T (Using F -> ID for the leftmost F, replacing ID with a)
7. a * F + T
8. a * ID + T (Using F -> ID for F, replacing ID with b)
9. a * b + T
10. a * b + F (Using T -> F for the rightmost T)
11. a * b + ID (Using F -> ID for F, replacing ID with c)
12. a * b + c (Matches input string!)

Parse Tree Construction (based on the derivation):

        E
       /|\
      E + T
     /    \
    T      T
   /|\     |
  T * F    F
  |   |    |
  F   ID   ID
  |   (b)  (c)
  ID
  (a)

In this tree:
- E is the root.
- Internal nodes (E, T, F) are non-terminals.
- Leaf nodes (a, *, b, +, c) are terminals, reading left-to-right gives a * b + c.
- The structure correctly shows that a * b is evaluated before + c due to operator precedence (multiplication branches deeper under T before the outer E + T rule is applied).

4. Key Takeaways

• Grammars formally define the correct structure (syntax) of a programming language using production rules.
• Production rules show how non-terminal symbols (abstract concepts) can be replaced by other non-terminals and terminal symbols (actual code elements).
• A parse tree is a visual, hierarchical representation of how a specific piece of code conforms to the grammar.
• The root of a parse tree is the grammar's start symbol; internal nodes are non-terminals, and leaf nodes are terminals.
• Parse trees are crucial for the compiler to understand the structural and semantic meaning of your code.

Common Mistakes to Avoid:
- Confusing terminals and non-terminals: Remember, terminals are the actual symbols in the code; non-terminals are placeholders for structures.
- Forgetting the start symbol: Every grammar needs a designated start symbol from which all valid programs derive.
- Not ensuring completeness: A grammar must be able to derive every valid statement in the language it describes.
- Ignoring operator precedence/associativity: A good grammar naturally resolves these issues, which is evident in the parse tree structure.

5. Now Try It

Using the arithmetic grammar from the "Core Material" section:

E -> E + T | T
T -> T * F | F
F -> ( E ) | ID

Derive the input string (a + b) * c. First, write down the leftmost derivation steps, then sketch the corresponding parse tree, making sure the parentheses correctly group a + b before multiplication. Your success will be seeing a derivation that correctly reaches (a + b) * c and a tree where a + b forms a subtree under an E that's enclosed in parentheses ( ) before being multiplied by c.