| 【编译原理】笔记 | 您所在的位置：网站首页 › ab前缀的意思 › 【编译原理】笔记 |
【编译原理】笔记
|
第一章
编译分了哪些阶段，每个阶段的任务 例如：变量检查重复定义在什么阶段 要前后连贯起来，要知道每个阶段的任务 第二章 给一个正规式，转成 NFA DFA 最小化一句话翻译成正规式词法分析的任务、输入输出什么内容，输出给语法分析来用用正规式这样形式化的方式进行词法形式化的表达，正规式的代数性质，如何证明两个正规式等价 第三章 词法分析、语法分析，两种自动机模型，及其对应文法 下推自动机：上下文无关文法有限自动机文法分级：0 1 2 3 两种语法分析方式 自上而下：从文法的开始符号，反复使用产生式，使用产生式的右部替换左部自下而上：使用产生式的左部替换右部，使用句柄给你一个文法，什么是短语，什么是直接短语，什么是句柄LL1 文法 first 、folllow 集预测分析表，证明该文法是 LL1 文法 自上而下 二义文法，如何证明一个文法是二义文法：找一个句子，能画出两个不同的语法树，这就是二义文法问题：左递归（死循环）、公共左因子（回溯） 自下而上 构造 SLR1 分析表 第四章 语义规则：两种表示方法 语法制导的定义语法制导翻译，直接生成代码 属性文法来表示语义 属性的计算次序 综合属性继承属性 继承属性的计算和自下而上生成语法树的过程一致（？）对符号表进行操作，完成说明性语句的执行 语义分析的核心是生成中间代码 逆波兰式 要会 加减乘除，与或非，改变优先级之后的写法按照不同的优先级转成中缀式、前缀式 三地址码树和图 短路计算 会用拉链回填技术，写出短路计算生成的代码，序号要准确不需要定义中间过程的语义 要会画注释树 给了语义规则，在规约的同时计算出表达式的值。 绪论 语言翻译与编译程序编译是把源语言程序，转换为目标语言程序的程序，后者与前者 在逻辑上等价 现在特指把高级语言程序转换为机器能够理解的低级语言 逆向工程： 从汇编语言到高级语言 编译器和解释器特点 编译器：工作效率高，可移植性差、交互性差所采用的技术： 从翻译的角度来讲，两者基本相同 编译程序的工作原理与基本结构程序的层次结构： 程序 子程序或分程序 语句表达式 算符、引用 通用程序设计语言的主要成分语法 词法规则 单词符号的形成规则 （标识符、关键字） 语法规则 如何从单词符号形成更大的结构 语法 规则是语法单位的形成规则 说明性语句、操作语句 编译的基本过程 词法分析语法分析语义分析与中间代码生成代码优化目标代码生成 词法分析从左到右逐个字符读入源程序，，对构成源程序的字符流进行扫描和分解，识别出一个个单词，把作为字符串的源程序改造为单词符号串的中间程序 2.1 词法分析中的若干问题 记号、模式与单词单词的基本分类 关键字标识符字面量 数字量、字符量、逻辑量、宏定义 运算符分隔符模式：产生和识别元素 （构词）规则 记号（token）： 按照模式，识别出的元素 单词 （lexeme）： 被识别出的元素自身的值，称为词值 过滤掉源程序的无用成分（注释、空格、回车）处理与具体平台有关的输入 （文件结束符的不同表示）识别记号，交给语法分析器，根据模式识别记号调用符号表管理器或出错处理器 模式的形式化描述 语言语言是有限字母表上有限长度字符串的集合 与一般意义上的集合不同，有序 正规式与正规集 （正则表达式）乔姆斯基体系 令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下: 1. ε是正规式，它表示集合L(ε)={ε} 2. 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a} 3. 若正规式r和s分别表示集合L®和L(s)，则 （a） r|s是正规式，表示集合L®∪L(s)， （r 或 s 出现） （b） rs是正规式，表示集合L®L(s)， （r 和 s 连接） （c） r*是正规式，表示集合(L®)*，(闭包 r 出现任意次) （d）®是正规式，表示的集合仍然是L® 可用正规式描述的语言称为正规语言或正规集。 正规式与正规集是一对多的关系 正规式 正规集 a，b，c {a}，{b}，{c} a|b，b|a {a}∪{b}={a，b} a(a|b)* {a，aa，ab，aba，abb，aab，…}，a为首的ab串 ∑* {ε，a，b，c，aa，ab，ac，ba，bb，bc，…} 记号的定义记号 = 正规式 记号是正规式 relation = < | | >= | = id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z) (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z |0|1|2|3|4|5|6|7|8|9)* num = (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* (ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*) (ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*) 简化的正规式 正闭包 r+可缺省 r? = r|e字符组 [abc] [0-9a-z]非字符组 [^abc] 辅助定义式 3有限自动机 模式的描述——正规式记号的识别——有限自动机根据下一个状态是否确定，自动机分为确定有限自动机，非确定有限自动机 确定型速度快，但占用资源更多 状态转化图
识别标识符的状态转化图 不确定的有限自动机Nondeterministic Finite Automaton ，NFA） NFA是一个五元组（5-tuple）： M =（S，∑，move，s0，F），其中 S是有限个状态（state）的集合； ∑是有限个输入字符（包括ε）的集合； move是一个状态转移函数，move(si，ch)=sj 表示，当 前状态si下若遇到输入字符ch，则转移到状态sj； 不确定性的表现：转移到的状态可以不唯一 s0是唯一的初态（也称开始状态）； F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。 直观的表示方式： 状态转换图
如何 识别记号：对于字符串，从初态开始，经过一系列的状态到达终态 状态转换矩阵
第i 个状态，遇到字符 a 变成第 j 个状态 例如： (a|b)*abb：
不是处处有定义的：偏函数
第一个填空题，第二个选择题，第三个判断题 NFA 当前状态下对同一字符有多于一个的下一状态转移 不确定性的表现： 定义：move 函数是 1 对 多 的转换图：同一状态有多于一条边标记相同字符转移到不同的状态 确定的有限自动机没有状态具有 ε 状态转移（ε-transition），即状态转 换图中没有标记 ε 的边； 对每个状态 s 和每个字符 a ，最多有一个下一状态。（可以没有转移） 从正规式到词法分析器1.描述：用正规式对模式进行描述； 2.构造****NFA：为每个正规式构造一个NFA； 3.确定化：将NFA转换成等价的DFA； 4.最小化：优化DFA，使其状态数最少； 5.构造词法分析器：由DFA构造词法分析器。 给定一个正规式，构造出最小化的完整过程 必考 Lec 工具实现了构造算法 有规范的一对一算法能构造出 NFA 自动机等价的概念： 如果 ：L(M1) = L(M2) 自动机识别的语言相同 它们识别同一个正规集，则称这两个自动机相等 定理： 一定存在一个确定型有限自动机和非确定型优先自动机等价 由正规式构造 NFATompson 算法 必考 首先分解正规式 对于 ε 直接构造 从 S0 到 f 对于 Σ \Sigma Σ 上的每一个字符 ，构造 N ( a ) N(a) N(a) 接受 a
若 N§ N(q) 是正规式 p q 的 NFA 对于 p|q
引入新的初态 s0 和终态 f，原来的专业关系不变，新增四个空转移 对于 pq
对于 p*
闭包运算，出现 0 次或多次 构造新的 NFA 最多增加两个状态 从 NFA 到 DFA 的转换这一过程也叫 确定化 从 NFA 构造识别同样语言的 DFA 的算法称为子集构造法 让新构造的 DFA 的每一个状态，代表 NFA 的状态集 消除空转移，——求闭包扩展状态转移函数，消除多于一个的下一状态转移 DFA 的化简等价状态的概念 如果从两个不同的状态出发，经过一系列同样输入序列转化为同样的终态，则这两个状态是等价的 算法 初始划分：划分为终态和非终态利用可区分的概念，反复划分 （看是否落回集合自身）由最终划分构造 D·消除可能的死状态和不可达状态2019 04 16 第三章 语法分析 语法规则：上下文无关文法语法分析：下推自动机，自上而下和自下而上分析
CFG 是一个四元组 G = (N, T, P, S) N 是非终结符的有限集合 （可以出现在产生式左边符号的集合） T 是终结符的有限集合 （可以出现在产生式左边符号的集合） P 是产生式(Productions) 的有限集合 A → a A\to a A→a S 是非终结符，称为文法的开始符号，一般出现在第一个产生式的左部 上下文无关是指完成产生式的替换之后，不影响表达式的正确性 例子： 简单算术表达式的上下文无关文法的表示
终结符与非终结 符书写上的区分 (a) 用大小写区分： E → id (b) 用" "区分： E → “id” E → E “+” E © 用< >区分： → + 教材约定：大写英文字母A、B、C表示非终结符； 小写英文字母a、b、c表示终结符； 小写希腊字母α、β、δ表示任意文法符号序列 产生式的缩写 当多个产生式的左部非终结符相同时，可合并为一个产生式。新的产生式的左部是此非终结符，右部是所有原来右部的或运算（并集合）使用符号 | 产生式通过推导的方法来产生语言 推导的形式化定义： 直接推导：用产生式的右部替代文法符号序列中的元素推导具有自反和传递性 上下文无关语言 由终结符构成的串，叫做 句子 由终结符和非终结符构成的串，叫做 句型 在推导过程中，如果每次直接推导均替换句型中最左边的非终结符，则成为最左推导。由最左推导产生的句型称为：左句型 一个给定的文法可以唯一确定他所产生的语言，但是对于一个给定的语言来说，可以用若干不同的文法来产生。
改写二义文法为非二义文法 算符优先文法：越靠近文法的开始符号，优先级越低 新引入的非终结符，限制了 每一步直接推导均有唯一选择非终结符的引入，增加了推导步骤如何改写【 引入新终结符，增加一个子结构，提高一级优先级 递归非终结符在终结符左边，运算具有左结合性，否则具有有结核性 消除文法的左递归建立语法数的时候会在左分支陷入死循环 提取左因子消除回溯，凡是前面相同的，将其提取，其右部合成为新的非终结符 当既含有左递归，又含有左因子时，先消除左递归 递归下降分析状态图的化简： 标记为 A 的边等价于标记 e 的边转向 A 转换图的初态 标记相同的路径可以合并 不可区分的状态可以合并 预测分析器非递归预测分析器的工作模式 分析方法：格局与格局变换分析表+驱动器预测分析表的构造LL文法 (无左递归，无公共左因子) 预测分析表最左一列：所有的非终结符 最上一行：所有的终结符 M[A,a] 若当前栈顶是非终结符 A，下一输入终结符是 a 则 M[A,a] 指示下一步的动作 如何扩展？将 M 入栈 （反序进栈） 匹配终结符展开非终结符报告分析成功工作方式 从初始格局开始，经过一系列的格局变化，最终到达接受格局，表明分析成功 到达出错格局，表明发现一个错误 格局： 格局是一个三元组：栈内容，当前剩余输入，改变格局的动作 改变格局的动作 匹配终结符：当前是终结符，且栈顶是终结符，那么栈顶出栈展开非终结符：当前是终结符，栈顶是非终结符，非终结符出栈，查表反向入栈报告分析成功：栈顶和当前都是结束符 #报告出错：所有其他情况 构造预测分析表first 集合 First( α \alpha α) 是一个串经过一步或多不推导之后，在句型头部最左边出现的终结符 follow 集合 FOLLOW（A） 是所有句型中，能紧跟在非终结符 A后面的终结符 a First 集合计算算法 如果 x 是终结符 firstx = xx是非终结符，且 x-> y1y2y3, 那么 x 的first 集与 y1 的first 集相同，特别的，如果 y1 可以推出空串，那么 x 的first 集还包含y2 的first 集， 以此类推Follow 集合计算算法 # 是 S 的FOLLOW 集合如果有 A-> aBb, first b 的全体加入 folllow B如果A->aB 那么 FOLLOW A 的全体加入 FOLLOW B自下而上计算 FIRST， 自上而下计算 FOLLOW 怎么填表
L: 自左向右读入 L: 最左推导 1：只向前看1个字符 当且仅当构造的预测表中不含多重定义的条目，这种语言叫做 LL（1）语言 如何判断： 构造分析表 没有多入口的分析表 自下而上的语法分析 自上而下：从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导递归下降分析：对每一个语法变量构造一个响应的自身徐，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别自下而上分析法： 从输入串开始，逐步 规约 直到文法的开始符号，从树的末端开始，构造语法树 规约： 规矩文法的产生式规则，把产生式的右部替换成左部符号 LR分析法：从左到右读入输入串，最右推导的逆过程 思路： 从左到右扫描。反复用产生式的左部替换产生式的右部，谋求对输入串的匹配，最终得到文法的开始符号。 规范规约与 「剪句柄」
短语是句型中的某部分
把输入符号进栈，如果栈顶元素可规约，那么就规约 句柄总是在栈顶形成（最左规约） 栈中保留的总是一个右句型的前缀（活前缀） 最左规约是逻辑上从下到上构造一颗语法数，从下到上为语法数剪句柄 需要解决的问题 如何保证栈中总是活前缀如何确定栈顶已经形成句柄并选择正确的产生式进行规约找句柄：找树中最左，最深的子树 规范规约是一个 最右推导的逆过程 最左规约 是 规范推导 由规范推导推出的句型，称为规范句型 移进规约： 用一个栈，记住规约句柄的前缀，句柄未形成，向前移进
把「历史」和「展望」综合抽象成状态，由栈顶的状态和现行的输入符号唯一确定每一步动作 LR 分析器的核心是分析表 LR 分析表的构造句柄都是在活前缀中出现的，在句柄之上不可能出现其他符号 构造一个可以识别文法中所有活前缀 的 DFA 活前缀：出现在移进-规约分析器栈中的右句型的前缀 右句型的前缀已经在分析栈中 LR(0) 项目集族的构造 字的前缀：字的任意首部活前缀：不含句柄之后的符号项目：在所有产生式的所有位置分别加一个点 .每个项目显示了分析过程中看到（移进）了产生式的多少， A → α . β A\to\alpha.\beta A→α.β β \beta β 不为空的项目称为可移进项目 β \beta β 为空的项目称为 可规约项目. 点 到达最右方的时候，表示产生了句柄构造活前缀的 NFA 若状态i ： LR(0) 分析表的构造
在同一状态中，若既有可规约项目，又有可移进项目时，存在移进和规约的冲突 如果存在两个可规约项目，即存在规约和规约的冲突 **解决办法：**简单向前看一个终结符 如果冲突可以解决，文法为 SLR(1) 文法 ：简单的 LR 分析法
如果 SLR(1) 无法解决冲突， 那么每个项目需要带上 k 个终结符，这样一个项目称为 LR(k) 项目 语法制导翻译与中间代码生成语法制导翻译是处理语义的基本方法，它以语法分析为基础，在语法分析得到语言结构的结果时，对附着于此结构的语义进行处理，如计算表达式的值、生成中间代码等。 简介语法和语义 语法是语言的结构（样子）语义是附着在语言结构上的实际含义 ①语义不能离开语法独立存在； ②语义远比语法复杂； ③同一语言结构可包含多种含义，不同语言结构可表示相同含义； ④语法与语义之间没有明确的界线。 语义分析的两个作用 ①检查是否结构正确的句子所表示的意思也合法； ②执行规定的语义动作，如： õ表达式求值 õ符号表填写 õ中间代码生成等 语义分析的方法 语法制导翻译 程序的动态语义：公里语义、操作语义、指称语义，程序的动态语义不适用属性文法描述 语法制导翻译通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。 具体方法： ①将文法符号所代表的语言结构的意思，用附着于该文法符号的属性表示； ②用语义规则规定产生式所代表的语言结构之间的关系（即属性之间的关系），即用语义规则实现属性计算。 语义规则的执行：在语法分析的适当时刻（如推导或归约）执行附着在对应产生式上的语义规则，以实现对语言结构语义的处理，如计算、查填符号表、生成中间代码、发布出错信息等。 属性文法在上下文无关文法的基础上，为每个文法符号，配 备若干相关的属性 属性代表与文法符号相关的信息，类型、代码、符号表属性可以进行计算和传递语义规则：对文法的每个产生式都配备了一组属性的计算规则说明 终结符只有综合属性，由词法分析器提供非终结符既可以有综合属性，也可以有继承属性 LR 分析翻译LR 分析中的语法制导翻译实质上是对LR 语法分析的扩充 扩充 LR 分析器的功能 规约时执行语义动作 扩充分析栈 增加了与分析栈并列的语义栈，存放分析栈中文法符号对应的属性值 中间代码中间代码生成器输出的中间表示 中间代码的主要形式：树、后缀式、三地址码 后缀式操作数在前，操作符紧随其后，不需用括号限制运算的优先级和结合性 三地址码1.三地址码的直观表示 语法： result := arg1 op arg2 或 result := op arg1 或 op arg1三地址码的种类
三地址码的实现 三地址码四地址码 图形表示 树作为中间代码树的语法制导翻译树和其他中间代码的关系 对树进行后序遍历，得到后缀式树的每个内部节点和他的孩子对应一个三元式或四元式 声明语句的翻译 变量的声明 变量的类型定义与声明 类型定义： 为编译器提供存储空间大小的信息变量声明： 为变量分配存储空间 变量声明的文法填写符号表信息的语法制导翻译 全程量 offset：记录当前符号存储的偏移量属性.type 和 .width 变量的类型和所占据的空间过程 enter(name, type , offset) 为 type 类型的变量 name 建立符号表条目，并为其分配存储空间要考的：布尔表达式的短路计算 加油! 感谢! 努力! |
【本文地址】