『compiler-1』grammar
文法和语言
一、字母表与字符串
字母表：符号的非空有限集合，记作 \(\Sigma\)
符号：字母表\(\Sigma\)中的元素
符号串：符号的有穷序列，设字母表为\(\Sigma\)
- \(\epsilon\) 是\(\Sigma\)上的符号串（归纳基础）
- 若 x 是\(\Sigma\)上的符号串，且a \(\in \Sigma\)，则 ax 或 xa 是\(\Sigma\)上的符号串
- y 是\(\Sigma\)上的符号串 \(\Leftrightarrow\) y 可由规则 a 或规则 b 产生
符号串的运算：设 x 和 y 是字母表\(\Sigma\)上的符号串
- 符号串相等：字符串 x = y \(\Leftrightarrow\) 组成x的每个符号和组成y的每个符号依次相等
- 符号串长度：字符串 x 的长度 |x| 为该符号串中符号的个数
- 符号串的连接：符号串 x 和 y的连接 xy 也是\(\Sigma\)上的符号串
注意：一般 xy \(\ne\) yx，但是 \(\epsilon x\) = \(x\epsilon\)
符号串集合的乘积运算：设 A 和 B 是符号串集合，则 AB = \(\{\text{xy } | \text{ x} \in A, \text{ y} \in B\}\)
注意：符号串集合的乘积本质上也是符号串的连接运算；\(\{\epsilon\}\text{A}\) = \(\text{A} \{\epsilon\}\)，\(\varnothing \text{A}\) = \(\text{A}\varnothing\) = \(\varnothing\)符号集合的幂运算：成绩运算的推广；设 A 是符号串集合，则有：
- \(\text{A}^0\) = \(\{\epsilon\}\)
- \(\text{A}^1\) = \(\text{A}\), \(\text{A}^2\) = \(\text{A}\text{A}\), ...
- \(\text{A}^n\) = \(\text{A}^{n-1} * \text{A}\) = \(\text{A} * \text{A}^{n-1}\) (n > 0)
符号集合的闭包运算：分为正闭包和闭包，设 A 是符号串集合
- 正闭包：\(\text{A}^+\) = \(\text{A}^1\) \(\cup\) \(\text{A}^2\) \(\cup\) \(\text{A}^3\) \(\cup\) ... \(\cup\) \(\text{A}^n\) \(\cup\) ... ，\(\text{A}^+ = \text{AA}^*\)
- 闭包（Kleene闭包）：\(\text{A}^*\) = \(\text{A}^0\) \(\cup\) \(\text{A}^+\)（即正闭包中多了个\(\text{A}_0\)）
二、文法和语言的形式定义
文法的定义：文法G[Z] = \(\{\text{V}_n, \text{V}_t, \text{P}, \text{Z}\)\(\}\)，其中：
- \(\text{V}_n\)：非终结符号集合
- \(\text{V}_t\)：终结符号集合
- \(\text{P}\)：产生式或规则的集合
- \(\text{Z}\)：开始符号，$ $\(\text{V}_n\)
规则：一个有序对 (U, x)，记作 \(\text{U} \rightarrow \text{x}\)，其中 \(\text{U} \in \text{V}_n\), \(\text{x} \in \text{V}^*\)，| U | = 1，| x | \(\ge\) 0
注意：\(\text{V}\) = \(\text{V}_n\) \(\cup\) \(\text{V}_t\)；规则的左侧必须是非终结符，右侧是终结符或非终结符组成的串文法的 BNF 表示：
- 使用 ::= 表示“定义为”，使用 <> 把“非终结符号”括起来，
- 将拥有相同左部的产生式体用“或运算符 |”连接在一起
推导的定义：设 v = xUy，w = xuy，其中 x、y \(\in\) \(\text{V}^*\)，U \(\in\) \(\text{V}_n\)，u \(\in\) \(\text{V}^*\) 若 U \(\rightarrow\) u，则 v \(\overset{G}{\Rightarrow}\) w，即将推导式的左侧非终结符替换为右侧符号串
- 最左推导：每次优先替换掉符号串中最左侧的非终结符
- 最右推导：每次优先替换掉符号串中最右侧的非终结符
注意：最右推导又叫规范推导，用带斜划线的右箭头表示
多步推导：设文法\(\text{G}\)，\(\text{u}_0\)，\(\text{u}_1\)，...，\(\text{u}_n\) \(\in\) \(\text{V}^+\)
- 若 \(\text{v} = \text{u}_0 \underset{G}{\Rightarrow}... \underset{G}{\Rightarrow} \text{u}_n = \text{w}\)，则记\(\text{v} \underset{G}{\overset{+}{\Rightarrow}} w\)（间接推导，至少1步推导）
- 若 \(\text{v} \overset{+}{\Rightarrow} \text{w}\) 或 \(\text{v} = \text{w}\)，则 \(\text{v} \underset{G}{\overset{+}{\Rightarrow}} \text{w}\)（任意步推导，可以是0步）
注意：当符号串中没有非终结符号时，推导就必须终止，因为只有规则左侧才有非终结符
语言的定义：设文法为 G[Z]
- 句型：设 \(\text{x}\) 是句型，则 \(\text{Z} \overset{*}{\Rightarrow} \text{x}\)，且 \(\text{x} \in \text{V}^*\)（即推导过程中的任意结果）
- 句子：设 \(\text{x}\) 是句子，则 \(\text{Z} \overset{+}{\Rightarrow} \text{x}\)，且 \(\text{x} \in \text{V}_t^*\)（即仅由终结符构成的符号串）
- 语言：\(\text{L(G[Z])}\) = \(\{\text{x } | \text{ x} \in \text{V}_t^*, \text{ Z} \overset{+}{\Rightarrow} \text{x}\}\)，即文法中句子的集合
注意：已知文法G，可以确定唯一的语言L；已知语言L，可能构造出多种文法\(\text{G}_i\)
三、文法构造
等价文法：设 G 和 G' 是两个不同的文法，若L(G) = L(G')，则称 G 和 G' 是等价文法
递归规则：即规则右部有与左部相同的非终结符号；设 \(\text{U} \rightarrow \text{xUy}\)
- 若 x = \(\epsilon\)，即 \(\text{U} \rightarrow \text{Uy}\)，则称左递归
- 若 y = \(\epsilon\)，即 \(\text{U} \rightarrow \text{xU}\)，则称右递归
- 若 x, y \(\ne \epsilon\)，则称自嵌入递归
递归文法：设文法G中存在非终结符 \(\text{U} \in \text{V}_n\)：
- 若 \(\text{U} \overset{+}{\Rightarrow} \dots \text{U} \dots\)，则称G为递归文法
- 若 \(\text{U} \overset{+}{\Rightarrow} \text{U}\dots\)，则称G为左递归文法
- 若 \(\text{U} \overset{+}{\Rightarrow} \dots \text{U}\)，则称G为右递归文法
注意：递归文法可以通过有穷条规则，定义无穷语言；但左递归文法不能使用自顶向下的方法语法分析
如何构造一个文法：先从最简单的句子出发做扩展
- 重复生成：从每一步扩展的句子中找出上一步重复出现的符号串，构造递归定义（如 \(\text{A} \rightarrow \text{a | Aa}\)）
- 对称生成：若某一步扩展得到的句子是回文的，则在其左右两侧增加相同的符号得到的句子也是回文的
四、短语和句柄
短语和简单短语：设文法G[Z]，w = xuy \(\in\) \(\text{V}^+\)是该文法的句型，\(\text{x, y} \in \text{V*}\)
- 短语：若 \(\text{Z} \overset{*}{\Rightarrow} \text{xUy}\)，且 \(\text{U} \overset{+}{\Rightarrow} \text{u}\)，则u是相对于U的句型w的短语（任何句型都是相对于Z的短语）
- 简单短语：若 \(\text{Z} \overset{*}{\Rightarrow} \text{xUy}\)，且 \(\text{U} \Rightarrow \text{u}\)，则u是相对于U的句型w的简单短语（必须存在一步推导）
注意： “短语一定是某个句型的部分或全部”，且是可由某个非终结符推导得到的符号串
句柄：任意句型的位于最左边的简单短语称为该句型的句柄；一个句型只能有一个句柄
- 如何查找某句型的句柄？先找出该句型所有的简单短语，再选出最左边的
五、语法树
语法树（推导树）：句子 or 句型的图表示
- 结点：表示符号；其中根节点是开始符号、中间节点是非终结符、叶节点是终结符或非终结符
- 有向边：表示结点之间的推导派生关系
语法树的生成（自顶向下）：设文法为G[Z]，句型为w
- 建立推导序列，\(\text{Z} \overset{*}{\Rightarrow} \text{w}\)
- 根据序列建立语法树：以Z为根节点，每步推导生成一个枝
“枝”是一组线连同线下面的若干结点，各结点取代该分支名称的符号串
注意：无论使用哪种推导方式，建立的语法树形状都是相同的（无二义性），但生长次序不同
子树与短语的关系：短语必由某个祖先节点推导；简单短语必由某个祖先节点直接推导
注意：这个定理说明可通过语法树的方式求出任意句型的短语、简单短语以及句柄规约：自下而上地剪掉子树的末端节点（即短语），每剪一次对应一次规约
规范规约与规范推导：互为逆过程
- 规范规约：每次剪掉当前句型中的句柄
- 规范推导：每次优先替换当前句型中最右侧的非终结符号
- 规范句型：通过规范规约或规范推导得到的句型
二义性文法：对于文法中的某一句子（或句型），存在两棵不同的语法树，则是二义性文法
- 若文法的一个句子存在两个不同的规范推导，则该文法是二义性的（会产生不同的语法树）
- 若文法中某些规范句型的句柄不唯一，则该文法是二义性的（不同语法树的句柄不一定相同）
注意：无二义性文法的句子可以有不同的推导过程，但只有一棵语法树；文法的二义性不可判定
有害规则：文法中存在形如 \(\text{U} \rightarrow \text{U}\) 的规则，会在推导时产生各种高度的语法树（二义性）
多余规则：包括不可达符号 + 不活动符号
不可达：始终用不到的规则，即该规则左侧的非终结符不出现在任何句型中（到不了）
不活动：含有推不出任何句子的非终结符（用不了）
被压缩的文法：不含有害规则和多余规则的文法
形式语言：用文法和自动机描述的没有语义的语言
文法定义：即文法的四元组，由乔姆斯基定义；语言即文法中所有句子组成的集合
文法和语言的分类：3型 \(\subseteq\) 2型 \(\subseteq\) 1型 \(\subseteq\) 0型
- 0型：\(\text{P: } \text{u} \rightarrow
\text{v}\)，其中\(\text{u} \in
\text{V}^+\)（| u | \(\ge\) 1），\(\text{v} \in \text{V}^*\)
0型文法又称短语结构文法，其规则的左右两侧都可以是符号串
0型语言可由图灵机接受 - 1型：\(\text{P: } \text{xUy} \rightarrow
\text{xuy}\)，其中\(\text{U} \in
\text{V}_n\)，\(\text{x, y, u} \in
\text{V}^*\)
1型文法是上下文有关的，即只有在前x后y的上下文中才能把U改写为u
1型文法可被线性界限自动机接受 - 2型：\(\text{P: U} \rightarrow
\text{u}\)，其中\(\text{U} \in
\text{V}_n\)，\(\text{u} \in
\text{V}^*\)，即将U改写为u时不必考虑上下文
2型文法与BNF表示等价；1型文法中 \(\text{x = y} = \epsilon\) 即为 2型文法
2型文法可由下推自动机接受（总控程序 + 分析表 + 读写头 + 栈，可以保存状态） - 3型：\(\text{P: U} \rightarrow \text{t |
}\text{Wt}\) （左线性）或 \(\text{P: U}
\rightarrow \text{t | tW}\)（右线性），其中 \(\text{U, W} \in \text{V}_n\)，\(\text{t} \in \text{V}_t\)
3型文法又称正则文法，即为2型文法的进一步限制
3型语言可由有穷自动机接受（总控程序 + 分析表 + 读写头，无法保存状态）
注意：0型文法可以产生 \(\text{L}_0\) ~ \(\text{L}_3\)；2型文法只能产生\(\text{L}_2\)；3型文法只能产生\(\text{L}_3\)
1型文法比0型文法指定了上下文约束；2型文法要求上下文必须是 \(\epsilon\)；3型文法约束了产生式必须是线性的- 0型：\(\text{P: } \text{u} \rightarrow
\text{v}\)，其中\(\text{u} \in
\text{V}^+\)（| u | \(\ge\) 1），\(\text{v} \in \text{V}^*\)
六、句子的分析
自顶向下分析：从待识别的符号串 \(\text{s} \in \text{V}_t^*\) 开始，根据规则建立推导序列，使得\(\text{Z} \overset{+}{\Rightarrow} \text{s}\)，则符号串s得到了识别
s是文法G的合法句子 \(\Leftrightarrow\) 语法树的末端节点从左到右连接起来构成s
注意：推导句子前应先找出文法中唯一出现的终结符号自底向上分析：从符号串 \(\text{s} \in \text{V}_t^*\) 开始将 s 规约为开始符Z；每次规约总会规约当前句型的句柄
注意：自顶向下一般采用最左推导；自底向上一般找当前句型的句柄