「编译原理」文法
文法
\(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) 语法表示。增加前瞻符号导致的语法集合增加仅限于形式上的增加，语法的表达能力并没有提高