编译原理第四章词法分析.

第4章词法分析4.1词法分析的基本概念4.2词法分析程序的设计与实现4.3算术常数处理机的设计【内容提要】※词法分析程序又称扫描器，任务有二：(1)识别单词——从用户的源程序中把单词分离出来;(2)翻译单词——把单词转换成机内表示，便于后续处理。4.1.1单词的分类与识别1.单词的分类⑴标识符——用户给一些变量起的名字；⑵常数——以自身形态面对用户和系统；⑶关键字——系统内部定义，具有固定的意义，⑷界符——单字符界符——+-*/，；：=…双字符界符——:=====/**/…按单词的语法功能可分为：如：算数常数，逻辑常数，字符串常数，…通常用来区分语法单元；2.单词的识别问题：1.字母开头——关键字或标识符；2.数字开头——数值型常量；3.‘或“开头——字符型常量或字符串常量；4.其它——多数以自身形态识别之，如+,-,=,…;==,!=,=,…※如何区别关键字和标识符？现在，大多数编译程序使用“保留字”，即标识符不能用作关键字。系统预先造好关键字表，拼好的字符串，先查“关键字”表，查到了，视为关键字，否则，视为标识符。简单识别方法程序设计语言的单词不但类别不同，而且长短不一，机内表示可以使：语法信息，即单词的分类码。语义信息，如：数组维数，上下界，类型等；TOKEN:目前，大多数采用如下二元式形式：①长短统一；②语法、语义信息分开。4.1.2单词的机内表示类值i·名字…c·123k·whilep·=※TOKEN的一种设计方案：【注】为了提高分析效率，实践中，TOKEN的类码设计采用统一编码,如：标识符为1，常数为2，其余（关键字，界符）则一词一码，且从3编起，…·标识符：TOKEN:·常数：TOKEN:·关键字：TOKEN:·界符：TOKEN:·IT[i]标识符表·CT[c]常数表·KT[k]关键字表·PT[p]界符表源程序TOKEN序列（字符串）（单词串）4.2词法分析程序的设计TOKEN序列扫描器语法分析器扫描器(2)作为语法分析器的子程序的扫描器(1)作为独立一遍的扫描器4.2.1词法分析程序功能划分:getword命令(语法分析后）TOKEN源程序一个简单的词法分析程序分别描述如下：4.2.2一个简单词法分析器的实现※一个简单识别器的设计以及（1）识别器---识别单词的有限自动机（2）翻译器---根据有限自动机所识别出的对象，完成从单词串到单词的TOKEN串的翻译。翻译器主程序识别器源程序(字符串)Token序列(单词串)一个简单识别器(有限自动机)的设计:①②③④⑤n?ℓℓd-dd.dd---⑥⑦==-…#-关键字/标识符无符号小数无符号整数等号赋值号其中⑴ℓ(字母),d(数字),#(源程序结束符);⑵?(空格，回车，换行)，需要滤掉。⑶(泛指单词的后继符)；⑷…(表示省略了其他界符的处理)。+※一个简单词法分析器设计：1.…处理框，…判断框；2.识别器(有限自动机)返回已识别的单词；3.常数处理把字符串型常数转换为算术型常数。开始结束调用识别器关键字/标识符算术常数结束符#查KT表查到查填IT表查填CT表常数处理C.TOKEN查PT表P.TOKENI.TOKENK.TOKENyn查到ere:非法界符ynyynnny注4.2.3词法分析结果示例【例4.1】Pascal片段:…x1:=x1+1;beginyy:=5;zz:=yy*x1;end;while(x1=20)dox1:=yy;…KT[k]BeginEndWhileDo…PT[p]:=;+*(IT[i]X1YyzzCT[c]1520)=…1234123456712341234关键字表界符表标识符表常数表符号表：【注】⑴KT[k]，PT[p]–静态表（系统设定）；⑵IT[i]，CT[c]–动态表（随源程序变化）；x1:=x1+1;beginyy:=5;zz:=yy*x1;end;while(x1=20)dox1:=yy;…(接上页)(接上页)x1x1:=+1;beginyy:=5;zz:=yy*x1;end;while(x1=20)dox1:=yy;…(i,i3),(p,p1),(i,i2),(p,p4),(i,i1)，(p,p2),(k,k2),(p,p2),(k,k3),(p,p5),(i,i1)，(p,p7),(c,c3),(p,p6),(k,k4),(i,i1),(p,p1),(i,i2),(p,p2)。(i,i1)(p,p1)(i,i1)，，，(p,p3)，(c,c1)(p,p2)，(k,k1)(i,i2)(p,p1)(c,c2)(p,p2)，，，，，，•经过扫描器，依次输出TOKEN序列：识别器分析器信息表4.3算术常数处理机设计字符型=数值型。•算术常数处理机的功能：⑴识别器（有限自动机主机）⑵翻译器（在自动机的状态节点处，插入·算术常数的基本形式：尾数指数dd…d.dd…de(+|-)dd…d；4.3.1识别器设计带有翻译功能的自动机称为处理机；其结构可分为两个部分：翻译子程序）①②③④⑤⑥⑦+dd-ddddd≮.≮e+|-≮……整数……小数……e指数e※一个算数常数识别器的设计：其中⑴d(数字)⑵节点②，识别整数；⑶(泛指单词的后继符)；⑷，节点④，识别小数；节点⑦，识别e指数；4.3.2翻译器设计1.算法设计：设置参数如下：n：拼尾数值变量；每当读入尾数数字d时：n:=10*n+val(d);【注】参数初值，分别为：n=p=m=t=0;e=1num=n*10e*P-m结果变量:Val(d)字符转数值函数p：拼指数值变量；每当读入指数数字d时：p:=10*p+val(d);m：小数位数变量;每当读入小数数字d时：m:=m+1;e：指数的符号变量（+：为1，-：为-1）；t：类型变量（整型：为0，实型：为1）；【注】val(d)字符型转数值型函数。设：在状态i结点处的语义动作为qi；q1：初始化，n:=p:=m:=t:=0；e:=1；num:=0；2.状态节点处动作函数设计：q2：n:=10*n+val(d)；q3：t:=1;q4：n:=10*n+val(d)；m:=m+1；q5：t:=1;q6：if‘-‘thene:=-1；q7：p:=10*p+val(d)；开始结束state:=1getchar(ch)查变换表：(state,ch)=?==ok回答:noynystate:=nSemfun(state)计算：num=n*10e*P-m执行翻译子程序常数的转换结果常数处理机程序框图：※算术常数处理过程示例：例如：8.67e-12#的翻译过程：【结果】num=n*10e*p-m=867*10-1*12-2=867*10-14符号变换nmpet翻译状态#21e76.8ok7754432867868210121000-1-1-111111111100001086720q(6)6q(4)48672q(7)78001q(3)3q(4)48672q(7)7q(2)2q(1)1-68672011q(5)5常数处理机常数识别器翻译函数习题：4.1叙述词法分析的任务；4.2程序设计语言单词是怎样分类的？4.3叙述单词的机内表示的结构和意义；4.4在单词识别中，如何区分关键字和标识符？4.5已知源程序片断：if(x5)y=3*x-a;…请写出词法分析后的TOKEN序列；【注】符号表自己设定。4.6P63_1,2,3,4谢谢收看！