大工20秋《编译原理基础》辅导资料四

作业辅导

编译原理基础辅导资料四
主    题：第二章词法分析
学习时间：2020年10月19日—10月25日“不忘初心、牢记使命”主题理论学习：
坚持党的领导，最根本的是坚持党中央权威和集中统一领导。党章规定“四个服从”，最根本的是全党各个组织和全体党员服从党的全国代表大会和中央委员会；党中央强调“四个意识”，最根本的是坚决维护党中央权威和集中统一领导。这都不是空洞的口号，不能只停留在表态上，要落实到行动上。
     摘选自《在十九届中央纪律检查委员会第二次全体会议上的讲话》内    容：
我们这周主要学习第二章词法分析有限自动机的相关内容，希望通过下面的内容能使同学们加深对本章相关知识点的理解。
教学目标：
能够理解有限自动机的概念
重点和难点：
重点
  正规式
  状态转换图
  有限自动机
  DFA构建
  子集构造法
   DAF化简
难点
有限自动机
一、有限自动机
1、DFA
识别器：是一个程序，取串x作为输入，当x是语言的句子时，它回答“是”，否则回答“不是”。
状态转换图（有限自动机）(识别器
确定/不确定有限自动机——时空权衡问题
确定有限自动机：快，空间大
确定的有限自动机（简称DFA）
DFA是这样一个数学模型，包括
状态集合S
输入字母表(
转换函数 move: S ( ( ( S
唯一的初态s( S
终态集合F ( S
2、NFA
不确定的有限自动机（简称NFA）
数学形式定义
NFA是这样一个数学模型，包括
状态集合S
输入字母表(
转换函数 move: S ( ((({(}) ( P(S)
唯一的初态s( S
终态集合F ( S
缺点：1）输入字符包括 (
2）一个状态对于某个字符，可能有多条输出边例 识别aa*|bb*的NFA




3、DFA与NFA的区别


状态转移表 (a|b)*ab
状态迁移动作，从开始状态到目标状态


优点：快速定位
缺点：字母表过大或大部分转换状态为空集时浪费空间本章练习题：填空题
1、设有C语言的程序段如下：
while ( i<= j )
{ c = 2015;
j = j + k;
i = i + 1;
}
则经过词法分析后可以识别的单词个数是_________个。
答案：24
2、从NFA构造出可识别同样语言的DFA，这个算法通常称为_________。
答案：子集构造法
问答题
1、构造正规式R＝0(10|01)*0的DFA
答案：
(1)根据正规式到转换NFA方法，构造 NFA M1

(2)根据NFA到DFA转换方法，构造 DFA M

写出字母表∑={a, b}上语言L={w| w中a的个数是偶数}的正规表达式，并给出接受该语言的最小状态DFA。
答案：
(b*ab*ab*)*b*
拓展资料
从lex&yacc说到编译器(正则表达式)
?
学过编译原理的朋友肯定都接触过LEX这个小型的词法扫描工具.?但是却很少有人真正把LEX用在自己的程序里.?在构造专业的编译器的时候,常常需要使用到lex和yacc.?正是因为这两个工具,使得我们编写编译器,解释器等工具的时候工作变得非常简单.不过话说回来,会使用lex和yacc的人也确实不简单. Lex和yacc里面牵涉到一系列的编译原理的理论知识,不是简单地看看书就能搞懂的.?本文只是简单地介绍一下lex和yacc的使用方法.相关编译理请查看本科教材.
?
国内大学教材里面对于lex和yacc的介绍很少,有些根本就没有,不过在国外的编译原理教材介绍了很多.?按照学科的分类,国内大学本科里面开的<<编译原理>>教程只是讲解编译的原理,并不讲解实践.?而对于实践方面则是另外一门学科<<编译技术>>.关于编译技术的书籍在国内是少之又少.?前不久,?听说上海交大的计科内部出版过编译技术的教材.可惜我们这些人就无法得见了.?还好,机械工业出版社引进了美国?Kenneth C.Louden所著的经典著作<<编译原理及实践>>中,比较详细地介绍lex和yacc的使用.
?
Lex属于GNU内部的工具,它通常都是gcc的附带工具.?如果你使用的Linux操作系统,那么肯定系统本身就有lex和yacc,不过yacc的名字变成了bison.?如果你使用的Windows操作系统,那么可以到cygwin或者GNUPro里面找得到.?网上也有windows版本lex和yacc,大家可以自己去找一找.
?
本文一共有两篇,一篇是介绍lex,另一篇是介绍yacc.??Lex和yacc搭配使用,?我们构造自己的编译器或者解释器就如同儿戏.?所以我把本文的名字叫做黄金组合.
?
本文以flex( Fase Lex)为例,两讲解如何构造扫描程序.
Flex可以通过一个输入文件,然后生成扫描器的C源代码.
?
其实扫描程序并不只用于编译器?.比如编写游戏的脚本引擎的时候,我看到很多开发者都是自己写的扫描器,其算法相当落后(完全没有DFA的概念化),?甚至很多脚本引擎开发者的词法扫描器都没有编写,而是在运行过程中寻找token(单词).?在现代的计算机速度确实可以上小型的脚本引擎在运行中进行词法扫描,?但是作为一个合格的程序员,?或者说一个合格的计算机本科毕业生而来说,?能够运用编译原理与技术实践,应该是个基本要求.
?
如果要说到词法分析的扫描器源代码编写,?其实也很简单,?会C语言的人都会写.?可是Kenneth Louden在<<编译原理及技术>里面,花了50多页,原因就是从理论角度,介绍标准的,可扩展的,高效的词法扫描器的编写.?里面从正则表达式介绍到DFA(有穷自动机),再到NFA(非确定性有穷自动机),最后才到代码的编写.?以自动机原理编译扫描器的方法基本上就是现在词法扫描器的标准方法,?也就是Lex使用的方法.?在Lex中,我们甚至不需要自己构造词法的DFA,?我们只需要把相应的正则表达式输入,?然后lex能够为我们自己生成DFA,然后生成源代码,可谓方便之极.
?
本文不讲DFA, lex的输入是正则表达式,?我们直接先看看正则表达式方面知识就可以了.
?
1.正则表达式(regular expression):
?
对于学过编译原理的朋友来说,这一节完全可以不看.不过有些东西还是得注意一下,因为在flex中的正则表达式的使用有些具体的问题是在我们的课本上没有说明的.
先看看例子:
例1.1
name??????Tangl_99
这就是定义了name这个正则表达式,它就等于字符串Tangl_99.所以,如果你的源程序中出现了Tangl_99这个字符传,那么它就等于出现一次name正则表达式.
?
例1.2
digit????????0|1|2|3|4|5|6|7|8|9
这个表达式就是说,正则表达式digit就是0,1,2,…,9中的某一个字母.所以无论是0,2,或者是9…都是属于digit这个正则表达式的.
“|”符号表示”或者”的意思.
那么定义正则表达式?name???Tangl_99|Running,同样的,如果你的源程序中出现了Tangl_99或者Running,那么就等于出现了一次name正则表达式.
?
例1.3
one???????1*
“*”符号表示”零到无限次重复”
那么one所表示的字符串就可以是空串(什么字符都没有), 1, 11, 111, 11111, 11111111111, 11111111…等等.总之,one就是由0个或者N个1所组成(N可以为任意自然数).
与”*”相同的有个”+”符号.请看下面的例子1.4
?
例1.4
realone????1+
“+”符号表示”1到无限次重复”
那么realone和one不同的唯一一点就是,realone不包含空串,因为”+”表示至少一次重复,那么realone至少有一个1.所以realone所表达的字符串就是1,11,111, 1111, 11111…,等等.
?
例1.5
digit??????[0-9]
letter?????[a-zA-Z]
这里的digit等于例1.2中的digit,也就是说,a|b|c就相当于[a-c].
同理,letter也就是相当于?a|b|c|d|e|f|…|y|z|A|B|C|D…|Z?不过注意的一点就是,你不能把letter写成[A-z],而必须大写和小写都应该各自写出来.
?
例1.6
notA????????[^A]
“^”表示非,也就是除了这个字符以外的所有字符
所以notA表示的就是除了A以外的所有字符.
下面让我们来看看一些一般高级程序语言中常用的综合例子.
digit????????[0-9]
number?????{digit}+
letter???????[a-zA-Z_]
digit前面多次提起过,就是0-9的阿拉伯数字.number就是所有的数字组合,也就是整数.
Letter前面也提起过,唯一不同的就是多了一个下划线.因为一般我们的C语言中容许有下划线来表示定义的变量名,所以我也把下划线当成英语字母来处理了.
这里number中使用上面定义的digit正则表达式.在lex中,用{digit}就是表示正则表达式digit.
?
newline??????[/n]
whitespace???[ /t]+
newline就是提行的意思.这里我们使用的是/n这个符号,它和C语言中表示提行号一致.问题是大家可能要问到为什么要使用[]符号.因为在lex中,如果你使用[],那么里面表示的肯定就是单个字符号,而不会被理解成”/”和”n”两个字符。
Whitespace就是空格符号的意思.一般的高级程序语言中有两种,一种就是简单的空格,还有一种就是/t制表符.使用了”+”符号,就表示了这些空白符号的无限组合。本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986