Parse the language you actually specified

Prerequisites: Strings, trees, recursion, and arithmetic expressions.

Learning objectives

• Separate lexical tokens from grammatical structure.
• Construct an expression tree using precedence and associativity.
• Explain why consuming the entire input is part of parsing correctness.

Characters become tokens before they become a tree

A lexer groups characters into tokens such as identifiers, integer literals, operators, and punctuation. For the input total + 12 * count, a lexer might produce IDENT(total), PLUS, INTEGER(12), STAR, IDENT(count). Whitespace can separate tokens without appearing in the resulting syntax tree. Comments and source locations also need explicit handling.

A parser then recognizes arrangements of tokens according to a grammar. Lexing and parsing solve different problems: recognizing the characters of an identifier does not determine whether that identifier is a function argument or an operand of multiplication.

Encode precedence in the grammar

A small arithmetic grammar can assign multiplication a tighter binding level than addition:

PSEUDOCODE: grammar, not executable program
expression := term (("+" | "-") term)*
term       := primary (("*" | "/") primary)*
primary    := INTEGER | IDENT | "(" expression ")"

A recursive-descent parser can implement one routine per grammar level. The expression routine first parses a term, then repeatedly combines it with subsequent plus or minus terms. This loop builds left-associated trees. Thus 10−3−2 means (10−3)−2, giving five, rather than 10−(3−2), giving nine. Precedence and associativity are separate decisions.

For 2+34, the first term is 2. After the plus, the term routine consumes 34 as one multiplication subtree. The result is Add(2, Multiply(3,4)), which evaluates to fourteen. Parentheses in (2+3)*4 force the addition subtree to be built as a primary before multiplication, giving twenty.

Reject malformed structure explicitly

After parsing a complete expression, require an end-of-input token if the entry point promises to parse one whole expression. Otherwise a parser might accept the prefix 2+3 and silently ignore an unexpected closing parenthesis or trailing identifier. Error messages should identify the unexpected token and its source location while explaining what was expected.

Unary minus introduces another grammar decision: does −2*3 parse as Multiply(Negate(2),3)? Exponentiation, if added, needs both a precedence level and an associativity choice. An ambiguous grammar does not become unambiguous because a few examples look obvious to a human.

The abstract syntax tree can omit parentheses and separator punctuation once their structural role is captured. Later stages use that structure for name resolution, type checking, evaluation, or code generation. Keeping source spans on nodes makes later errors traceable to the original text. A useful parser test suite covers nested expressions, equal-precedence chains, malformed input, and complete token consumption, not only successful single-number inputs.

Primary reading

• Implementing a Parser and AST (LLVM Project).

Practice problem

Draw or describe the abstract syntax tree for 20−6/2−1 under the stated grammar and compute its result. Explain how a right-associative subtraction rule would change the tree. Then identify the required parser response to the input 2+3) when the entry point promises one whole expression.

Worked solution

Division binds more tightly, so the term 6/2 becomes Divide(6,2). The expression loop makes subtraction left-associative, producing Subtract(Subtract(20,Divide(6,2)),1). Its value is (20−3)−1=16. A right-associative subtraction rule would instead produce Subtract(20,Subtract(Divide(6,2),1)), evaluating to 20−(3−1)=18. This difference shows that precedence alone does not determine all structure. For 2+3), parsing the prefix 2+3 succeeds but leaves a closing-parenthesis token. Since the entry point requires end of input, the parser must report an unexpected trailing token rather than silently accept the prefix. An inner parser invoked after an opening parenthesis would have a different stopping contract.

Check your understanding

What tree does the stated grammar produce for 8−3−1?

• Subtract(8,Subtract(3,1))
• Subtract(Subtract(8,3),1)
• Multiply(8,Subtract(3,1))
• A single integer token 831

Explanation

The repeated subtraction loop combines from the left.

Which obligation catches an accepted prefix followed by garbage?

• Ignoring all remaining tokens.
• Checking for the expected end-of-input token at the top-level entry point.
• Removing multiplication from the grammar.
• Using longer identifier names.

Explanation

Recognizing a prefix is not the same as validating the complete input.

Primary reading

• Implementing a Parser and AST: LLVM Project

Open the study and save your work →