编译原理讲义

编译学习QQ群：922706712

http://staff.ustc.edu.cn/~qlzheng/compiler/

编译原理与技术

2023－2024学年.秋季.第一学期

课程名称	学时	编号	上课时间
编译原理和技术011163	100/100	011163.01	GT-B210 :1(6,7) , 3(3,4)
编译原理和技术011163	100/100	011163.03	2405 :2(8,9) , 5(8,9)

教材：

《编译原理》陈意云、张昱高教出版社（第3版）

参考书：

（1）《Compilers: Principles, Techniques, and Tools》，A.Aho，et al, 第二版中译本，机械工业出版社，2007.

（2）《编译器构造－C语言描述》，郑启龙，姚震，机械工业出版社，2005

（3）Introduction to Compiler Design

（4）A Practical Approach to Compiler Construction

（5）Foundations of Programming Languages

（6）Programming Language Concepts

（7）Compiler Design - Analysis and Transformation

（8）Compiler Design - Syntactic and Semantic Analysis

（9）Compiler Design - Virtual Machines

（10）Modern Compiler Design

（11）Formal Languages and Compilation

课程讲义	阅读内容
第一讲编译器概述
第二讲词法分析（1）
第三讲词法分析（2）	ANSI C 词法
第四讲文法和语言	ANSI C 语法
第五讲自顶向下分析	ANSI C 2011规范
第六讲自底向上分析	LR(0)分析的正确性
第七讲语法制导翻译
第八讲运行时环境
第九讲中间代码生成（1）	数组元素访问三地址代码生成
第十讲中间代码生成（2）	数组与指针
第十一讲代码优化（1）
第十二讲代码优化（2）
第十三讲代码生成
第十四讲类型检查
第十五讲 SSA中间代码介绍

TA:

011163.01，高新校区GT-B210：（周三交作业）

李嘉璇，ljxx@mail.ustc.edu.cn

任萧涵，renxiaohan@mail.ustc.edu.cn

施海涵，shh924@mail.ustc.edu.cn

——————————————————

011163.03，东区2405：（周五交作业）

高光雄，ggx@mail.ustc.edu.cn

Home Work:

Homework 9

（1）针对第十二讲代码优化（2）P31上流图，

（1.1）计算到达-定值数据流方程，并给出相应的ud链。

（1.2）计算各基本块的生成表达式集e_gen[B]和注销表达式集e_kill[B]。

（2）针对第十二讲代码优化（2）P55上流图，计算活跃变量数据流方程。

Homework 8

（1）针对以下C程序片段，直接在源程序上进行循环优化（循环不变计算外提，强度消弱与复写传播优化等）

int a[100][100],b[100][100],c[100][100];

int i,j,k; //int : 4 bytes

for(i=0;i<100;i++)

for(j=0;j<100;j++)

for(k=0;k<100;k++)

c[i][j] = c[i][j] + a[i][k] * b[k][j];

（2）针对Homework 7的（1）中的C函数，在其三地址码基础上，给出流图，回边和自然循环。

（3）针对Homework 7的（2.2）中（b），在其三地址码基础上，给出基本块和流图。

Homework 7

（1）针对以下C函数，给出其函数体三地址码。

#define N 32

int a[N],b[N];
int arr[N+1][N+1];

void lcs()
{

for (i = 1; i <= len1; ++i){
for (j = 1; j <= len2; ++j) {
  if (a[i - 1] == b[j - 1]) { //串中的下标从0开始
   arr[i][j] = arr[i - 1][j - 1] + 1;
  }
  else {
   arr[i][j] = arr[i - 1][j] > arr[i][j - 1] ? arr[i - 1][j] : arr[i][j - 1];
  }
}
}
} // end of lcs()

（2）按要求给出以下C表达式的三地址代码(编号均从100开始)：

（2.1）数值计算方式。

（2.2）短路计算方式，并指出最终的真/假出口链所含跳转代码编号。

（a）第十讲中间代码生成（2）p18~p20翻译方案。

（b）第十讲中间代码生成（2）p21~p27，更精简的短路代码翻译方案。

a && (b || c) && (d || e && f) || (g || h) && (i || j)

Homework 6（运行时环境）

（1）PL0编译器运行时及中间代码生成练习

（2）C runtime练习

（3）链接给出一个Pascal程序及其汇编代码：

（3.1）针对该Pascal程序中的名字，参考第八讲运行时环境的第35页内容，给出相应表格；

（3.2）阅读相应汇编代码，给出各个过程(procedure)较精确的活动记录内容安排。

（3.3）解释过程son的每条汇编代码含义或作用（不仅仅是字面含义）。

Homework 5

（1）习题4.9，并分别给出（a）和（b）两个语法制导定义的属性栈代码实现（非yacc代码）。

（2）习题4.12，并分别给出（a）和（b）两个翻译方案的属性栈代码实现（非yacc代码）。

（3）第七讲语法制导翻译第34页的翻译方案，在输入串是 (id+id)*id 时的输出结果。

（4）针对习题4.3或4.12中的文法：

（4.1）参考第五讲自顶向下分析的第57-58页内容，给出相应的递归下降语法分析函数；

（4.2）在（4.1）基础上，分别给出习题4.3(a)和习题4.12(a)的（递归下降）预测翻译器。

Homework 4

（1）针对习题3.1中的文法，构造两个版本的递归下降语法分析程序。

（2）习题3.11，并描述该文法产生的语言。

（3）习题3.17、3.21、3.22、3.24、3.25。

（4）为以下文法构造LR(1)分析表：

S→ a S

S→ A

A→ a A b

A→

（5）给出接受以下文法：

S→ B B

B→ b B

B→ a

的活前缀且以LR(1)项目为状态的一个NFA。

Homework 3

（1）以下是C语言数组变量声明初始化的示例：

int f[][8][5] = { {{1},{2}},{3,},4,{5,},{6,},{7},8, };

填写合适的数字，补全数组变量f 声明[]处的空白！

并给出初始化描述中数值1~8在数组f中的下标。

（2）针对习题3.1文法，给出(a,((a,a)))的最左、最右推导和分析树。

（3）习题3.2(a)。

（4）有如下C程序：

int main()

{

int i = 0;

int *p = &i;//语句1

++ *p ++ ; //语句2

return i;

}

经x86-64 gcc 13.2编译生成如下intel汇编代码：

push rbp

mov rbp, rsp

mov DWORD PTR [rbp-12], 0

lea rax, [rbp-12]

mov QWORD PTR [rbp-8], rax

mov rax, QWORD PTR [rbp-8]

lea rdx, [rax+4]

mov QWORD PTR [rbp-8], rdx

mov edx, DWORD PTR [rax]

add edx, 1

mov DWORD PTR [rax], edx

mov eax, DWORD PTR [rbp-12]

pop rbp

ret

• 给出语句1所对应的汇编代码；

• 给语句2中表达式添加嵌套小圆括号()来表示计算次序，越内层越优先计算;再给出每层()所对应的主要汇编代码。例如，(p)将是最内层括号,对应汇编代码mov rax, QWORD PTR [rbp-8]。

Homework 2

（1）针对习题2.3中的（b），（d）和（e）：

• 简述各正规式所描述的语言；

• 采用第三讲词法分析（2）中第19页Thopmson 方法，为正规式（b）构建非确定有限自动机；

再进行确定化和极小化。

• 采用第三讲词法分析（2）中第38页方法，先为正规式（e）构建非确定有限自动机，

再进行确定化和极小化。

（2） • 针对习题2.14,构造相应DFA D；

• 采用第三讲词法分析（2）中第41-43页方法，

• 给出正规式 R，使得 L(R) = L(D)。

• 针对第三讲词法分析（2）中第12页上4个状态的DFA M，给出正规式 S，使得 L(S) = L(M)。

Homework 1

（1）观察讲义lec1中P4和P11上的函数fact的C代码及其汇编代码，初步了解编译器的作用。你可以：

（a）简要注释每条汇编代码；

（b）尝试指出C程序与汇编代码间的联系，

比如，C程序中的参数n在汇编中是如何表示的；if语句对应哪几条汇编代码......

（2）针对以下C/C++程序或片段：

（2.1）用文字简要描述以下C变量p的类型信息。

int (*(*(*p(int x))())[20])(int *y);

例如，int* a[10];变量a的类型信息描述如下：

变量a是一个含10个元素的数组，每个元素是指向整型变量的指针。

（2.2）给出以下程序在你的电脑上运行结果：

void main(){

int iii = 1000;
int & ii = iii;
int *pii = &ii;
int * &pr = pii;

cout << "iii = " << iii << " @: " << &iii << endl;
cout << "ii = " << ii << " @: " << &ii << endl;
cout << "pii points to: " << pii << " with value = " << *pii << " @: " << &pii << endl;
cout << "pr points to: " << pr << " with value = " << *pr << " @: " << &pr << endl;

return ;
}