机器语言 ---> 汇编语言(助记符 MOV...) ---> 高级语言(不依赖于特定机器)
机器语言 --- > 汇编语言或高级语言的过程 :
编译系统的结构
image-20210830163918375语义分析(Semantic Analysis)
语义:中间表示,独立于表示语言
编译器的结构
image-20210830164732319主要任务:从左向右逐行扫描源程序的字符,识别出各个单词,确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元(Token)形式
image-20210830165359571举个例子
image-20210830165538515😃 如何实现词法分析器?
从词法分析器输出的token序列中识别出各类短语,并构造语法分析树(parse tree)
举个例子
image-20210830170121279主要任务:
- 收集标识符的属性信息
- 种属Kind:简单变量、复合变量、过程
- 类型Type: 整型、字符型...
- 存储位置、长度
- 值
- 作用域
- 参数和返回值信息
符号表:用于存放标识符的属性信息的数据结构
- 语义检查
- 变量或过程未经声明就使用
- 变量或过程名重复声明
- 运算分量类型不匹配
- 操作符和操作数之间的类型不匹配
三地址码(Three-address Code)
由类似汇编的指令序列组成,每个指令最多由三个操作数(operand)
常用的三地址指令
image-20210830171023260三地址指令的四元式表示
image-20210830171111052举个例子
image-20210830172102677语法结构树/语法树(Syntax Tree)
字母表:一个有穷符号集合
乘积、n次幂、正闭包、克林闭包
串:字母表中符号的有穷序列(空串的长度为0)
连接(connection):y附加到x后面形成的串,xy
空串是连接运算的单位元
image-20210830172522935串s的n次幂:将n个s连接起来
文法的形式化定义
image-20210830172924632Vn 非终结符:用来表示语法成分的符号(“语法变量”)
image-20210830173602635S:开始符号,表示该文法中最大的语法成分
image-20210830174100349符号约定
image-20210830174146387
image-20210830174157061
image-20210830174324785推导Derivations和规约Reductions
image-20210901172339176
image-20210901172605747
image-20210901172850226归约是推导的逆过程
句型和句子
image-202109011732468380型文法
image-202110261641311360型文法生成的语言是0型语言 L(0)
1型语言
image-202110261643166872型文法
上下文无关文法
image-202110261643471993型文法
正则文法
image-20211026164600834联系
逐级的包含关系,0型文法包含域最广
image-20211026164933836句型的短语
分析树中每一棵自身的边缘 : 该句型的一个短语
直接短语:子树只有父子两代节点,则子树的边缘叫这个句型的直接短语
直接短语一定是某个产生式的右部
产生式的右部不一定是给定句型的直接短语
二义性文法
一个文法可为某个句子生成多棵分析树,则这个文法是二义性的
描述正则语言的更紧凑的方法,按照一定的规则递归构建
image-20211026165918119可以用正则表达式定义的语言叫正则语言或者正则集合
代数规律
image-20211026170108127等价性
image-20211026170141425
image-20211026170231330提供了类似Alias之类的东西
例子
image-20211026170424415Finite Automata
具有离散的输入输出信息和有穷数目的内部状态。根据当前的状态和面临的输入信息可以决定系统的后继行为(电梯装置)
image-20211026170802603
image-20211026170828588如果存在一个对应于输入串x的从初始状态到某个终止状态的转换序列,称串x被该FA接受![image-20211026171404673](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211026171404673.png)
一个有穷自动机M接受的所有串构成的集合是该FA定义的语言 L(M)
最长子串匹配
输入串的多个前缀与一个或者多个模式匹配时,总是选择最长前缀进行匹配
到达某个终止状态后,只要输入带还有符号,FA就继续前进,寻找尽可能长的匹配
分类
image-20211027143046811DFA 可以用转换图或者转换表表示
image-20211027143449774沿着标记a 的边能达到的状态的集合(不是单一的)
image-20211027143523033
image-20211027143734974等价性
对于任何NFA 都存在识别同一语言的DFA
对于任何NFA 都存在识别同意语言的NFA
带有空边的NFA
image-20211027144532929与不带空边NFA的等价性
image-20211027144650234不同的正则表达式对应的NFA类型
image-20211027145312770
image-20211027145543629
image-20211027150323489You can't use 'macro parameter character #' in math mode \varepsilon-closure(s)$$: 能够从NFA状态s开始只通过$$\varepsilon$$转换到达NFA状态集合 ### 识别标识符的DFA ![image-20211027150803811](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211027150803811.png) 转换 ![image-20211027151105738](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211027151105738.png) 整合多个DFA为一个DFA ![image-20211027151303681](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211027151303681.png) ### 词法分析阶段的错误处理 * 单词拼写错误 int i = 0x3G * 非法字符 ~ @ 如果当前状态与当前输入符号在转换表对应项中的信息为空,则报错,调用错误处理程序 * 查找已扫描字符串中的最后一个对应于某终态的字符 * 找到了,将该字符与前面的字符识别成一个单词。输入指针退回到该字符,扫描器重新回到初始状态 * 没找到,说明出错,采用错误恢复策略 **恐慌模式** 在剩余的输入中不断删除字符,直到词法分析器能在剩余输入的开头发现一个正确的字符为止 ## 自顶至下分析 ### First和Follow集 #### 计算FIRST **First(X)**:可以从X推导出的所有**串首终结符**构成的集合,如果X能推到出e,则e∈FIRST(X) ![image-20211027152208916](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211027152208916.png) 计算方式: * 计算一个符号的FIRST ![image-20211013161156540](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211013161156540.png) * 计算符号串的FISTR ![image-20211013161604282](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211013161604282.png) #### 计算终结符的FOLLOW FOLLOW(A) : 可能在某个句型中紧跟在A后边的终结符a的集合,如果A是某个矩形的最右符号,则把$添加到FOLLOW(A)中 ![image-20211013161756283](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211013161756283.png) 一个终结符的follow集可能依赖于另一个终结符的follow集 ![image-20211027152929030](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211027152929030.png) 算法: ![image-20211013163110606](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211013163110606.png) **注意要迭代更新哦!!!** #### 计算SELECT集合 定义 ![image-20211013164202043](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211013164202043.png) 计算 ![image-20211013164234537](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211013164234537.png) #### LL(1)文法 ![image-20211013164326833](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20211013164326833.png) $$SELECT(A \rightarrow \alpha) \cap SELECT(A \rightarrow \beta) = \phi 其中alpha 和beta不能同时 $$\xRightarrow * \varepsilon$$
注意第一条 ----> α和β的SELECT集就不会相交了
第三条意义:同一非终结符的各个产生式的可选集不相交
- L:从左向右扫描输入
- L:产生最左推导
- 1:每一步只需要向前看一个输入符号来决定语法分析动作
在预测下降分析中,编写每一个非终结符对应的过程时,根据预测分析表进行产生式的选择
为每一个非终结符都要编写递归的下降过程
根据预测分析表构造一个自动机 (表驱动的预测分析)
下推自动机PDA。DFA不能识别下面的例子
image-20211027155042904
image-20211027155343212
image-20211027155414682
image-20211027155533916总结
image-20211027155712340- 栈顶非终结符和当前输入符号不匹配
- 栈顶非终结符与当前输入符号在一蹙额分析表对应项中的信息为空
采用恐慌模式:忽略输入中的一些符号,知道输入中出现由设计者选定的同步词法单元集合中的某个词法单元
例子
image-20211027160145284
image-20211027160429586以消除剩余输入为主
image-20211027161701527
image-20211027161927887一有匹配就归约(以刚进来的为准)
失败情况
image-20211027162628334< IDS >,ib 没有进行规约,错误的识别了句柄
句柄:句型的最左直接短语
image-20211027163000350基本原理
image-20211027163142562状态堆栈 + 输入符号堆栈 + 缓冲符号栈
image-20211027164920571
image-20211027164749977
image-20211027165127289增广文法
image-20211027165227328
image-20211027165405765
image-20211027170026739closure函数
image-20211027170944130
image-20211027171011018goto函数
image-20211027171028416
image-20211027171047696
image-20211027170912641
image-20211027171131963移入/归约冲突
image-20211027171227654归约归约冲突
image-20211027171319095不是所有的CFG上下文无关文法都能用LR0方法进行分析,CFG不总是LR0文法
FOLLOW集帮助判定什么时候规约,SLR(1):向前查看一个符号
image-20211103095603535
image-20211103095819326
image-20211103095927692SLR分析存在的问题
- 仅仅简单考察下一个输入符号是否属于规约项目的FOLLOW集,但不能确保正确的规约
image-20211103100100103
image-20211103100320722