Context-free languages and parsing theory

Từ vựng

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}

Luyện tập

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

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay

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}

Luyện tập

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

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay

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}

Luyện tập

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

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay