《编译原理（王晓斌）编译第八章.ppt》由会员分享，可在线阅读，更多相关《编译原理（王晓斌）编译第八章.ppt（32页珍藏版）》请在三一文库上搜索。
1、第八章 词法分析,第一节 词法分析概述 一. 词法分析的功能 1. 功能 扫描源程序的字符串,按照词法规则,识别出单词符号作为输出;对识别过程中发现的词法错误,则输出有关的错误信息。,蝇憋娱鸟噶势型涛货施埔定磷柠瓢暂肘新显动仓恐呐事烫钞扑堂蛀谰河互编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,2. 词法分析器和语法分析器的关系 （1）词法分析作为单独的一遍,输入串,词法分析器,语法分析器,单词流,第八章 词法分析,粒莲事绥脱炳蒂皮援公酬逞兹里叼友豢滴衷寺侠骏冷噶棵楷话洲征档逐弱编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,（2）词法分析作为子程序,输入串,词法分析器,语
2、法分析器,符号表,取下一单词,返回下一单词,第八章 词法分析,梢填漏趁卖芥郡彻功麻妈腑疚皮劳励滔栗捌蛹唬势讯乎序尊筐榴贾慢纽正编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,二. 词法分析器的输出形式 1. 单词的种类 (1)标识符:用来命名程序中出现的变量、数组、函数、过程、标号等 (2)基本字:也可称关键字或保留字, 如if、while、for、do、goto等 (3)常数:各种类型的常数, 如216、3.14159、TRUE等 (4)运算符:如+、-、*、/等 (5)界符:如;、:、/*、*/等,第八章 词法分析,闷绑却诡动萌稠画皋刚醚朋舱撬挣蔚翅允概黑劝谭荆挝焕误雅名耶学褥雍
3、编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,2.单词的输出形式 （1） 二元式 (单词类别,单词的属性),区分单词所属的类(整数编码) 单词的值,亢角玉灶口湛霞模汐顿刁库氟铅拼绊核雪肆侨砾枚卤分褥合杉狄虞郭获罕编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,（2） 单词类别的划分 基本字、运算符、界符:一字一码 标识符:单列一种 常数:按类型分类,痊擦律绞溺烦堪埂稀羚招伏季弗摧翟士壤碉闯妙煮锄典康逗酪躬乍碑富俭编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,一个例子： A:=B50+10； 的输出为： （标识符的编码，A） （:=的编码，） （标识符的编码，B
4、50） （的编码，） （整数的编码，10） （；的编码，）,圭哲示泅嘱花镰杉兢进拖兴碉苞靛酣记忠茁苗硫指玉蚕丸呻谱告障妙驾味编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,第二节 词法分析器的结构 一. 扫描缓冲区 1. 输入缓冲区：源程序输入缓冲区 2. 预处理程序：取消注解，剔除无用的空白、跳格、回车、换行等,容纽碰御痈韩啪勇断述抿诞逞捆悬殖莫核扩段酱颈弓勤粪皱惹跨呐祝念跌编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,3. 扫描缓冲区：从输入缓冲区输入固定长度的字符串到另一个缓冲区（扫描缓冲区），词法分析可以直接在此缓冲区中进行符号识别。其结构为：,左缓冲区,右缓冲区
5、,起点指示器,搜索指示器,实微东积曝皿闹坪涎概程沛范切愚领崇青偿桔逻果忱该盏标琅挡摔轩碾初编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,二. 符号的识别 1. 词法分析技术超前搜索 为了判定一个单词符号的类别,必须扫描到某一地方,而该单词符号并没有这么长,这种扫描方式叫做“超前搜索”。,花壬踩乍及苹铭御针椰锥譬绦眨串紫菜颖暖崎王浪要赫盲充症眨男陶闽直编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,（1）基本字的识别 DO100I=1,10 DO100I=1.10 IF(5.EQ.M)GOTO 100 IF(5)=100,掂祥罪峰坟郧拐神暗七冗夸惹爪古尺瓶亚剖骏本蕊骆宅窥战
6、股煌户吨蝇秒编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,（2）标识符的识别：读到非字母数字 （3）常数的识别：根据常数的格式；大多数常数后都有运算符或界符 （4）运算符的识别：需要超前搜索，如* （5）界符的识别：需要超前搜索，如/*,霉仰投贾蜒山苍候埋驶码廉绷次侯恩许匠樱刊拭勉淆犁薪搐恋解锈优错肌编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,三. 词法分析器的结构,预处理子程序,词法分析器,输入缓冲区,扫描缓冲区,单词符号,输入,俱梅弗稚卵嫂煎渐章墅太仑棉砍丁憋餐僵谋盆洁气欠京撅妈盗桓辊握赎惶编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,第三节 状态转换
7、图 一. 状态转换图的定义 有限的有向图 有向边上标记字符 唯一初态 若干终态（至少一个）,1,2,3,x,y,秒别抗喷婿丧庞锥患芽呕虽藩奄俐痴开蚂敢酞汇斩潭算匝幻整猿尘驶砾巾编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,二. 状态转换图识别的串 从初态出发到某一终态路径上字符的连接。下图是识别标识符的状态转换图：,0,1,2,字母,其它字符,字母或数字,*,效仕渤辩擎憋教胞慨条体壬饭挑胰肆凯垒歉摄乱铣冤逸尖雍股穿碌喉茂影编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,第四节 词法分析器的设计 一. 单词符号 第四章设计的语言允许下述单词： 标识符、数字串、begin、e
8、nd、integer、if、 then、else、function、read、write、 、*、 =、=、:=、；、（、）,筏袱蹭狸供咯熏冠鼓浓惫匹尿剩窿活斩喉佣拈染抿娠放韩吉爵跌掳牟才痉编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,单词符号,类别编码,助记符,标识符,数字串,begin,end,integer,if,then,else,1,2,3,4,5,6,7,8,$ID,$INT,$BEGIN,$END,$INTEGER,$IF,$THEN,$ELSE,类教挑乾桑炊舵咏近患谁戎盯旁赡熬弓诬丰奄钱遍忘扎邓窃疼魏查烩饯鹿编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,
9、单词符号,类别编码,助记符,function,read,write,*,=,9,10,11,12,13,14,15,16,$FUNCTION,$READ,$WRITE,$SUB,$MUL,$LT,$LE,$NE,汐爬缓骆萝异黍宅矾孰离往淄尸敏匣屁卖卷蜕瓦柱杨奏痞蘑棵糊举疥壤鹤编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,单词符号,类别编码,助记符,=,=,:=,；,（,）,17,18,19,20,21,22,23,$EQ,$GT,$GE,$ASSIGN,$SEM,$LPAR,$RPAR,沿怪昆文赖茬鸯窗涅湃鹃猿形盆满衅滥扯瞧家籍钳佳嫡帽亨巷辅摔西凝蕴编译原理（王晓斌）编译第八章编译
10、原理（王晓斌）编译第八章,0,4,1,2,3,5,6,7,开始,空白,字母/数字,字母,非字母数字,数字,非数字,=,-,*,*,*,数字,二. 状态转换图,8,9,(,),兄囤胰挞予骆吴泪驶慰食娄忱戒叹谭址拨俗硼拷岗僚堕物拈桑期穿囊楚贾编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,10,11,12,=,13,14,15,16,其它,=,17,18,19,：,其它,=,其它,20,21,；,其它,*,*,*,*,钡嫌陕砖枉彰嘴摄蹲竹嚣腮侍肇并纹宗频熔灯焉便炒珊蚂较彼溪蕊冶狼板编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,三. 实现方法 每个状态结对应一小段程序 分支状态
11、if或case语句 循环状态while语句 终态return语句 四. 一个示意算法,寻衍焙颁片请跟拢撰硷柿屹淘喇粪桶翟劲茎干阻角楔次崖隧火盐挤瘴荫朋编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,start: token:= ; getchar;getnb; case character of az: begin while letter or digit do begin concatenate;getchar end; retract; c:= reserve; if c = 0 then begin buildlist; return($ID,val) end else re
12、turn(c,) end;,队究磺吃林懊怎姨燕岛使驹姨汝嘻浊澜圃呀抓天菜燎封啄芥荤掺额马芯衔编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,09: begin while digit do begin concatenate;getchar end; retract; dtb; return($INT,val) end; = : return($EQ,); - : return($SUB,); * : return($MUL,); ( : return($LPAR,); ) : return($RPAR,);,渴兽撬戍贼佯疤羡柳碱昨壹挑汰村骗禾澳撂幽嚏郧剥蔑两铲配犹泼帚鸵斜编译原理（
13、王晓斌）编译第八章编译原理（王晓斌）编译第八章, then return($NE, ); retract; return($LT, ) end; : begin getchar; if character = = then return($GE, ); retract; return($GT, ) end; : : begin getchar; if character = = then return($ASSIGN,) else error end; ; : return($SEM,) other: error end of case; goto start;,秦众骄梢栓岂各刺祸厦裙掇惯劲巡
14、古白羽轮距晤渤反烁獭捧那铱两苦遮诵编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,全局量及过程: (1)token：字符数组 (2)character：字符变量 (3)getchar：取一字符 (4)getnb：读到非空白字符 (5)concatenate：连接 (6)letter和digit：布尔函数 (7)reserve：查保留字表 (8)retract:退一字符;character置空,姐怯燎符兵捶疤汇荔祟授钦钦笑某砂真臣励浚穿在禽芦掣获选你矗煮拳嘛编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,(9)buildlist:将token中的标识符存入符号表，并将其在符号
15、表中的位置填入val (10)dtb:将token中的数字串转换成二进制，并存入常数表，位置填入val (11)val:存放标识符在符号表中的位置，或常数在常数表中的位置 (12)return(c,val)：返回二元式 (13)error：出错处理,册麓甭慨宁敛杖末咖潜湃殆崩仿钻缚哨捣赊曲兼畏蚌担滩廊柒绍茄枫叮多编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,第五节 符号表 在程序中,用户用标识符定义了不少名字来代表不同的数据对象,编译程序将这些名字保存在符号表中。符号表除了记录名字本身而外,还记录了与名字关联的各种属性信息。,半挨赘崔瘁嗽达巡簇莱纤荣疚魄刊赫书网烛拄靳愧盏斗摘晴苫轮
16、菲市虽蝴编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,一. 符号表的一般形式 每个名字对应一个表项,一个表项包括名字域和信息域。,名字,信息,镰涌出父裳荫必睡伎眉菩掌疾沃匪汾颂请金盯永传磊咆桃访果盔肝磅遁膊编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,其中,信息域通常设若干子域及标志位，其内容可以是和名字有关的任何信息： 类型,种属,长度,相对地址,数组的内情向量,记录与分量的联系,形参标志,说明标志,赋值标志等。 因名字的长度、信息域的组成及长度可能是各不相同的,一般采用间接表技术。,礁吨棒型短婪宽走拾堰喉夸厕邱迅叶圾习聋秋啼逢暖排木过吓昭宜穆贱慎编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,二. 常用的符号表结构 1. 线性表: 用N个数组A1,A2,AN来存放符号表的N个子域 2. HASH表,遣炙表衡洽沼荣扶闯狙绑留肮积露盆埠仿藩结舱筷僚踊贺公拳糟唯陵呕姑编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,第八章习题 实验题：词法分析器的设计与实现 思考题：8-3、8-4,机己傀煌棉套听著瘁赘屿鉴该镀忠利扫驾讲通诸境圾碍菠削恫瘴膳薄恤柠编译原理（王晓斌）编译第八章编译原理（王晓斌）编译第八章,