编译原理概念总结

第一章 引论

? 为什么要用编译器 ? 与编译器相关的程序 ? 翻译步骤

? 编译器中的主要数据结构

1、语言处理器 1、简单的说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。

2、编译器的重要任务之一就是报告它在翻译过程中发现的源程序中的错误。 3、使用编译器是为了提高编程的速度和准确度。 4、与编译器相关的程序：解释程序（interpreter）、汇编程序（assembler）、连接程序（linker）、装入程序（loader）、预处理器（preprocessor）、编辑器（editor）、调试程序（debugger）、描述器（profiler）、项目管理程序（project manager）。

5、解释器是另一种常见的语言处理器。它并不通过翻译的方法生成目标程序。从用户的角度来看，解释器直接利用用户提供的输入执行源程序中指定的操作。

Object

Loader, Linker Program Source

Translator and Run-time Program Output

System

6、一个源程序可能被分割成多个模块，并存放于独立的文件中。把源程序聚合在

一起的任务有时会由一个被称为预处理器（preprocessor）的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。

7、连接器（linker）能够解决外部内存地址的问题。

8、加载器（loader）把所有的可执行目标文件放到内存中执行。

2、一个编译器的结构

Source Program Lexical Analysis Syntax Analysis Semantic Analysis High-level IR to low-level IR conversion Controlflow/Dataflow Optimization Code Generation Machine independent asm to machine dependent

Scanner Parser Front end

Context Symbol Table CFG Build high-level IR Back end

Assembly Code 1、将编译器看成黑盒，则源程序映射为在语义上等价的目标程序，而这个映射由

两部分组成：分析部分和综合部分。

2、分析部分把源程序分解成多个组成要素，并在这些要素之上加上语法结构。 3、综合部分根据中间表示和符号表中的信息来构造用户期待的目标程序。 4、编译器的第一个步骤：词法分析（lexical）或扫描（scanning）。词法分析器读

入组成源程序的字符流，并且将它们组成有意义的词素（lexeme）的序列。词法分析器产生词法单元（token）。

5、分隔词素的空格会被词法分析器忽略掉。

6、编译器的第二个步骤：语法分析（syntax）或解析（parsing）。语法分析器使用

由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。

7、语义分析（static semantic analysis）：语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。语义分析的一个重要部分是类型检查（type checking）。编译器检查每个运算符是否具有匹配的运算分量。

8、总的说，编译器的翻译步骤是：扫描程序----语法分析程序----语义分析程序----源代码优化程序----代码生成器----目标代码优化程序。 3、编译器结构中的主要数据结构 1、记号（token） 2、语法树（syntax tree） 3、符号表（symbol table） 4、常数表（literal table） 5、中间代码（intermediate code） 6、临时文件（temporary file） 4、将编译器分成了只依赖于源语言（前端（ front end））的操作和只依赖于目 标语言（后端（ back end））的操作两部分。

第二章 词法分析

? 扫描处理 ? 正则表达式 ? 有穷自动机

? 从正则表达式到D FA ? 利用L e x自动生成扫描程序

1、 Tokens记号标记：identifiers、keywords、integers、floating-point、symbols、strings、comments

1、 使用正则表达式去描述程序语言tokens 2、 一个正则表达式是归纳确定

3、 一个正则表达式R描述一组字符串集合L(R) 4、 L(R) = the language defined by R

5、 所有的token都能用正则表达式表示 2、 正则表达式：

1、 基本正则表达式：他们是字母比哦啊中的单个字符且自身匹配

2、 正则表达式运算：

1、 从各选择对象中选择，用元字符“|”表示 2、 连结，由并置表示（不用元字符） 3、 重复或“闭包”，由元字符“*”表示 3、从各选择对象中选择： 4、连结：正则表达式r和正则表达式s的连接可写作rs 5、重复：正则表达式的重复有时称为Kleene闭包（（Kleene）closure），写作r* 6、运算的优先和括号的使用：前面的内容忽略了选择、连接和重复的优先问题。 7、正则表达式的名字：为较长的正则表达式提供一个简化了的名字很有用处，这样就不再需要在每次使用正则表达式时书写常常的表达式本身了。 3、有穷自动机（有穷状态机）：是描述（或“机器”）特定类型算法的数学方法。 1、确定性有穷自动机：下一个状态由当前状态和当前输入字符惟一给出的自动机。 2、非确定性有穷自动机：由它产生的。 4、从正则表达式到DFA 1、构造一个个扫描程序的自动过程可分为3步

2、从正则表达式到NFA

3、从NFA到DFA

4、将DFA中的状态最小化

第三章 上下文无关文法及分析

? 分析过程 ? 上下文无关文法

? 上下文无关语言的形式特性 ? 分析树与抽象语法树 ? 二义性

1、分析过程：

2、上下文无关文法：

3、分析树与抽象语法树：

4、二义性：

可生成带有两个不同分析树的串的文法称作二义性文法（ ambiguous grammar） 有两个解决二义性的基本方法。

其一是：设置一个规则，该规则可在每个二义性情况下指出哪一个分析树（或语法树）是正确的。

另一种方法是将文法改变成一个强制正确分析树的构造的格式，这样就可以解决二义性了。

第四章 自顶向下的分析

? 使用递归下降分析算法进行自顶向下的分析 ? LL(1)分析

? First 集合和F o l l o w集合

1、使用递归下降分析算法进行自顶向下的分析

2、LL(1) 分析方法是这样得名的：第1个“L”指的是由左向右地处理输入（一些旧式的分析程序惯于自右向左地处理输入，但现在已不常用了）。第2个“L”指的是它为输入串描绘出一个最左推导。括号中的数字1意味着它仅使用输入中的一个符号来预测分析的方向。 3、定义：如果文法G相关的L L ( 1 )分析表的每个项目中至多只有一个产生式，则该文法 就是L L ( 1 )文法(LL(1) grammar)。

本文来源：https://www.bwwdw.com/article/pcm2.html