编译原理总结-1 第3~5章
编译器的结构 词法分析 语法分析 语法制导翻译 源程序 … 目标程序
词法分析 逐个读构成源程序的字符，把它们组成词法单元 (token)流。 实例：position = initial + rate * 60 （２）赋值号（=） （３）标识符（initial） （４）加号（＋） （５）标识符（rate） （６）乘号（＊） （７）数（60）
词法分析的主要方法 正则表达式 NFA DFA
正则表达式 元字符 代码 说明 . 匹配除换行符以外的任意字符 \w 匹配字母或数字或下划线或汉字 \s 匹配任意的空白符 \d 匹配数字 \b 匹配单词的开始或结束 ^ 匹配字符串的开始 $ 匹配字符串的结束 代码/语法 说明 * 重复零次或更多次 + 重复一次或更多次 ? 重复零次或一次 {n} 重复n次 {n,} 重复n次或更多次 {n,m} 重复n到m次
正则表达式 贪婪与懒惰 表5.懒惰限定符 代码/语法 说明 *? 重复任意次，但尽可能少重复 +? 重复1次或更多次，但尽可能少重复 ?? 重复0次或1次，但尽可能少重复 {n,m}? 重复n到m次，但尽可能少重复 {n,}? 重复n次以上，但尽可能少重复
关系转换图 开始 letter other letter或digit return(install_id()) 识别标识符的关系转换图 11 9 10 11 开始 letter other * letter或digit return(install_id())
NFA与DFA 形式化定义 NFA：一个符号标记离开同一状态有多条边 DFA：一个符号标记离开同一状态只有一条边
从正则表达式到DFA 正则表达式到NFA NFA到DFA DFA的最简化 直接构造 McMaughton-Yamada-Thompson算法 子集构造法 DFA的最简化
子集构造法 ε-closure(s) 从NFA的状态S出发，只用ε转换就能到达的状态 的集合 ε-closure(T) 从NFA的状态集合T中每个状态出发，只用ε转换 就能到达的状态的集合 Move(T,a) 状态集合T中每个状态通过a能到达的所有状态集 合 1 9 开始 a b 6 7 8 2 3 4 5
语法分析 把词法记号流依照语言的语法结构按层次分组，以 形成语法短语。 实例： position = initial + rate * 60 的语法分析树
上下文无关语言 形式化定义 0~3型形式语言
语法分析处理技术 预处理 自顶向下分析 自顶向上分析 左递归 左公因子 LL(1)文法 LR文法 FIRST集合 FOLLOW集合 SLR LALR
LL(1)文法 求FIRST集合 求FOLLOW集合 基于FIRST集合，构建预测分析表 只有遇到ε时，才需要考虑FOLLOW集合
LR文法 移进-归约分析 SLR 规范的LR 构建可行前缀的DFA 基于DFA构建预测分析表 重新定义项目，让它带上搜索符，成为如下形式 [A->a·b,c]
LALR LALR和SLR的分析表有同样多的状态，比规范LR 分析表要小得多 LALR的能力介于SLR和规范LR之间
语法制导翻译 对语法树进行语义分析 例如：将中缀表达式转化成为后缀 语法制导定义 语法制导翻译方案 9 - 5 + 2 -> 9 5 – 2 +
属性文法 通过把属性附加到代表语法结构的文法符号上，将 语义信息和程序设计语言的语法结构联系起来，属 性的值是用与文法产生式相联系的语义规则来计算 的 语法制导定义SDD：文法产生式和语义规则分开 说明关于语言翻译的高层次规格，隐藏了许多具体实现细节，使用户不必显式地说明发生的顺序 语法制导翻译方案SDT：文法产生式和语义规则交 错 把语义规则用{}括起来，插入到规则右部的合适位置上，指明了语义规则的计算顺序，以便说明某些实现细节
L属性与S属性 L属性翻译方案（L代表从左到右） S属性翻译方案（S代表综合） 包含了所有不必显式构造语法分析树即可完成的翻译方案，即可以在语法分析过程中完成的翻译方案 S属性翻译方案（S代表综合） 可以很容易和自底向上语法分析（如LR语法分析）过程联系起来的L属性翻译方案
综合属性和继承属性 综合属性 继承属性 语法分析树结点N上的非终结符A的综合属性是由N上的产生式所关联的语义规则定义的 语法分析树结点N上的非终结符B的继承属性是由N的父结点上的产生式所关联的语义规则定义的 这个产生式的体中一定包含非终结符B；结点N上的继承属性只能通过其父节点、其本身及其兄弟结点上的属性值来定义