编译原理知识点整理

Posted on Edited on In

语言(Language)

语言研究包括如下三个方面。

  • 语法(Syntax)：语言的正确形式；
  • 语义(Semantic)：语言的含义；
  • 语用(Pragmatics)：语言和使用者的关系。

编程语言(Programming Language)

可通过时期对编程语言进行如下分类。

第一代语言：机器语言(Machine Language)；

机器语言使用计算机唯一能够识别的二进制代码指令来编写程序的语言，不同的硬件对应不同的机器语言，因而不易移植。

第二代语言：汇编语言；

汇编语言又称符号语言，比机器语言直观，更易理解和记忆。

汇编器(Assembler)

将汇编程序替换为机器码。

汇编器生成的文件称为目标文件(Object File)，或二进制文件(Binaries)。

助记符(Mnemonics)指为每个操作码分配的简单记号。助记符后紧跟操作数(Operand)，形成完整指令。汇编程序即这些指令的集合，和底层硬件紧密联系。起初，汇编语言的指令只是机器指令的助记表示，后来，宏指令被加入到汇编语言中。

链接器(Linker)

将多个目标文件外加库链接为一个可执行文件，涉及符号解析和重定位工作。

链接的时机如下。

  • 编译时：静态链接器负责；
  • 加载时：加载器负责；
  • 运行时：动态链接器负责。

加载器(Loader)

将可执行文件放到内存中执行。

第三代语言：高级程序设计语言；

编译器(Compiler)

将源语言程序转换为等价的、更为低级的目标语言程序。

Assembly languages have direct, one-to-one mapping to machine instruction. But, a single line of a high-level programming language might result in dozens of instructions.

编译的大体过程如下。

  • 词法分析；
  • 语法分析；
  • 语义分析(Semantic Analysis)；
  • 中间代码生成(Intermediate Code Generation)；
  • 代码优化(Code Optimizer)；
  • 目标代码生成(Object Code Generation)。

贯穿其中的两个逻辑部分如下。

  • 符号表管理；
  • 错误处理。

对输入文件从头到尾扫视，完成预定处理的过程，称为一遍(Pass)或一趟。

解释器(Interpreter)

直接利用用户提供的输入执行源程序中指定的操作。

在把用户输入映射为输出的过程中，由编译器产生的机器语言目标程序通常较解释器快很多；然而解释器的错误诊断效果通常比编译器更好，因为它逐个语句地执行源程序。

解释、编译、汇编都可称为翻译(Translate)，即将源语言转换为目标语言。

预处理器(Preprocessor)

将源程序聚合在一起，将宏转换为源语言。

第四代语言：特定应用设计语言；

第五代语言：基于逻辑和约束的语言。

乔姆斯基谱系(Chomsky Hierarchy)

诺姆·乔姆斯基(Noam Chomsky)

美国语言学家，现代语言学之父。

乔姆斯基将文法分为如下四种类型。

其中，四种文法对应的四种语言有关系。

类型 名称 产生式的特征
0型文法 递归可枚举文法 且至少含一个非终结符，。
1型文法 上下文有关文法 在0型文法的基础上满足，或仅。
2型文法 上下文无关文法 且。
3型文法 正规文法、右线性文法 满足或，其中且。

巴科斯范式(BNF; Backus-Naur Form)

即上下文无关文法(Context Free Grammar)，由约翰·巴科斯等提出。

文法(Grammar)以更广泛的方式描述词法和语法，可以说是以有穷集合刻画无穷集合的工具。

文法定义为四元组，内容如下。

  • 终结符(Terminal)集合；
    • 字母表：非空有穷的基本符号集，因此字母表中的元素称为符号；
    • 符号串：由符号组成的任何有穷序列。 > 空符号串用表示，长度为0。 符号串的次方幂即把符号串重复写次。 即的闭包，表示上所有有穷长的符号串的集合。 而称为的正闭包。
  • 非终结符(Nonterminal)集合；
  • 产生式(Production)集合，形式如下； 其中读作「定义为」或「可具有此般形式」。
  • 指定一个非终结符为开始符号。

推导(Derivation)

即从开始符号起，不断将某个非终结符替换为非终结符的某个产生式的结果。

直接推导记为，步数大于等于1的推导记为，步数大于等于0的推导记为。

归约(Reduction)即推导的逆过程。

语言可定义为推导所得所有终结符串的集合。

代表性的文法

如下的文法指明了运算符的结合性和优先级，常被用作示例。

词法分析(Lexical Analysis)

将源代码分割为若干个词法单元的处理，又称扫描(Scanning)。

词法单元(Token)

又称记号，由一个词法单元名和一个可选的属性值组成。

词法单元在形式上可表示为二元组。

词法单元的常见类别有关键字、标识符、字面量、运算符和界符等。

词素(Lexeme)

源程序中的字符序列，与某个词法单元的模式匹配。

词法分析器将词素分析为词法单元的实例，并发送至语法分析器以回应其下一个词法单元的请求。

将词法分析工作分离的考虑如下。

  • 使整个编译程序的结构更简洁、清晰和条理化；
  • 编译程序的效率会改进；
  • 增强编译程序的可移植性。

词法单元的形式化描述工具有正规文法、正则表达式和有穷自动机。

有穷自动机(Finite Automata)

模式的识别装置。

确定有穷自动机(DFA; Deterministic Finite Automata)定义为五元组。

  • 有穷状态集；
  • 输入符号字母表；
  • 转换函数，是的映像，即定义状态关于输入符号的后继状态；
  • 初态；
  • 终态集，终态又称可接受(Accept)状态。

不确定有穷自动机(NFA; Nondeterministic Finite Automata)中，和的定义有如下差异。

  • 转换函数，是的映像，即输入可为符号串，且相同输入的后继状态可有复数个；
  • 非空初态集。

显然DFA是NFA的特例。对于每个NFA都存在一个与之等价的DFA。

子集构造(Subset Construction)算法

将NFA转换为等价的DFA，即NFA的确定化。

其中，子集指NFA状态的子集。

子集构造算法中的函数定义如下。

操作 描述
能够从NFA的状态开始，只通过转换到达的NFA状态集合。
即。
能够从中某个状态出发通过符号的转换到达的NFA状态集合。

子集构造算法的伪代码如下。

SUBSET-CONSTRUCTION
输入：一个NFA ，开始状态为；
输出：一个接受同样语言的DFA ，为其构造转换表。
一开始，是中的唯一状态，且它未加标记;
在中有一个未标记状态
给加上标记;
每个输入符号

不在中 将加入到中，且不加标记;

任何正则语言都有一个唯一的状态数目最少的DFA，称最小确定有穷自动机(Minimal DFA)。

无用状态(Dead State)

无法到达或无法由此状态到达终态的状态，又称「死状态」。

无用状态可以非常简单地被消除。

等价状态(Non-distinguishable State)

DFA的最简化中需要合并的状态，又称「不可区分状态」。

两个状态等价的条件如下。

  • 一致性条件：两个状态必须同时为可接受状态或不可接受状态；
  • 蔓延性条件：对于所有输入符号，两个状态必须转换到等价的状态里。

可以通过不断分割，将DFA的状态分割为不相交的子集，使任两个来自不同的子集的状态都是可区分的，任两个来自同一子集中的状态都是等价的，找到并合并等价状态，以实现DFA的最小化。

lex

自动生成词法分析器的工具，通过输入扩展名为.l的文件，输出词法分析器的C语言代码。

flex是增强版的lex，其中f指快速(Fast)。

一个lex程序具有如下形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 定义区块 */
%{
/* C Codes */
#include "y.tab.h"
/* 定义yywrap函数可避免手动链接lex的库文件 */
int yywrap(void) { return 1; }
%}
pattern_name regular_expression
%%
/* 转换规则区块 */
pattern /* or {pattern_name} */ { action; }
%%
/* 用户代码区块 */

下例定义匹配实数模式串并返回实数的规则。

1
2
3
4
5
6
([1-9][0-9]*)|0|([0-9]+\.[0-9]*) {
    double tmp;
    sscanf(yytext, "%lf", &tmp);
    yylval = tmp;
    return LITERAL;
}

下例忽略代码中的空白。

1
[ \t] ;

若匹配失败则出现词法错误，结束程序。

.用于匹配除换行符\n外的任何字符。

1
2
3
4
. {
    fprintf(stderr, "Lexical Error!\n");
    exit(EXIT_FAILURE);
}

语法分析(Syntax Analysis)

从词法单元构建语法树的处理，又称解析(Parsing)。

抽象语法树(AST; Abstract Syntax Tree)

又称语法树，包含代码中所有词法单元。

语法树涉及的概念如下。

  • 句型：在语法树生长过程的任何时刻，所有叶子结点的排列；
  • 短语：完整语法树中一棵子树的所有叶子排列；
    • 直接短语：限制子树为仅有父子两代的一棵子树；
    • 句柄：最左的直接短语。

自顶向下分析

从文法的开始符号出发，根据当前的输入符号唯一地确定使用的产生式以继续推导。

在上下文无关文法、且的条件下作如下定义。

操作 描述
(若，则规定)
(若，则规定)

LL(k)文法

从左向右扫描输入串，使用最左推导，需向前看个符号以确定使用的产生式。

通常采用文法。

LL(1)文法

文法的充分必要条件如下。

其中，和是的两个不同产生式。

某些非文法可通过如下方式转换为文法。

  • 提取左公因子；

    对于产生式可改写为如下形式。

    不含左公因子只是文法的必要条件，而非充分条件。

  • 消除直接左递归。

    对于产生式可改写为如下形式。

    将前述代表性的文法消除直接左递归，得到如下形式。

    要消除间接左递归，需通过产生式置换非终结符，转换为直接左递归后再消除。

预测分析表(Transition/Parsing Table)

以前述代表性的文法为例，求出各非终结符的集合、集合和可空情况如下。

Nonterminal Nullable?
✓
✓

再求出各产生式的集合。

最后构造预测分析表，若，则把放入中。

Nonterminal

自底向上分析

LR(k)文法

向右查看个符号唯一地确定分析器的移进或归约及其使用的产生式。

通常。

LR(0)文法

文法在分析过程中不需向右查看输入符号，因而它对文法的限制较大。

项(Item)

在文法的每个产生式右部适当位置添加一个圆点构成。

产生式的各项如下。

对空产生式有且仅有一个项即。

增广文法(Augmented Grammar)

在原文法中加入产生式，以保证开始符号只在左部出现。

文法的规范项集族(Canonical Collection)提供了构建自动机的基础。

为了构造文法的规范项集族，需要增广文法及如下两个操作的定义。

其中是文法的一个项目集，。

操作 描述
1. 一开始，将的各项加入到中；
2.如果在中，则加入形如的项；
3. 重复规则直至不再扩大。
中所有形如的项所对应的项的集合的闭包，
即当前输入为时离开状态的转换。

SLR(1)文法

S指Simple。

文法要求不含如下的移进—归约冲突项集。

同时，文法也要求不含如下的归约—归约冲突项集。

如前述代表性的文法存在项集，不是文法。

文法的前提如下，其中冲突项集。

文法向前查看一个符号以解决冲突项集，具体技术如下表。

情况 规则
移进
使用规则进行规约
使用规则进行规约

yacc

自动生成语法分析器的工具，通过输入.y扩展名的文件，输出语法分析器的C语言代码。

yacc指Yet Another Compiler Compiler。

bison则是yacc的机能扩展版本，由GNU项目发布。

一个yacc程序具有如下形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 定义区块 */
%{
/* C Codes */
%}
%%
/* 翻译规则区块 */
nonterminal : x { action; } | y { action; } ;
%%
/* 用户代码区块 */
int main(void) {
    extern int yyparse(void);
    extern FILE* yyin = stdin;
    if(yyparse()) {
        fprintf(stderr, "Error!\n");
        exit(EXIT_FAILURE);
    }
}

在.l和.y文件的首行C代码加入如下定义可将输入捕获为浮点数。

In .l file, this definition must take place before the #include ".tab.h".

1
#define YYSTYPE double

若要使yylval能表示多种类型，在.y文件加入如下联合体声明。

1
2
3
4
%union {
    int int_value;
    double double_value;
}

使用%token<>指定词法单元的类型。

1
2
%token <double_value> LITERAL
%token <int_value> VARIABLE

使用%type<>指定非终结符的类型。

1
%type <double_value> expr

追加如下部分以实现错误恢复机制。

其中error是匹配错误的特殊记号，CR指换行符\n，yyclearin丢弃预备读入的词法单元，yyerrok通知yacc程序已经从错误状态恢复。

1
2
line : ...
    | error CR { yyclearin; yyerrok; } ;

在用户代码区块定义yyerror函数，以输出错误的位置。

1
2
3
4
5
int yyerror(const char* str) {
    extern char* yytext;
    fprintf(stderr, "Parser error near %s.\n", yytext);
    return 0;
}