实验一词法分析器.ppt

《实验一词法分析器.ppt》由会员分享，可在线阅读，更多相关《实验一词法分析器.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1词法分析器词法分析器编译原理编译原理上机作业（上机作业（1 1）2一、上机作业的目的一、上机作业的目的 通通过过做做上上机机题题加加深深对对编编译译器器构构造造原原理理和和方方法法的的理理解解，巩固所学知识。巩固所学知识。会用正规式和产生式设计简单语言的语法；会用正规式和产生式设计简单语言的语法；会用递归下降子程序编写编译器或解释器；会用递归下降子程序编写编译器或解释器；会写上机报告。会写上机报告。二、上机题目简单函数绘图语言的解释器二、上机题目简单函数绘图语言的解释器 2.1 2.1 题目简述题目简述 实现简单函数绘图的语句实现简单函数绘图的语句 循环绘图（循环绘图（FOR-DRAWFOR

2、-DRAW）比例设置（比例设置（SCALESCALE）角度旋转（角度旋转（ROTROT）坐标平移（坐标平移（ORIGINORIGIN）注释注释 （-或或 /）屏幕（窗口）的坐标系屏幕（窗口）的坐标系 左上角为原点左上角为原点 x x方向从左向右增长方向从左向右增长 y y方向从上到下增长方向从上到下增长(与一与一般的坐标系方向相反般的坐标系方向相反)3 函数绘图源程序举例函数绘图源程序举例 -函数函数f(t)=tf(t)=t的图形的图形origin is(100,300);origin is(100,300);-设置原点的偏移量设置原点的偏移量rot is 0;rot is 0;-设置旋转角度

3、设置旋转角度(不旋转不旋转)scale is(1,1);scale is(1,1);-设置横坐标和纵坐标的比例设置横坐标和纵坐标的比例for T from 0 to 200 step 1 draw(t,0);for T from 0 to 200 step 1 draw(t,0);-横坐标的轨迹（纵坐标为横坐标的轨迹（纵坐标为0 0）for T from 0 to 150 step 1 draw(0,-t);for T from 0 to 150 step 1 draw(0,-t);-纵坐标的轨迹（横坐标为纵坐标的轨迹（横坐标为0 0）for T from 0 to 120 step 1 dr

4、aw(t,-t);for T from 0 to 120 step 1 draw(t,-t);-函数函数f(t)=tf(t)=t的轨迹的轨迹 默认值：默认值：origin is(0,0)origin is(0,0)rot is 0;rot is 0;scale is(1,1)scale is(1,1)42.2 2.2 语句的语法和语义（语句的语法和语义（syntax&semanticssyntax&semantics）语句满足下述规定语句满足下述规定(原则原则)：各类语句可以按任意次序书写，且语句以分号结尾。各类语句可以按任意次序书写，且语句以分号结尾。源程序中的语句以它们出现的先后顺序处理。

5、源程序中的语句以它们出现的先后顺序处理。ORIGINORIGIN、ROTROT和和SCALESCALE 语句只影响其后的绘图语句，语句只影响其后的绘图语句，且遵循最后出现的语句有效的原则。例如，若有下述且遵循最后出现的语句有效的原则。例如，若有下述ROTROT语句语句序列：序列：ROT IS 0.7 ROT IS 0.7；ROT IS 1.57 ROT IS 1.57；则随后的绘图语句将按则随后的绘图语句将按1.571.57而不是而不是0.70.7弧度旋转。弧度旋转。无无论论ORIGINORIGIN、ROTROT和和SCALESCALE语语句句的的出出现现顺顺序序如如何何，图图形的变换顺序总是

6、：形的变换顺序总是：比例变换比例变换旋转变换旋转变换平移变换平移变换 语言对大小写不敏感，例如语言对大小写不敏感，例如forfor、ForFor、FORFOR等，均被等，均被认为是同一个保留字。认为是同一个保留字。语句中表达式的值均为双精度类型，旋转角度单位语句中表达式的值均为双精度类型，旋转角度单位为弧度且为逆时针旋转，平移单位为点。为弧度且为逆时针旋转，平移单位为点。52.2.1 2.2.1 循环绘图（循环绘图（FOR-DRAWFOR-DRAW ）语句）语句 语法：语法：语义：语义：举例：举例：说明：说明：注意：注意：FOR FOR T T FROMFROM 起起点点 TOTO 终终点点

7、STEPSTEP 步步长长 DRAWDRAW(横横坐坐标标,纵纵坐坐标标););令令T T从从起起点点到到终终点点、每每次次改改变变一一个个步步长长，绘绘制制出出由由(横横坐坐标标，纵纵坐标坐标)所规定的点的轨迹。所规定的点的轨迹。FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(cos(T),sin(T);FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(cos(T),sin(T);该该语语句句的的作作用用是是令令T T从从0 0到到2*PI2*PI、步步长长 PI/50PI/50，绘绘制制出出各各个个点点的的坐标坐标(cos(T)(cos(T

8、)，sin(T)sin(T)，即一个单位园。，即一个单位园。由于绘图系统的默认值是由于绘图系统的默认值是ORIGIN IS(0,0);ORIGIN IS(0,0);ROT IS 0;ROT IS 0;SCALE IS(1,1);SCALE IS(1,1);所以实际绘制出的图形是在屏幕左上角的一个点。所以实际绘制出的图形是在屏幕左上角的一个点。62.2.2 2.2.2 比例设置比例设置(SCALESCALE)语句语句语法：语法：语义：语义：举例：举例：说明：说明：SCALE IS(SCALE IS(横坐标比例因子，纵坐标比例因子横坐标比例因子，纵坐标比例因子););设置横坐标和纵坐标的比例，并分

9、别按照比例因子进行缩放。设置横坐标和纵坐标的比例，并分别按照比例因子进行缩放。SCALE IS(100,100);SCALE IS(100,100);将横坐标和纵坐标的比例设置为将横坐标和纵坐标的比例设置为1:11:1，且放大，且放大100100倍。倍。语法：语法：语义：语义：举例：举例：说明：说明：2.2.3 2.2.3 坐标平移坐标平移(ORIGINORIGIN)语句语句ORIGIN ISORIGIN IS(横坐标，纵坐标横坐标，纵坐标););将坐标系的原点平移到横坐标和纵坐标规定的点处。将坐标系的原点平移到横坐标和纵坐标规定的点处。ORIGIN IS(360,240);ORIGIN IS

10、(360,240);将原点从将原点从(0,0)(0,0)平移到平移到(360,240)(360,240)处。处。若：若：SCALE IS(100,100/3);SCALE IS(100,100/3);则：则：横坐标和纵坐标的比例为横坐标和纵坐标的比例为3:13:1。72.2.4 2.2.4 角度旋转角度旋转(ROTROT)语句语句语法：语法：语义：语义：举例：举例：说明：说明：ROT ISROT IS 角度；角度；逆时针旋转角度所规定的弧度值。具体计算公式：逆时针旋转角度所规定的弧度值。具体计算公式：旋转后旋转后X X=旋转前旋转前X*COSX*COS(角度角度)+)+旋转前旋转前Y*SINY

11、*SIN(角度角度)旋转后旋转后Y Y=旋转前旋转前Y*COSY*COS(角度角度)-)-旋转前旋转前X*SINX*SIN(角度角度)ROT IS PI/2;ROT IS PI/2;逆时针旋转逆时针旋转PI/2PI/2，即逆时针旋转，即逆时针旋转9090度。度。2.2.5 2.2.5 注释语句注释语句 注释的作用：注释的作用：语法：语法：语义：语义：便于理解；便于理解；屏蔽暂时不需要的语句。屏蔽暂时不需要的语句。/This is a comment line/This is a comment line 或或 -此行是注释此行是注释 /或或 -之后，直到行尾，均是注释之后，直到行尾，均是注释8

12、语句功能的测试语句功能的测试ORIGIN IS(360,240);ORIGIN IS(360,240);/(1)/(1)原点移至原点移至(360,240)(360,240)SCALE IS(100,100);SCALE IS(100,100);/(2)/(2)图形放大图形放大100100SCALE IS(100,100/3);SCALE IS(100,100/3);/(3)/(3)纵坐标缩小为三分之一纵坐标缩小为三分之一ROT IS PI/2;ROT IS PI/2;/(4)/(4)逆时针旋转逆时针旋转9090度度-绘制园的轨迹绘制园的轨迹FOR T FROM 0 TO 2*PI STEP P

13、I/50 DRAW(cos(T),sin(T);FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(cos(T),sin(T);仅仅(1)(1)和和(2)(2)加入加入(3)(3)加入加入(4)(4)9其他函数图形：其他函数图形：看实例看实例102.3 2.3 记号的语法和语义记号的语法和语义 记号的种类：记号的种类：常数常数 参数参数常数、参数、函数、保留字、运算符、分隔符常数、参数、函数、保留字、运算符、分隔符 常数字面量常数字面量和标识符形式的和标识符形式的常量名常量名均称为常数。字面量均称为常数。字面量的形式为普通的数值，如果没有小数部分，可以省略小数点。的形式为

14、普通的数值，如果没有小数部分，可以省略小数点。例如例如2 2、2.2.、2.02.0都是合法的常数。都是合法的常数。标识符标识符PIPI、E E也是常数，也是常数，它们分别代表圆周率和自然对数的底。常数不能有符号位，它们分别代表圆周率和自然对数的底。常数不能有符号位，如如-1-1和和+2+2不是常数而是（一元运算的）表达式。不是常数而是（一元运算的）表达式。本作图语言中唯一的、已经被定义好的本作图语言中唯一的、已经被定义好的变量名变量名T T被称为参被称为参数数，它也是一个表达式。由于作图语言中只有这唯一的变量，它也是一个表达式。由于作图语言中只有这唯一的变量，因此作图语言中无需变量或参数的声

15、明和定义语句。因此作图语言中无需变量或参数的声明和定义语句。为简单起见，当前的函数仅支持正弦函数为简单起见，当前的函数仅支持正弦函数SinSin，余弦函数，余弦函数CosCos，正切函数，正切函数TanTan，算术平方根函数，算术平方根函数SqrtSqrt以及指数函数以及指数函数ExpExp和和对数函数对数函数LnLn。有兴趣的同学可以再加入其他函数。有兴趣的同学可以再加入其他函数。函数（调用）函数（调用）112.3 2.3 记号的语法和语义（续）记号的语法和语义（续）保留字保留字 运算符运算符 分隔符分隔符 语句中具有固定含义的标识符，包括：语句中具有固定含义的标识符，包括：ORIGIN,S

16、CALE,ROT,IS,TO,ORIGIN,SCALE,ROT,IS,TO,STEP,DRAW,FOR,FROM STEP,DRAW,FOR,FROMPLUS,MINUS,MUL,DIV,POWERPLUS,MINUS,MUL,DIV,POWER即即:+-*/*SEMICO,L_BRACKET,R_BRACKET,COMMASEMICO,L_BRACKET,R_BRACKET,COMMA即即:;(),12三、三、题目与要求题目与要求1.1.用某种程序设计语言（如用某种程序设计语言（如C/C+C/C+、PascalPascal、JavaJava等）和等）和递归下降子程序方法编写完整的解释器，由于

17、环境限制，递归下降子程序方法编写完整的解释器，由于环境限制，本书统一采用本书统一采用C/C+C/C+程序设计语言；程序设计语言；2.2.利用编译器编写工具利用编译器编写工具LEX/YACCLEX/YACC提供的方式规定绘图语言提供的方式规定绘图语言的词法和语法，用的词法和语法，用C/C+C/C+语言编写解释器的语义。语言编写解释器的语义。3.1 3.1 解释器的实现方法解释器的实现方法题目：为函数绘图语言编写一个解释器题目：为函数绘图语言编写一个解释器 解解释释器器接接受受用用绘绘图图语语言言编编写写的的源源程程序序，经经语语法法和和语语义义分分析析之后，将源程序所规定的图形显示在显示屏（或窗

18、口）中。之后，将源程序所规定的图形显示在显示屏（或窗口）中。目目的的：通通过过自自己己动动手手编编写写解解释释器器，掌掌握握语语言言翻翻译译特特别别是是语语言言识识别的基本方法。别的基本方法。133.1 3.1 解释器的实现方法解释器的实现方法 两种方法的语义部分基本相同，主要区别在于词法和两种方法的语义部分基本相同，主要区别在于词法和语法分析器的构造是手工完成还是借助于工具完成。语法分析器的构造是手工完成还是借助于工具完成。143.3 3.3 任务划分与上机报告任务划分与上机报告 任务划分：（三个阶段）任务划分：（三个阶段）词法分析器、语法分析器、语义分析器词法分析器、语法分析器、语义分析器

19、机时比例（大概）：机时比例（大概）：2:3:32:3:3要求：要求：验收经过测试的程序验收经过测试的程序提交上机报告。其中上机报告可以包括以下内容：提交上机报告。其中上机报告可以包括以下内容：任务与目的任务与目的 软件设计软件设计a.a.软件的总体结构与模块划分软件的总体结构与模块划分b.b.关键算法与重要数据结构关键算法与重要数据结构 测试例程设计与测试结果分析测试例程设计与测试结果分析 总结、体会、改进建议等总结、体会、改进建议等 工作方法建议：工作方法建议：每个阶段均进行设计与测试，并且写出报每个阶段均进行设计与测试，并且写出报告；采用增量式设计；工作全部完成后将三个阶段的工作告；采用增

20、量式设计；工作全部完成后将三个阶段的工作进行总结即可。进行总结即可。15四、递归子程序方法的参考解决方案四、递归子程序方法的参考解决方案4.1 4.1 词法分析器的构造词法分析器的构造 步骤：正规式步骤：正规式NFANFADFADFA最小最小DFADFA编写程序测试编写程序测试 4.1.1 4.1.1 记号的设计记号的设计 词法分析器的三个任务：词法分析器的三个任务：1 1滤掉源程序中的无用成分；滤掉源程序中的无用成分；2 2输出记号供语法分析器使用；输出记号供语法分析器使用；3 3识识别别非非法法输输入入，并并将将其其标标记记为为“出出错错记记号号”。记号的组成：记号的记号的组成：记号的类别

21、类别和和属性属性。记号的数据结构：记号的数据结构：struct struct TokenToken/记号的数据结构记号的数据结构 Token_TypeToken_Type type;type;/类别类别char*lexeme;char*lexeme;/属性属性，原始输入的字符串，原始输入的字符串double value;double value;/属性属性，若记号是常数则是常数的值，若记号是常数则是常数的值double(*FuncPtr)(double);double(*FuncPtr)(double);/属性属性，若记号是函数则是函数指针，若记号是函数则是函数指针;164.14.1词法分析器

22、的构造（续词法分析器的构造（续1 1）函数绘图语言中记号的分类与表示函数绘图语言中记号的分类与表示enumenum Token_Type Token_Type /记号的类别记号的类别 ORIGIN,SCALE,ROT,IS,ORIGIN,SCALE,ROT,IS,/保留字（一字一码）保留字（一字一码）TO,STEP,DRAW,FOR,FROM,TO,STEP,DRAW,FOR,FROM,/保留字保留字;T,T,/参数参数SEMICO,L_BRACKET,R_BRACKET,COMMA,SEMICO,L_BRACKET,R_BRACKET,COMMA,/分隔符分隔符PLUS,MINUS,MUL,

23、DIV,POWER,PLUS,MINUS,MUL,DIV,POWER,/运算符运算符FUNC,FUNC,/函数函数CONST_ID,CONST_ID,/常数常数NONTOKEN,NONTOKEN,/空记号（源程序结束）空记号（源程序结束）ERRTOKENERRTOKEN /出错记号（非法输入）出错记号（非法输入）174.1.2 4.1.2 模式的正规式表示模式的正规式表示 letterletter=a-zA-Z=a-zA-Zdigitdigit=0-9=0-9 COMMENT COMMENT =/|-=/|-WHITE_SPACE WHITE_SPACE=(|t|n)=(|t|n)+SEMIC

24、O SEMICO =;=;L_BRACKET L_BRACKET=(=(R_BRACKET R_BRACKET=)=)COMMA COMMA =,=,PLUS PLUS =+=+MINUS MINUS =-=-MUL MUL =*=*DIV DIV =/=/POWER POWER =*=*CONST_ID CONST_ID =digit=digit+(.digit(.digit*)?)?ID ID =letter=letter+由于是手工构造词法分析由于是手工构造词法分析器，而正规式个数越少越便于器，而正规式个数越少越便于程序的编写，因此设计上采用程序的编写，因此设计上采用相同模式的记号共用一

25、个正规相同模式的记号共用一个正规式的方法。式的方法。常数的字面量部分设计为常数的字面量部分设计为CONST_IDCONST_ID，而常量名则合并到，而常量名则合并到IDID中。中。这就带来一个问题，函数这就带来一个问题，函数绘图语言中的保留字、常量名、绘图语言中的保留字、常量名、参数名、以及函数名均被描述参数名、以及函数名均被描述为为IDID，当识别出，当识别出IDID时，如何再时，如何再细分它们？细分它们？184.1.3 4.1.3 区分记号的符号表区分记号的符号表 static Token TokenTab=static Token TokenTab=CONST_ID,CONST_ID,P

26、I,PI,3.1415926,3.1415926,NULL,NULL,CONST_ID,CONST_ID,E,E,2.71828,2.71828,NULL,NULL,预先定义且内容不变的符预先定义且内容不变的符号表更多被习惯地称为号表更多被习惯地称为字典字典。T,T,T,T,0.0,0.0,NULL,NULL,FUNC,FUNC,SIN,SIN,0.0,0.0,sin,sin,FUNC,FUNC,COS,COS,0.0,0.0,cos,cos,FUNC,FUNC,TAN,TAN,0.0,0.0,tan,tan,FUNC,FUNC,LN,LN,0.0,0.0,log,log,FUNC,FUNC,

27、EXP,EXP,0.0,0.0,exp,exp,FUNC,FUNC,SQRT,SQRT,0.0,0.0,sqrt,sqrt,ORIGIN,ORIGIN,ORIGIN,ORIGIN,0.0,0.0,NULL,NULL,SCALE,SCALE,SCALE,SCALE,0.0,0.0,NULL,NULL,ROT,ROT,ROT,ROT,0.0,0.0,NULL,NULL,IS,IS,IS,IS,0.0,0.0,NULL,NULL,FOR,FOR,FOR,FOR,0.0,0.0,NULL,NULL,FROM,FROM,FROM,FROM,0.0,0.0,NULL,NULL,TO,TO,TO,TO,0.

28、0,0.0,NULL,NULL,STEP,STEP,STEP,STEP,0.0,0.0,NULL,NULL,DRAW,DRAW,DRAW,DRAW,0.0,0.0,NULLNULL;19例例2.2 2.2 语句语句ROT IS PI/6ROT IS PI/6的记号流的记号流 ROTNULLISNULLCONST_IDNULLDIVNULLCONST_IDNULL204.1.4 4.1.4 正规式的正规式的DFA DFA letterletter=a-zA-Z=a-zA-Zdigitdigit=0-9=0-9 ID =letter+ID =letter+CONST_ID =digit+(.dig

29、it*)?CONST_ID =digit+(.digit*)?POWER =*POWER =*COMMENT =/|-COMMENT =/|-SEMICO =;SEMICO =;L_BRACKET =(L_BRACKET =(R_BRACKET =)R_BRACKET =)COMMA =,COMMA =,PLUS =+PLUS =+MINUS =-MINUS =-MUL =*MUL =*DIV =/DIV =/“WHITE_SPACE=(|t|n)WHITE_SPACE=(|t|n)+注意：注意：WHITE_SPACEWHITE_SPACE（白空）没有在（白空）没有在DFADFA中。中。如何处

30、理白空？如何处理白空？214.1.5 4.1.5 词法分析器的程序框架词法分析器的程序框架struct Token token=ERRTOKEN,struct Token token=ERRTOKEN,“”,0.0,NULL;,0.0,NULL;/用于返回记号用于返回记号token.lexeme=TokenBuffer;token.lexeme=TokenBuffer;/记号的字符指针指向字符缓冲区记号的字符指针指向字符缓冲区char=GetChar();char=GetChar();/从源文件中读取一个字符从源文件中读取一个字符/空格、空格、TABTAB、回车等字符的过滤、回车等字符的过滤A

31、ddInTokenString(char);AddInTokenString(char);/将读入的字符放进缓冲区将读入的字符放进缓冲区TokenBufferTokenBuffer中中if (isalpha(char)if (isalpha(char)/识别识别IDID else if (isdigit(char)else if (isdigit(char)/识别数字常量识别数字常量 else else switch(char)switch(char)case case ;:token.type=SEMICO;:token.type=SEMICO;return token;return tok

32、en;224.1.6 4.1.6 与语法分析器的接口与语法分析器的接口 词法分析器的测试词法分析器的测试#include scanner.h#include scanner.hvoid main(int argc,char*argv)void main(int argc,char*argv)Token token;Token token;if(argc2)printf(please input Source File!n);return;if(argc2)printf(please input Source File!n);return;if(!if(!InitScanner(argv1)In

33、itScanner(argv1)/初始化词法分析器初始化词法分析器 printf(Open Source File Error!n);return;printf(Open Source File Error!n);return;printf(printf(记号类别记号类别 字符串字符串 常数值常数值 函数指针函数指针n);n);printf(_n);printf(_n);while(1)while(1)token=token=GetToken()GetToken();/通过词法分析器获得一个记号通过词法分析器获得一个记号 if(token.type!=NONTOKEN)if(token.typ

34、e!=NONTOKEN)/打印记号的内容打印记号的内容printf(%4d,%12s,%12f,%12xn,printf(%4d,%12s,%12f,%12xn,token.type,token.lexeme,token.value,token.FuncPtr);token.type,token.lexeme,token.value,token.FuncPtr);else else break;break;/源程序结束，退出循环源程序结束，退出循环;printf(_n);printf(_n);CloseScanner()CloseScanner();/关闭词法分析器关闭词法分析器CloseSc

35、anner23 测试实例与测试结果测试实例与测试结果 例如源程序：例如源程序：FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(cos(T),sin(T);FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(cos(T),sin(T);测试结果：测试结果：(看运行结果看运行结果)词法分析器的测试比较简单，可以分为三个部分：词法分析器的测试比较简单，可以分为三个部分：1.全部合法的输入全部合法的输入2.各种组合的非法输入各种组合的非法输入3.由记号组成的句子由记号组成的句子24课程及第一次上机要点课程及第一次上机要点1.1.分析研究函数绘图语言，深刻理解每条语句的语法和语义；分析研究函数绘图语言，深刻理解每条语句的语法和语义；深刻理解记号的语法和语义；深刻理解记号的语法和语义；2.2.分析上机题目与要求，思考词法分析器的设计；分析上机题目与要求，思考词法分析器的设计；3.3.参考课堂上的记号设计与参考课堂上的记号设计与DFADFA的实现方案，设计并实现词的实现方案，设计并实现词法分析器，并自己设计测试例程，进行详细测试；法分析器，并自己设计测试例程，进行详细测试；4.4.写出词法分析器部分的上机报告。写出词法分析器部分的上机报告。