尹剑飞 科技楼1406 yjfbase@yahoo.com.cn 13424410028 编译原理 尹剑飞 科技楼1406 yjfbase@yahoo.com.cn 13424410028

编译原理和技术的重要性 设计和开发编译器的原理和技术将会在一个计算机工作者的职业生涯中被多次使用。--- << Compilers: Principles, Techniques, and Tools>> 编译器的构造综合了计算机科学的各个方面：计算机理论、程序设计、软件工程，是理论应用于实践的成功典范。--<< Engineering A Compiler>>

编译原理和技术的重要性 自计算机科学诞生以来，语言处理器的工程化就一直在推动，随着相关理论的开发不断改进。-- <<Programming Language Processors in Java - COMPILERS AND INTERPRETERS >> 相对其它技术而言，编译器技术是一种内功修炼，因为任何计算机问题都可以化为语言翻译问题 -- some one

第一章 编译器介绍 1.1 编译器概貌 1.2 源程序分析 1.3 编译器的阶段 1.4 编译器的同胞 1.5 阶段的组合 1.6 编译器构造工具

1.1.1 编译器IO 编译器 （程序） 源程序 目标程序 错误信息 1.1 编译器概貌 第一个编译器出现于1950年 第一个Fortran编译器花了18人年 通过工具支持，基本的编译器可作为学生项目，在一个学期内完成。

1.1.2 编译过程分为两个基本部分 分析 ( Analysis ) 综合 ( Synthesis ) 中间表示 目标程序 源程序 语法树 1.1 编译器概貌 1.1.2 编译过程分为两个基本部分 分析 ( Analysis ) 综合 ( Synthesis ) 中间表示 综合 分析 目标程序 源程序 语法树

position = initial + rate * 60 1.1 编译器概貌 1.1.3 语法树例子 = position + initial * rate 60 position = initial + rate * 60

很多软件（不一定是编译器）执行类似的“分析” 1.1 编译器概貌 很多软件（不一定是编译器）执行类似的“分析” 结构编辑器，如：HTML editor 格式化（美化）打印，如：自动排版系统 静态检查，如：语法检查器 解释器，如：表达式计算器，SQL检查解释器，java …

程序的执行 是怎样炼成的？ a.h,b.h, ..,C.cpp 库可重定位的 可重定位的 机器码 机器码 预处理 D.cpp 1.1 编译器概貌 a.h,b.h, ..,C.cpp 库可重定位的 机器码 可重定位的 机器码 汇编器 预处理 程序的执行 是怎样炼成的？ D.cpp 装载和联接编辑器 编译器 绝对机器码 E.asm 操作系统

1.2 源程序 “分析” 分析包括三个阶段 词法分析（线性分析）：字符->词（Token） 语法分析（层次分析）：词->句 语义分析：句->正确（有意义）的句子

标识符：position, initial, rate 赋值运算符：= 加法运算符：+ 乘法运算符：* 数：60 1.2 源程序 “分析” 1.2.1 词法分析 （线性分析） 输入字符串：‘p’ ‘o’ ‘s’ ‘i’ ‘t’ ‘i’ ‘o’ ‘n’ ‘ ‘ ‘=‘ ‘ ‘ ‘ ‘ ‘i’ ‘n’ ‘i’ ‘t’ ‘i’ ‘a’ ‘l’ ‘ ‘ ‘+’ ‘r’ ‘a’ ‘t’ ‘e’ ‘*’ ‘6’ ‘0’，得到下述词(Token): 标识符：position, initial, rate 赋值运算符：= 加法运算符：+ 乘法运算符：* 数：60 空格？

1.2.2 语法分析 （层次分析） * 与1.1.3不同的语法树 1.2 源程序 “分析” 标识符 | => <标识符, rate> rate position = initial + rate * 60 的语法树 赋值语句 = 表达式 标识符 + 表达式 表达式 position 表达式 * 表达式 标识符 与1.1.3不同的语法树 标识符 数 initial rate 60

规则3：<表达式1> + <表达式2> 规则4：<表达式1> * <表达式2> 1.2 源程序 “分析” 1.2.2 语法分析 （层次分析） 程序的层次结构通常由递归规则定义： 规则1：任何<标识符>是<表达式> 规则2：任何<数>是<表达式> 给定<表达式1>和<表达式2>，则下述也是表达式 规则3：<表达式1> + <表达式2> 规则4：<表达式1> * <表达式2> 规则5：（<表达式1> ） 那些是更基本的规则呢？

用自然语言表述计算机语言显示了它的不足，需要一种更为严谨更易评价的表达方法来刻画词法和语法等语言要素。 1.2 源程序 “分析” 1.2.3 词法分析 VS 语法分析 线性 VS 层次 非递归定义 VS 递归定义 三型文法 VS 二型文法 （more on later…) 用自然语言表述计算机语言显示了它的不足，需要一种更为严谨更易评价的表达方法来刻画词法和语法等语言要素。

1.2.3 语义分析 检查是否存在语义错误，获取类型信息。 类型检查 = = position + position + * initial 1.2 源程序 “分析” 1.2.3 语义分析 检查是否存在语义错误，获取类型信息。 类型检查 = = position + position + * initial * initial rate int2real rate 60 60

1.3 编译器的阶段 源程序 词法分析器 语法分析 语义分析 错误处理器 符号表管理器 中间代码生成器 代码优化器 代码生成器 目标程序

符号表，记录符号与其关联的属性，如类型、作用域，对于过程名符号，有其参数个数和类型、传值还是传引用、返回类型。 1.3 编译器的阶段 1.3.1 符号表管理 符号表，记录符号与其关联的属性，如类型、作用域，对于过程名符号，有其参数个数和类型、传值还是传引用、返回类型。 符号在词法分析阶段进入符号表，而与其关联的属性要在后继阶段补充。 float position, initial, rate;

在遇到错误时，应尽可能继续执行相应阶段。 词法分析：不成词的余留串，如3int 1.3 编译器的阶段 1.3.2 错误处理 在遇到错误时，应尽可能继续执行相应阶段。 词法分析：不成词的余留串，如3int 语义分析：语法结构良好，但语义错误，如加两个标识符，类型分别为数组和过程。

中间代码可看作是一种抽象机上的程序，如GCC产生的中间代码，Java Byte代码。 重要特性：容易从语义分析阶段产生，容易翻译到目标代码。 1.3 编译器的阶段 1.3.3 中间代码生成 中间代码可看作是一种抽象机上的程序，如GCC产生的中间代码，Java Byte代码。 重要特性：容易从语义分析阶段产生，容易翻译到目标代码。 中间代码有多种形式。 三地址码，最多三个操作数 流控和过程调用 （more on later…)

1.3 编译器的阶段 1.3.4 代码优化 1.3.5 代码生成 （more on later…)

1.4 编译器的同胞 预处理器 宏扩展 文件包含 语法糖衣 汇编器 装载和联结器 OS 外部引用

1.5 阶段的组合 前端：主要依赖源程序，独立于目标机器，词法分析、创建符号表、语法分析、语义分析、中间代码生成，可能有优化器的参与。 后端：代码优化、代码生成

1.6 编译器构造工具 解析产生器 扫描产生器 语义导向的翻译引擎 自动代码生成器。 数据流引擎

Chaper2.1 一个简单的一遍编译器 文法基础

提纲 本章为后继章节，特别是编译器前端（词法分析、语法分析、中间代码生成）提供一个实践的铺垫。 通过设计与开发一个简单的一遍编译器，展示了编译器前端构造的基本技术。 该一遍编译器为将中缀表达式语句编译成后缀表达式语句。 该例子还不够完善，希望同学们努力读懂并完善之。

编译器前端结构 语法导向的翻译器 词法分析器 字符流 单词流 中间代码

文法Grammar 我们采用文法来描述语言的句子结构 在得到某语言的文法基础上，我们可判定一个句子是否属于该语言 判定一个句子是否满足某语言的文法成为语法分析的核心问题 下面的内容围绕如何设计上下文无关的文法以解决这个判定问题

上下文无关的文法 stmt -> if (expr) stmt else stmt 上下文无关的文法，有以下几个组成： 终止符（集合），或称为token if, (, ), else 非终止符（集合） stmt, expr 产生式（集合） 左侧有且仅有一个非终止符 有且仅有一个非终止符作为起始符，如非终止符S为文法G的起始符，表示为G[S]

描述加减的文法G[list]，有以下4个产生式组成 list -> list + digit list -> list – digit list -> digit digit -> 0|1|2|3|4|5|6|7|8|9 ------------------------------------------ 左部相同的产生式，可以合并为： list -> list + digit | list – digit | digit 终止符集合VT为：{+,-,0,1,…,9}， 非终止符集合VN为：{list, digit}

文法导出串（句型） 从起始符开始，重复替换非终止符为其所在产生式的右侧，所得到的符号串即称为文法导出串，也称为句型。 如文法G[list]的句型有： list => list + digit （一个句型） => list – digit + digit （一个句型） => digit – digit + digit （一个句型） => 9 - 5 + 2 （一个句型且是句子） 只包括终止符的文法导出串，称为该文法的句子，句子的集合，称为该文法定义的语言。 *

描述块的文法-G[block] stmt_list -> stmt_list ; stmt | stmt block -> { opt_stmts } opt_stmts -> stmt_list | ε stmt_list -> stmt_list ; stmt | stmt ε是终止符，还是非终止符 ε是终止符

给定文法G[S]，其分析树/语法树 根S为起始符 叶节点为终止符（token）或ε 中间节点为非终止符 例子：9-5+2，按下述文法的分析树 分析树-Parse Tree 语法树-Syntax Tree

9-5+2，按文法G[list]的分析树（语法树） digit 9-5+2是G[list]的一个句型（这里是句子）的依据： 可为9-5+2产生一棵分析树 digit list digit 9 - 5 + 2 list -> list + digit | list – digit | digit digit -> 0 | 1| 2|3|4|5|6|7|8|9

分析树构造过程/句型推导过程 判断9-5+2是否是文法G[list]的句型（这里是句子）的最左推导过程如下： list list digit => list – digit + digit digit list => digit – digit + digit digit => 9 – digit + digit => 9 – 5 + digit 9 - 5 + 2 => 9 – 5 + 2 list -> list + digit | list – digit | digit digit -> 0 | 1| 2|3|4|5|6|7|8|9

小结：分析树构造过程/句型推导过程 为判定一个串是否是一个文法的句型或句子，分析树方法与推导方法效果一样。 分析树方法直观，但无法直接从结果分析树中看出推导步骤。 推导方法可以看出中间推导过程。 一个串是一个文法的句型或句子 iff 存在一棵分析树（语法树） iff 存在一个的最左推导或一个最右推导（规范推导）或即非最左也非最右推导。 一棵分析树对应唯一的最左推导和唯一的最右推导。

9-5+2的最左推导与规范推导（最右推导）比较 最右推导（规范推导） list => list + digit 最左推导 list => list + digit => list - digit + digit => list + 2 => list – digit + 2 => digit - digit + digit => 9 - digit + digit => list – 5 + 2 => 9 - 5 + digit => digit – 5 + 2 => 9 - 5 + 2 => 9 - 5 + 2 list -> list + digit | list – digit | digit digit -> 0 | 1| 2|3|4|5|6|7|8|9

最左归约和最右归约 与推导相反的过程称为归约 最左归约是最右推导的逆过程 最右归约是最左推导的逆过程 关于归约，我们将在自底向上的语法分析章节详解。

文法二义性 文法G[string]为二义性文法 string -> string + string | string - string | 0|1|2|3|4|5|6|7|8|9 因为有1棵以上的分析树对应9-5+2 大家动手画一下 G[string]在+,-运算符的左结合性问题上出现了二义性

文法二义性 给定文法G[S]： S -> if E then S | if E then S else S | N if E1 then if E2 then S1 else S2，是G[S]的合法句型，但存在不同的解释，即有1棵以上的分析树与之对应，所以G[S]为二义性文法。 G[S]在else与then结合性的问题上出现了二义性

文法二义性 给定某文法G，若存在某句子或句型w，与w对应的分析树（语法树）不只一个，则称G为二义性文法。 或者说，与w对应的最左推导不只一个 我们在设计文法时，应努力避免二义性。

操作符的结合性-左结合 文法G[list] list -> list + digit | list – digit | digit 谁体现左结合性？ 文法G[list] list -> list + digit | list – digit | digit digit -> 0 | 1| 2| 3|4|5|6|7|8|9 ------------------------------------------ 文法G[lst] lst -> digit + lst | digit – lst | digit

操作符的结合性-左结合 lst list lst - list digit + digit digit digit + lst list - 9 2 5 digit digit 5 9 2 lst -> digit + lst | digit – lst | digit list -> list + digit | list – digit | digit

操作符的结合性-左结合 文法描述了特定的数据结构 文法设计也即数据结构设计 合适的数据结构设计可以方便对数据的操作 语法树操作包括对语言特征（如左结合性）的验证 经验：文法左递归可以体现左结合性 但是，我们应转换文法中含有左递归的产生式，以去除左递归，从而利于自顶向下的语法分析（见后）

操作符的结合性-右结合 文法G[right] right -> letter = right | letter letter -> a |b|…|z a=b=c的语法树，如何画？ 经验：文法右递归可以体现右结合性

文法设计内功心法1-左递归 文法G[list] list -> list + digit | list – digit | digit 上述文法较好地体现了+,-运算的左结合性，要产生带有*,/运算的表达式，可依照左递归范式进行。

四运算表达式文法G[ex]草案 文法G[ex] ex -> ex + digit | ex – digit

文法设计内功心法2-按优先级引入非终止符 为处理以下3种优先级 我们引入2个非终止符 常数, () *,/ +,- term：封装仅含有*,/计算过的表达式 factor：封装仅含有常数,()计算过的表达式

文法设计内功心法2-按优先级引入非终止符 文法G[expr] expr -> expr + term | expr – term term -> term * factor | term / factor | factor factor -> digit | (expr) expr term + term - term factor * factor / factor digit (expr)

term -> term * factor | term / factor | factor factor -> digit 里程碑1. 得到四则运算表达式的一个原始文法 G[expr]的特点： 可产生四则运算表达式（句子） expr -> expr + term | expr – term | term term -> term * factor | term / factor | factor factor -> digit | (expr) digit -> 0|1|…|9 体现结合性和优先级 可处理括号 无二义性 左递归 一位十进制 只能一次产生一个表达式

我们离一个简单的后缀表达式编译器还有多远 语法制导的翻译概念 自顶向下（递归下降）的语法分析（解析） 预测分析方法 左递归消除 后缀表达式代码生成

练习 给定上下文无关的文法G[S] 写出下述语言的文法 S-> S S+ | S S * | a aa+a*是G[S]的句子吗？ {an bn| n>=0} 任何不是以0开始的所有偶整数所组成的集合 所有由奇数个1和偶数个0所组成的符号串的集合 后缀表示的算法表达式 逗号分隔的左结合的标识符列表

练习 给定文法G[S]: 下面是否存在二义性？ 试分别用最左推导和规范推导导出bbaacb S -> 0 S 1 | 01 S -> S v S S -> S S->S a | b S S -> S ( S ) S | ε 给定文法G[S]: S → AB S →c A →bA A →a B →aSb B → c 试分别用最左推导和规范推导导出bbaacb

Chapter2-2 语言的形式化定义基础

语言的形式化定义基础 以下给出若干本书用到的基本语言形式化定义的基本概念 以便于读本书时理解

字母表 字母表(符号集) 由符号组成的集合，如字母表A={a,b,c} a,b,c称为符号，一般为常量，也可以是变量，根据具体上下文确定。

符号串 符号串 A={a,b,c}是一个字母表，则a,b,c,ab,ac,bc,abc,aabc等都是字母表A上的符号串。 设,,，x 是符号串， 若x = ,则称是x的子串； 特别地，当=  （= ）时，称 是x的前（后）缀,若  x，则称是x的真前（后）缀

符号串操作 符号串连接 符号串的n次方幂 ε x = x ε = x 符号串长 strlen(“ab”) 符号串长 |ab|=2，长度为0的符号串，记为ε 符号串连接 若令符号串x=abc，符号串y=123，则xy表示符号串x与y的连接，即xy=abc123 ε x = x ε = x strcat(x,y) 符号串的n次方幂 若有符号串x,则 x1 = x, x2 = xx, xn = xn-1x = xxn-1 特别地有， x0= ε

符号串连接的特征 = xε = x εx ε 是<符号串连接运算>的单位元 因此我们定义 x0 = ε

符号串集合的操作 A1 = A, A2 = AA, 符号串集合的和（并集） 符号串集合的积 符号串集合的方幂 A + B = {w| w  A 或 w B}，其中A,B为符号串的集合 符号串集合的积 AB = {xy | x  A 且 y B} 符号串集合的方幂 A1 = A, A2 = AA, An = An-1A = AAn-1 (n>0)

符号集合和运算（并运算）的特征  + A A +  A = = <和运算+> 满足交换律  是<和运算+>的单位元

符号集合连接运算的特征 A = A =  是<符号集合连接运算>的零元

符号集合连接运算的特征 A{ε} A {ε}A A0 = {ε} = = εx x0 = ε = xε x {ε}是<符号集合连接运算>的单位元 A0 = {ε} εx ε 是<符号串连接运算>的单位元 x0 = ε = xε x

符号集合的闭包 A的正闭包： A的自反传递闭包：

文法形式定义和语言的Chomsky分类 文法形式定义 G=(VN, VT, P, S)，其中VN  VT = , VN  VT = V {E, T, F, D}, {+,-,*,/,(,),0,1,2..,9}, {E -> …, T -> …, F -> …, D -> …}, E) 文法G[E]: E -> E + T| E – T | T T -> T * F | T / F | F F -> D | (E) D -> 0|1|…|9

四类基本的文法 Chomsky将文法按产生语言的能力由强到弱分为四类基本的文法 0型文法（短语结构文法，PSG） 1型文法（前后文有关文法/上下文相关的文法，CSG） 2型文法（前后文无关的文法/上下文无关的文法，CFG） 3型文法（正规文法，RG）

0型文法（短语结构文法，PSG） 若文法G中任一产生式都有一般形式  V+ V* 其中，对， 不加任何限制 PSG: Phrase Structure Grammar)。由0型文法生成（或者说：定义）的语言称为0型（递归可枚举）语言。它可由图灵（Turing）机识别。

0型文法（短语结构文法，PSG） 文法G[S] SACaB CaaaC CBDB CBE aDDa ADAC aEEa 就是一个0型文法，它所产生的语言为

1型文法（前后文有关文法，CSG） 1A2 12 若一0型文法所有产生式具有形式（第一定义） 其中， 1,2V* V+ AVN | 1A2 |<=| 12 |，例外S->(S为起始符）且S不出现在任何产生式的右侧。 CSG ( Context Sensitive Grammar) 。1型文法产生的语言称为前后文有关语言CSL，它可由线性限界自动机识别。

CSG第一定义 根据定义，含有产生式的文法不是1型文法。但S-> （S为起始符）可作为1型文法的特例而接受之，条件是S不出现在所有产生式的右边。 例 文法G： S | A AaABC AabC CBBC bBbb bCbc cCcc 因G含有S ，但S不出现在所有产生式的右侧，按第一定义，G仍被认为是1型文法。

CSG第二定义 1 型文法还有另一种定义形式（第二定义）： G的每个产生式形为且满足： |  | |  | , V+ 今后，我们采用第一定义。

2型文法（前后文无关的文法，CFG） 若一1型文法G中所有产生式具有形式: A 其中， V+， AVN CFG(Context Free Grammar)。2型文法产生的语言称为前后文无关语言CFL，它可由下推自动机识别。 非严格CFG允许-产生式存在，即非严格CFG产生式形式为 A 其中，V*，AVN

2型文法（前后文无关的文法，CFG G[S]=({S},{a,b}, {SaSb Sab}, S) 产生的语言为

3型文法（正规文法，RG） 若一2型文法G中仅含有形如 AaB 或 Aa 的产生式， 其中 A,B VN , a VT 3型文法（正规文法）的产生式只有上述两种形式。

3型文法（正规文法，RG） RG（Regular Grammar），3型文法产生的语言称为3型（正规）语言，它可由有限自动机识别。正规语言可用正规表达式表示。 3型文法还可拓广定义为 AB A （  VT +）（不推荐!）

四类语言之间的关系

CSG，CFG，RG产生语言的特征 RG：xy*z CFG：anbn CSG：anbncn，anbncndn,…

练习 给定上下文无关的文法G[S] 写出下述语言的文法 S-> S S+ | S S * | a aa+a*是G[S]的句子吗？ {an bn| n>=0} 任何不是以0开始的所有偶整数所组成的集合 所有由奇数个1和偶数个0所组成的符号串的集合 后缀表示的算法表达式 逗号分隔的左结合的标识符列表

练习 给定文法G[S]: 下面是否存在二义性？ 试分别用最左推导和规范推导导出bbaacb S -> 0 S 1 | 01 S -> S v S S -> S S->S a | b S S -> S ( S ) S | ε 给定文法G[S]: S → AB S →c A →bA A →a B →aSb B → c 试分别用最左推导和规范推导导出bbaacb

练习 下面的文法哪些是正规文法、右线性文法、上下文无关文法或上下文有关文法？ （1）S → aB (2) S → AB B → Bc A → a B → b B → bC C → c B → b C → c

（3）S → aB (4) S → AB B → bC A → a C → c B → bC C → ε C → c C → ε

（5）S → aAb (6) S → aA aA → aB S → ε aA → aaA A → aA B → b A → aB A → a A → a B → b

（7）S → aCd (8) S → aA aC → B S → ε aC → aaA A → bAb B → b A → a

Chapter2-2 语言的形式化定义基础 4类语言识别方法

题纲 目的和基本思想 规则序列 规则序列应用实例

目的和基本思想 通过特定的过程（算法），以识别任意文法是4类文法（语言）中的哪一类 特定的过程是通过一系列有序的判定规则定义的 每一判定规则，针对某一产生式P，判定P是哪一类文法中的产生式 运用判定规则，对所有产生式{Pi}，得到其判定集合{Pi-所属的文法产生式}，其中最大者决定文法G是哪一类文法

规则序列：1. A-> 规则 for 产生式P，顺序应用规则1~6： 1. A-> 规则 1.1 若A为起始符且A在某产生式的右则，则 P是短语文法的产生式 1.2 否则不影响前面对每条产生式的判定结果，即如下情况不影响判定结果： 1.2.1 A为起始符且A不在任何产生式右则 1.2.2 A不为起始符

规则序列：2. 右线性规则 当产生式P不满足规则1时，应用下述规则 2. 右线性规则 若P满足下面3个条件，则P是右线性产生式 2.1 左侧只有一个非终止符（VN) 2.2 右侧最多只有1个VN且在最右 2.3 右侧至少有1个VT且在最左

规则序列：3. 左线性规则 当产生式P不满足规则2时，应用下述规则： 3. 左线性规则 若P满足下面3个条件，则P是左线性产生式 3.1 左侧只有一个非终止符（VN) 3.2 右侧最多只有1个VN且在最左 3.3 右侧至少有1个VT且在最右

规则序列：4. CFG规则 当产生式P不满足规则3时，应用下述规则 4. CFG规则 若P满足下面3个条件，则P是CFG产生式 4.1 左侧只有一个VN 4.2 右侧>=1个VN 4.3 若右侧仅有1个VN ，则该VN 不在右侧的两端，否则依据规则3/4识别

规则序列：5. CSG规则 当产生式P不满足规则4时，应用下述规则 5. CSG规则 若P满足下面2个条件，则P是CSG产生式 5.1 左侧串长>1且至少有一个VN 5.2 右侧串长>=左侧串长 注意，| |=0

规则序列：6. PSG规则 当产生式P不满足规则5时，应用下述规则 6. PSG规则 P是短语文法（PSG）产生式

规则序列应用实例 下面的文法哪些是正规文法、右线性文法、上下文无关文法或上下文有关文法？ （1）文法G[S] S → aB B → Bc C → c 解：对文法G[S]的每条产生式顺序应用规则1~6，有：

规则序列应用实例1 S → aB （由规则2，得右线性） B → Bc （由规则3，得左线性） B → b （由规则2/3，得左/右线性） C → c （由规则2/3，得左/右线性） 因为G中存在左线性和右线性产生式，所以G为正规文法。即 max{右线性,左线性,左/右线性} = 正规文法

规则序列应用实例2 (2) S → AB （由规则4，得CFG） B → Bc （由规则3，得左线性） C → c （由规则2/3，得左/右线性） 按最大文法原则，G为CFG，即 max{CFG，左线性, 左/右线性}=CFG

规则序列应用实例3 （3）G[S] S → aB （按规则2，右线性） B → bC （按规则2，右线性） C → c （按规则2/3，左/右线性） C → ε （按规则1，不影响） max{右线性, 左/右线性,不影响}= max{右线性, 右线性,不影响}=右线性，所以G为右线性 注意C → c 可以判定为左线性也可以是右线性，但若判定为左线性，则max= {右线性, 左线性,不影响}=正规，则将文法G所属文法类放大了。

规则序列应用实例4 （4）G[S] S → aAb （按规则4，CFG） aA → aB （按规则5，CSG） aA → aaA （按规则5，CSG） B → b （按规则2/3，左/右线性） A → a （按规则2/3，左/右线性） max={CFG,CSG,左/右线性}=CSG，即G为CSG

规则序列应用实例5 (8) G[S] S → aA （按规则2，右线性） aC → B （按规则6，PSG） aC → aaA （不用判断了） B → b （不用判断了） max{PSG,…} = PSG，即G为短语文法

Chapter3.1 词法分析 概念

提纲 关于suffix的Lexer::getNextToken 解决思路 基于状态编程的Lexer::getNextToken 关于状态的问题 所需学习的理论知识 3.1 设计扫描器时应考虑的问题 3.1.2 单词符号的内部表示 3.1.3 识别标识符的若干约定和策略

关于suffix的Lexer::getNextToken http://192.168.150.81/sei 进入编译原理->第二章 有多少人读过 Suffix源代码？

关于suffix的Lexer::getNextToken while (1) { cin >> c; //超前读 if (c == ' ' || c == '\t') ; // omit white space else if (c == ‘\n’) … // number of lines else if (isdigit(c)) … // number else if (isalpha(c)) … // identifier,keywords else if (c == EOF) … else { } // *,/,+,-,err } 单词识别程序的自动生成问题 else if 风格、回退字符回题 单词识别的长度和优先次序 输入缓冲区问题

讨论-else if 风格 Switch/case/default 风格：与else if一样：对输入分类、前后处理之间无关联 状态编程风格：对程序自身的状态分类，前后有关联 while (1) { switch(current_state) { case s_zero: cin >> c_char; c_state = s_ws; break; case s_ws: if (c_char==' ' || c_char== '\t') cin >> c_char; else c_state = s_n; break; case s_n: if (c_char == '\n') { ++line_no; cin >> current_char; } else current_state = s_digit; while (1) { c = inFile->get(); switch(c) { case EOF: …; case ' ': case '\t': case '\r': …; case '\n': …; default: …} }

<=，期望>，但等到是a，该怎么办？ 讨论-单词识别的长度和优先次序 对于有共同前缀的单词，采取最长匹配原则： 最长单词优先 为单词识别的长度建立一个规则 若期望的最长匹配失败了，如已读到 <=，期望>，但等到是a，该怎么办？ 语法分析 词法分析 < < = > a < = 输入流 < < < a = b > c

最长匹配导致的回退字符和性能问题 在词法分析器中建立双缓冲区以提高性能 通过双指针lexeme_begining, forward { i n t _ x lexeme_begining lexeme_begining getChar MoveBegin backward getLexeme _ f o o { 送语法分析

词法分析程序的自动生成问题 以3型文法描述单词 解析某个3型文法，以自动生成单词识别器

基于状态编程的Lexer::getNextToken nc: nextChar /nc ws/nc s_zero s_ws return anything EOF/return EOF other \n/nc s_n digit/nc other digit/nc s_digit s_number other other/return number s_alpha alpha or digit/nc s_id_keyword alpha/nc other other/return ID or KW s_EOF other 用/分开输入和动作，如ws/nc，表示当输入一个空白字符，则获取下一字符 s_unknown

基于状态编程的Lexer::getNextToken while (1) { switch(current_state) { case s_zero: cin >> current_char; current_state = s_ws; break; case s_ws: if (current_char == ' ' || current_char == '\t') cin >> current_char; else current_state = s_n; break; case s_n: case s_digit: case s_number: case s_alpha: case s_id_keyword: case s_EOF: case s_unknown: } }

关于状态编程的问题 每次处理一个字符，或为达到不回退字符，是引入状态编程的原因之一 如读取到某个identifier的中间（pointer） 由其它程序段（状态段）处理当前状态段无法处理的、多读出来的字符，如 123+，123由s_number状态段处理，+由s_unknown状态段处理

关于状态编程的问题 需注意的是 回退字符有时也方便编程 状态编程并不会比无状态编程更简单 执行效率也不见得高 但开发效率高，因为可自动生成单词识别器 程序逻辑上更清晰（什么状态下处理什么输入） 程序的可控制性高，程序当前处理什么状态

关于状态图的质量问题 对某一状态图的质量，我们将提出下列问题 状态数是不是最小，越小，程序越简单、程序的逻辑容易分析 这就是我们要研究的状态机最小化问题

关于状态图的质量问题 存不存在一个状态A对于同一输入x，A迁移到两个或以上不同的状态B,C,… 如果存在，是否存在一种转换机制将该状态图化为确定的状态图，即不存在上述现像 这就是我们要研究的状态机确定化问题

关于状态图的自动化问题 我们已经学习了文法知识，初步掌握了用BNF范式来表示一个语言的结构，现在的问题是，是否可以用BNF范式来表达一个状态图？ 答案是肯定的，用3型文法 如果能够用3型文法表示状态图，那么是否可以写一程序读入一个3型文法，输出一个状态图程序（switch/case）？ 答案也是肯定的

关于状态图的3型文法等价表示问题 我们是用BNF范式来写3型文法，如何保证我们不会写成2型文法（CFG）或是1/0型文法？ 虽然可以开发分析文法的程序来检验一个文法是否是3型文法，但这毕竟是事后的做法 为更好地解决上述问题，人们开发了正规语言，一种可易于使用的语言来描述状态图（机），已证明正规则语言与3型文法等价 同时，也开发了工具将正规语言翻译成状态图程序，如LEX工具

关于状态图的质量问题 关于状态图的自动化问题 关于状态图的3型文法等价表示问题 初步了解了上述3个问题，我们就确定了所需学习的理论知识

所需学习的理论知识 研究单词的文法形式 研究状态机 研究正规表达式（正则表达式） 3型文法、DFA、正规表达式的等价性 3型文法 3型文法到状态机转换 状态机到3型文法转换 NFA、DFA NFA确定化和最小化 研究正规表达式（正则表达式） 表示单词 正规表达式到状态机转换 3型文法、DFA、正规表达式的等价性 三者的互相转换

所需学习的理论知识 状态机 DFA NFA 正规语言 正则表达式 3型文法 正规文法

3.1 设计扫描器时应考虑的问题 词法分析程序亦称为扫描器 扫描器的任务是识别基本的语法单位—单词

词法分析的必要性 描述单词的结构仅用3型文法就够了； 将单词识别从语法分析识别分离出来，分而治之 有些语言的单词识别与前后文相关，不宜将其与语法分析合并；

扫描器的输出是语法分析程序的输入 Suffix::Parser调用Suffix::Lexer.getNextToken

3.1.2 单词符号的内部表示 常用的内部表示方法: (class,value) class Token { public: enum {NUM=256, DIV=257, MOD=258, ID=259, DONE=260, EMPTY=261, NONE=-1 }; int type; //对应class int value; //对应value }

Token的class几点解释 Token的class: NUM, DIV, MOD, ID DONE: 伪class指示 EOF EMPTY: 伪class，指示Token对象的type初值 单词的分类方法：可一词一类（+、-、begin、end等）或多词一类（如关键字类、操作符类、分隔符类、变量名类、常数类等）。 以方便Parser处理为目的

Token的value几点解释 在识别出变量名、函数（过程）名时，还应进行查填符号表的工作。 Token的 value 为索引，如果相应的type是 ID, 或 keywords(DIV,MOD) 数值，如果相应的type是NUM NONE，其它 (ID/keywords, index)的原因是 内存效率、ID和keywords有其它信息与之关联，如类型信息、同一名字类型不同（如foo的为类型为void foo(int i)，foo的类型也可以是int foo

Token的(type,value)列表 type value 说明 NUM 正整数的10进制值 (NUM,123) DIV 索引号 符号表(SymbolTable) type value 说明 NUM 正整数的10进制值 (NUM,123) DIV 索引号 (DIV,0) MOD (MOD,1) ID (ID,2) DONE NONE EOF 输入字符 (‘+’,NONE) EMPTY Token对象的初始值 索引号 词文(串) “MIV” 1 “MOD” 2 “I” 符号表并不只两列，还包括符号的类型信息等

3.1.3 识别标识符的若干约定和策略 一般来说，单词的长度是有限制的 class Lexer { enum {BSIZE = 128 } …}; Token Lexer::getNextToken() { … else if (isalpha(c)) { // ID or keywords for(; isalnum(c) && p < BSIZE ; ++p, cin >> c) { lexbuf[p]= c; } if (!isalnum(c)) {…} else { error("lexbuf overflow..") }; }

3.1.3 识别标识符的若干约定和策略 在允许长度下，应按最长匹配原则进行识别 < = : = i n t x

3.1.3 识别标识符的若干约定和策略 有时需要超前扫描来进行单词识别 FORTRAN语言中的算术条件句 IF(e)=L1,L2,L3和语句函数定义句 IF(x)=f(x)中的IF的识别；以及<和<=、<>等。 在进行超前扫描时，还应注意“回退”字符，即将多吃掉的字符退还回输入缓冲区。 < = a : = b

Lexer::getNextToken-字符回退 else if (isalpha(c)) { // ID or keywords int p = 0; for(; isalnum(c) && p < BSIZE ; ++p, cin >> c) { lexbuf[p]= c; } if (!isalnum(c)) { cin.putback(c); string alexeme(lexbuf, lexbuf+p);

Chapter3.2 词法分析 正规文法<=>状态转换图

状态机 DFA NFA 3型文法 正规文法

3.2.1 正规文法=>状态转换图 3型文法 左线性正规文法：所有产生式均为左线性产生式 右线性正规文法：所有产生式均为右线性产生式 或为左线性产生式 或为右线性产生式

3型文法例子 假设字母、数字属于VT 文法G[<标识符>]: <标识符><标识符>字母 <标识符><标识符>数字 <标识符> 字母 书P49 G[<无符号数>] = (VN, VT, P, <无符号数>) 假设字母、数字属于VT

命题 凡能用正规文法描述的语言，均可由某种有限状态算法——状态转换图进行分析。 得到的状态转换图可识别相应正规文法所产生的句子（单词）

状态转换图 由有限个结点所组成的有向图 每个结点代表在识别分析过程中扫描器所处的状态，其中 含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。 状态之间可用有向边连接，其上标记一字符a，表示从有向边的射出状态出发，识别一字符a后，将进入箭头所指状态（结点）

d a b 1 3 c d 2 为字母表 a,b,c,d  

状态转换图所识的语言 初态出发,分别沿一切可能的路径到达终态结点,并将路径中矢线上所标记的字符依次连接起来,便得到状态转换图所能识别的全部符号串,这些符号串组成的集合构成了该状态转换图所识别的语言

状态转换图所识的语言-例子 d a b 1 3 c d 2

3.2.1(1)右线性文法=>状态转换图 设G=(VN,VT,P,S)是一右线性文法,令|VN|=K， 2.1) G的开始符S为初态状态 3) 终止状态,用F(VN)标记　 F是新加(状态）节点

右线性文法=>状态转换图 转换规则 a A -> aB A B A -> a A F a A A ->ε A F 右线性文法=>状态转换图 转换规则 a A -> aB A B A -> a A F a 若A为起始符（G[A]） A A ->ε 消除ε，重用上述规则 A F [other]

右=>状 讨论1：消除ε产生式的方法-1 右=>状 讨论1：消除ε产生式的方法-1 按P34页方法 注意P34页算法2.4有缺陷，在(ii)步，若Xi W(即Xi可产生ε)，且文法中仅含一个Xi的产生式Xi -> ε时，Yi只能取ε而不能是Xi，否则Yi无法产生终止符串。

右=>状 讨论1：消除ε产生式的方法-2 右=>状 讨论1：消除ε产生式的方法-2 如文法G[S]： S -> A A -> aX X -> ε 消除ε后，G[S]为 A -> a 而不是： A -> aX | a （显然A无法产生终止符串）

右=>状 讨论2 A-other->[[F]] vs [[A]] 以下述文法作例子讨论，X考虑了所有右线性产生式情况 G[S]： S -> aA A -> bX X -> c|ε|eY

右=>状 讨论2 A-other->[[F]] vs [[A]] S -> aA A -> b|bX X -> c|eY a S A a S A [other] b b F c X F c X e e Y Y S -> aA A -> bX X -> c|ε|eY 左状态机与右状态机在识别语言的层面上等价。 左有利于编程实现（X状态下只有收到一个非c或e才算识别ab），右有利于手工推理和文法化简（去除ε）

右=>状 讨论2 A-other->[[F]] vs [[A]] b b F X X G[S]： S -> aA A -> bX X -> ε 左：X状态下收到任意一个终止符，则宣告识别句子ab 右：A状态下收到b，则宣告识别句子ab 左略显繁琐但有利于编程实现，右有利于手工推理

右=>状 讨论3 一条简化规则 A -> a A F a A -> a A B a G中除 A -> a外，若还存在A -> aB，则 A -> a A B a 该简化规则， 1）有利于手工推理 2）p51页图3-3就是应用本条规则并结合其它转换规则将P49页文法转换得到的。

右=>状 讨论4 状态图=>右线性文法 右=>状 讨论4 状态图=>右线性文法 1 3 2 a b c d 文法G[0] 规则应用 0->a1 A->aB  [A]-a->[B] 1->d1 同上 1->b A->a  [A] –a->[[F]] 0->c 0->c2 注意终态2有出弧 2->d 检查方法： 1）由右线性文法再画状态图 2）找句子：c可产生，cd可产生, adb可产生… 注意转换结束后，应检查一下：L(G[0])产生的语言是否=L(状态机)=

3.2.1(2)左线性文法=>状态转换图 设G=(VN,VT,P,S)是一左线性文法,令|VN|=K， 2.1) G的开始符S为终止状态 3) 起始状态,用R(VN)标记 R是新加(状态）节点

左线性文法=>状态转换图 转换规则 a A -> Ba B A A -> a R A a A A ->ε R A 左线性文法=>状态转换图 转换规则 a A -> Ba B A A -> a R A a 若A为起始符（G[A]） A A ->ε 消除ε，重用上述规则 R A [other] 不存在这种转换

左=>状 讨论1：消除ε产生式的方法-1 左=>状 讨论1：消除ε产生式的方法-1 R U S 1 因此得到： 1） G[S]： S -> S1 S -> U1 U -> U0 U -> 0 S -> ε 因此，将初态标记为终态，以表示 头脑想像从右则向左看 S <- S1 S <- U1 U <- U0 U <- 0 S <- ε S -> ε不可消除，因为

左=>状 讨论1：消除ε产生式的方法-2.1 左=>状 讨论1：消除ε产生式的方法-2.1 2) G[S]： S -> S1 S -> U1 | N0 U -> U0 N -> U | N1 U -> ε 找到可以产生ε的VT集合：由 U <- ε N <- U 得可以产生ε的VT={U，N}

左=>状 讨论1：消除ε产生式的方法-2.2 左=>状 讨论1：消除ε产生式的方法-2.2 G[S]： S -> S1 S -> U1 | N0 U -> U0 N -> U | N1 U -> ε 消除ε产生式 (N=>* ε 和 U=>* ε ) G’[S] 说明 S -> S1 S -> 1 1. U可以产生ε S -> U1 2. 除了U-> ε ,还有U->U0 S -> 0 | N0 同理1/2 U -> 0 | U0 N -> 1 | N1

左=>状 讨论1：消除ε产生式的方法-2.3 左=>状 讨论1：消除ε产生式的方法-2.3 由去除了ε产生式的新左线性文法G’作状态图 R N U S 1 G’[S]： S -> S1 S -> 1 | U1 S -> 0 | N0 U -> 0 | U0 N -> 1 | N1

左=>状 讨论2：状态图=>左线性文法 左=>状 讨论2：状态图=>左线性文法 1 3 2 a b c d 文法G[3](从右向左看） 规则应用 1 -> a A->a  [R]-a->[A] 1 -> 1d A->Ba  [B] –a->[A] 3 ->1b 同上且3为起始符 2 -> c 同上 3 -> 2 2为终态 3 -> 2d 终态2有出弧 检查方法： 1）由左线性文法再画状态图 2）找句子：c可产生，cd可产生, adb可产生… 注意转换结束后，应检查一下：L(G[0])产生的语言是否=L(状态机)=

由左线性文法构造状态转换图的例子 已给文法G=({S,U},{0,1}, {SS1 |U1, UU0 | 0},S) R U S 1

由左线性文法构造状态转换图的例子 句子00011的识别

识别符号串与归约 由构造状态转换图的方法可知,从初态R到下一状态A的转换,对应了形如Ba 的产生式,即将终结符a归约成非终结符B; 类似地,从状态B转换到状态A,对应了形如ABa的产生式,即将Ba归约为A; 如此下去,直到从某状态A转换到状态S(终态),对应了形如S Aa的产生式,即将Aa归约为开始符S.此时归约成功,也恰好进入了终态,即状态转换图识别了(或接受)该符号串. 前面识别00011的例子对应的归约过程见右图

S S U U U 0 0 0 1 1

3.2.2 状态转换图的实现-状态矩阵法 我们已看到,状态转换图可方便地用于识别单词.但是,如何让计算机利用状态转换图来进行词法分析呢? 一个简单实用的方法就是将图以矩阵的形式保存在内存中.这就是所谓的状态矩阵法. 状态矩阵 以图中各个状态S1,S2,…,Sn为行,以各个输入符号a1,a2, …,am为列,组成一个nm矩阵B,其元素Bij=B[Si,aj]指明下一状态Sk和扫描器此时应完成的语义动作.其含义是,在Si状态下,扫描到aj符时,按序偶(Si,aj)查矩阵B,扫描器根据Bij的指示,先执行相应的语义动作,再转换到下个状态Sk. 若Bij为“出错”,则说明输入符号串有误,拒绝接受.扫描器将调用出错处理程序进行处理.

程序3-2 状态矩阵驱动程序 CurStat=0; FlagOfFS=NoneSeen; /*将终态标志置为“未经历”*/ if(CurStat==EOF) return 0; while (CurStat != EOF){ if(Stat=TransMat[CurStat][CurChar]!=NULL) { CurStat=Stat; advance( ); if( CurStat 是终态){ FlagOfFS=HasSeen; /*已经历过终态*/ 记下输入串中当前位置及该状态相关的动作; }/*end if CurStat 是终态*/ }

else{ if(FlagOfFS==NoneSeen) { /*未经历过终态*/ 报告词法错误;略过当前词文及输入字符; CurStat=0; } else { 回退到最近经历的那个终态的输入字符位置;执行所记录的该 终态的相关动作; } /*end if FlagOfFS==NoneSeen */ } /*end if Stat !=NULL*/ }/*end while*/

识别无符号数的状态矩阵

关于状态无符号数识别矩阵 语义 动作中的返回值ICON、FCON分别为整型数、浮点型数的值； 一般说来，无符号数具有形式dmdm-1…d0.d-1…d-nEdd 即 dmdm-1…d0d-1…d-n*10^(dd-n);

矩阵中w,p,n,e分别用于计录尾数、指数、小数位及指数的符号。因此数值为： N=w*10^(e*p-n) 处理整数部分时，对于每个di ,令w=w*10+di ; 处理小数部分时，对于每个di ,令w=w*10+di ;及n++; 处理指数时，E后若有‘-’号，令e=-1；计算指数值p=p*10+d; 在出口处，令ICON=w或FCON=w*10^(e*p-n). 识别程序见P57程序3-3。

Chapter3.3 有限状态机 形式化定义 NFA确定化 DFA最小化

DFA 形式化定义 NFA 形式化定义 状态机 DFA NFA 最小化 确定化

提纲 3.3.1 DFA的形式定义 3.3.2 NFA 3.3.3 NFA与DFA的等价性 3.3.4 带 迁移的FA

3.3.1 DFA的形式定义 DFA: Deterministic Finite Automata 一个DFA M定义为M=(K, , f, S0, Z)，其中 1) K={状态i} 2) =字母表，即{输入字符i} 3) f : K ×  -> K，f为函数，表示某状态接受某个字母所到达的状态，如：f(p,a) =q, p,qK, a   4) S0 K， S0为初态 5) Z K，且Z  ，Z为终态集合

DFA例子 左侧的状态图，在数学上称作DFA，其形式化定义为 M=(K, , f, S0, Z) K={0 , 1 , 2 , 3 } 1 3 2 a b c d 左侧的状态图，在数学上称作DFA，其形式化定义为 M=(K, , f, S0, Z) K={0 , 1 , 2 , 3 } ={a , b , c , d } f: 源状态 输入 目的状态 a 1 C 2 d b 3 S0=0 Z={2 , 3}

函数f的推广定义f^ f^ : K × * -> K，表示某状态接受一个字母串（而不是一个字母）所到达的状态， 1） f^(p, ) = p, if p K，即任意一状态p接受（串长为0）的输入，状态不变 2） f^(p, aw) = f^( f(p,a), w), if p K, a  , w  *

函数f的推广定义f^ : 例子 = 3 对于x = adb, x  *， 那么从状态0可以迁移到的状态p可以这样求出： 1 3 2 a b c d 对于x = adb, x  *， 那么从状态0可以迁移到的状态p可以这样求出： P = f^(0, adb) = f^(f(0,a), db) = f^(1, db) = f^(f(1,d), b) = f^(1, b) = f^(f(1,b), ) = f^(3, ) = 3 因为从初态0接受输入字母串adb后，迁移到f^(0,adb)= 3 Z，所以adb为DFA所识别

函数f的推广定义f^ : 不做区别 f : K ×  -> K f^ : K × * -> K 上述被看作： 与C++的method overload是一个道理： K_type f(K_type, Sigma_type); K_type f(K_type, SigmaString_type);

DFA所识别的语言 令M 为一DFA，我们： 定义L(M)={x | f(S0, x) Z, x  *} L(M)称为DFA M所识别的语言 有定理：L(M) = L(G)，其中M为一DFA，G为一正规文法

DFA关键特征 状态迁移映射f是入射函数即 f(x)  f(y) 蕴含 x  y 即对任意状态结点p，其出弧上的字母各不相同且不为 从状态图角度，如出现下述情况的状态结点，则不是DFA（而是NFA） P Q N a Q  N P Q  P  Q Why?

3.3.2 NFA Nondeterministic Finite Automata  从文法上讲，NFA对应的文法具有下述特征： P Q N a Q  N P Q  P  Q 从文法上讲，NFA对应的文法具有下述特征： 1）左线性文法：至少存在右部相同的两个产生式： A->Ua B->Ua 2）右线性文法：至少存在形如下的两个产生式： U->aA U->aB

NFA的形式定义 一个NFA M定义为M=(K, , f, S0, Z)， 除f外其余成员与DFA相同，f定义为 f : K ×  -> (K)， 其中(K)为集合K的幂集合，即有 |(K)|=2^|K| f 表示某状态接受某个字母所到达的状态集合，如：f(p,a) ={q,m} p,q,mK, a  

映射f的推广定义f^ f^ :  (K) × * ->  (K)， 表示某状态集合接受一个字母串（而不是一个字母）所到达的状态集合， f^递归定义如下(依赖于f)： f^({p}, ) = {p} f^({p},a) = {p1, p2,...} if f(p,a)={p1,p2,…}  if f(p,a) =  f^({p},aw) = f^(f^({p},a), w) 属于什么？ 其中，p,p1,p2 K, a , w  *

映射f的推广定义f^ : 不做区别 f : K ×  -> (K) f^ :  (K) × * -> (K) 上述被看作： f :  (K) × * -> (K) 与C++的method overload是一个道理： KSet_type f(K_type, Sigma_type); KSet_type f(KSet_type, SigmaString_type);

NFA所识别的语言 令N 为一NFA，我们： 定义L(N)={x | f(S0, x)  Z  , x  *} L(N)称为NFA N所识别的语言 有定理：L(N) = L(M) = L(G)，其中N为一NFA，M为一DFA，G为一正规文法

NFA例子 – 写状态迁移表f  为什么是NFA f : K ×  -> (K) 对每状态结点，按出弧上的字母写出状态迁移表 S A B C a b a,b 为什么是NFA f : K ×  -> (K) 源状态 输入 目的状态集合 ->S a {A,C} A b {A,B} B C [C] x    对每状态结点，按出弧上的字母写出状态迁移表 C行可以不填

NFA例子 – 接受串 解决办法？  f : K ×  -> (K) 源状态 输入 目的状态集合 ->S a {A,C} A b {A,B} B C [C] x    当前状态 余留输入 后续状态 选择状态 S ababb A,C A or C ? 解决办法？ 注意，NFA识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（带回溯），这影响了NFA的效率。

3.3.3 NFA与DFA的等价性 定理3.1 对于字母表上的任一NFA N，必存在与M等价的DFA M，使L(N)=L(M) 基本idea: DFA的 f : K ×  -> K NFA的f : K ×  -> (K)，将其改造为 f’ : (K) ×  -> (K)，并证明f’是入射函数 且f’^接收的串与f^接收的串相同 有了该定理，为提高NFA识别字符串的效率提供了tips： 将NFA转换为DFA， 即NFA的确定化

无 迁移的NFA确定化 M={{S0, S1}, {a,b}, f, S0, {S1}} b a a,b S1 S0 b (K) ×  -> (K)

无 迁移的NFA确定化 a,b a S0,S1 S0 S1 b b

3.3.4 带 迁移的FA M=(K, , f, S0, Z)， 除f外其余成员与DFA相同，f定义为 f : K × ( {}) -> (K)， 带 迁移的FA是扩充的NFA 带 迁移的FA是NFA吗？ P Q  P  Q

带 迁移的FA例子  a b c  b S0 S1 S3 a S2 c S0 {S0} {S1, S2} S1 {S1, S3}

带 迁移的FA的所识别的语言 令N 为一 迁移的FA ，我们： 定义L(N)={x | f(S0, x)  Z  , f^ :  (K) × * -> (K)

引入带 迁移的FA的目的 是为了将识别不同类的单词的DFA用  迁移连接起来 => 确定化 => 设计综合的词法分析器

3.3.5 带 迁移的NFA的确定化 步骤： 1) 求-closure，且将所有状态表上（除的列以外）状态q用相应的-closure(q)替代 2) 删除列 3) 从起始状态S0的-closure(S0)开始走 3.1) -closure(S0)做 行计算：对每字母a，求-closure (S0)-a->? 3.2)对-closure(S0)所能到达的每个状态集做 行计算 4) 标记“起始状态”，“终止状态”，“可达性” 5) 用样本串测试所得的DFA

S0 S1 S3 a S2 c  b

0）画出状态表 a b c  S0 S1,S2 S1 S1,S3 S2 S3

1）求-closure，且将所有状态表上（除的列以外）状态q用相应的-closure(q)替代，如S0和S2 a b c  S0 S1,S2,S3 S0, S1 S1,S3 S2,S3 S3

2) 删除列 a b c  S0 S1,S2,S3 S0, S1 S1,S3 S2,S3 S3

3) 从起始状态S0的-closure(S0)开始走 可达性 a b c  -起始-> S0 S1,S2,S3 S0, S1,S3 S2,S3 S1, S1 -> S3

4) 标记“起始状态”，“终止状态”，“可达性” 可达性 a b c  -起始-> [S0 S1,S2, S3] S0, 令q0={S0,S1,S2,S3}, q1={S1,S3}, q2={S2,S3} 得下图

5) 用样本串测试所得的DFA，如原NFA识别abb, ac，所得新DFA也识别 ->[q0] q0 q1 q2 [q2] [q1]

3.3.6 DFA状态数最小化 可区分状态 A B 状态A,B被某一输入串w=a1a2..an所区分，指 2）而从另一个状态出发进入非终态

可区分状态的递归定义 在一个DFA中，状态A与状态B可区分： 1）A是终止状态，B是非终止状态 或 B是终止状态，A是非终止状态 2）对于字母a，有f(A,a)=C, f(B,a)=D 2.1) C与D可区分 2.2) C=NULL 且 D  NULL且D可达终态 或 C  NULL且C可达终态 且 D=NULL

DFA状态数最小化-例子 a a a b b S4 S1 S3 S0 a b a S2 b b

习题讲解 P101 页3-13(2)

Chapter3.4 正规表达式与正规集

状态机 DFA NFA 最小化 左/右<=>状态机 确定化 正规语言 正则表达式 3型文法 正规文法 Thompson

提纲 3.4.1正规表达式及正规集的定义 3.4.2 正规文法=>正规式 3.4.3 正规式=>NFA的FAThompson法

正规表达式的概念 可用于描述三型语言的特征,特别是对自动生成词法分析程序而言，它是非常有用的工具。 所谓正规表达式就是用特定的运算符及运算对象按某种规则构造的表达式，用于描述给定三型语言的所有句子。

3.4.1正规表达式及正规集的定义 1.  空集 2.  {} 3. a a {a} 正规式 正规集 1.  空集 2.  {} 3. a a {a} 4) (r) •(s) L(r) • L(s) (r)|(s) L(r)  L(s) (r)* (L(r))*

正规式的操作符(), *, • , | 1) 优先级从高到低依次为 (), *, • , | 正规式的操作符(), *, • , | 1) 优先级从高到低依次为 (), *, • , | ( (r) • ( (s)* ) ) | ( r )，其中r,s,r 可化简为 r •s*|r • 常常可省略不写，再化简为 rs*|r

正规式与正规集的例子 ={a,b}

单词用正规式定义的例子 <keyword> -> BEGIN|END|THEN|ELSE <identifier> -> <alpha>(<alpha>|<digit>)* <number> -> <digit><digit>* <rop> -> ‘<‘|’<=‘|’=‘|’<>’|’>’|’>=‘ <alpha> -> [A-Z]|[a-z] <digit> -> [0-9]

正规式 N-----1 正规集 给定正规式,它唯一确定一正规集;反之不真.即一个正规集可由多个不同的正规式表示. 若两个正规式描述同一正规集,则称两式等价(相等)

正规式的基本等价关系 A1. r|s=s|r A2. r|r=r A3. r|=r A4. (r|s)|t=r|(s|t) A5. (rs)t=r(st) A6. r(s|t)=rs|rt A7. (s|t)r=sr|st A8. r = r =  A9. r = r =r A10. r*=(|r)*=|rr*

3.4.2 由正规文法构造相应的正规式 文法G[S] SaS | bA | b AaS 介绍一种方程组的方法，将 | 用 +替换，-> 用 = 替换 以我们习掼的线性方程组求解S

论断3.1 方程X= X + ，有解 X= * X= X + 即：X -> X | 

文法G[S] SaA AbA | aB | b BaA

对于左线性文法,在解联立方程时最终会得到形如x=x+的方程, 文法G[S] S->Aa|c A->Ab|d

文法G[S] S -> aA | Bc A -> bA | d B -> Se | S B -> Se | fS 什么类型的文法

3.4.3 正规式构造FAThompson法 r= r= r=a s f f s f a

r= r1|r2  r1  f1 S01 s Sf r2 f2 S02  

r=r1r2 r1 r2  S01 S02 f01 f02

r=r*    Sf f1 s S01 

练习 a(b|aa)*b P102页第3-18 P103页第3-21 P103页第3-22（5） P103页第3-23 P103页第3-11

Chapter4 语法分析和语法分析程序 概念

语法分析在编译阶段中的地位 Where are we now? 源程序 词法分析器 语法分析 语义分析 错误处理器 符号表管理器 中间代码生成器 代码优化器 代码生成器 目标程序 错误处理器 符号表管理器 Where are we now?

语法分析在编译阶段中的地位-More Closer Token类型 token 源程序 词法 分析 语法 分析 Get next token parse tree 语义分析 中间代码生成 中间代码

语法分析的I/O 输入：<单词流>形式的源程序 任务：根据文法G的语法规则，分析源程序是否是G的句子（语法检查） 输出：若是句子，解析树 (parse tree) 若否，报错 假定：先不考虑语义问题

语法分析的两大套路 自顶向下()：S =>* token组成的句子  : 递归下降法, 预测分析法(LL分析法) 自底向上()：token组成的句子 ~归约->S  : 优先分析法, LR分析法

Chapter4.1 自顶向下的语法分析 自顶向下分析方法要求的两个前提 1）无（最）左递归 2）提取公因子

1 自顶向下的语法分析的基本思想 输入串是否是给定文法的句子 语法分析的根本任务是什么？ 对输入串w,试图自顶向下地建立一棵解析树 或者说,从G[S]的S出发,试图为w构造一个最左推导 若成功,有w  L(G)，继续下一步 若失败，报错，进入错误处理 输入串是否是给定文法的句子 语法分析的根本任务是什么？

2 最左推导的穷举法 在为w寻求最左推导的每一步, 都要将当前句型的最左VN替换为相应产生式的右部 如：当VN具有形如： VN  AB | AC | CD | … 应该选择AB or AC or CD or …中的哪一个替换VN ? 最简单的方法是：逐一试探（穷举法）

look_ahead是非常重要的概念，无论在词法分析，还是语法分析（包括两种套路的分析方法） 2.1 最左推导的穷举法-成功了 G[Element] 根据look_ahead将VN替换为 VN产生式的某个右部 <address lang=“en” /> 是G[Element]的句子吗？ <address lang=“en” > 是G[Element]的句子吗？ look_ahead 似曾相识？ look_ahead是非常重要的概念，无论在词法分析，还是语法分析（包括两种套路的分析方法）

2.2 最左推导的穷举法-失败了 G[E]: E EAT | T T F | TMF F (E) | i A + | - w = i * i + i是G[E]的句子吗？

2.3 最左推导的穷举法-穷举法为什么失败 教科书以怎样的自顶向下方式看待最左推导的 ？ G[E]: switch(look_ahead) void E() { { E(); A(); T(); } { T(); } } G[E]: E EAT | T 穷举法没有考虑的 重要因素 导致死循环或回溯 switch(look_ahead) case ‘[]’: 教科书要我们这样看待最左推导

3. 消除死循环和无回溯的方法 G[E]: E EAT | T void E() { switch(look_ahead) case ‘[]’: { E(); A(); T(); } case ‘[]’: { T(); } } G[E]: E EAT | T 由于无法在文法上直接表示swith…case结构，因此需要对文法进行改造以体现switch…case的效果，从而避免 1）最左推导的死循环 2）最左推导的回溯

3.1 避免：最左推导的死循环 1.若G有（最）左递归,则分析不能正常进行.因此, 分析必须先消除文法的左递归; G[E]: E EAT | T void E() { switch(look_ahead) case ‘[i]’: { E(); A(); T(); } case ‘[i]’: { T(); } } G[E]: E EAT void E() { { E(); A(); T(); } } i * i + i look_ahead

3.2 避免：回溯-1 2.若G有（最）左公因子,则分析不能正常进行.因此, 分析还提取公因子; G[E]: E TA | TB void E() { switch(look_ahead) case ‘[i]’: { T(); A();} case ‘[i]’: { T(); B();} } G[E]: E TX X A | B void E() { T(); X(); } void X() { switch(look_ahead) case ‘[a]’: A(); Case ‘[b]: B(); } 例子G[Element]

3.2 避免：回溯-2 3.若G的某产生式的若干候选项的First单词（可为）存在交集,则分析不能正常进行.因此, 分析还需改造文法; G[E]: E AX | BY A a B  Y  a void X() { switch(look_ahead) case ‘[a]’: A(); Case ‘[a]: B(); } G[E]: E AX | BY A a B a void X() { switch(look_ahead) case ‘[a]’: A(); Case ‘[a]: B(); }

3.3 自顶向下分析方法-可行的2个必要条件 修改文法 若给定文法不满足这2个必要条件，又仍想用自顶向下分析方法 消除（最）左递归 消除回溯 提取（最）左公因子 改造文法 修改文法 若给定文法不满足这2个必要条件，又仍想用自顶向下分析方法

4. LL(1)文法定义： 对G中每个A 1 | 2 | … | m, A-产生式中任何两个候选式i,j,均满足: (1)FIRST(i)  FIRST(j)=  (ij 1 i, j  m) (2) i, j中,至多有一个能推导出; (3)若j * ,则 FIRST(i)  FOLLOW(A)= (i=1,2,…,m ij) 注: 条件(2)可省略. 即(1) (2)

4.1.0 提取公因子 若有形如A  1|2 |…| n 则提取公因子后，上述产生式被替换为以下两个产生式： A  A’ 例子G[Element] 若1~n之间还有公因子，则继续提取

4.1.1 消除文法的左递归：1-直接（最）左递归 设文法是已简化的.若文法含直接左递归式: AA |  (V+) , 则类似正规式求解方法,我们有 A A’ A’ A’| 由于不以A打头, A非（最）左递归.

例子 G[E]: E EAT | T T F | TMF F (E) | i A + | - M * | / G[E]: ETE’ E’ATE’| TFT’ T’MFT’| F(E)|i A+|- M *|/ G[E]: E EAT | T T F | TMF F (E) | i A + | - M * | /

4.1.1 消除文法的左递归：1-直接（最）左递归 一般地,设文法中全部A-产生式为 AA1|A2|…|An| 1|…| m 其中, i不以A打头, 则消除直接左递归后的产生式为 A1A’|…| mA’ A’ 1A’|…| nA’

4.1.1 消除文法的左递归：2-间接（最）左递归 S  Ab|c ASa S  Sab|c S cS’ S’ abS’ | 

4.1.1 消除文法的左递归：2-间接（最）左递归

消除文法左递归的矩阵方法 设文法的非终结符为 X1, X2, …, Xn, 其中,Xi的产生式可分为以VN符和VT符打头的两类.类似正规式方法,将‘|’改写为‘+’,有 Xi=X11i+X22i+…+Xnni+ i 其中,  i 是以VT符打头的产生式之和, ki 可以为 这样,文法G可表示为 该方程有解: X=BA* 为得到A*,由 则有: X=BZ Z=I+AZ 其中X的产生式以VT符打头,而Z的产生式以ijV*打头,因此将不含左递归. 注意,由此所得的文法含有无用符号和无用产生式,需化简 或: X=XA+B

例子 SSa | Ab | a ASc S aZ11 Z11aZ11 |cZ21| Z21 bZ11

Chapter4.1.3 递归下降分析法 自顶向下分析方法的 手工程序编写方法

递归下降分析法(recursive descent method)的原理是 4.1.3 递归下降分析法 递归下降分析法(recursive descent method)的原理是 对于文法的每个非终结符,根据其各候选式的结构,为其建立一个递归的子程序(函数), 用于识别该非终结符所表示的语法范畴.

expr_prime( ){ } if(match(PLUS)){ advance( ); term( ); i + i * j - k

例4.2 文法G[statements]: statements exression;statements |  expression term expression’ expression’ +term expression’ |  term factor term’ term’ *factor term’ |  factor  num_or_id | (expression) 可以验证, G[statements]满足LL(1)文法条件.故可用递归下降法分析.教材中P112程序4-1,给出了其递归下降语法分析程序.

4.1.4 预测分析法 预测分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序(表驱动程序)及一分析栈组成 输入 X Y Z # 分 析 栈 a1 a2 … ai … an # 输入 输入是待分析的符号串（单词流），以# 结尾。 分析表是一二维数组，M:VN(VT{#}) (P{ERR}), M[A,a]的值按下述规则确定:对于每个产生式A1|2|…|m (1)若aFIRST(i), 则置M[A,a]=“Ai”; (2)FIRST(i), aFOLLOW(A), 置M[A.a]=“Ai”, (3)除上述两种情况外,其它元素均填“ERR”. 分析表元素的含义:指明当前应用何产生式进行推导,或指明输入串出现错误

一、分析器的工作原理 分析器对输入串的分析在控制程序的控制下进行，步骤如下： 1.初始化.首先将#及开始符S压入栈,各指针置初值.此时,格局为 # S a1 a2 … … an # # X1 X2 …Xm-1 Xm ai ai+1 … … an #c 2.设在分析的某时刻,的分析格局为 此时,根据当前栈顶符号Xm的不同情况,分别作如下处理: (1) XmVT,且Xm=ai,则匹配,将Xm 顶出栈,输入指针++;否则(Xmai),出错; (2) XmVN 查表M[Xm,ai],若M[Xm,ai]=“ERR”,则出错;若M[Xm,ai]= “Xm Y1Y2…Yk” ,则将Xm 出栈, Y1Y2…Yk 按逆序压入栈,得到格局 # X1 X2 …Xm-1YkYk-1...Y1 ai ai+1 … … an # (3)若Xm=ai=#,则表明输入串已完全得到匹配,分析成功,结束.

预测分析法实例 考虑文法(4.1)’.各个 FIRST集与FOLLOW集如右表所示 文法(4.1)’相应的LL(1)分析表见右 注:在分析表中我们有意省略了左侧的非终结符(why?).在实际的表存储时,还可用产生式编号表示

对i+i*i进行预测分析的过程

二、构造FIRST集的算法 对于G中的每个文法符号X,为求FIRST(X),反复应用如下规则,直到集合不再增大: (1) if (XVT) { FIRST(X)={X};} (2)if (XVN) { if(XaP  aVT) aFIRST(X); if (XP) {FIRST(X);} } (3) if (XY1Y2…YkP) {if (Y1VN) {FIRST(Y1)-{} FIRST(X);} for(1 j k-1)if (YjVNFIRST(Yj)){FIRST(Yj)-{}FIRST(X);} if (for(1 j k):  FIRST(Yj)) {FIRST(X);} V*,=X1X2…Xn,求FIRST()类似于求XY1Y2…Yk,略.

构造FOLLOW集的算法 FOLLOW: VNVT{#},反复使用如下规则,直到不再增大: 1. # FOLLOW(S); 2. if (ABP) {FIRST()-{}FOLLOW(B);} 3. if ( (ABP)  ( AB  FIRST() ) ) {FOLLOW(A)FOLLOW(B);} 算法的证明: 对于1.,由定义直接得到; 对于2.,由于A是有用符号,则必存在含A的句型: S * A  B  Ba (a FIRST()); 对于3., 类似地, S * A  B[],显然, FIRST()FOLLOW(A),并且, FIRST()FOLLOW(B).证毕//

构造FIRST集和FOLLOW集的例子 我们以文法(4.1)’为例,计算相应的FIRST集和FOLLOW集. 1.求所有VN符的FIRST集.利用规则(2),有 FIRST(M)={*,/}, FIRST(A)={+,-} FIRST(F)={(,i}; 再利用规则(3),有FIRST(T’)=FIRST(M){}={*,/, }, FIRST(T)=FIRST(F)={(,i}, FIRST(E’)=FIRST(A) {}={+,-,} FIRST(E)=FIRST(T)={(,i} 2.求FOLLOW集 (1)由规则(1),#FOLLOW(E),再由产生式F(E), ) FOLLOW(E), 从而,FOLLOW(E)={),#} (2)由规则(3)及产生式ETE’可知FOLLOW(E)FOLLOW(E’),即有 FOLLOW(E’)={),#}

求FIRST,FOLLOW集例子(续) (3)由规则(2)及产生式E’ATE’有 FIRST(E’)-{}FOLLOW(T);再由规则(3)及ETE’和E’*有 FOLLOW(E)FOLLOW(T) 即FOLLOW(T)={+,-}{),#}={+,-,),#} (4)由规则(3)有TFT’有FOLLOW(T)FOLLOW(T’),即FOLLOW(T’)={+,-,),#} (5)由规则(2)及T’MFT’,有 FIRST(T’)-{} FOLLOW(F),再由规则(3)及T’MFT’和T’*,有FOLLOW(T’) FOLLOW(F),从而, FOLLOW(F)={*, /}{+,-,),#}={+,-,*,/,),#} (6)由规则(2)及E’ATE’,T’ MFT’ ,有 FIRST(T)FOLLOW(A), FIRST(F) FOLLOW(M),故有 FOLLOW(A)={(,i}, FOLLOW(M)={(,i}. 最终所得的FIRST集和FOLLOW集结果,见P119

三、预测分析表的构造 造表的算法 在AVN所在行,aVT所在列, M[A,a]的填写方法如下: 对已给的LL(1)文法,在得到各文法符号的FIRST集和FOLLOW集之后,就可容易地构造出预测分析表(也称LL(1)分析表). 在实际的表存储结构中,矩阵中每个元素并非真正存储的是产生式,而是其右部的逆序(也可以是产生式序号),这样便于分析时使用,并节省了内存空间. 造表的算法 在AVN所在行,aVT所在列, M[A,a]的填写方法如下: (1) if ( AP and aFIRST() )M[A,a] =‘A’; (2) if ( * ( FIRST()) and aFOLLOW(A) ) M[A,a]=‘A’; (3) Otherwise, M[A,a]=‘ERR’. 文法(4.1)’的LL(1)分析表见P119表4-2

4.1.5 某些非LL(1)文法的改造 对于LL(1)文法而言,我们总能构造出相应的预测分析表,且表中决不会含有多重定义的元素. 然而对于非LL(1)文法,它们不满足LL(1)文法的条件,尽管仍可为其建立预测分析表,但表中必然会出现多重定义的元素(why?) 例如,文法G[S]: SabB ASC|BAA| BAbA CB| FIRST(S)={a} FIRST(A)={a,b, } FIRST(B)={a,b} FIRST(C)={a,b,c} FOLLOW(S)= FOLLOW(A)=FOLLOW(B)= FOLLOW(C)= {a,b,c,#}, 由造表规则,有 M[A,a]={ASC,A}, 同理, M[B,b]={ABAA, A }. 可见非LL(1)文法所造之表中,必有冲突元素.事实上, 是否有冲突元素也是判别一文法是否是LL(1)文法的方法之一. 对于某些非LL(1)文法而言,通过消除左递归,反复提取左因子等方法,有时是可以将其改造成LL(1)文法的.

某些非LL(1)文法的改造(续) 提取左因子 当文法中含有形如 A1|2|…|m 的产生式时,可将其改写为: AA’ A’1|2|…|m 若诸候选式1,2,…,m 中的一部分仍含有左因子 ,则再进行提取工作,如此等等.这样,就可能得到一个LL(1)文法. 例如, EE+T | T T(E) | a(E) | a 经改造后可得文法 ETE’ E’+TE’|  TaT’ | (E) T’ (E) |  这是一个LL(1)文法. 应当指出,并非所有的文法都能改造为LL(1)文法. 例如,文法G[S]: SAU | BR AaAU | b BaBR | b Uc Rd 文法中S的两个候选式AU及BR的FIRST集相交,G是非LL(1)的.为提取左因子,先将S产生式中的A,B用其右部替换,得: SaAUU|bU|aBRR|bR, 经提取左因子,得 S aS’|bS” S’AUU|BRR S” U|R A… 显然它仍不是LL(1)文法

关于LL(1)的一些结论 能由LL(1)文法产生的语言称为LL(1)语言.它们已被证明具有许多重要特性, 主要有: (5) CFL是否是LL(1)语言是不可判定的; (6) 非LL(1)语言是存在的. 若在分析过程中,每步向前扫描k个符号来确定选用的产生式,此分析方法称为是LL(k)分析.此法极少用,故从略.

Chapter4.2.4 LR分析方法 概念 运行LR分析表

提纲 已学分析方法的局限性 LR分析方法综述 LR分析器的逻辑结构及工作原理 LR分析表 LR分析器的总控程序 LR分析实例

1. 已学分析方法的局限性 LL(1)分析方法 算符优先分析方法 无左递归，左公因子要合并 First集不相交，First集与Follow集（若产生式的相应右则可推出）不相交 算符优先分析方法 忽略了VN在分析过程中的作用 无法处理单目-和双目-的问题

2. LR分析方法综述1 自左至右扫描的自底向上的分析 LR分析对文法要求很少,效率极高,且能及时发现错误 LR分析法所能识别的语言与LL(1)和算符优先的真超集

LR分析方法综述2 LR(k)文法是无二义性文法 LR(k)文法与LR(1)文法等价 LR(0)<SLR(1)<LALR(1)<LR(1) 生成LALR分析方法的编译器的生成程序有 YACC: Yet Another Compiler Compiler SableCC

3. LR分析器的逻辑结构及工作原理 a1 a2 … ai …an# 分 析 栈 分析表 top Sm Xm … S1 X1 S0 # 把握“现在” 分 析 栈 总控程序 记住“历史” 分析表 展望“未来” Sm Xm … S1 X1 S0 # top 根据“现在”状态+输入V+分析表 决定 (移进、归约、接受、报错)

4. LR分析表 Action表 单词 状态 a b , # S r3 ERR acc Goto表 V-{#} 状态 a b , E 3 2

5. LR分析器的总控程序 parser( ){ 初始化； while((item=ACTION[TopStat] [InpSym])) != Acc) { if(item==ERROR) error( ); if(item==Sj){push(j);advance( );} else reduce(i); //item== ri }//while accept( ); }

5. LR分析实例 1. LE,L 2. LE 3. Ea 4. Eb ACTION GOTO a b ， # L E s3 s4 状态 ACTION GOTO a b ， # L E s3 s4     1 2 1       ac     2     s5 r2     a,b,a是否是上述文法的句子？ 3     r3 r3     4     r4 r4     5 s3 s4     6 2 6       r1    

分析栈的两个主要动作：归约、移进 #  a , b , a # # a , b , a # # E  , b , a # # E , E  , a #  E , E , a # E , E ,  a #  E , E , a # E , E , a #  E , E , a # E , E , E #  E , E , E 最右推导是最左归约的逆过程  E , E , L # E , E , L # # E , L #  E , L # L # L

6. 句柄、短语 a,b,a的最右推导 L  E , L  E , E , L  E , E , E  E , E , a  E , b , a  a , b , a L2 E1 , E2 L3 a1 , b E3 a2 句型a1 b a2相对于L3的短语为：a2 ... L2的短语为：ba2 ... L1的短语为：a1ba2 句型a1 b a2相对于E1的直接短语为：a1 ... E2的直接短语为：b ... E3的直接短语为：a2 下划线子串是当前句型最应归约的子串，称为句柄，也称最左直接短语

Chapter4.2.4 LR分析方法 LR(0) 分析表的构造

提纲 LR(0)的含义 规范句型的活前缀(viable prefix) LR(0)项目集 识别所有规范句型全部活前缀的DFA

1. LR(0)的含义 LR(K)中，K的值为look_ahead的数量 LR(0)分析就是K=0时的LR(K)分析 K=0的含义是 即超前读取的单词数 LR(0)分析就是K=0时的LR(K)分析 K=0的含义是 不读取词法分析器供应的单词 仅根据当前的栈顶状态确定下一步动作

2. 一种证明思路 G[S]: SA | B AaAb | c BaBb | d 如何证明任意给定串w是G[S]的句子呢？

2.规范句型的活前缀(viable prefix) G[L]: LE,L LE Ea Eb

将栈内符号与未扫描的输入串拼接起来就是一规范句型 分析动作 余留符号 分析动作 # a,b,a# s3 将栈内符号与未扫描的输入串拼接起来就是一规范句型 栈内符号串称为规范句型的活前缀,且不含句柄右侧的符号. b是句柄, “”, “E” , ”E ,” , ”E , b”都是活前缀 #a ,b,a# r3 #E ,b,a# s5 #E, b,a# s4 #E,b ,a# r4 #E,E ,a# s5 #E,E, a# s3 #E,E,a # r3 #E,E,E # r2 #E,E,L # r1 #E,L # r1 最右推导（规范推导） #L # acc

LR分析过程实际上就是一个逐步产生(识别)规范句型的活前缀过程. # a,b,a# s3 LR分析过程实际上就是一个逐步产生(识别)规范句型的活前缀过程. 在分析的每一步,栈内符号总是活前缀 若能构造一个识别所有活前缀的自动机,则构造分析表就不难了. #a ,b,a# r3 #E ,b,a# s5 #E, b,a# s4 #E,b ,a# r4 #E,E ,a# s5 #E,E, a# s3 #E,E,a # r3 #E,E,E # r2 #E,E,L # r1 #E,L # r1 最右推导（规范推导） #L # acc

3. LR(0)项目集1 #E  , b , a # s5 #E ,  b , a # s4 由活前缀不含句柄右侧符号得：其与当前句柄的关系分为: 1）句柄全部在活前缀中且句柄是活前缀的后缀 #E , b  , a # r4 2）活前缀只含句柄的部分符号 # T *  1 + 2 # s2 3）活前缀不含任何句柄符号 #E  , b , a # s5 #E ,  b , a # s4

LR(0)项目的分类 1）归约项目: 形如A →   (可为空串) 句柄全部在活前缀中且句柄是活前缀的后缀 2）移进项目: 形如A    X , ( XVT,可为空串) 活前缀只含句柄的部分符号 3）待归约项目: 形如A    X , ( XVN, 可为空串) 活前缀不含任何句柄符号

LR(0)项目集3 例 SA | B AaAb | c BaBb | d 为方便识别, 引入新开始符S’及产生式S’ S,得到拓广的方法G’，求LR(0)项目 0. S’  S 1. S  A 2. S  B 3. A  aAb 4. A  c 5. B  aBb 6. B  d

4.识别所有规范句型全部活前缀的DFA 首先,初态I0含有项目S’→●S,期待将要扫描一个符号串恰好匹配S.由于S是VN符,不可能从输入串中读出,因此应把可能构成S的产生式相应的的项目S→●A及S→●B列入项目集中; 同理,由A,B为VN符,应将A→●aAb, A→●c, B→●aBb, B→●d放入项目集中.因此,I0由如下项目组成: S’→●S, S→●A, S→●B, A→●aAb, A→●c, B→●aBb, B→●d 其中, S’→●S称为基本项目.从S’→●S出发构造整个项目集的过程为求基本项目的闭包过程,即整个项目集称为基本项目集的闭包CLOSURE({S’→●S})

求项目集闭包的算法 设I为一项目集,构造I 的项目集闭包CLOSURE(I)的算法如下: 1. I CLOSURE( I ) 2. 若A→XCLOSURE(I), XVN, 则任何X-产生式 X→P, XCLOSURE(I) 3.重复上述过程,直到CLOSURE(I)不再增大

5. 构造DFA的方法1 有了初态I0,为求下一状态的方法是: 设I为一状态,X∈V,且A →  X  I, 当分析器识别出X后,将进入下一状态Ii且必含有项目A →X  (称为项目A →  X 的后继) 对于整个项目集而言,关于X的后继可能有多个,将其合并在一起构成集合J (即下一状态Ii的基本项目),再通过求闭包得出Ii全部项目: Ii =CLOSURE( J ) 为指明Ii是I的后继,记GO(I,X)= Ii

构造DFA的方法2 例 SA | B AaAb | c BaBb | d

构造DFA的方法3 重复上述构造新状态的过程,我们可得到全部的状态,其集合称为方法G的LR(0)项目集规范族,记为C(上例中,C={I0,I1,…,I10}); 至此,我们所要构造的识别方法G[S]全部活前缀的DFA为: M=(C,V,GO,I0,C);其中, 状态集及终态集为项目集规范族C; 字母表为V=VN∪VT∪{S’} 初态为I0; 转换函数为GO;

6. LR(0)分析表的构造 每个项目集代表了分析过程中的一个状态,且其每个项目与分析动作相关.因此要求每个项目集的诸项目是相容的,即在同一项目集中,不应出现: 1.移进项目与归约项目并存; 2.多个归约项目并存. 若文法G满足上述条件,即不含上述冲突项目,则称G为LR(0)文法. 显然,只有当一文法是LR(0)文法时,才能构造出无冲突动作的分析表来.

LR(0)分析表的构照方法如下: (1)A→X项目,若GO(Ii,X)= Ij 若X∈VT,则置ACTION[i,X]=sj, 否则(X∈VN),置GOTO[i,X]=j; (2) A→项目属于Ii,且A→是P中第j产生式,则对于aVT{#},置ACTION[i,a]=rj (3)若接受项目S’ →S·属于Ii,则置ACTION[i,#]=“acc” (4)在表中其它未填入信息的栏目中均填“ERR”. 在存储ACTION表时,可用正负值分别表示归约和移进.

例子 文法G[S]的扩展文法 0. S’->S 1. S-> A 2. S-> B 3. A-> aAb 4. A-> c 5. B-> aBb 6. B-> d

文法G[E]: EE + T ET TT * F TF F(E) Fid

Chapter4.2.4 LR分析方法 SLR(1) 分析表的构造 Contruction of Analysis Table for Simple Left-to-right Right-derivation(SLR) Parsing

上一节课回顾 LR(0)分析表 构造DFA识别 所有规范句型的 全部活前缀 规范句型的活前缀 (viable prefix)

提纲 LR(0)的问题 LR(0)问题分析 LR(0) 冲突的解决思路 SLR(1)规则 SLR(1)分析表 SLR(1)文法 例子

1. LR(0)的问题 G[B]: B → { D ; S } D → D ; d | d S → t ; S | t 常见程序设计语言都不是LR(0)的,所以LR(0)分析表缺乏实用性 例如 G[B]: B → { D ; S } D → D ; d | d S → t ; S | t

识别G[B]活前缀的DFA：构造-1 G[B]: B → { D ; S } 0. B’ → B D → D ; d | d S → t ; S | t G[B]的拓广文法G[B’]: 0. B’ → B 1. B → { D ; S } 2. D → D ; d 3. D → d 4. S → t ; S 5. S → t

识别G[B]活前缀的DFA：构造-2 I0 B’ →  B B →  { D ; S } 增加红色虚线，以表达完全的DFA 基本项目（特殊的核心项目） 待归约项目 B’ →  B B →  { D ; S } I0 移进项目 增加红色虚线，以表达完全的DFA

识别G[B]活前缀的DFA：构造-3 B → {  D ; S } D →  D ; d D →  d I0 B’ →  B 核心项目 { 待归约项目 I1 B → {  D ; S } D →  D ; d D →  d 待归约项目 移进项目 每一状态都是终止状态， 表明识别了一个活前缀（分析栈中的内容）

识别G[B]活前缀的DFA：构造-4 B’ → B  # B # I0 I11 接受项目 I0 B’ →  B B →  { D ; S } 接受项目 归约项目 B 核心项目 # B’ 句 I11 B’ → B  归约项目对应的状态为 句柄识别状态 # B I0 I11 #

识别G[B]活前缀的DFA：构造-5 { ; d I3 I2 D → d  I3 { B → { D  ; S } D D → D  ; d D I1 B → {  D ; S } D →  D ; d D →  d { I1 d ; d d I3 I2 D → d  I2 D → d D * D 归约项目 句 归约项目对应的状态为 句柄识别状态

识别G[B]活前缀的DFA：构造-6 B → { D ;  S } D → D ; d D → D ;  d S →  t ; S I1 I3 { D B → { D  ; S } D → D  ; d ; d I4 B → { D ;  S } D → D ;  d S →  t ; S S →  t I5 D → D ; d * D 句

识别G[B]活前缀的DFA：构造-7 ; I6 t S → t  ; S S → t  ; * S t I7 S → t ;  S B → { D ;  S } D → D ;  d S →  t ; S S →  t ; t * S S → t ;  S S →  t S →  t ; S I7 发现 什么问题？ 句

LR(0)分析表 状态 ACTION GOTO { d ; t } # B D S S1 11 1 S2 3 2 S1 11 1 S2 3 2 R3 R3 R3 R3 R3 R3 3 S4 4 S5 S6 9 5 R2 R2 R2 R2 R2 R2 6 R5 R5 S7,R5 R5 R5 R5 7 S6 8 8 R4 R4 R4 R4 R4 R4 9 S10 10 R1 R1 R1 R1 R1 R1 11 acc

2. LR(0)问题分析-分析栈的动作冲突1 S … t ; … {;}  {*} =  ? 分析栈动作 可能冲突？ 归约 移进 Let me do which one? S Y … t ; … S → t ;  S ; S → t  ; S S → t  句 * S {;}  {*} =  ?

2. LR(0)问题分析-分析栈的动作冲突2 a b M … N M -> ab  N -> ab  分析栈动作 可能 冲突？ 归约 移进 a b M … N do which one? Y Y * M M -> ab  N -> ab  句 * N {*}  {*} =  ?

2. LR(0)问题分析-分析栈的动作冲突：小结 分析栈动作 可能冲突？ 归约 移进 . . . a b … Y … Y . . ab b a M -> a  b N -> a  b …

3. LR(0) 冲突的解决思路- 归约vs移进 {;}  {follow} =  分析栈动作 冲突的解决思路 归约 移进 不要盲目归约 I6 S → t ;  S ; S → t  ; S S → t  句 follow S {;}  {follow} = 

3. LR(0) 冲突的解决思路- 归约vs归约 M -> ab  N -> ab  分析栈动作 冲突的解决思路 归约 移进 不要盲目归约 不要盲目归约 follow1 M M -> ab  N -> ab  句 follow2 N {follow1}  {follow2} = 

follow(S) = first(})= {}} 3. LR(0) 冲突的解决-寻找follow S S -> t  ; S S -> t  I6 }… ‘}’ … t ; … follow(S) = first(})= {}} ACTION GOTO { d ; t } # B D S 状态 6 R5 R5 S7,R5 R5 R5 R5 6 S7 R5

3. LR(0) 冲突的解决-寻找follow M M -> ab  N -> ab  {d} d … {e,f,#} S → M D | N E K M → a b N → a b D → d E → e | ε K → f | ε N follow(M) = first(D) = {d} follow(N) = first(E) U follow(E)

4. SLR(1)规则-1 Ii={ A1→·a11 ,…, Am→·amm, B1→· ,…, Bn→· } 当集合FOLLOW(Bk)(1≦k≦n)与{a1,a2,…,am}两 两互不相交时, 则可按下述方法解决冲突:

4. SLR(1)规则-2 不盲目归约 aVT{#}, ACTION[i,a]=SJ if a{a1,a2,…,am} ACTION[i,a]=R(BK) if aFOLLOW(BK) ACTION[i,a]=“ERR” [otherwise] 不盲目归约

5. SLR(1)分析表 状态 ACTION GOTO { d ; t } # B D S S1 11 1 S2 3 2 R3 S1 11 1 S2 3 2 R3 R3 R3 R3 R3 R3 R3 3 S4 4 S5 S6 9 5 R2 R2 R2 R2 R2 R2 R2 6 S7 R5 R5 R5 S7,R5 R5 R5 R5 7 S6 8 8 R4 R4 R4 R4 R4 R4 R4 9 S10 10 R1 R1 R1 R1 R1 R1 R1 11 acc

6. SLR(1)文法 对于给定的文法G,若按SLR(1)规则构造的SLR(1)分析表无冲突项, 则称G是SLR(1)文法.

7. LR(0) 冲突识别的方法1-DFA 从活前缀DFA中查找归约项（归约子状态），是否有形如： S -> t  ; S M -> ab  N -> ab 

7. LR(0) 冲突识别的方法2-分析表 单元格中有两项

8. 例子 G[S]是否为SLR(1)文法，其扩展文法G[S’]，如下： 0. S’ → S 1. S → a A 2. S → b B 3. A → c A d 4. A →  5. B → c B d d 6. B → 

Chapter4.2.4 LR分析方法 LR(1) 分析表的构造

提纲 GO函数及DFA的构造方法 SLR(1)的问题 SLR(1)问题分析 LR(1)项目 LR(1)项目集闭包算法 LALR(1)分析简介 关于各类文法的一些结论

1. SLR(1)的问题 G[S]的拓扩文法 0. S’→S 1. S→AaDC 2. C→Cba 3. C→ba 4. D→A 5. D→Ba 6. A→b 7. B→b 请同学们动手画出 识别G[S]的全部活前缀的DFA

是否存在冲突？ 冲突能由SLR(1)规则解决吗？

2. SLR(1)问题分析 活前缀-状态机 动作冲突有： SLR(1)对于归约项目A→ 归约-归约 归约-移进 归约-归约 归约-移进 SLR(1)对于归约项目A→ 只要输入是FOLLOW(A)中的单词，就归约 这也有一定的片面性,没有考虑所在的“环境”. 我们称SLR(1)的FOLLOW为静态FOLLOW 而LR(1)就是将静态FOLLOW改成动态FOLLOW 动态FOLLOW 是静态FOLLOW的子集

SLR(1)问题分析 对于上述文法的规范句型Aababa,当分析达到格局 # A a b aba 由于输入符a∈FOLLOW(A), 若用A->b来归约,得到 # A a A aba 但AaA不是任何规范前缀! 因此在移进a之前,分析将报错.

3. LR(1)项目 因此,将#a归约成#Aa…的前提条件不仅仅是要求a∈FOLLOW(A),还必须要求Aa是某规范句型的前缀. 为了确保上述条件,应在原来的每个LR(0)项目[A]中放置一向前搜索符号a: [A,a],称为LR(1)项目. 向前搜索符号a，记录当前LR(1)项目所处的环境

4. LR(1)项目集闭包算法 类似LR(0)分析,活前缀-DFA的状态是由LR(1)项目集表示 对每个LR(1)项目集I,相应的闭包J的定义为 J := I; repeat J = J ∪ { [ B →.η, b ] ｜ [ A → α.Bβ, a ] ∈ J, b ∈ FIRST( βa ) until J 不再扩大 有可能 β→ ε，此时 b = a

5. GO函数及DFA的构造方法 为求GO(I,X), I为LR(1)项目集,X∈V: GO(I,X)=CLOSURE(J) 其中, J={[ AX , a ] | [ AX , a ] I} 注意,每个LR(1)项目与其后继项目有相同的搜索符号

例：LR(1)项目集及DFA G[S]的拓扩文法 0. S’→S 1. S→AaDC 2. C→Cba 3. C→ba 4. D→A 5. D→Ba 6. A→b 7. B→b

6. LALR(1)分析简介 简化 LR(1) 分析 减少资源开销 ( lookahead-LR ) 在不带来移进-归约冲突的条件下，合并状态，重构分析表 可行性（合并条件） LR(1) 项目有相同的 LR(0) 项目，但后继符可能不同 (可能带来归约-归约冲突)

LALR(1)分析简介 高于 SLR(1) 分析 合并的后继符仍为 FOLLOW 集的子集 局限性 合并中不出现归约-归约冲突

7. 关于各类文法的一些结论 各文法类之间的关系见P172图4-24 任何LR(K),LL(K)及简单优先文法类都是无二义性文法; 任何二义性的文法不可能性是LR(K)文法,但借助其它方法,可对某些二义性文法建立无冲突的LR(K)分析表; LR(0) < SLR(K)<LALR(1)< LR(K)

习题 4-38: (1),(2),(3),(4) 4-37 4-41