当前位置: 首页 > news >正文

编译原理笔记

与其说是笔记,不如说是读ppt,因此本文只记录ppt中有关概念的知识点。

如想直接跳转,请使用ctrl+f。

概论

源程序:用汇编语言或高级语言编写的程序称为源程序。

目标程序:用目标语言所表示的程序。

翻译程序:将源程序转换为目标程序的程序称为翻译程序。

 解释程序:对源程序进行解释执行的程序。

 编译过程分为五个阶段:

词法分析:分析和识别单词。

语法分析:根据语法规则,分析并识别出各种语法成分,如表达式、各种说明、各种语句、过程、函数等,并进行语法正确性检查。

语义分析、生成中间代码:对识别出的各种语法成分进行语义分析,并产生相应的中间代码。

代码优化:得到高质量的目标程序。

生成目标程序:由中间代码生成目标程序。

遍:对源程序从头到尾扫描一次,称为一遍。 

文法和语言的概念和表示

字母表:符号的非空有限集

符号:字母表中的元素

符号串:符号的有穷序列

空符号串:无任何符号的符号串

符号串集合的运算:

把单词看作符号,句子就是符号串,若把字符看作符号,单词就是符号串。

文法:文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为文法。

语法规则:我们通过建立一组规则,来描述句子的语法结构。

由规则推导句子:有了一组规则之后,就可以按照一定的方式用它们去推到或产生句子。

推导方法:从一个要识别的符号开始推导,即用相应规则的右部来替代规则的左部,每次仅用一条规则去推导。

有若干语法成分同时存在时,我们宗死后从最左的语法成分进行推导,这称为最左推导,类似的有最右推导。

语法树:我们用语法树来描述一个句子的语法结构。

文法定义:

 短语是前面句型中的某个非终结符所能推出的符号串。

任何句型本身一定是相对于识别符号Z的短语。

任一句型的最左简单短语称为该句型的句柄。

语法树:句子结构的图示表示法,它是有向图,由结点和有向边组成。

子树:语法树中的某个结点连同它向下派生的部分所组成。

自下而上地修剪子树的某些末端结点,直至把整棵树剪掉,每剪一次对应一次归约。

通常我们每次都剪掉当前句型的句柄,即每次均进行规范归约。

通过规范推导或规范规约所得到的句型称为规范句型。

若对一个文法的某一句子存在两棵不同的语法树,则该文法是二义性文法。

若一个文法的某句子存在两个不同的规范推导,则该文法是二义性的。

若一个文法的某规范句型句柄不唯一,则该文法是二义性的。

词法分析

词法分析:根据词法规则识别及组合单词,进行词法检查。

主要是刻画状态机没啥别的。

符号表管理技术

符号表:在编译过程中,编译程序用来记录源程序中各种名字的特性消息,所以也称为名字特性表。

运行时的存储组织及管理

目标程序运行时所需存储空间的组织与管理以及源程序中变量存储空间的分配。

静态存储分配:在编译阶段由编译程序实现对存储空间的管理和为源程序中的变量分配存储的方法。如果在编译时能够确定源程序中变量在运行时的数据空间大小,且运行时不改变,那么就可以采用静态存储分配方法。(但是不是所有数据空间大小都能在编译过程中确定)

动态存储分配:在目标程序运行阶段由目标程序实现对存储空间的组织与管理,和为源程序中变量分配存储的方法。在目标程序运行时进行变量的存储分配,编译时要生成进行动态分配的目标指令。

静态存储分配

分配策略:由于每个变量所需空间的大小在编译时已知,因此可以用简单的方法给变量分配目标地址。

  1. 开辟一数据区;
  2. 按编译顺序给每个模块分配存储空间;
  3. 在模块内部按顺序给模块的变量分配存储,一般用相对地址,所占数据区的大小由变量类型决定;
  4. 目标地址填入变量的符号表中。

动态存储分配

  • 编译时不能具体确定程序所需数据空间;
  • 编译程序生成有关存储分配的目标代码;
  • 实际上的分配要在目标程序运行时进行;

分配策略:

整个数据区为一个堆栈;

  • 当进入一个过程时,在栈顶为其分配一个数据区;
  • 退出时,撤销过程数据区;

源程序的中间形式

波兰表达

波兰表示:

前缀表示:<操作符><操作数序列>(波兰表示)

后缀表示:<操作数序列><操作符>(逆波兰表达)

算法:设一个操作符栈;当读到操作数时,立即输出该操作数,当扫描到操作符时,与栈顶操作符比较优先级,所栈顶操作符优先级高于栈外,则输出该栈顶操作符,反之,则栈外操作符入栈。

波兰表达法的优点:

  • 在不使用括号的情况下可以无二义地说明算数表达式。
  • 波兰表达法更容易转换成机器的汇编语言或机器语言。(操作数出现在仅靠操作符的左边,而操作符在波兰表示中的顺序即为进行计算的顺序)
  • 波兰表示不仅能用来作为算数表达式的中间代码形式,而且也能作为其他语言结构的中间代码形式。

使用波兰表达的问题:优化不是很方便。

N一元表示

在该表示中,每条指令由n个域组成,通常第一个域表示操作符,其余为操作数。

使用三元式不便于代码优化,因为优化要删除一些三元式,或对某些三元式的位置要进行变更,由于三元式的结果(表示为编号),可以时某个三元式的操作数,随着三元式位置的变更也将做相应的修改。

三元式的执行次序用另一张表表示,这样在优化时,三元式可以不变,而仅仅改变其执行顺序表。

相关文章:

  • vue中如何监听localStorage值的变化
  • Acwing算法基础课总结
  • Libgdx游戏开发(1)——环境配置及demo运行
  • ESB产品调用场景分析
  • 【微机原理】微处理器与总线
  • 【youcans 的图像处理学习课】11. 形态学图像处理(下)
  • Day19NAT
  • ARMv9新特性:虚拟内存系统架构 (VMSA) 的增强功能
  • 大数据入门之 Hadoop,HDFS,Hbase,Hive
  • 令人头秃的js隐式转换面试题,你能做对吗
  • 信号(软件中断)编程
  • django基于python的酒店预订管理系统--宾馆管理系统-计算机毕业设计
  • Google 翻译插件不能用了怎么办
  • OpenJudge NOI 1.5 编程基础之循环控制(41-45题)C++ 解题思路
  • 硬件设计基础----通信协议UART
  • ASP.NET Core--配置文件
  • React-Hooks怎样封装防抖和节流-面试真题
  • 基于移动平台的会展导游系统APP设计与实现
  • 为什么python证券接口通达信系统中没有接口?
  • SpringBoot高级知识【原理分析、监控、项目部署】