文法
$G=(V_n, V_t, P, Z)$
- $G$ 文法
- $V_n$ 非终结符号集
- $V_t$ 终结符号集
- $P$ 产生式或规则的集合
- $Z$ 开始符号（识别符号）
- $V$ 词汇表，$V=V_n\cup V_t$
规则是一个有序对，通常写为 $U\rightarrow x$，其中 $U\in V_n,x\in V^{*}$
| 类别 | 定义 | 分析器 | 特点 |
|---|---|---|---|
| 0 型文法 | $P:u\rightarrow v$ 其中 $u\in V^{+},v\in V^{*}$ | 图灵机 | 短语结构文法。规则的左部和右部都可以是符号串,一个短语可以产生另一个短语。需要能够随意访问上下文 |
| 1 型文法 | $P:xUy\rightarrow xuy$ 其中 $U\in V_n,x,y,u\in V^{*}$ | 线性界限自动机 | 上下文敏感或上下文有关。只有在 $x, y$ 这样的上下文中才能把 $U$ 改写为$u$ |
| 2 型文法 | $P:U\rightarrow u$ 其中 $u\in V_n,u\in V^{*}$ | 下推自动机 | 上下文无关文法。即把 $U$ 改写为 $u$ 时,不必考虑上下文 |
| 3 型文法 | $P:U\rightarrow t$ 或者 $U\rightarrow Wt$ 其中 $U,W\in V_n,t\in V_t$ | 有限自动机 | 正则文法。它是对 2 型文法进行进一步限制，左线性或者右线性 |
- 图灵机：随便看随便存
- 线性界限自动机：能看到的位置是当前位置的线性函数
- 下推自动机：使用了包含数据的栈的有限自动机
- 有限自动机：略
文法之间有包含关系，即 $3\subset 2\subset 1\subset 0$，判断的时候反向操作
一般使用 2 型以上文法
一个有穷语言，一定是正则语言
短语，简单短语和句柄
刚开始接触到这些概念的时候极其懵逼，形式化表示很难在脑海里留下印象。
事实上学完语法树再回来感性理解还是挺简单的
- 短语：对文法 $G[Z]$，句型 $w=xuy$，若有 $Z\stackrel{*}{\rightarrow}xUy$（推导），并且有 $U \stackrel{+}{\rightarrow}u$（至少一步推导），那么 $u$ 是（相对于非终结符号 $U$ 的句型 $w$ 的）短语
- 体现在语法树上，任意一棵非叶子树的根节点就是 $U$，叶子节点从左到右的组合就是 $u$，短语实则是某个非终结符号（事实上是句型中的“伪终结符”）的推导结果
- 简单短语（直接短语）：在短语的基础上，若 $U{\rightarrow}u$（直接推导），则 $u$ 是（相对于非终结符号 $U$ 的句型 $w$ 的）简单短语
- 语法树上除了短语的要求之外，还要保证子树的深度是 $2$（只有根和叶子节点），从而满足直接推导的要求
- 句柄：任一句型的最左简单短语称之为句柄
- 按照定义在语法树上找
Q&A
增加的一个前瞻符号，使 LR(2) 语法分析器比 LR(1) 语法分析系统所能识别的语法集合更大。但几近于矛盾的是，增加的前瞻符号并不能增大这种语法分析器可以识别的语言集合。对 k>1, LR(1)语法分析器与 LR(k) 语法分析器接受的语言集合是相同的。同一种语言的 LR(1) 语法可能比 LR(k) 语法更复杂（《编译器设计》P94）
- 意味着能被 LR(k) 语法分析器接受的语言必定能被 LR(1) 语法分析器接受？
- 根据老师的意思，若一种语言可以用 LR(k) 语法表示，那么也必定可以用 LR(1) 语法表示。增加前瞻符号导致的语法集合增加仅限于形式上的增加，语法的表达能力并没有提高