1_context_free_grammars.md

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可以有等价的二叉树