CS compiler

编译原理笔记02：构造一个简单的编译器

Posted by LiYixian on Sunday, September 17, 2023 | 阅读 | 共 2751 字，阅读约 6 分钟

Summary:

  • 上下文无关文法（CFG）
    • 推导和语法树
  • 语法制导翻译
    • 翻译模式
    • Yacc 编程
  • 自顶向下预测分析
    • 设计实现预测分析器
  • 简单词法分析
  • 代码生成

语法定义

上下文无关文法（CFG）：描述源程序的语法结构
CFG 的四个部分：

  • 终结符 terminal：不可被取代、不可拆分的基本符号（e.g. if, else）
  • 非终结符 nonterminal（e.g. expr, stmt）
  • 产生式 production 左部只有一个非终结符，右部是非终结符
  • 唯一一个特定的非终结符：开始符号 start symbol

定义几个概念：

  • Σ：有穷字母表，其中元素（符号）构成符号串
    • 空字 ε：不含任何符号的序列
    • Σ*：符号串全体，包括空字
    • φ：空集{}，注意区分空集和空字
  • 符号串子集的（笛卡尔）积，注意顺序
    • n 次积和 0 次积
    • 闭包 closure \(V*\) 和正则闭包 \(V^+\)
  • 终结符集合 \(V_T\)，非终结符集合 \(V_N\)，产生式集合 \(P\)，开始符号 \(S\)

符号约定：

  • expr, digit
  • 终结符：数字、运算符、黑体
  • 非终结符：斜体
  • ｜= 或，候选式

推导

推导 derivation：从 start symbol 开始，用 production 右部替换左部，反复替换得到最终的单词串

语法分析树 parse tree：从根节点开始，每个节点应用 production 产生子节点

  • 叶节点从左到右构成树的输出 yield
  • 定义无歧义语法消除 ambiguity（同一个单词有多棵语法树）
  • 运算符结合律：左结合 +,-,*,/；右结合 ^,=
  • 运算符优先级
    • 结合优先级的表达式文法：expr, term, factor

语法制导翻译

确定每个语法结构如何翻译后，把翻译方法转换为语义规则/语义动作，附着在 production 上。
或：一边解析 parse 字符串一边干别的事 （构造语法树/直接生成中间代码/类型检查…），语法分析起支配作用

e.g.表达式 E 的后缀形式 Postfix (E)生成：

when E = E1 op E2:  
Postfix(E) = Postfix(E1 op E2) = Postfix(E1) Postfix(E2) op

语法制导定义

syntax-directed definitions (SDD)：对 CFG 的推广

  • 每个文法符号关联一组属性
  • 每个 production 关联一组语义规则 semantic rule，这些规则用来计算该 production 中各个符号的属性值

e.g.后缀表达式的语法制导定义

文法符号的属性：

  1. 综合属性 synthesized attribute：节点综合属性由其子节点/自身属性决定，bottom-up 计算（后序遍历、深度优先）
  2. 继承属性 inherited attribute：节点属性由其父节点/自身/sibling 节点属性决定（终结符没有继承属性）

语法制导翻译的基本过程：

  1. 输入单词串，生成语法分析树
  2. 节点 n 标记为 \(X\)，其属性为 \(a\)，写作 \(X.a\)
  3. 利用 \(X\) production 的语义规则计算节点 n 的 \(X.a\) 的值
  4. 注释语法分析树 annotated parse tree

语法制导翻译模式

syntax-directed translation scheme (SDT)：在 production 中嵌入语义动作，计算文法符号的属性值
语义动作在 production 中的位置就是在语法树中的位置，也就是动作执行的顺序
考虑属性的依赖关系，确定嵌入位置。

rest -> + term {print('+')} rest

带语义动作的语法分析树：一边进行语法分析，一边从左至右执行语义动作
或：后序遍历语法树，遍历到语义动作节点执行相应代码 （属性计算/结果输出/…）

Yacc 程序

yacc/bison 程序结构（*. y，分三部分，%%分隔）

/*P1: declarations 定义段*/
%{

/*
定义段一般分两种：
1. C语言编写的，包括头文件include、宏定义、全局变量定义、函数声明等  
2. 声明文法的终结符和非终结符  
常用的 Bison 标记声明有：%token %union %start %type %left %right %nonassoc 等。
- %token TOKEN1 TOKEN2 定义使用了哪些终结符
- %left % right %nonassoc 同上，表明了结合性，先定义的优先级低
*/

%}

%%

/*P2: grammar rules 规则段(rule & action)*/

A: a1 {语义动作1}
	|a2 {语义动作2}
	|...
	|an {语义动作n}
	|b //没有{...}时就使用缺省的语义动作
; //production 结束标记
// 语义动作一般在产生式右部分析完，归约动作进行前执行
// 动作中$1指右边第一个标记的值，$2表示右边第二个标记的值，依次类推；$$表示归约后的值(左边的值)

%%

/*P3: supporting C routines 用户辅助程序段(C函数)*/
// 为C代码，会被原样复制到C文件中，一般自定义一些函数

e.g.简单表达式计算

语法分析

自顶向下 top-down：从 start symbol 开始，不断进行推导，直到推导所得的符号串与输入串相同为止。

预备概念：LL (1) 文法是什么？
第一个 L：left to right，从左向右扫描输入的 token 序列；
第二个 L：leftmost derivation，分析时从文法最左边开始进行推导；
(1)：只需要向右看一个符号就可以决定推导方向。

LL (1)是如何解析 token 序列的？

  1. 用 parsing queue 的第一个元素和 input 的第一个 token 匹配；
  2. 如果第一个元素是非终结符（可以继续迭代），就找到对应的 production 并替换，回到步骤 1，若找不到这样的 production，报错；
  3. 如果第一个元素是终结符（无法继续迭代），则和 input 的第一个 token 匹配，二者都消去，回到步骤 1，若匹配不上，报错；
  4. parsing queue 和 input 都为空时，匹配成功，结束。

预备工作：消除文法的二义性，消除左递归，提取左公共因子，计算 FIRST 集合和 FOLLOW 集合，判断文法是否为 LL (1)型文法；如果是，就可以用下面 LL (1)型文法的两个具体实现进行分析。

一些额外问题：

  1. 如何消除左递归？
    改写文法
A -> Aa|b 改写为  
A -> bR; R -> aR|ε
  1. 如何判断文法是否是 LL (1)型？

递归下降分析

  1. 对节点选择一个 production，利用右部构造子节点；继续选择下一个没有扩展的子节点，迭代
  2. 扫描，与当前输入单词逐个比较，不匹配就回溯

预测分析 predictive parsing

递归下降的问题：回溯花费的时间过多，可能会组合爆炸
-> 如何在每步都确定唯一可能的候选式？
根据下一个输入单词（超前单词）选择

  1. production 选择
    1. 对所有 production 构造 FIRST 集，和当前第一个 token 比对，有匹配就可以替换；
    2. 如果有冲突（FIRST 交集），则预测分析不适用；
    3. 若当前非终结符可以被替换为空（即存在 S->ε），且替换后 parsing queue 的下一个终结符（构造 FOLLOW 集）可以和当前第一个 token 匹配，就可以替换。
  2. production 的使用
    1. 对非终结符，调用对应的递归函数；
    2. 对终结符，和当前第一个 token 比较，若匹配就继续读，否则报错。

问题：如何构造 FIRST 集和 FOLLOW 集？
A->a, A->b, FIRST (a) 和 FIRST (b) 不能有交集
参考资料：你知道LL(1)吗

结合翻译模式：将语义动作复制到预测分析器里
位置：语义动作位于语法符号 X 之后，就将其紧接在处理 X 的代码之后；如果位于 production 开始，就复制到函数最前面

词法分析

语法分析是主体，词法分析器作为前者的调用接口，调用一次返回一个 token
平凡算法：根据下一字符判断进入哪个 token 的识别

  • 去除空白和注释
  • 常量
  • 标识符、关键字识别
    • <id, 符号表项指针>
    • 关键字 keyword、保留字 reserved
    • 运算符，每个独自作为一类单词

符号表

字典保存单词的实例和索引 token

insert(s,t) 单词t的实例s（字符串）插入符号表，返回t
t 可以是 id 或关键字（if,else）
lookup(s) 查找字符串s对应的表中索引

一种实现方式：指针指向符号串存储的位置（紧凑存储）
带符号表功能的词法分析器：先查询 lexbuf 是否已经在符号表里，没有再插入

代码生成

语法符号的属性 - 汇编代码
上层语法结构的代码 - 下层语法结构的代码，再拼接一些汇编指令

expr -> expr1 + term {
	expr.addr = newtemp;
	expr.code = expr1.code || term.code ||
				"MOV EAX, expr1.addr
				MOV EBX, term.addr
				ADD EAX, EBX
				MOV expr.addr, EAX"
}

stmt -> id := expr 赋值
{stmt.code = expr.code ||
	"MOV EAX, expr.addr
	MOV id.addr, EAX"}

stmt -> if(expr) stmt1 { 控制流
	out = newlabel;
	stmt.code = expr.code || 'jz' out || stmt1.code || out
}

stmt -> while(expr) stmt1 {
	test = newlabel; out = newlabel;
	stmt.code := test || expr.code || 'jz' out ||
	stmt1.code || 'jmp' test || out
}

翻译模式：

stmt -> if
	expr {out:=newlabel; print('jz', out);}
	then
	stmt1 {print(out);}

stmt -> while {test:=newlabel, print(test)}
	expr {out:=newlabel; print('jz', out);}
	then
	stmt1 {print('jmp', test); print(out);}
CATALOG
    FEATURED TAGS
    compiler computer-architecture computer-networking cs operating-system