Abstract syntax tree 2026-10-13
An abstract syntax tree is a rooted tree recording the meaningful syntactic pieces of a program and how they fit together. A program identifier such as
x, a literal value such as 2, and a node representing addition have different roles. Their arrangement answers structural questions: which program expression supplies an operand, which name is a variable assignment target, and which construct encloses another. This makes an abstract syntax tree useful to a compiler, an interpreter, and the type system that checks a program.The word "abstract" describes what is omitted. Lexical analysis first recognizes lexical tokens, such as
x, =, 2, +, 3, *, 4. A concrete parse tree can retain grammar derivation structure, including punctuation and intermediate context-free grammar categories such as expression, term and factor. An abstract syntax tree usually keeps the operation and its operands without all those grammar scaffolds. Parentheses can determine its shape without surviving as separate nodes. A parser may construct the abstract syntax tree directly; it need not first allocate a concrete parse tree.An abstract syntax tree records programming language syntax, but does not by itself supply all programming language semantics. In
a+b, the names do not reveal their current values, and + might perform addition of integers or concatenate strings. The programming language rules, name bindings, and operand types determine the meaning. In Python, successfully calling ast.parse also does not guarantee that later compilation will accept the result: parsing return 42 succeeds, but compiling that statement outside a function fails. [ref]ast — Abstract syntax trees, Python 3.14 documentation. ast.parse: parsing performs no scoping checks; the return 42 example
An abstract syntax tree is not machine code. Its nodes describe language constructs. A compiler can check and transform this structure before translating it into executable instructions; an interpreter can evaluate an appropriate tree directly. The little evaluator below demonstrates this distinction without pretending to implement an entire programming language.
Ambiguous grammar 2026-10-31
A context-free grammar is ambiguous when some accepted token sequence has two distinct parse trees. Giving a language an unambiguous context-free grammar requires specifying grouping in the productions themselves, rather than relying on an unstated parser conflict rule.
Concatenation grammar Created 2026-09-24 Updated 2026-11-05
For context-free grammars and with disjoint nonterminal symbol sets, introduce a fresh nonterminal symbol and putThen , the concatenation of the two formal languages. After the first production, every production rule acts within one of the two component parse trees. Their terminal words form one word from followed by one from . Conversely, any pair of component derivations can be performed after .
The construction does not work for arbitrary variable-based grammars. Let have production rules and , and let have the single production rule . Here is empty and , but the combined formal grammar derives . The production rule consumes a terminal symbol supplied by the other component, crossing the boundary that context-free grammar rules preserve.
Leftmost derivation 2026-10-31
A grammar derivation that always expands the leftmost remaining nonterminal symbol. In a context-free grammar, each parse tree specifies exactly one leftmost derivation. Two distinct leftmost derivations of the same word therefore prove that the context-free grammar is an ambiguous grammar.
Parser 2026-10-13
A parser recognizes how text fits a programming language syntax and can construct a parse tree or abstract syntax tree.
Past exam of the computer science course of the University of Oxford 2015 Compilers 1 b Solution 2026-10-31
Take the lexical tokens
ID, ASSIGN, SEMI, BEGIN, END, CASE, OF, COLON, and BAR, corresponding to identifiers and the displayed punctuation or keywords. Let E be the already defined context-free grammar category for a program expression, with attribute E.tree; expressions do not consume statement delimiters except inside their own explicitly delimited constructs. ID.name is the recognized program identifier. The following context-free grammar uses S for a statement, C for a closed elementary statement, D for a nonempty sequence of closed statements, and A for a nonempty arm list. The braces in this display are semantic actions, not input lexical tokens.S -> C { S.tree = C.tree }
S -> C SEMI S1 { S.tree = Seq(C.tree, S1.tree) }
S -> CASE E OF A { S.tree = Case(E.tree, A.arms) }
C -> ID ASSIGN E { C.tree = Assign(ID.name, E.tree) }
C -> BEGIN S END { C.tree = S.tree }
D -> C { D.tree = C.tree }
D -> C SEMI D1 { D.tree = Seq(C.tree, D1.tree) }
A -> E COLON S { A.arms = [(E.tree, S.tree)] }
A -> E COLON D BAR A1 { A.arms = [(E.tree, D.tree)] ++ A1.arms }Here
++ is list concatenation, and distinct suffixes distinguish occurrences of the same nonterminal symbol. Every statement and arm body is nonempty; no empty statement or optional trailing semicolon is needed for the supplied language.The distinction between
D and S resolves both possible sources of grammar ambiguity. First, an unbracketed CASE can occur only at the right end of an S: there is no production S -> S SEMI S. Consequently all semicolon-separated statements after such a CASE enter its last arm. Enclosing that whole CASE in BEGIN ... END turns it into a C, which can be followed by another statement outside the CASE.Second, an arm followed by another arm at the same level must have a
D body. Such a body contains no unbracketed CASE. If an arm body does contain an unbracketed CASE, only the final-arm production A -> E COLON S can apply, and every following BAR before the enclosing END or end of input must be consumed by the inner CASE. Thus each bar belongs to the nearest preceding CASE whose block has not ended. A CASE inside BEGIN ... END is hidden from that rule outside its block.For uniqueness, at any statement level an initial
ID or BEGIN determines a C; an immediately following SEMI determines the recursive sequence production. An initial CASE determines the third S production. In an arm, a bar at the current block level either follows an entirely closed body, forcing the second A production, or follows an unbracketed nested CASE, forcing it into that inner arm list. With an unambiguous expression sublanguage these choices leave a unique parse tree. Closed bodies before an outer bar, and a possibly open body only in the final arm, enforce the required interpretation. Thus the context-free grammar implementsThe word has these two leftmost derivations:In the first grammar derivation, supplies an extra ; the remaining goes directly to the empty word. In the second grammar derivation, is used, and the remaining uses before disappearing. Every step expands the leftmost nonterminal symbol, so these are genuinely different leftmost derivations, with different parse trees already distinguished by the production rule at the node.
A context-free grammar is an ambiguous grammar if some word in its generated formal language has two distinct parse trees. Equivalently, that word has two distinct leftmost derivations from the start nonterminal symbol. A leftmost derivation always expands the leftmost remaining nonterminal symbol.
Two arbitrary grammar derivations of the same word do not by themselves prove ambiguity: expanding independent nonterminal symbols in a different order can describe the same parse tree. Requiring distinct parse trees, or distinct leftmost derivations, avoids that issue.
Every generated word satisfieswhere count occurrences of the indicated terminal symbols. To see this, follow the unique chain of occurrences in a parse tree. Each use of introduces one from , at least one from its rightmost , and possibly one further from . Each use of adds one and no . The terminating contributes neither. Hence no generated word has more symbols than symbols.
Also, for every , the word is generated: apply exactly times, choose each time, then use and all remaining .
Suppose were a regular language, and let be a pumping length from the pumping lemma for regular languages. Apply it to . Every allowed decomposition with and has for some . Pumping twice giveswhich violates the proved counting inequality and hence is not generated. This contradicts the pumping lemma for regular languages. Therefore is not a regular language. Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 3 4H b Solution Created 2026-09-24 Updated 2026-10-03
Use the CYK algorithm. For a nonempty input word , let be the set of nonterminals that derive the substring . InitializeFor increasing substring lengths, computeAccept exactly when the start symbol belongs to . The proof is a mathematical induction on substring length: a one-letter derivation uses a terminal production, while every longer parse tree has a root production whose two subtrees yield two adjacent nonempty substrings. The recurrence considers every possible split point and therefore finds exactly all possible roots. For a fixed grammar the algorithm uses time. Under the strict form in part (a), it rejects immediately.
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 3 12F i Solution Created 2026-09-24 Updated 2026-09-25
A parse tree has the start variable at its root; the ordered children of a variable spell the right side of the production used at that occurrence, and its leaves, read left to right, spell the derived word.
For a grammar in Chomsky normal form with variables, take pumping length . A parse tree for a word of length at least has a root-to-leaf path containing one variable twice. The yield can therefore be writtenwhere , , and replacing the subtree between the repeated variables zero, one, or several times provesThis is the pumping lemma for context-free languages. Without Chomsky normal form but with no epsilon or unit productions, use the maximum production length to choose a larger exponential ; bounded branching and the same repeated-variable argument apply.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 1 4I b Solution Created 2026-09-24 Updated 2026-09-25
The length isIndeed, the parse tree has terminal-production nodes and, as a full binary tree with leaves, binary-production nodes. This is the Chomsky-normal-form derivation length.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 1 4I c Solution Created 2026-09-24 Updated 2026-10-03
One parse tree can be recorded unambiguously by the nested expressionEvery internal node uses one of the given productions, and the leaves read from left to right areEquivalently, the corresponding leftmost grammar derivation isHence the required word is generated by the grammar.
A context-free grammar with start symbol , terminal alphabet , and the following productions generates all binary palindromes:Each production preserves the palindrome property: it either supplies a central string of length zero or one, or wraps the same symbol around a shorter palindrome. This proves soundness by structural induction on the parse tree.
Conversely, any palindrome of length at least two has equal first and last symbols. Remove them to obtain a shorter palindrome, apply mathematical induction on length, and then use the corresponding wrapping production. The three base cases are , , and , proving completeness.
A context-free grammar is an ambiguous grammar if some terminal string has two distinct parse trees, equivalently two distinct leftmost derivations. Different orders of expanding independent nonterminals do not by themselves constitute ambiguity.
The context-free grammar just given is unambiguous. It suffices to prove this for the reversed productions, because reversing a parse tree preserves whether two parse trees are distinct.
For , the empty string forces the empty production. A nonempty string must use . In any resulting nonnegative balanced path, the displayed one is the unique first return to zero. It therefore uniquely determines the two shorter substrings generated by . Mathematical induction on length makes both smaller parse trees unique.
For , the empty string again forces the empty production. A nonempty path with no return to zero must use , since always returns to zero. A path with a return must use , since stays positive after its first step. In the latter case, the first return uniquely determines the substring and the remaining substring. Applying mathematical induction to these shorter substrings proves uniqueness throughout. Hence
Suffix-nonnegative binary language 2026-10-31
A context-free language recognized by scanning a string over the alphabet from right to left, counting 0 as and 1 as , and requiring every partial count to remain nonnegative. A context-free grammar with a unique parse tree for each generated string is , . To see uniqueness, reverse the strings: every nonempty nonnegative path either never returns to zero after its first step, or has a unique first return. These two cases determine the production and its component substrings.