编译原理学习笔记

视频

编译器结构

词法分析 Lexical analysis or scanning

词法分析把程序字段变成关键字words or 词法单元tokens

if x == y then z = 1; else z = 2;

分号,标点,分隔符都是词法单元

语法分析syntax analysis parsing

if then else包含三部分

predicate条件判断,then语句和else语句

{% asset_img image-20200626235143347.png image-20200626235143347 %}

语义分析

尝试去找出矛盾的地方

优化

修改代码使之使用更少的资源

代码生成

高级语言转变成汇编

Cool语言

class Main {
    i : IO <- new IO;
    main() : Int { { i.out_string("Hello wordld!\n"); 1;} };
};

Int 是return type。

class Main {
    i : IO <- new IO;
    main() : IO { { i.out_string("Hello wordld!\n"); } };
};//一旦打印完string就退出
class Main {
    i : IO <- new IO;
    main() : Object { { i.out_string("Hello wordld!\n"); } };
};//Object 返回类型

class Main {
    main() : Object { { (new IO).out_string("Hello wordld!\n"); } };
};

下面是继承的写法

class Main inherits IO{
    main() : Object { { self.out_string("Hello wordld!\n"); } };
};

class Main inherits IO{
    main() : Object { { out_string("Hello wordld!\n"); } };
};

词法分析

目标是将输入流划分为词素。

从左到右的扫描字符串,有时必须对输入字符串向前看,才能弄清楚当前字符串和子字符串在语言中的角色

变量名称:字母开头

字符串-> 语法分析器 ->变成token<class, string> parser解析器

foo = 42 -> <Id, “foo”> <operator, “=”> <Int, “42”>

有以下几类:

  • 空格whitespace
  • keyword
  • identifiers
  • numbers

这些子字符串称为词素(构成词的要素),<token class, lexemes词素>,这就是一个token

正则表达式

基础表达式

单字符

‘c’ = {‘c’}

Epsilon

Epsilon = {“”} = 单个字符的空字符串 != 空字符串

复合表达式

Union

A + B = {a|a属于A} U {b|b属于B}

A并B

Concatencation 级联

如[a,b]与[c,d]级联得到[ac,ad,bc,bd]

AB = {ab | a属于A ^ b 属于B }

Iterator 串联

A* = 0到无穷个A串联

匹配变量名

A+ = AA* = 至少一个A

digit = ‘0’ + ‘1’ + ‘2’ + ‘3’ + ‘4’ + ‘5’ + ‘6’ + ‘7’ + ‘8’ + ‘9’

letter = [a-zA-Z] 匹配所有字母

letter(letter+digit)* 字母+0或多个字母和数字的组合

空格 ‘ ‘ + ‘\n’ + ‘\t’

opt_function = (‘.’digits)?

Opt_exponent = (‘E’(‘+’ + ‘-‘)?digits)?

###词法规范

当输入值有两种不同的前缀,且这两种都是有效的词法单元时,就应该选择最长的那个,最长匹配原则Maximal Munch

当匹配到两个规则的时候,如keiword,identifiers,会优先匹配第一个choose the one listed first。

捕获有可能错误字符串的正则表达式并赋予其最低优先级

有限自动机Finite Automata

定义

  • 一组能读取的输入字符串
  • 一个有限状态的集合
  • 一个特殊的集合被设定为开始状态
  • 一组用于接受状态的集合(读取完可接受状态输入后自动结束,否则拒绝输入
  • 有一些用于状态转换的集合

Exampls

确定性自动机和非确定性自动机的区别

DFA只有一条道可以通过

NFA基于输入执行,可能处于许多不同的状态,只要有任何一条路径可以接受,就会处于接受状态 ,这个字符串就属于这个NFA可以接受的语言

NFA要远比DFA来的小,可以成倍缩小,DFA执行速度更快

将正则表达式转换为NFA 非确定性有限自动机

NFA to DFA

Epsilon-closure:是状态选择,可以是一组状态,但只针对单个状态进行处理,只关注那些仅通过空跳就可以到达的状态。

N种状态,可用状态数量子集|S| <= N,公用2^N -1种非空子集

所维护的每一个属性都指代一条计算执行路径,DFA的状态记录了NFA基于相同输入可能进入的可能状态集

原视频讲解链接:link 11:15秒

实现有限自动机

实现NFA

节省了大量表空间,但是

执行速度比确定性自动机慢很多

总结

DFA执行速度更快,结构上较为松散

NFA速度较慢,结构紧凑

PA2

https://github.com/mrbelieve128/Stanford-Compilers-PA/tree/master/PA2


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

Natas 下一篇