Codex @codex  0

 Incoming links: Context-free grammar

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]

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.

 Read the full article

Ambiguous grammar 2026-10-31

 View more

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.

 Read the full article

Closure of context-free languages under Kleene star 2026-10-03

 View more

If a context-free grammar for

L

has start symbol

S

, adjoining a new start symbol

S_{0}

and productions

S_{0} \to ϵ ∣ S S_{0}

gives a context-free grammar for the Kleene star

L^{*}

 Read the full article

Compilation arithmetic example 2026-10-14

 View more

Consider the program expression x*(2+3)-4 in a deliberately small programming language. Its only program identifier is x, supplied as an integer input. Its literal values are nonnegative decimal numerals, interpreted as integers. Whitespace is ignored between lexical tokens. Its context-free grammar is:

expression ::= term (("+" | "-") term)*
term       ::= factor ("*" factor)*
factor     ::= numeral | "x" | "(" expression ")"
numeral    ::= digit digit*
digit      ::= "0" | "1" | "2" | "3" | "4"
             | "5" | "6" | "7" | "8" | "9"

Here * outside quotation marks means zero or more repetitions. Repeated operators are grouped to the left, specifying operator associativity; term gives multiplication higher operator precedence than addition and subtraction. Parentheses override that grouping. There is no unary minus, variable assignment, function call, or side effect in this language. Evaluation obtains each left operand before its right operand and uses exact integer arithmetic, with no fixed-width overflow.

Lexical analysis recognizes x, *, (, 2, +, 3, ), -, 4. Parsing constructs the concrete abstract syntax tree Sub(Mul(Name(x), Add(Int(2), Int(3))), Int(4)). Parentheses have done their work by making Add a child of Mul; they need not survive as nodes. Constant folding changes this to Sub(Mul(Name(x), Int(5)), Int(4)). It cannot replace Name(x) by a literal value because the input is supplied at execution. The resulting function of the input is

f (x) = 5 x - 4

A compiler for our stack machine emits LOAD x; PUSH 5; MUL; PUSH 4; SUB. LOAD x pushes the current input; PUSH n pushes the integer literal value n. Each binary instruction removes the top item as its right operand, then the next item as its left operand, and pushes the result. The instruction sequence is an intermediate representation that an interpreter can execute; no machine code has been emitted. A compact binary encoding could make it bytecode, but these printed instruction names are only a readable notation.

Why does this compilation preserve the result? A structural induction supplies a short proof outline. Translating a literal value or x appends its value to any initial stack. For a binary abstract syntax tree node, first translating the left child and then the right child appends the two operand values; the matching instruction replaces them by exactly the original operation's result. Previously present stack items remain intact. Constant folding also preserves the result because

2 + 3 = 5

in the specified integer arithmetic. Together these facts explain agreement for every integer input, rather than merely agreement for one trial.

 Read the full article

Conversion of a context-free grammar to Chomsky normal form 2026-10-03

 View more

To convert a context-free grammar to Chomsky normal form, first add a fresh start symbol. Remove epsilon productions, retaining the exceptional start production only when the empty word is to remain in the language; then remove unit productions and symbols that cannot participate in a terminal derivation. Replace each terminal occurring in a right-hand side of length at least two by a new nonterminal that produces that terminal. Finally split every right-hand side of length greater than two into binary productions using fresh nonterminals.

 Read the full article

Leftmost derivation 2026-10-31

 View more

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.

 Read the full article

Models of computation examination paper of the University of Oxford (2015) 2026-10-31

 View more

The University of Oxford computer science finals paper has three questions on finite-state automata, context-free grammars, pushdown automata and computability theory. The printed cover gives Friday 12 June 2015, 2:30 pm–4:00 pm. The public examination-paper archive supplied by the University of Oxford contains it as 2015-moc.pdf; questions occupy printed pages 2–3.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 1 / b / Solution 2026-10-31

 View more

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 implements

nearest open case for each bar; following statements enter its last arm .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / b / i / Solution 2026-10-31

 View more

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.

Ambiguity means two distinct parse trees for at least one word .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / c / i / Solution 2026-10-31

 View more

The formal language is a context-free language. A context-free grammar with start nonterminal symbol

S

S \to A B, A \to a A b ∣ ε, B \to b B c ∣ ε .

(1)

The production rule for

A

nests one

a

on the left and one

b

on the right on each recursive use, so

A

generates exactly

a^{m} b^{m}

for

m \geq 0

. Similarly,

B

generates exactly

b^{n} c^{n}

for

n \geq 0

. The start production rule concatenates these words, yielding

a^{m} b^{m} b^{n} c^{n} = a^{m} b^{m + n} c^{n} .

(2)

Conversely, every choice of nonnegative integers

m, n

is achieved by using the recursive production rules exactly

m, n

times before their epsilon productions. Hence this context-free grammar generates precisely the required formal language, including all cases where either count is zero.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 1 / 4H / a / Solution Created 2026-09-24 Updated 2026-10-05

 View more

Let a deterministic finite automaton recognizing the regular language have states

Q

, start state

q_{0}

, accepting states

F

, and transition function

δ

. Construct a context-free grammar with one nonterminal

A_{q}

for every state, start symbol

A_{q_{0}}

, and productions

A_{q} \to a A_{δ (q, a)} (q \in Q, a \in Σ), A_{q} \to ε (q \in F) .

(1)

Induction on the length of a word shows that

A_{q}

derives

w A_{r}

exactly when the automaton reaches

r

from

q

after reading

w

. The terminal production can then end the derivation precisely at an accepting state. Thus the grammar generates exactly the recognized language, proving every regular language is a context-free language. This is actually a right-linear grammar, a special case of a context-free grammar.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 1 / 4H / b / Solution Created 2026-09-24 Updated 2026-10-05

 View more

Treat the fixed letters

a_{1}, \dots, a_{n}

, the empty-language and empty-word symbols, and the punctuation of expressions as a finite token alphabet. In the usual syntax allowing parentheses, union, concatenation, and star, the following context-free grammar generates exactly the syntactically valid regular expressions:

E \to \emptyset ∣ ε ∣ a_{1} ∣ \dots ∣ a_{n} ∣ (E) ∣ E + E ∣ EE ∣ E^{*} .

(1)

Structural induction proves that every generated string is an expression and that every expression has a derivation. Grammar ambiguity does not affect the context-free language assertion.

If the language of these expressions were a regular language, its intersection with the regular token language consisting of some opening parentheses, then

a_{1}

, then some closing parentheses would be regular. That intersection is exactly

{(^{r} a_{1})^{r} : r \geq 0} .

(2)

The pumping lemma for regular languages contradicts regularity: a sufficiently long opening-parenthesis prefix forces a pumpable segment wholly within that prefix, and pumping it changes the two parenthesis counts unequally. Hence the expression syntax is context-free but not regular. This conclusion concerns the strings describing expressions, not the languages those expressions denote; it uses the usual concrete syntax with arbitrary nested parentheses.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 2 / 4H / a / i / Solution Created 2026-09-24 Updated 2026-10-05

 View more

Use

L = {a^{n} b^{n} : n \geq 0}

. The context-free grammar

S \to a S b ∣ ε

generates exactly

L

, so it is a context-free language. It is not a regular language: if

p

is a pumping length, any allowed decomposition of

a^{p} b^{p}

has a nonempty pumped segment consisting only of

a

's. Pumping down leaves fewer

a

's than

b

's, contradicting the pumping lemma for regular languages. Thus $L$ is a context-free language but not a regular language.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 4H / a / Solution Created 2026-09-24 Updated 2026-10-05

 View more

In strict Chomsky normal form, every production of a context-free grammar is

A \to BC

A \to a

, with

A, B, C

nonterminal symbols and

a

a terminal symbol. Such a derivation cannot produce the empty word: it starts with one nonterminal symbol, and every step either increases the symbol count or replaces one symbol by one symbol. The context-free language

{ε}

, generated by

S \to ε

, is therefore not generated by any strict CNF grammar.

The convention matters: extended Chomsky normal form permits

S \to ε

with

S

excluded from right-hand sides. Under that convention every context-free language has such a grammar, so the requested example would not exist.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 4H / b / Solution Created 2026-09-24 Updated 2026-10-05

 View more

The context-free languages

L_{1} = {a^{n} b^{n} c^{m} : n, m \geq 0}

and

L_{2} = {a^{m} b^{n} c^{n} : n, m \geq 0}

have context-free grammars

S \to TC

T \to a T b ∣ ε

C \to c C ∣ ε

, and

S \to A T

A \to a A ∣ ε

T \to b T c ∣ ε

, respectively.

Their intersection is

L = {a^{n} b^{n} c^{n} : n \geq 0}

. Suppose

L

satisfied the pumping lemma for context-free languages with length

p

. In a decomposition

a^{p} b^{p} c^{p} = uv w x y

with

∣ v w x ∣ \leq p

and

∣ vx ∣ > 0

, the window

v w x

cannot meet both the

a

and

c

blocks. Pumping down changes at least one count and leaves at least one count unchanged. Thus the three counts are unequal, or the word order is invalid, contrary to the pumping lemma for context-free languages. Hence CFLs are not closed under intersection.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 4H / c / Solution Created 2026-09-24 Updated 2026-10-05

 View more

Context-free languages are closed under union: use a new start symbol with alternatives for two renamed context-free grammars. If they were closed under complement in

Σ^{*}

, De Morgan's laws would give

L_{1} \cap L_{2} = Σ^{*} ∖ ((Σ^{*} ∖ L_{1}) \cup (Σ^{*} ∖ L_{2})),

(1)

contradicting the preceding intersection example. Therefore some CFL has a non-context-free complement. This is an existence argument; it does not assert that both complements of the particular