编译原理复习

Thalia ·

更新时间:2024-09-21

· 729 次阅读

一引论

编译程序：将源程序翻译成目标程序
源程序：多为高级语言，eg：c,c++;
目标程序：汇编语言/机器语言。
编译过程：
词法分析——语法分析——语义分析——中间代码的生成——代码优化——目标代码的生成

词法分析：从左自右读入源程序，识别出一个个的单词。
语法分析：在词法分析的基础上将单词序列分解成语法短语。
语义分析：审查源程序有无语义错误，收集类型信息。
中间代码的生成：进行以上阶段分析之后的源程序叫做中间代码。
中间代码的特点：1.易生成；2易翻译成目标代码。
代码优化：优化中间代码。
目标代码的生成：与硬件有关，较为复杂。
前端：主要依赖与源语言而与目标机器无关的阶段
后端：依赖与目标机器的阶段
解释程序：接受某个语言的源程序并立即运行这个源程序
编译程序输出目标代码，解释程序输出结果。
解释程序的输入：源程序+初始数据；输出：结果
编译程序的输入：源程序；输出：目标程序
目标程序+数据作为输入到运行程序中去才能得到结果
根本区别：是否生成目标代码
处理源程序的软件工具：
1.语言的结构化编辑器：源程序的正文编辑，检查括号匹配，输入正确，检查语法错误
2.源程序的调试工具：检查结果与遗体是否一致，一行行跟踪
3.程序格式化工具：分析源程序，使其结构清晰
4.语言程序测试工具：
分为静态分析器：不运行程序；动态分析器：比较运行结构和期望；
5.程序理解工具：对程序进行分析，确定模块间的调用关系，画出控制流程图，帮助用户理解程序，
6高级语言之间的转换工具：转换高级语言

语言分类

强制式/过程/命令式语言：C，Fortran，Pascal 函数式/应用式：ML，LISP 基于规则的：PROLOG 面向对象的：C++,JAVA 二文法和语言

语法：构成句子各个记号之间的组合规律；
语义：各个记号的含义
语用：各个记号的来源,使用以及影响；

形式语言：只考虑语法层面，抽象的定义为一个数学系统；形式代表语言的规则只能以什么符号串能出现表示
文法：描述词法，语法的工具，对含有无穷句子的语言进行有穷表示字母表：元素的非空有穷集合
符号：字母表中的元素
符号串：符号的有穷序列

空符号串也是字母表上的符号串；符号串有顺序；

文法G(Vn,Vt,P,S)
Vn：非终结符；Vt：终结符；P:产生式；S：开始符号
句型：由文法的开始符号推导出的符号串；
句子：由文法的开始符号推导出的终结符符号串；
语言：句子的集合；
重点**语言和文法的转换
文法的等价：不同的文法能过产生相同的语言
文法的类型：(限制产生式)

1.0型（PSG）：产生式的左部至少有一个非终结符
2.1型（CSG）：a1Aa2–>a1Ba2 只有上下文相同时才可以替换
3.2型（CFG）：上下文无关
4.3型（RG）：A–>aB/A–>a或者A–>Ba/A–>a;
最右推导为规范推导，所得句型为规范句型；
二义文法：句子对应不同的语法树/最左（右）推导；
改造二义文法：规定优先顺序和结合律；
句型分析：识别一个符号串是否为文法的句型
自上而下的分析法：开始符号–>输入符号串
自下而上的分析法：输入符号串–>开始符号
短语：
直接短语：
句柄：最左直接短语；
文法中不得有二义；不得有多余；一般不含空规则；