2.1 Context-Free Grammars

定义2.2（CFG）

A context-free grammar is a 4-tuple $(V,\Sigma,R,S)$, where

1. $V$ is a finite set called the variables,
2. $\Sigma$ is a finite set, disjoint from $V$, called the terminals,
3. $R$ is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
4. $S\in V$ is the start variable

记号

• 单步推导（yield）$uAv\Rightarrow uwv$
• 任意步推导（derive）$u\Rightarrow^*v$. 并产生一棵parse tree

定义（CFL）

A launguage is called a context-free launguage if it can be generated by a CFG.

CFL=L(CFG)

如何设计CFG

合并、正则、匹配、递归

{CFLs}对$\cup$封闭

是一个创作过程

定义2.7（ambiguously）

A string $w$ is derived ambiguously in CFG $G$ if it has two or more different leftmost derivations.

Grammar $G$ is ambiguous if it derives some string ambiguously.

固有歧义性：有些context-free language只能被ambiguous CFG产生，比如$\{a^ib^jc^k|i=j$ or $j=k\}$

定义2.8（Chomsky normal form）

A context-free grammar is in Chomsky normal form if every rule is of the form

​ $A\rightarrow BC$

​ $A\rightarrow a$

其中$a$是terminal，$A,B,C$是variables，$B,C$不是start variable

定理（Chomsky normal form的普适性）

Any context-free language is generated by a CFG in Chomsky normal form.

证明方法：构造法，提供了一套把任意CFG改写成等价Chomsky normal form的流程。

这样理解：Parse tree可以有等价的二叉树