第2章 上下文无关文法
2.1 概述
一个文法有一组替换规则组成，替换规则又称为产生式。如下G:
\[A \rightarrow 0A1
\]
\[A \rightarrow B
\]
\[A \rightarrow \#
\]
也可写为
\[A\rightarrow 0A1|B| \#
\]
第一条规则的左边的变元称为起始变元
（符号称为变元如A，B。终止符如01#即小写字母、数字或特殊符号表示）
如用文法G生成000#111字符串。获取字符串的替换序列称为派生，即：
\[A\rightarrow 0A1\rightarrow 00A00\rightarrow 000A000 \rightarrow 000\#111
\]
也可用语法分析树描述这一派生过程
上述方式生成的所有字符串称为该文法的语言，用\(L(G_1)表示\)，可知该文法\(L(G) = \left\{0^n\# 1^n | n\ge 0 \right\}\), 称为上下文无关语言(CFL)
\(———————————————————————————————\)
\[G_2 = (\left\{S \right\}, \left\{a, b \right\}, R, S)
\]
其中规则集R：
\[S\rightarrow aSb|\ SS| \varepsilon
\]
S是起始变元
上述方式就是上下文无关文法(CFA)的形式化定义
由CFL构造CFG