编译原理简单概要

本文只对《龙书》前面几章进行简单的概要分析,也就是只涉及到词法分析和语法分析,由于能力有限,对于后面大部分章节并没有去研究。
另外提一句就是,该笔记屯很久了,只是一直没有上传到博客。最近心血来潮想着怎么也得更新几篇文章。😅

语法定义

上下文无关文法——用于组织编译器的前端

即大多数的编程语言都支持的一个简单的语句

if (expression) statement else statement,这个产生式:

stmtif(expr) stmt  else  stmtstmt\rightarrow \text{if} (expr) \ stmt\ \ \text{else} \ \ stmt

上下文无关文法(Context-Free Grammar)定义
  • 一个终结符号集合,即 词法单元。(可以理解为将非终结符号 断开/分隔 的符目的是易于翻译)
    • 词法单元由两部分组成: 名字/终结符号属性/指向符号表的指针
    • 比如:数位123、符号<,=,while 、if …
  • 一个非终结符号集合,即 词法变量,每一个非终结符号表示一个终结符号串的集合。
  • 一个 产生式 集合,每一个产生式包括一个称为 产生式头左部非终结符号(stmt),一个箭头\rightarrow) ,和一个称为 产生式体右部 的由终结符号及非终结符号 组成的序列(if (expr) stmt else stmt)
  • 指定一个非终结符号的开始符号。
推导

首先从开始符号出发,不断地将某个非终结符号替换为该非终结符号的某个产生式的体。可以从开始符号推导出得到的所有终结符号串的集合称为该文法定义的 语言(language)。

1. listlist+digit2. listlistdigit3. listdigit4. digit01234567891.\ list \rightarrow list+digit\\ 2.\ list \rightarrow list-digit\\ 3.\ list\rightarrow digit\\ 4.\ digit\rightarrow 0|1|2|3|4|5|6|7|8|9

该文法的 终结符号+0123456789+ -0123456789非终结符号:list、digit,其中 list 是开始符号。

零个终结符号组成的串称为空串,记为 ϵ\epsilon

例子:推导 9 - 5 + 2 是一个list

  • 因为 9 是一个 digit ,根据产生式 3. 可知 9 是一个 list
  • 因为 5 是一个 digit ,且 9 是list,根据产生式 2. 可知 9 - 5也是 list
  • 因为 2 是一个digit,且9 - 5是一个list,有产生式 1. 可知 9 - 5 + 2 是一个 list
语法分析树

如果一个非终结符号 AA 有一个产生式 AXYZA\rightarrow XYZ ,那么在语法分析树中就有可能有一个标号为 AA 的内部节点,有三个 XYZXYZ 的子节点。

一颗语法分析树具有以下性质:

  • 根节点的标号为文法的 开始符号
  • 每个 **叶子节点 **的标号为一个 终结符号ϵ\epsilon
  • 每个 **内部节点 **的标号为一个 非终结符号
  • 如果非终结符号 AA 是某个内部节点的标号,并且他的子节点的标号从左到右分别为 X1,X2,...,XnX_1,X_2,...,X_n ,那么必然存在产生式 AX1X2...XnA\rightarrow X_1X_2...X_n
二义性
运算符的结合性
运算符的优先级

语法制导翻译

语法制导翻译是通过向一个文法的产生式附加一些规则或程序片段而得到。

后缀表示
  • 如果 E 是一个变量或常量,则 E 的后缀表示的是 E 本身。
  • 如果 E 是一个 E1opE2E_1 op E_2 表达式,其中 op 是一个二元运算符,那么 E 的后缀表示是 E1E2opE_1'E_2'op
  • 如果 E 是一个 (E1)(E_1) 的被括号括起来的表达式,则 E 的后缀表示就是 E1E_1 的后缀表示。

例如: ( 9 - ( 5 + 2 ) ) 的后缀表达式为 952± 。即, ( 5 + 2 ) 首先被翻译成 52- ,然后这个表达式又成为减号的第二个运算分量。(由里到外)

语法分析

  • 自顶向下
  • 自底向上
预测分析法

递归下降分析方法是一种自顶向下的语法分析方法,他使用一组递归过程来处理输入。

从标号为 开始的非终结符号 stmtstmt 的根节点开始,反复执行以下过程

  • 在标号为 非终结符号 AA 的节点 NN 上,选择一个产生式,并为产生式体中的各个符号构造出 NN 的子节点。
  • 寻找下一个节点来构造子树,也就是 最左的子树节点 ,最左推导。

输入中当前被扫描的 终结符号 通常被称为 向前看符号( lookahead )。如果当前正在考虑的符号是一个终结符号,且与 当前的 向前看符号 匹配,则同时将 当前的 终结符号向前看符号 前进一步。

抽象语法和具体语法

设计一个翻译器时,名为 抽象语法树(abstract syntax tree) 。对于 抽象语法树语法分析树 两者有区别

  • 抽象语法树(AST 抽象语法)的 内部节点代表的是 程序构造
  • 语法分析树(CST (concrete syntax tree)具体语法)的 内部节点代表的是 非终结符号

词法分析

一个词法分析器从输入中读取字符时,并将他们组成 词法单元对象

构成一个词法单元的 输入字符 叫做 词素 (lexeme)

剔除空白和注释

在错误消息中加入 行号和上下文 有助于定位错误,比如 line

1
2
3
4
5
for (;; peek = next input character){
if (peek is a blank or a tab ) do nothing;
else if(peek is newline) line ++;
else break;
}

预读peek

对于某一些操作比如:>= ,当前读到 < ,下一步需要预读一个字符,如果是=,说明当前的序列表示 大于等于。

一个通用的预先读取输入的方法是使用 输入缓冲区词法分析器 可以从缓冲区中读取一个字符,也可以将字符放回到缓冲区中。

词法分析器只有在需要的时候才需要预读,对于像 * 之类的字符不需要再次读取。

常量

如果在一个表达式中要出现常量,那么可以创建一个代表整数的常量的 终结符号

将数位转化为整数,注意返回的 token 是一个二元组 <num,v><num,v>

1
2
3
4
5
6
7
if (peek holds a digit){ 
v = 0;
do{
v = v*10 +integer value of peek;
}while(peek holds a digit)
return token<num,v>;
}

识别关键字和标识符

语言的文法通常将 标识符 当作 终结符号 来处理。注意,对于一个简单的例子,可以使用一个表来保存字符串

1
2
count = count + i
语法分析器处理的是 终结符号序列 id = id + id

词法单元 idf 有一个属性保存他的 词素<id,"count">=<id,"count"> + <id,"i">

  • 单一表示:一个字符串表可以将 编译器的其余部分表中字符串的具体表示 分隔开。因此编译器只需操作表中的引用或指针。
  • 保留字 :要实现保留字,可以在初始化时将需要的 保留字 添加到表中,这样当词法分析器解析时,如果当前的终结符号存在与表中,则直接从表中取出这个词法单元,否则返回带有终结符号id 的词法单元
1
2
3
4
5
6
7
8
9
10
11
if (peek 存放了一个字符){
将字母或数位读入一个缓冲区b (不断的读取,直到不满足情况,遇到空白字符?)
//s = b 中的字符形成的字符串s'
String s = b + s';
w = words.get(s);
if (w!=null)return w;
else {
words.insert( {s,<id,s>} );
return 词法单元<id,s>
}
}

词法分析器

两种实现方法

  • 手工编码的实现方法
    • 相对复杂,容易出错
    • 但是目前非常流行的实现方法
      • GCC, LLVM
  • 词法分析器的生成器
    • 可以快速原型,代码量少
    • 难控制细节

符号表

符号表(syntax table) 是一种提供给编译器用于保存有关源程序构造的各种信息的数据结构,这些信息在编译器的分析阶段被逐步收集并放入符号表。符号表中的每个条目包含以下信息:

引入符号表的目的是:需要支持同一个标识符在一个程序中的多重声明

  • 字符串/词素
  • 类型
  • 存储位置
  • 其他相关信息
谁来创建符号表条目?

符号表条目 是在分析阶段由 词法分析器、语法分析器、语义分析器 创建并使用的。

在某些情况下,词法分析器可以在他碰到组成一个词素的字符串时立刻 建立一个符号表条目。但是在更多的情况下,词法分析器 只能向 语法分析器 返回一个 词法单元 ,以及指向这个词素的指针。

作用域

如果程序块可以嵌套,那么同一个标识符多次声明 就可能出现在同一个块中。

block{ decls  stmts  }block \rightarrow '\{' \ decls \ \ stmts \ \ '\}'

语句块的 最近嵌套 规则:

一个标识符 xx最近xx 声明的作用域内,也就是说,从 xx 出现的块开始,从内向外检查各个块时找到的第一个对 xx 的声明。

块的符号表的优化

块的符号表的实现可以利用作用域的最近嵌套规则。嵌套的结构确保可应用的符号表形成一个栈。

栈的顶部当前块的符号表。栈中的表的下方是包含这个块的各个块的符号表。有些编译器维护了一个散列表来存放可访问的符号表条目。

实现语句块的最近嵌套规则时,可以i将符号表进行 链接 ,也就是使得内嵌语句块的符号表指向外围语句块的符号表。

生成中间代码

编译器的前端构造出源程序的中间表示,而后端根据这个中间表示表示生成目标程序。

两种形式的中间表示形式

  • 树型构造,包括语法分析树和(抽象)语法树
  • 线性表示形式, 三地址代码

编译器在分析阶段只会保存讲过用于 语义检查或其他目的的节点及其属性,同时也保存了用于语法分析的数据结构。而不会保存一个整棵抽象语法树。

语法树的构造

1
2
3
op
/ \
E1 E2

可以为任意的构造创建抽象语法树,而不仅仅是为表达式创建语法树,比如 C语言中的一个

while ( expr ) stmt\text{while}\ (\ expr\ )\ stmt

静态类型检查

静态类型检查是在编译阶段过程中完成的各种一致性的检查

  • 语法检查
  • 类型检查

EE类型检查可以在创建他对应的抽象语法树的节点时进行。

1
2
if (E1.type == E2.type) E.type = boolean;
else error;

三地址码

x=y  op  zx=y \ \ \text{op}\ \ z

例子:将 函数;rvalue a[i]=2*a[j-k] 应用于,得到的语法树,生成:
t3 = j - k
t2 = a [t3]
t1 = 2 * t2
a [ i ] = t1


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!