Context-free languages and parsing theory
Introducido
Vocabulario
| English | Significado |
|---|---|
| derivation | derivation |
| parse tree | parse tree |
| ambiguity/ˌæmbɪˈɡjuːɪti/ | ambiguity |
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}
Práctica
In the layered grammar, id + id * id has — parse tree(s)
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Layering enforces precedence: x binds under T, deeper than +.
English
Ambiguity and precedence
- With the layered grammar,
id + id * idhas 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}
Práctica
The leftmost derivation of id + id * id takes — steps
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
E, E+T, T+T, id+T, id+TF, id+idF, id+id*id - six.
English
The next ceiling
- $\{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}
Práctica
The language a^n b^n c^n requires —
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Two independent counts: CFGs pump one, not both.