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

openhelp100

编译原理基础辅导资料五
主    题：第二章词法分析
学习时间：2020年10月26日--11月1日“不忘初心、牢记使命”主题理论学习：
群众路线是我们党的生命线和根本工作路线，是我们党永葆青春活力和战斗力的重要传家宝。不论过去、现在和将来，我们都要坚持一切为了群众，一切依靠群众，从群众中来，到群众中去，把党的正确主张变为群众的自觉行动，把群众路线贯彻到治国理政全部活动之中。
                      摘选自《坚持和运用好毛泽东主席思想活的灵魂》《习近平谈治国理政》内    容：
我们这周主要学习第二章词法分析DFA构建的相关内容，希望通过下面的内容能使同学们加深对本章相关知识点的理解。
教学目标：
能够理解DFA构建的过程
重点和难点：
重点
  正规式
  状态转换图
  有限自动机
  DFA构建
  子集构造法
   DAF化简
难点
有限自动机
DFA or NFA
在机器上实现字符串识别过程是基于DFA? 还是基于NFA?
NFA更贴近于人们对正规式的认识
DFA因为每次状态转换都是确定性的，即从当前状态s与当前字符a，可以转换到唯一的目标状态s’。
DFA构建


途径1：DFA构建方法
实例：


途径2: 正则表达式=>DFA


实例：关系运算符的识别


状态转换图


途径3：正规式=>NFA=>DFA


从正规式到NFA
按照正规式的构建规则，逐步从简单到复杂地讨论从正规式构建NFA的过程。


从正规式到有限自动机
首先构造识别(和字母表中一个符号的NFA。




构建实例


本章练习题：选择题
1、以010结尾的二进制串的正规式为_______。
A. (1|0)*01    B.  0*01*      C. (1|0)*010   D. 0(1|0)*01
答案：C与(s|t)* (s|t)等价的正规式是_______。
A． s*| t*       B. (st)*(s|t)      C. (s|t)(s|t)*      D. (s|t)*
答案：C问答题
1、构造一个DFA，它接受Σ={0,1}上1的个数为3，而0的个数任意的字符串，如 0010101，1000110。        
答案：


拓展资料
从lex&yacc说到编译器(flex的使用)?
关于正则表达式的说明后,下面我们就来通过它,使用flex这个词法分析工具来构造我们的编译器的词法分析器.
关于lex的教程应该是很多,这里我就简单地介绍一下,然后着重后面的lex和yacc的配合使用以及其技巧.所以,如果你不看了后还是不太明白lex或者yacc的使用,请你自己上网去查查,这方面的教程是很多的.我知道的一篇常见的就是Yacc 与 Lex 快速入门Lex 与 Yacc 介绍
它的作者就是Ashish Bansal.
Flex就是fast lex的意思.而lex就是Lexical Analyzar的意思.flex可以在cygwin或者gnupro中找到.它是unix的一个工具,属于GNU组织产品.网上也可以找到单独可以在windows下用的版本.
我们一般把我们的词法扫描程序要扫描的一些单词(token)用正则表达式写好,然后作为lex的输入文件,输入命令flex xxx.l(xxx.l就是输入文件),lex经过处理后,就能得到一个名字叫lex.yy.c的C源代码.这个C源代码文件,就是我们的词法扫描程序.通常lex为我们生成的词法分析器的C源代码都是十分复杂而且庞大的,我们一般根本不会去查看里面的代码(放心好了,flex这个东西不会出错的)
下面让我们看看几个我已经使用过的几个lex输入文件.
这是一个前段时间我为GBA上的一个RPG游戏写的脚本引擎所使用的lex输入文件(部分)
例2.1
%{
/* need this for the call to atof() below */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "globals.h"
?
%}
digit????????[0-9]
number???????("-"|"+")?{digit}+
hexnumber????"0x"({digit}|[a-fA-F])+
letter???????[a-zA-Z]
identifier???({letter}|_)({number}|{letter}|_)*
newline??????[/n]
whitespace???[ /t]+
string???????/"[^"]*/"
comment??????"#"[^#]*"#"
%%
?
{string}?????{ return VM_STRING;????????}
"Logo"???????{ return VMIN_LOGO; }
"FaceIn"?????{ return VMIN_FACEIN; }
"FaceOut"????{ return VMIN_FACEOUT; }
"LoadTile"???{ return VMIN_LOAD_TILE;???}
"CreateRole" { return VMIN_CREATE_ROLE; }
"ReleaseRole" { return VMIN_RELEASE_ROLE;}
"CreateMap"??{ return VMIN_CREATE_MAP;??}
"ReleaseMAP" { return VMIN_RELEASE_MAP;}
"ShowBitmap" { return VMIN_SHOWBITMAP;??}
"CreateDialog" { return VMIN_CREATE_DIALOG; }
"ReleaseDialog" { return VMIN_RELEASE_DIALOG;}
"Fight"??????{ return VMIN_FIGHT;???????}
"Delay"??????{ return VMIN_DELAY;???????}
"PressA"?????{ return VMIN_PRESS_A;?????}
"PressB"?????{ return VMIN_PRESS_B;?????}
"PressR"?????{ return VMIN_PRESS_R;?????}
"PressL"?????{ return VMIN_PRESS_L;?????}
"PressStart" { return VMIN_PRESS_START; }
"PressSelect" { return VMIN_PRESS_SELECT;}
{number}?????{ return VM_NUMBER;????????}
{whitespace} { /* skip whitespace */????}
{identifier} { return VM_ID;????????????}
{newline}????;
.????????????;
%%
int yywrap()
{
??????return 1;
}
?
这里的lex输入文件一共有三个部分,用%%分开.第一部分中的%{和}%中的内容就是直接放在lex输出C代码中的顶部.我们通过它可以来定义一些所需要的宏,函数和include一些头文件等等.我的这个lex输入文件中也没什么特别的东西,就是常规的C源文件的include头文件
%{
/* need this for the call to atof() below */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "globals.h"
%}
?
第一部分中,除了前面的%{和}%包含的部分,下面的就是正则表达式的定义.
看了第一篇的正则表达式,这样你就能够在这里派上用场了.
让我们来看看我这里定义的正则表达式:
digit????????[0-9]
number???????("-"|"+")?{digit}+
hexnumber????"0x"({digit}|[a-fA-F])+
letter???????[a-zA-Z]
identifier???({letter}|_)({number}|{letter}|_)*
newline??????[/n]
whitespace???[ /t]+
string???????/"[^"]*/"
comment??????"#"[^#]*"#"
?
digit就不用说了,就是0-9的阿拉伯数字定义,第一篇文章中也举了这个例子.number就是digit的1到无限次的重复,再在其前面加上”+”和”-“符号.
注意:
“a”: 即使a是元字符,它仍是字符a
/a: 当a是元字符时候,为字符a
a?: 一个可选的a,也就是说可以是a,也可以没有a
a|b: a或b
(a): a本身
[abc]: 字符a,b或c中的任一个
[a-d]: a,b,d或者d中的任一个
[^ab]: 除了a或b外的任何一个字符
.: 除了新行之外的任一个字符
{xxx}: 名字xxx表示的正则表达式
?
这里需要特别说明的就是
newline??????[/n]
newline就是新行,这里我使用了[]把/n换行号括起来.因为如果我直接用/n表示的话,那么按照上面的规则,那就会看成/和n两个字符,所以我使用了[/n].有些时候newline也被写成[/n]|[/r/n].因为在文本文件中,一般换行一次,那么就是一个/n(0xA),可是在二进制文件中,换行有时候又是/r/n(0xD,0xA)一共两个字符号.
?
?
?
第二部分就是定义扫描到正则表达式的动作.
这些动作其实就是C代码,它们将会被镶嵌在lex输出的C文件中的yylex()函数中.
上面的例子的动作其实十分平常,就是返回一个值.
我们在外部使用这个lex为我们生成C代码的时候,只需要使用它的int yylex()函数.当我们使用一次yylex(),那么就会自动去扫描一个匹配的正则表达式,然后完成它相应的动作.这里的动作都是返回一值,那么yylex就会返回这个值.通常默认yylex返回0时候,表示文件扫描结束,所以你的动作中最好不要返回0,以免发生冲突.当然,动作中也可以不返回一值,那么yylex就会完成这个动作后自动扫描下一个可以被匹配的字符串,一直到扫描到文件结束.
当扫描到一个可以被匹配的字符串,那么这个时候,全局变量yytext就等于这个字符串
?
请大家一定记住这些正则表达式的顺序.
如果出现一个字符串,可以同时匹配多个正则表达式,那么它将会被定义在前面的正则表达式匹配.所以我一般把字符串string定义在最前面.
如果文件中的字符没有被lex输入文件中任何一个字符匹配,那么它会自动地被标准输出.所以大家一定要记住在每个正则表达式处理完毕后,一定要加上{newline}和.这两个正则表达式的动作.
?
好,让我们看看lex为我们输出C文件中提供一些常量
Lex 变量
yyin
FILE* 类型。 它指向 lexer 正在解析的当前文件。

yyout
FILE* 类型。 它指向记录 lexer 输出的位置。 缺省情况下，yyin 和 yyout 都指向标准输入和输出。

yytext
匹配模式的文本存储在这一变量中（char*）。

yyleng
给出匹配模式的长度。

yylineno
提供当前的行数信息。（lexer不一定支持。）

?
例2.2
这是<<编译原理与实践>>书中配套的源代码的lex输入文件.大家可以参考一下,作者为它自己定义的一个Tiny C编译所做的词法扫描器.
/****************************************************/
/* File: tiny.l?????????????????????????????????????*/
/* Lex specification for TINY???????????????????????*/
/* Compiler Construction: Principles and Practice???*/
/* Kenneth C. Louden????????????????????????????????*/
/****************************************************/
?
%{
#include "globals.h"
#include "util.h"
#include "scan.h"
/* lexeme of identifier or reserved word */
char tokenString[MAXTOKENLEN+1];
%}
?
digit???????[0-9]
number??????{digit}+
letter??????[a-zA-Z]
identifier??{letter}+
newline?????/n
whitespace??[ /t]+
?
%%
?
"if"????????????{return IF;}
"then"??????????{return THEN;}
"else"??????????{return ELSE;}
"end"???????????{return END;}
"repeat"????????{return REPEAT;}
"until"?????????{return UNTIL;}
"read"??????????{return READ;}
"write"?????????{return WRITE;}
":="????????????{return ASSIGN;}
"="?????????????{return EQ;}
"<"?????????????{return LT;}
"+"?????????????{return PLUS;}
"-"?????????????{return MINUS;}
"*"?????????????{return TIMES;}
"/"?????????????{return OVER;}
"("?????????????{return LPAREN;}
")"?????????????{return RPAREN;}
";"?????????????{return SEMI;}
{number}????????{return NUM;}
{identifier}????{return ID;}
{newline}???????{lineno++;}
{whitespace}????{/* skip whitespace */}
"{"?????????????{ char c;
??????????????????do
??????????????????{ c = input();
????????????????????if (c == EOF) break;
????????????????????if (c == '/n') lineno++;
??????????????????} while (c != '}');
????????????????}
.???????????????{return ERROR;}
?
%%
?
TokenType getToken(void)
{ static int firstTime = TRUE;
??TokenType currentToken;
??if (firstTime)
??{ firstTime = FALSE;
????lineno++;
????yyin = source;
????yyout = listing;
??}
??currentToken = yylex();
??strncpy(tokenString,yytext,MAXTOKENLEN);
??if (TraceScan) {
????fprintf(listing,"/t%d: ",lineno);
????printToken(currentToken,tokenString);
??}
??return currentToken;
}
?
这里有点不同的就是,作者用了另外一个getToken函数来代替yylex作为外部输出函数.其中getToken里面也使用了lex默认的输出函数yylex(),同时还做了一些其它的事情.不过我建议大家不要像作者那样另外写自己的结果输出函数,因为在后面,需要和yacc搭配工作的时候,yacc生成的语法分析程序只认名字叫yylex()的词法结果输出函数.
if (firstTime)
??{ firstTime = FALSE;
????lineno++;
????yyin = source;
????yyout = listing;
??}
其中的yyin,yyout,source,listing都是FILE*类型.yyin就是要lex生成的词法扫描程序要扫描的文件,yyout就是基本输出文件(其实我们通常都不用yyout,即使要生成一些输出信息,我们都是自己通过fprintf来输出).
"{"?????????????{ char c;
??????????????????do
??????????????????{ c = input();
????????????????????if (c == EOF) break;
????????????????????if (c == '/n') lineno++;
??????????????????} while (c != '}');
????????????????}
其中,作者的这个Tiny C是以{}来包括注释信息.作者并没有写出注释信息的正则表达式,但是它可以通过检索“{”,然后用lex内部函数input()一一检查 { 后面的字符是不是 } 来跳过注释文字.(C语言的/* */注释文字正则表达式十分难写,所以很多时候我们都用这种方法直接把它的DFA(扫描自动机)写出来).
?
本文就是通过简单地举出两个比较实际的例子来讲解flex输入文件的.再次说明,如果你是第一次接触lex,那么请看看前面我推荐的文章,你可以在IBM的开发者网上查到.下一篇关于yacc于BNF文法的说明也是如此.请大家先参考一下其它标准的教程.
本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986