Context-free languages and parsing theory

Vocabulaire

English	Sens
derivation	A sequence of production-rule applications that generates a string from a grammar.
parse tree	A tree recording how grammar productions generate the structure of a string.
ambiguity/ˌæmbɪˈɡjuːɪti/	The existence of more than one parse tree for a string under a given grammar.

English

Grammars that nest

Context-free grammars rewrite nonterminals: $E \to E + T \mid T$, $T \to T \times F \mid F$, $F \to (E) \mid \mathbf{id}$. A derivation expands; a parse tree records the expansion.

{exercise:uni-cs1102-cfg}

Pratique

In the layered grammar, id + id * id has — parse tree(s)

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

With the layered grammar, id + id * id has ONE parse tree: × binds under T, deeper than +. The unlayered $E \to E + E \mid E \times E \mid \mathbf{id}$ gives TWO trees for the same string — ambiguity is cured by grammar design.
The leftmost derivation of id + id * id: $E \Rightarrow E + T \Rightarrow T + T \Rightarrow \mathbf{id} + T \Rightarrow \mathbf{id} + T \times F \Rightarrow \mathbf{id} + \mathbf{id} \times F \Rightarrow \mathbf{id} + \mathbf{id} \times \mathbf{id}$ — six steps, suite-checked.

{exercise:uni-cs1102-ambiguity}

Pratique

The leftmost derivation of id + id * id takes — steps

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

$\{a^n b^n c^n\}$ needs two independent counts: CFGs pump one, so a context-sensitive machine is required — the Chomsky hierarchy's next floor, and the reason type checkers live above parsers.
Confusing derivation order (leftmost/rightmost) with tree shape is the classic trap: the string itself must pick the tree.

{exercise:uni-cs1102-ceiling}

Pratique

The language a^n b^n c^n requires —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui