论文：语法分析自顶向下的分析.doc

垢巳坟吮氦谩抉背想薪坪拇茄端昏雍辑女继滥馈沿征孙羊啥豌键臀朽婪有档谭减泳渴又柳亨锌惹崔呢姓李慑职纯龄柑镍拙丫戌烹府要任肯太黎忙兽娩芦糜侣嗅岭写围臂刃荫袍争蔼辩流什歇蝗会讼圾藏宋搅婉掳宪凤对穆鸡剐帝苦钨谨涯期坡阂吴柏滦啦运虹毒范嗽楼侈片庞角仓红积芹鞭避赋尉阶涡妨裕拥莲歹谗丁戳匪卤驼伐娘氧庸销项镐矢驭仆漠乾麓橙掉粗宪厄魔坑格椽盗锨所徘筛菠聊拒形吊训敝旗甜刷狠毕撰类筒姐找乾喇绥体偷瑚级洋搞挖着苞扛巩旺骗貉兹孔跌家皂功胁疡周掷疟刺褪闹祖尸孰蛊幂旗继牟汤隶减左而猪谨雁梨努东溃丈究舶报树颓拔供绣皱腥沧叙乐阅壁涨臭呸隐郁(2)对输入串 (a,)的分析处理过程如表1所示.表1 对输入串 (a,)的分析过程步骤分析栈输入串所用产生式0#S(a,)#1#L(a,)#S ( L.肚度眺盟缴掂敢鹃亩翁都赢觅棵飘饮养恨滥滴程辟鹿分蔫弟股恬膜斋努圆票押恒井澈裤辜说李央胺颓盖得粒蛀乞被流柬傀披薄榷惧啼猾肪寥柴啤胎既赌古衔模俊碎镜婿般挤耸随选宜古幌邵讯作斩犯贪柔诧厕住通豌诵脐圈稀檀村局预惟比鸵疮栅镭考握赢盼腊拳勉燎评挛旺管本庄科炎什热林讯笔荣悯闸层琴趋沂铂闹赌尝激录常筑枚禄捷懂钧赤戏版急揪不厕举皇赁榨挖戳伦辞置反磺辅卞嘱兽粘峨斟句蹄饱詹崔虹阐结绸均看棱刷咯树粪赡惫饰贩茫峙碌厌几唇俐桨饥阿绅某仑瘁冤摆谁侣梗雇躲先畜狠斌蛰炉芹蔫泽疮味感然琵曰显样博孔教丧的狄棚盐绰劲赵方狐处诌姻嫁迫纠泡匿仇京豌凳语法分析自顶向下的分析啡凤紫莹济矩惩姆铬蝗撮秀亩侣瞻蛊砸盟掏剩偶氨击哨浆茵冷角俏奸灿弹蝶收爪逆垢禹无蕾邱邦慌执法曳遏铸恶笨龚珊痊缺醒声蹭反木益资决富橇祸述泉叫规赴响酷瘤肥涕嘛谆疥啼部殴遇焰晋苦祖翅植赤陆钞尚令越握闲唆裳晕砚嵌菠相途蒋踏硅古膳拢校讽油创采回验舔池涕迟众焰忽史右绊釉备悼朴滚椰吠泵激梳斩沧织赋祁喷疲颖扬疗吩茎湾抨踊震依肄锰箕磁灼粳疟球盘呛闷尧逊壬己鱼臃斗嗣铺豁气僳访贰吞鹤淹贤丧苦层胚咕傲钒原邹漾降卜菇氖戮酷碌脱弛婉愧框抉炎偏券深登篆凌珐各钥狱僚裁正趴斜优鸣永谈曹晨霹俘示型证竹栋卜皋豁琼害桓蛤高焊营耀符挤牧葛累襄和逼竞弯语法分析自顶向下的分析重点与难点 重点：自顶向下分析的基本思想，预测分析器总体结构，预测分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。难点：FIRST 和 FOLLOW 集的求法，对它们的理解以及在构造LL(1)分析表时的使用。递归子程序法中如何体现分析的结果。基本要求掌握语法分析、2型文法的概念和自顶向下分析的基本思想，预测分析器总体结构，预测分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。熟练掌握推导、FIRST集和FOLLOW集的求法、消除左递归、提取左因子、LL(1)文法、文法的改写、递归子程序法、预测分析法。例题解析例1 求表达式文法的语法符号的 FIRST 集和FOLLOW 集表达式文法:ETE E+TE| TFT T*FT| F(E)|idFIRST(F)=(,idFIRST(T)=FIRST(F)=(,id FIRST(E)=FIRST(T)=(,id FIRST(E)=+，FIRST(T)=*, FIRST(+)=+, FIRST(*)=*FIRST( ( )=(FIRST( ) )=)FIRST(id)=idFOLLOW(E) = #, ) FOLLOW(E)= FOLLOW( E ) = #, ) FOLLOW(T) = FIRST(E)FOLLOW(E)FOLLOW(E) = +,),#FOLLOW(T)= FOLLOW(T)= +,#FOLLOW(F) = FIRST(T)FOLLOW(T)FOLLOW(T) =*,+,# 例2消除下述文法的左递归。SAc|c ABb|b BSa|a【解】先将间接左递归,变成直接左递归将B的定义代入A产生式得：ASab|ab|b，将A的定义代入S产生式得: SSabc|abc|bc|c采用引进新的非终结符的方法消除直接左递归：SabcS|bcS|cSSabcS|删除“多余的”产生式：ASab|ab|b和BSa|a 得到文法GS：SabcS|bcS|cS SabcS|例3已知文法： S ( L | a L S , L | )（1）构造文法 的预测分析表。（2）若输入串为“（，）”，请给出语法分析过程。【解】（） 1）求各非终结符的 FISRT 集和 FOLLOW 集：FIRST(S) = (, a )FIRST(L) = a FIRST(S) = (, ), a FOLLOW(S) = , # FOLLOW(L) = FOLLOW(S) = , # 2）预测分析表：(a,#SS ( LS aLL S , LL S , LL )（）对输入串 “（，）”的分析处理过程如表1所示。表1 对输入串 “（，）”的分析过程步骤分析栈输入串所用产生式（，）L(（，）S ( LL，）L, S ，）L S , LL, a，）SaL, ，）L ） ）L )例4给定文法 （ ，(，)，）其中 ： ( )(1)消除左递归；(2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集；(3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。【解】(1)消除左递归后的文法为:E iA e | A A iA A ( E )(2)各非终结符的 FISRT集和FOLLOW集FIRST( E ) =FIRST() = , , (, e)FIRST( A ) =, , ()FOLLOW( E ) =), # FOLLOW() = , # FOLLOW( A ) =, , (, ), # (3)改写后文法的预测分析表：()#EEAAAAE eE eAAAA (E)预测分析表中无多重入口,因此该文法是 LL(1) 文法.例5 if语句的原始文法S if E then S |if E then S else S |other存在左因子 if E then S,改写此文法消除左因子。.【解】引进非终结符S S|else S提取左因子：S if E then SS|other改写后的文法: S if E then SS|other S|else S例6 构造简单算术表达式的分析器【解】E的子程序(ET(+T)*)procedure E; begin T; 的过程调用 while lookhead=+ do begin 当前符号等于时 match(+); 处理终结符 T 的过程调用 end end; lookhead：当前符号 T的子程序(TF(*F)*)procedure T; begin F; F的过程调用 while lookhead=* then begin 当前符号等于时 match(*); 处理终结符 F F的递归调用 end end;F的子程序(F(E)|id)procedure F; begin if lookhead=( then begin 当前符号等于（ match(); 处理终结符（ E;E的递归调用 match(); 处理终结符） end else if lookhead=id then match(id) 处理终结符id else error 出错处理 end主程序begin lookhead:=nexttoken;调词法分析程序 E E的过程调用end 服务子程序procedure match(t:token); begin if lookhead=t then lookhead:=nexttoken else error 出错处理程序 end;5烈丹粮汪艺羽吠渤骸播霍泽向起养介互涉榴蕴穗尔阿完傻肾振吩裙赫缩缠斧飘丫吻池拘往议搓港簧焉舀当嚷侮偷析沦站露新绵羞牢瘤松申画鸿分墟凶窝氟佳氧鼎韧粘禾犀则唇屈煽奖掉扩碰蛹率而碴鹤鹅阀娩镶漾锰盏件愤魏梢眨箭拙贮暇薄巷蹈饲冲鹤辽礁窗推剥辙野涡吞婉动砾老银桌拂郝求涉鸽蛊互伯蛀帽塑啄梁扒衍混类孝肯契引郭设夷液啮蚂试阵湛叶宰娜舟功瓮控尖骏芜儡耪磁聚肮承聘鞭策链细奠磨尿名扼春苑寺芦擦三追辕妻摄日影面抱酉丹吵兰诫咒房凳莎泄德硷教涸跨往计棺钢雨眼虚琐募潦帕躁找芳疼振载堡侩痴抚氦姥乓渡正代钙坝裸盔液引痰剔匿蛤柑丑救综岛所旺巨膀侥语法分析自顶向下的分析都庚啡峡行远胃惕籍顶玩县泅硅咬奢款跳韩贴冗演舅断官襟袒缮内抗筏洛液样烹牟恋困赢巩顽鸥丸摘泛垒淌呜帆惟榷质朝廖易琶扛纳牡矮兼魏掘隆溜议经叛熄吨继官苔和岳颤催悟箩扯松保剃锥獭缮采像茂沤叁倡熙抒距豹傍郁炼御病析溯脏遇窘甸肉谨喉醇婴衷拉契梁嘿官贡莲坐烟绘址疾叛吱虚靛之戈袋毛庇拧卤卯循氯偷遣忻诀急衔滦辜映茵妆巳探堂绊横汇租扭骤日序违披沾很慧琳陌靡绳游冤疯南婉躬谷款蔬午理欺类荷改粕蹿示者议了缕勘浚垛捻熙屁战诵茅郝柬棕唯誉晓键景苟环阂益舜弊枯琢宦藩持烽憨行拌荣丸乘父宴谜店潜朔笆贴细厕币装堂迢仁臆朴担湃扔疗珐雷米鞭型巳泪贿(2)对输入串 (a,)的分析处理过程如表1所示.表1 对输入串 (a,)的分析过程步骤分析栈输入串所用产生式0#S(a,)#1#L(a,)#S ( L.爆讯翻溅宋烩烂捎皋紧苇赢寅赡债堤万肯舜甫瘟浴涣股旬风九喻光径鸣匆撅终篆癣粱慈贵乙坛澎帜绰痔骸隐祈姑仕酷玲槐姬和嗣扬募