电子科技大学 编译原理期末女娲补天

变量是一个(或多个)存储单元的抽象，赋值语句是修改存储单元内容的抽象。

• 功能域：可访问变量的程序范围
• 生存期：一个储存区绑定于一个变量的时间区间
• 值：变量对应存储单元的内容
• 类型：与变量相关的值类， 以及对这些值的操作说明。


 

• 活动记录：执行单位所需的信息,以及该单元的局部变量所绑定的数据对象的存储区

简答题~

• 实现数据抽象
• 从机器的具体特性中解脱程序员
• 提高编程效率

填空题~ 

• 检查数据对象的类型和操作是否匹配，称为类型检查
  • 静态检查
  • 动态检查



• 顺序


• 选择

 

• 重复

 

• 语句级控制结构分析


规定程序单元之间控制流程的机制 

• 非局部变量 一个程序单元可以引用未被本单元说明而被其他单元说明的变量

int a; int b = 666; a = 666; —— a为非局部变量 可以这么理解？

• 非局部变量绑定于其他的程序单元（定义该非局部变量的程序单元）的活动记录中的数据对象；
• 或非局部变量绑定全局数据区中的数据对象称为非局部环境

  哪俩属于别名？   

程序设计语言是用来描述计算机所执行的算法的形式表示；   


 用英文大写字母表示非终结符；小写字母表示终结符；希腊小写字母表示串

• 0型文法 产生式形如α→b
  • α中至少含一个非终结符
• 1型文法 │α│<=│β│（S→e例外）或产生式形如αAβ→αwβ，w∈V+ (上下文有关文法)
  • α中终结符个数小于β
• 2型文法 产生式形如A→α (上下文无关文法)
  • 产生式右端均为终结符
    • S—>aB|bA
    • A—>aS|bAA|a
    • B—>bS|aBB|b
• 3型文法 产生式形如A→α或A→αB (正则文法,右线性文法) α∈VT*
  • 在2型的基础上要求右端最多有一个非终结符，且位于最右端
    • S—>bA
    • A—>(B|a
    • B—>aA


 

 


• 例一


• 例二

 

• 短语——叶子节点
• 句柄——最左直接短语


字面意思~

• 例一

 

• 例二


• 例三


翻译：将一种语言编写的程序转换成完全等效的另一种语言编写的程序的过程。在计算机中，翻译由一 个程序来实现，称为翻译程序

**宿主语言：**编写编译程序的语言。运行翻译程序的机称为宿主机

静态语言需要先进行编译，才能执行代码  动态语言则是可以边解释 边执行代码 

• 词法分析
  • 输入字符串 根据词法规则识别出单词符号
• 语法分析
  • 根据语法规则 将单词符号构成各类语法单位 并进行语法检查
• 语义分析
  • 根据语义规则，进行初步编译
• 优化
  • 对中间代码进行等价变换 以使代码更有效
• 目标代码生成
  • 生成机器语言程序或汇编语言程序
• 符号表管理
  • 完成符号表的建立、查找、更新
• 出错处理


• 扫描源程序的字符串,按照词法规则,识别出单词符号作为输出

• 对识别过程中发现的词法错误输出有关的错误信息。

• 词法分析器是子程序

  • 
  • 

• 标识符
• 基本字
• 常数
• 运算符
• 界符

 

简称转换图,是一张有限方向图，是设计词法分析器的有效工具；它由如下成分构成： 1.结点(node)：圆圈表示结点，代表状态（state） 2.有向边（弧）:连接结点，边上的标记字符表示该状态下可能接收或识别的字符；  



语法分析分为两种 第七章——自上而下(自顶而下) 第八章——自下而上(自底而上) 

 

这个例子是啥意思？👇 

提取公共左因子  先提取左公因子 再消除左递归也ok



• 公式


• 例题




• 这个产生的语言是怎么出来得？

 


对于文法G=（{a,b,c,d,},{S,A},S,P）; 其中P为: S → Aa|Ac|bc A → Ad|Sbc|d 请先提取文法G的工共左因子，再消除左递归 

这个不在老师画的重点中 要考察麽？  

预测分析表 对于LL(1)文法来说，在使用最左推导时，非终结符号的每一步推导使用的产生式是确定的，不用进行试探和回溯。 求预测分析表 要先求出来FIRST表 FIRST(α)中的每一个终结符号a，表格项M(A,a)=A→α 如果是非空串产生式A→α，求FIRST(α)，对于FIRST(α)中的每一个终结符号a，M(A,a)=A→α 如果是空串产生式A→α，求FOLLOW(A)，对于FOLLOW(A)中的每一个终结符号b，M(A,b)=A→ε 



  

 大白话：

• 非空串产生式

1. 在所要求的字符产生式的右边的第一位寻找终结符，假设该字符产生式集的第一位就是终结符，那么该终结符就是所要求的first集；
2. 假设产生式的右边第一位是非终结符，那么继续寻找该非终结符的first集，直至寻找到一个终结符，即是起初所要求字符的first集；       

https://www.jianshu.com/p/210fda081c76

• 如果存在产生式A -> αBβ ，那么 FIRST(β)中所有非ε的符号都在FOLLOW(B)中；
  • 
• 如果存在产生式A -> αB，或者A -> αBβ 且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都加入到FOLLOW(B)中
  • （$=>#）

follow集的意义是寻找所要求字符的下一个字符可能产生的集合，所以寻找follow集应从产生式的右边进行寻找。

1. 在产生式的右边找到相应的字符（从左到右第一个非终结符），假设紧跟其后的是一个终结符，那么该终结符就是所要求的follow集；
2. 假设跟在其后的是一个非终结符，那么需要判断该非终结符是否可以为空：
3. 假如可以为空，那么将该产生式的左边的follow集加入到寻找集合当中，
   1. 因为假如该非终结符为空的话，那么需要寻找产生这个非终结符的产生式左边的非终结符，因为产生式左边的非终结符的follow集就有可能是该非终结符的follow集；
4. 假如不为空，那么寻找该非终结符的first集，并将结果加入到搜索集合当中。
5. 直到不再有非终结符产生，找到所有的终结符，计算结束。

找L的Follow集，先从式子右边找到L——


• 默认将右端结束标记 # 放到 FOLLOW(S) 中
• 按照下面两个规则不断迭代，直到所有的FOLLOW集合都不再增长为止
  • 如果存在产生式A -> *B)，那么FOLLOW(B) = { ), # }；——对应上面大白话的1
    • 
  • 如果存在产生式A -> *BC ，那么FOLLOW(B) = FIRST© - ε；——对应上面的2.b
    • 
    • 
  • 如果存在产生式A -> *B，或者A -> xxBC 且FIRST©包含ε，那么FOLLOW(B)=FOLLOW(A)——对应上面的2.a.i

• 空串产生式
  • 
  • 

 每一个推导式经过推导其对应的SELECT集的交集为空，其为LL（1）文法。

p55之后

  

上下文无关文法G,没有形如P→ε或P→. . .QR. . .的产生式,则称G为算符文法。 若算符文法G的任何终结符a,b之间的优先关系至多有=、>、<中的一个, 则G为算符优先文法

![image.png](https://img-blog.csdnimg.cn/img_convert/c9f1e83d6a3a3e3206858988338a547f.png#clientId=ub82bd813-5d31-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=334&id=ue30211a8&margin=[object Object]&name=image.png&originHeight=417&originWidth=600&originalType=binary&ratio=1&rotation=0&showTitle=false&size=368