编译原理 CS-143(更新至week4)_开发一个编译器来解析源代码,以下哪些算法可以帮助你完成这个任务:递归下降解析,l

Pre-Course Survey

一个小调查，无伤大雅

实验所需虚拟机
链接: https://pan.baidu.com/s/16KXICHhpBb22v4CyNQugMg 提取码: n44a

Navigation Your Course

课程导览

属性bar用的

介绍了 课程模块，大纲模块，讨论模块，测评模块，测评模块会打分

讨论模块要遵守规则，不发一些不必要的内容，淫秽色情，垃圾邮件，抄袭的内容

01-01: Introduction (8m20s)

编程语言又两种实现，也就是编译器和解释器

解释器做了啥

我们将数据和程序发送给了解释器，解释器开始运行，有了输出，解释器相当于是一个在线的

写一个程序，产生了一个可执行文件，当然不只是可执行文件

可能是汇编，字节码之类的，

现在你不需要输入数据，就能得到输出

在结构中就是线下，

当然是相对于解释器的，解释器需要结合一个数据进行执行，而编译器不需要

因此，我们不需要对程序进行重编译或者做其他处理，我们就能对可执行程序传入很多不同的值或数据集进行处理

编译器开发历史：

IBM 704软件成本超过了硬件成本

用解释器比你直接跑代码会慢很多，10-20倍

fortran

直接翻译成机器可执行的，会快很多

formulas translated 公式翻译

有些仍然保留了FORTRAN 1的框架

什么是fortran 1 框架呢

lexical Analysis 词法分析

parsing 解析

这两个共同关注语言的语法部分syntactic

semantic analysis 语义分析，关注语义方面，包括类型和作用域

optimization 优化 运行的更快，更节省

code generation 也就是translation 转换，转换结果可以是字节码，机器码，或者是另一种高级语言

01-02: Structure of a Compiler (13m53s)【编译器结构】

first step：recognize words

对单词的认识/理解

this is a sentence

你需要理解 大小写，空格，句点才能够正确的理解这个意思

如果给我们一个其他的

ist his ase nte nce

is this a sentence

我们也无法很容易得到结果

词法分析的目标，就是将程序代码文本按照他的方式进行分词，

也就是对词的一个区分

这个句子，分为几个token呢（词法单元）

if,then,else,

x,y,z

1,2

=，空格 ，

同时，我们仍然要区分一个等于号和两个等于号

句法分析

分析词的意思后（名词，动词，形容词），我们就会有句法

（主语subject，谓语verb，宾语object）

共同构成了一个句子树，这就是一个英文句子进行语法分析的例子

代码也同理

针对if then else进行分析

if-then-else就是解析树的树根

如下为if-then-else的分析树

if then else

分成了三个部分，断言部分，then部分，else部分

if包含了 x == y

then包含了 z = 1

else 包含了 z = 2

句意分析

当理解句子结构厚，我们就要去理解这句话写了什么内容

编译器只能做有限的语义分析，找到自相矛盾的地方，

example

jack said jerry left his assignment at home

这里的his 我们无法知道他是指定jack还是jerry

worse

jaca said jack left his assignment at home

这个更糟糕的情况，我们不知道有几个人，jack是两个人，his是一个人？

可能性很多

编程语言中，为了避免这种尴尬，就有了变量绑定

非常严格的规则，防止歧义

如上的程序，会输出4

外层的定义jack会被隐藏

编译器执行文本的语义分析时，不需要考虑对变量进行作用域的绑定分析

jack和her的类型不匹配，肯定不是一个人

optiimization（优化）

比较像一个专业的编辑在一定的字数范围内对文章长度做删减

but a little bit like editing

替换为

but akin to editing

意思没变，但是词变少了，节省了资源

run faster，use less memory，lower power,database,network

一个需要优化的程序

y*0 和给x赋值为0 是一致的，因此我们比起乘法，仅仅做赋值即可

但是这个不是一个正确的规则

仅仅对integer有效

浮点数无效，

finally code Gen

也就是翻译成其他语言，编译器把高级语言转换为汇编语言

最基本的fortran对于语义分析会很小

而现代的编译器，优化会占据很大

01-03: The Economy of Programming Languages (19m51s)【编译器性价比】

本节课，将会谈论这三个问题，

为什么这么多的语言
为什么又新的语诞生
什么是一个好的编程语言
1
2
3

首先第一个

why are there so many progamming languages

首先我们是有三个大概的范围，应用领域不同

他们的优势不同，作用域不同，语言不同

科学研究：需要好的浮点数运算，FP，好的数组支持，大并行支持（parallelism）FORTRAN语言 （公式 翻译）fomulate translate

商业领域：需要好的稳定性，防止丢失数据，而且要可靠，需要报告的生成，数据分析，数据处理之类的， 也就是SQL比较常用

系统编程：也就是嵌入式，控制设备之类的，我们需要控制一些底层的资源，细粒度控制，需要能够预判时间（实时控制），在一定时间内做出反应，或者对网络进行大量的响应 广泛的就是c和c++

why are there new programming languages？

为什么需要设计一个新的语言

培养程序员以及培养某种语言程序员的成本 这个比较重要，如何教会他们去使用

因为去开发，去开发一个新的编译器的成本并不是很高

有如下的预测

有两点，也就是

第一个预测是 广泛使用的编程语言改变的很慢，会越来越保守

第二个预测是 很容易的去开发一个新的语言，培训成本为0，新的编程语言进化的会很快。

productivity > tranning cost

生产力要大于学习耗费

就会选择新的语言

什么时候呢？

需要一种语言去填补空白的时候（新的应用领域），往往 会选择新的语言

旧的语言不一定能够支持新的应用领域

新的语言有时候会看起来像旧的语言，就比如java很像c++

猜测:为了降低培训成本，通过学过的语言更轻松的去解除

what is a good programming language？

从语言设计的通用性来说，没有一个好的编程语言

讨论这个问题，无法达成共识，关于什么是好的语言，也没有普遍接受的共识，

讲师的猜测：

是大众的接受度/使用度，可以作为是一个好的语言的标准

Summarize

很难设计出一个整合你所有想要功能的语言

培养程序员花费了大量成本

02-01: Cool Overview (19m58s)【cool语言概述】

classroom object oriented language = cool

课堂专用面向对象语言

被设计短期内/一个学期内写出编译器，需要易于编写

本课程的目的：完整的编译器编写，包括MIPS 指令集

我们可以运行编译器，也可以生成mips汇编语言，然后可以在你能访问的任何机器上模拟mips汇编语言

分为五个任务，编译器本身包含四个阶段

词法分析

语法分析

语义分析

代码生成

我们编写如上模块采用的是 插件兼容

也就是，我们可以使用模板填充其他几个，然后我们只是去编写词法分析，然后和标准输出进行比对，保证自己编写的足迹按没问题

优化可以当一个可选的作业

开始编写程序

1- 每个cool程序必须要有一名为main的class

class main{

};
1
2
3

class 后面跟名字，然后花括号带分号结尾

一个程序包含若干类

main类中，main方法必须存在，这个方法用来启动程序，此外，这个方法必须无参，main方法永远无参

class Main{
	main():Int{
	1
	};
};
1
2
3
4
5

在main类中，有一个main方法

cool中，需要对方法指明返回值的类型，这里写int

cool是一种表达式语言，也就是一段代码

表达式可以写的随意一点，即这个表达式对于这个方法的表达而言没有显示的返回语句

() -> a+b ,返回a+b的值
1

上面那个方法体中只有一个数字1 所以运行程序的时候，返回的就是这个方法的值

那么如何编译？

coolc就是cool的编译器，

coolc 1.cl

就会生成1.s的新文件，

我们尝试运行，spim（mips模拟器）

接着出现了一些数据，例如 执行了多少条指令，load指令，store指令，和一些分支的数量

spim 1.s
1

stat里面的参数是为了让我们进行优化使用的，现在我们不需要考虑

如果在cool程序中打印出某些内容，则必须对此操作进行明确声明

cool中有特殊的类，也就是IO原始类

可以为main这个类进行属性的声明，我们声明一个属性为IO的i变量，同时给i分配一个新的对象，之后就能用它进行IO操作了

class Main{
	i : IO <- new IO;
	main():Int{
	1
	};
};
1
2
3
4
5
6

在main方法中，添加out_string的调用，

i.out_string() 就是我们调用方法的方式

我们尝试输出helloworld

class Main{
	i : IO <- new IO;
	main():Int{
		{
		i.out_string("Hello World\n");
		1;
	};
};
1
2
3
4
5
6
7
8

方法中语句块由用分号分隔的一系列表达式组成，

tips：

感叹号小贴士

!运算符跟着之前输入的命令前缀，就可以执行之前的命令
例如：
执行过coolc 1.cl
那么我们执行
!c
和coolc 1.cl是一样的
1
2
3
4
5
6

修改：

{i.out_string(“hello world”);}1; 很繁琐，修改成如下问题，但是返回值类型会不同，不是int了，类型匹配出错

class Main{
	i : IO <- new IO;
	main():Int{
	i.out_string("Hello World\n");
	};
};
1
2
3
4
5
6

因此我们修改成IO

class Main{
	i : IO <- new IO;
	main():IO{
	i.out_string("Hello World\n")
	};
};
1
2
3
4
5
6

当然我们可以增加自己的灵活性

main返回结果设置为object

class Main{
	i : IO <- new IO;
	main():Object{
	i.out_string("Hello World\n");
	};
};
1
2
3
4
5
6

这里我们在外面进行定义，我们可以直接在里面调用

class Main{
	main():Object{
	(new IO).out_string("Hello World\n");
	};
};
1
2
3
4
5

或者说，我们main类直接继承io，main就能够拥有io的所有功能,cool中self等于this

class Main inherits IO{
	main():Object{
	self.out_string("Hello World\n");
	};
};
1
2
3
4
5

或者，cool的特性，不显式命名调用对象的情况下调用方法默认为self

class Main inherits IO{
	main():Object{
	out_string("Hello World\n");
	};
};
1
2
3
4
5

02-02: Cool Example II (15m04s)【cool样例2】

这次我们写阶乘，不写hello world

class Main{
	main():Object{
		(new IO).out_string("1\n")
	};
};
1
2
3
4
5

我们想让用户输入，然后进行输出

需要调用in_string,同时为了美观，我们组合一个换行

class Main{
	main():Object{
		(new IO).out_string((new IO).in_string().concat("\n"))
	};
};
1
2
3
4
5

我们输入多少，就会返回多少

接下来，我们讨论如何将字符串转换为整数

阶乘计算需要对数字，我们这里接受的是字符串

cool中有一个专门编写的库用来做整数和字符串之间的转换

也就是A2I 意思是ascii码转换为整数

class Main inherits A2I{
	main():Object{
		(new IO).out_string(i2a(a2i((new IO).in_string())+1).concat("\n"))
	};
};
1
2
3
4
5

代码的意思就是，输入的字符串ascii转整数 然后加一然后 整数转ascii（字符串）输出

但是编译器中没有提供a2i的相关函数，需要我们在编译的时候，指明我们需要的函数，

coolc fact.cl atoi.cl
1

我们找到相关atoi.cl库函数

复制到code中，即可编译完成

我们来编写阶乘，需要调用fact（阶乘）函数

在cool中，if的结构是 if-then-else-fi 也就是一个完整定义

这里可能会感到奇怪，i=0不是赋值么，但是这里确实是一个判断

class Main inherits A2I{
	main():Object{
		(new IO).out_string(i2a(fact(a2i((new IO).in_string())).concat("\n"))
	};

    fact(i:Int):Int{
        if(i = 0) then 1 else i * fact(i-1) fi
    };
};
1
2
3
4
5
6
7
8
9

我们尝试把i == 0试试

发现编译失败

我们接下来使用循环来写阶乘

我们在cool中使用let声明局部变量

定义fact值为1

cool中赋值为<-

循环的开始和结束是loop和pool

最后一个语法块的值，就是这个方法的返回值

class Main inherits A2I{
	main():Object{
		(new IO).out_string(i2a(fact(a2i((new IO).in_string()))).concat("\n"))
	};

    fact(i:Int):Int{
        let fact:Int <- 1 in{
  			while(not (i = 0)) loop
            {
            	fact <- fact *i;
            	i <- i-1;
            }
            pool;
            fact;
        }
    };
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

02-03: Cool Example III (18m05s)【cool样例3】

本次课程，我们学习创建list

let表达式可以定义多个常量,使用逗号做分隔符

class Main inherits IO{
	main() : Object{
	let hello : String <- "Hello",
	    world : String <- "World!!",
	    newline : String <- "\n"
	in
		out_string(hello.concat(world.concat(newline)))
	};
};
1
2
3
4
5
6
7
8
9

没有问题

然后，我们不使用这样的引入，而是使用一个抽象的list，构建字符串列表

list都会包含两部分，一个是值，一个是next指针指向其他list

nil:List 如果不赋值，默认是为空的也就是void

isvoid cool自带的检查是否为空

class List{
	item:String;
	next:List;
	
	init(i:String, n:List):List{
		{
			item<-i;
			next<-n;
			self;
		}
	};
	
	flatten():String{
        if(isvoid next) then
            item
        else
            item.concat(next.flatten())
        fi
    };
};
class Main inherits IO{
	main() : Object{
	let hello : String <- "Hello",
	    world : String <- "World!!",
	    newline : String <- "\n",
	    nil:List,
	    list:List <- (new List).init(hello,(new List).init(world,(new List).init(newline,nil)))
	in
		out_string(list.flatten())
	};
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

同样，成功输出

我们这里item可以进行修改，成为object

同时，我们需要修改flatten，通过case进行选择他的类型进行输出

如果传入int 那就i2a，其他同理

abort函数，终止并退出,返回一个object对象，但是这里的case需要返回stirng对象，我们放入语句块中

case分支必须分号结束

class List inherits A2I{
	item:Object;
	next:List;
	
	init(i:Object, n:List):List{
		{
			item<-i;
			next<-n;
			self;
		}
	};
	
	flatten():String{
       let string:String <-	
       	   case item of
       	   		i:Int => i2a(i);
       	   		s:String =>s;
       	   		o:Object =>{abort();"";};
       	   esac
       	in
       		if(isvoid next) then
           		string
            else
                string.concat(next.flatten())
            fi
    };
};
class Main inherits IO{
	main() : Object{
	let hello : String <- "Hello",
	    world : String <- "World!!",
	    i:Int <-42,
	    newline : String <- "\n",
	    nil:List,
	    list:List <- (new List).init(hello,
	    					(new List).init(world,
	    							(new List).init(i,(new List).init(newline,nil))))
	in
		out_string(list.flatten())
	};
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

CS-143 Week2 Lexical Analysis&Finite Automata[词法分析和有限自动机]

03-01: Lexical Analysis (12m06s)【词法分析】

我们对该段进行分割

if(i == j)
	z = 0;
else 
	z = 1;
1
2
3
4

将他们转换成为（token）词法单元，if，变量名 i,n,j 关系运算符，== 之类的

在词法分析器的眼中，是这样的

\tif(i==j)\n\t\tz=0;\n\telse\n\t\tz=1;
1

整个代码就像字符串，也可以类比作为字节

词法分析器通过绘制分割线，将字符串转换为词法单元

Token class（标记类）

光分词法单元是不行的，需要根据作用进行分类

这里类比在英语中，和在编程语言中的标记类

每个标记类，都会对应程序中的一组字符串，

比如：

名词：apple，banana，。。。

keywords：if，else，while

标记类对应一组字符串，也就是，这组字符串可以用来被标记类描述

identifier（标识符）

大多数编程语言中，标识符的标记类是字母或数字，以字母开头

例子：C语言中

integer（整数）

非空数字字符串
例：0，12，001，00，
keyword：
keywords：if，else，while

whitespace（空格）
空格也是一个标记类
例：if_ _ _()这里三个空格，就会被当作一个空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

词法分析的目标是根据程序的子串的角色，然后对其进行分类

这里的role就是一个标记类

然后把标记类传递给解析器

这里是词法分析器和解析器之间的传递

1- 词法分析器获取到字符串，并存储为字节序列

2-发送给解析器的时候是一个序列对<class,string>,也就是，标记类和你的子字符串，也就是<class,string> 这个pair叫做token

例如：

如果字符串是

“foo = 42”

会传递三个token（词法单元）

<identifier,“foo”>,<operator,"=">,<“integer”,“42”>

传递的单元是以字符串形式来存储的，这里的42也是字符串

这些序列传递给解析器

词法分析器本质：
输入字符串并将其分块儿为成对的序列，其中每一个对都是一个标记类和原始输入的子字符串
1
2

样例分析

\tif(i==j)\n\t\tz=0;\n\telse\n\t\tz=1;
1

我们首先写一下标记类

whitespace  空格，回车，tab
keywords
identifiers
numbers（integer）
operator

1
2
3
4
5
6

特例： ( 、) 、;、= 这四个是单字符标记类,一组中只有这一个字符串

但是一个特殊的== 归类为关系运算符的标记类

这里使用开头首字母当作划分

\tif(i == j)\n\t\tz=0;\n\telse\n\t\tz=1;

w|k|(|i|w|o|w|i|)|w|w|w|i|=|n|;|w|w|k|w|w|w|i|=|n|;
1
2
3

Summarize

总结两点，

第一个：识别输入中与标记相对应的子字符串

tips 这是编译器的术语，这些子字符串称为词素lexemes（构成词的要素）

第二个，对于每个词素，我们需要确定标记类token class

<token class,lexemes> 等于token

Quiz

x=0;\n\twhile (x < 10) { \n \tx++; \n }
W: Whitespace
K: Keyword
I: Identifier
N: Number
O: Other Tokens:
{ } ( ) < ++ ; =
ionowwkwoiwownwowwwwioowwwo
虽然对空格有异议，但是I K N 是固定的，3 1 2

1
2
3
4
5
6
7
8
9
10

Note that '\t\n' is a single whitespace token. Also remember that 'x' is an identifier but 'while' is a keyword. Finally, note that '++' and '10' are both single tokens.
请注意“\t\n”是单个空白标记。还要记住，“x”是一个标识符，“while”是一个关键字。最后，请注意，'+'和'10'都是单个标记。
1
2

03-02: Lexical Analysis Examples (13m03s)【词法分析案例】

在fortran中，空格是不重要的

例如:VAR1 和 VA R1是一样的

fortran理念：你可以将程序中所有的空格删除，但是不会改变你程序想要表达的东西

tips:以后的例子部分来自龙书