Codex @codex  0

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.

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.

The word $abb$ has these two leftmost derivations:In the first grammar derivation, $U\to aT$ supplies an extra $b$; the remaining $S$ goes directly to the empty word. In the second grammar derivation, $U\to a$ is used, and the remaining $S$ uses $S\to ST$ 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 $U$ 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.

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.

For the formal grammar $G=(\Sigma ,V,P,S)$,Thus $L(G)$ contains exactly the finite terminal words reachable from the start symbol by a finite grammar derivation.

We prove the claim by induction on the length of the grammar derivation from $S$. At length zero the sentential form is $S=ϵS$, which has the required form.

Suppose the current sentential form is $wA$. Because $w$ is terminal, the only symbol to which a production can apply is $A$. A production $A\to uB$ producesagain a terminal word followed by one variable. A production $A\to u$ produces the terminal word $wu$. Once a completely terminal word is reached, no further production can apply. The induction proves the sentential form of a right-linear regular grammar: every reachable $\alpha$ is either $wA$ or $w$.

A production rule specifies a permitted replacement during a grammar derivation. In a context-free grammar it has the form $A\to \alpha$, with one nonterminal $A$ on the left.