编译原理讲义

编译原理期末考试安排：

考试时间：2019年元月15日，下午2：30~4：30

考试地点：西区三教 3C103

考试形式：闭卷

编译原理期末复习

编译学习QQ群： 875026178

课程实践2：2018年11月29前完成并提交设计报告

课程实践1：2018年12月13前完成并提交设计报告

验收时间：2018年12月17/20/24/27/31日，在上课教室。

实验1验收例子：

int *p;

int *pa[20][30];

int (**pp);

int (**ap[20])[30];

int (*fpa(int i,int *j))[20];

int * fa(int i)[20]; //type-error!

int af[20](int k); // type-error!

void (*(*paa)[10])(int a);

void (*afp[10]) (int b);

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

//function(void => pointer(function(int => pointer(array(20,pointer(function(pointer(int) => int)))))))

int (*p(int * s,int (*t)(int *m, int n, int (*l())[20]),int k[10]))[10][20];

//function(pointer(int) X pointer(function(pointer(int) X int X function(void => pointer(array(20,int))) => int)) X array(10,int) => pointer(array(10,array(20,int))))

编译原理与技术

2018－2019学年.秋季.第一学期

课程名称	学时	上课时间	教室
编译原理和技术01116301	60/40	周一下午6－7	西区3B102
		周四上午3－4

教材：

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

参考书：

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

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

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

TA:

刘彬彬, robbertl@mail.ustc.edu.cn

丁上义，dingsyyo@mail.ustc.edu.cn

凤维杰，fengwj@mail.ustc.edu.cn

姜靖，jjdl@mail.ustc.edu.cn

Home Works（每周四交）:

Homework 6（2018年11月29日交）

（1）针以下对文法G：
S -> ( L ) | a

L -> L , S | S

（1.1）给出自上而下的预测翻译程序，输出括号嵌套的最大深度；

（1.2）给出自下而上的属性栈实现代码，输出每个a的嵌套深度。

（2）针对以下C程序片段（假设其中所有名字均为整型相关的变量。）

m = n;
while( m > 0) {
b = m / 2; m = m / 2;
for( i=0;i<b;i++) if (L[i] < L[i+m]) L[i] = L[i+m];
}
Max = L[0]; Min = L[n-1];
for(i=n/2;i<n;i++) if (L[i] < Min) Min = L[i];

给出上述程序片段的三地址代码；

（3）针对如下C程序及其在i386 Linux下的汇编代码（片段）：

#include<stdio.h>
union var{
char c[5];
int i;
};

int main(){

union var data;
char *c;

data.c[0] = '2';
data.c[1] = '0';
data.c[2] = '1';
data.c[3] = '6';
data.c[4] = '\0';

c = (char*)&data;

printf("%x %s\n",data.i,c);

return 0;
}

//C程序

       .section   .rodata
.LC0:
       .string    "%x %s\n"
       .text
.globl main
       .type       main,@function
main:

       movl       %esp, %ebp
       subl        $40, %esp
       andl        $-16, %esp
       movl       $0, %eax
       subl        %eax, %esp
       movb      $50, -24(%ebp)





       movl       %eax, -28(%ebp)



       pushl      $.LC0
       call        printf
       addl        $16, %esp

       leave
       ret
//汇编程序

（3.1）上述C程序的输出是什么？

（3.2）补全10处划线部分的汇编代码。

（4）针对以下C程序及其汇编代码：补全下划线部分的C语句或汇编代码

int test(int i,int j)
{
      int score;
if(                  )
            score = 100;
else
            score = 60;
   return score;
}//C程序

.text
.globl test
       .type       test,@function
test:
       pushl      %ebp
       movl       %esp, %ebp

       movl       8(%ebp), %eax
       cmpl       12(%ebp), %eax
       jle          .L4
       cmpl       $0, 12(%ebp)
       je           .L4
       cmpl       $10, 12(%ebp)
       jle          .L4
       cmpl       $0, 8(%ebp)
       je           .L4

cmpl       $20, 8(%ebp)
       jg           .L3
.L4:
       cmpl       $100, 8(%ebp)
       jg           .L3
       cmpl       $99, 12(%ebp)
       jle          .L2
       cmpl       $40, 8(%ebp)
       jg           .L2
       cmpl       $20, 12(%ebp)
       jle          .L3
       cmpl       $-10, 8(%ebp)
       jge          .L3
       jmp        .L2
.L3:
       movl       $100, -4(%ebp)
       jmp        .L5
.L2:
       movl       $60, -4(%ebp)
.L5:

       leave

ret

（5）扩展PL0编译器练习

Homework 5（2018年11月15日交）

lec9_1 pp61, e.g.14 语句 A[ i, j ] := B[ i, j ] * k 的翻译
数组A：A[ 1..10, 1..20] of integer;
数组B：B[ 1..10, 1..20] of integer;
w : 4 （integer）

我们还可以产生如下形式的三地址代码：

t1 := i * 80
t2 := j * 4
t2 := t1 + t2
t3 := A – 84

t4 := i * 80
t5 := j * 4
t5 := t4 + t5
t6 := B - 84
t7 := t6[t5]

t8 := t7 * k

t3[t2] := t8

尝试修改lec9_1中的数组元素地址计算的翻译方案，
使之输出上述形式的三地址代码。

Homework 4（2018年10月11日交）

（1）习题3.9（构造递归下降分析程序），3.11和3.16（a和b）

（2.1）删除以下文法G中的左递归，并由此得到文法G1。

	文法G: A是开始符号
1	A → B a
2	B → d a b
3	B → C b
4	C → c B
5	C → A c

(2.2) G1是否为LL（1）的文法？如不是，适当修改该文法G1，使之成为LL(1)的。

Homework 3（2018年9月27日交）

（1）阅读ANSI C 语法中从primary_expression 到 expression的产生式，

了解C语言表达式的语法定义，并设计如下表格给出其中C算符的优先级和结合性。

（制作电子版的哦）

优先级	算符（组）	结合性
1

（2）阅读ANSI C 语法中declaration相关产生式，给出如下声明的分析树：

int* (*b[10])[10];

Homework 2（2018年9月20日交）

（1）采用lec3 P38所列方法，给出习题2.3中(e)NFA。并对此NFA进行确定化和极小化。

（2）习题2.14。并给出相应的正规式R，使得L(R) = L(M)。

（3）习题3.1和3.3

Homework 1（2018年9月13日交）

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

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

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

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

（2）针对以下C程序，给出标号L处变量 j 可能的值集合。

int main()
{int i,j = 0;
for(i=0;i<10;i++)
{ switch(i)
{
    case 0:case 2: break;
    case 3:case 5: continue;
    default:    j = i;
}
L: j += i * 2;
}

}

（3）针对以下C/C++程序：

（3.1）补全相关代码

（3.2）用文字简要描述变量b和p的类型信息。

如变量a的类型信息描述如下：变量a是一个含10个元素的数组，每个元素是指向一个整型变量的指针。

int main()
{
    int i;
    int* q;
    int* a[10];
    int* (*b[10])[10];
    int* (*(*p)[10])[10];

    i = 100; q = &i; a[1] = q; b[1] = &a; p = &b;