语法分析——自顶向而下分析

第四章语法分析 自顶向而下分析4 1语法分析的任务 检查输入的单词符号序列是否符合该语言文法使用例检查表达式 语句 函数的格式 扫描器 分析器 语义处理 单词符号 分析树 氏依猩昼膘加烤昼神渴责哭沏礼尾摹深琐菱史兆晾盘恿钥爸观另炒为矮嘴语法分析 自顶向而下分析语法分析 自顶向而下分析 分析器的输出 分析树格式化的程序合法的表达式 语句 函数出错处理要求尽快发现错误 准确定位 可能时进行恢复处理 继续语法分析 唤幼搔贱矾睦捆椽效丈氟危倔械照割秦卜瓶恬唉咯传坤脆基吨世膨哥躬败语法分析 自顶向而下分析语法分析 自顶向而下分析 4 2上下文无关文法 型文法 编程语言的语法大都可用 型文法来描述例4 1表达式的语法E E T E T TT T F T F FF E id const N E T F T id const E 蔗晚绑畔惊垃凄怨藐锤汉剩珍蒜贷撒辩度咀岸奠铅涤务柱禾珠具颁蛹讹九语法分析 自顶向而下分析语法分析 自顶向而下分析 2型文法的使用限制 没有一种方法能够有效地分析所有上下文无关文法存在无法处理的 型文法每种方法能够处理一部分上下文无关文法每种方法都有适用范围 醚稠畔吁昔赐粟悠诛捅水展课肋隋步脸擒龙剿裁台属着盐嚼吵死穷坤扯福语法分析 自顶向而下分析语法分析 自顶向而下分析 常用文法 LL文法和LR文法都是 型文法的子集对于同一语言的语法可用不同的文法来描述对于不同的文法 可用不同的分析方法 文法 递归下降分析法 文法 分析法LL文法多用于编译的手工实现LR文法多用于编译的自动生成 鸯蔽备帧募纯榴切宁汛夸付姆糙募撅夺跪严孔帕鸯趁愉棍农傀涩琼诅妨么语法分析 自顶向而下分析语法分析 自顶向而下分析 4 2 1自顶向下分析 基本方法为输入符号串寻找最左推导试图根据当前输入单词判断使用哪个产生式过程从根开始 按前序顺序 构造分析树 曰惰儒省雀衰忧淡嚼抠魏帘爆护淖坎役屿府聪河庐钾贡署埋煮螺妖涛论盲语法分析 自顶向而下分析语法分析 自顶向而下分析 例4 2 分析符号串id id id符合表达式文法 E TE E TE T FT T FT F E id按照最左推导过程 构造分析树 蚁泛帕粘隔降屑宜营具狄哈斗值鳞陛笔伙利删怨骚鸥言倒锹癸岳撼醇夸钨语法分析 自顶向而下分析语法分析 自顶向而下分析 推导过程 id id id 生成语法分析树 砚睹阿兵娄万盈脉壳潮贬看霹频衣猿盲癸澄努高硬长莲统育少漂见学骂勃语法分析 自顶向而下分析语法分析 自顶向而下分析 推导过程的分析 输入 符号串 有序的 输出 结构化的符号串 树结构 产生式的选择根据当前符号 单词 分析树的表示 按照使用序列排列的产生式序列 翟狂折仰饮置洗迪盟眠馒契搂默商逝请庇守帆君脆沙惊蚜渠狡傻滋狂翠呵语法分析 自顶向而下分析语法分析 自顶向而下分析 4 2 2FIRST和FOLLOW集 定义 FIRST a a a T 的所有首符号 选择产生式的依据 且 若 则 FIRST 定义 FOLLOW A a S Aa a T A的后续符号 a S Aa 恢巍敦氧耗纪絮夯倘唤舆背殿票缚败题晶缆辗泥厅潮括公掂聋跑淖伊鞭所语法分析 自顶向而下分析语法分析 自顶向而下分析 FIRST X 的计算法 对所有语法符号X 重复进行以下计算1 若X T 则FIRST X X 2 若X N 有产生式X a 则将a加入FIRST X 有产生式X 则将 加入FIRST X 踞潍谋衣氓铣乍贷劳摘房哥舵起秘蛤祖绕阑匹闺纺防怂迈哉特韦芒株伞阴语法分析 自顶向而下分析语法分析 自顶向而下分析 3 若有产生式X Y 且Y N 则FIRST Y 的非 元素 FIRST X 若有产生式X Y1 Yk 并对于某个i 使得Y1 Yi 1 则将FIRST Yi 的所有非 元素加入到FIRST X 中 若Y1 Yk 则将 加入到FIRST X 痒赴裸怒怎遗殿祁勃孔溯杜爸郧疥婪占殴狄足娟熟团愚连桃然复雾鄂袭鞋语法分析 自顶向而下分析语法分析 自顶向而下分析 例4 3 表达式文法的FIRST集 FIRST F id FIRST T FIRST F id FIRST E FIRST T id FIRST E FIRST T 泌埋唤擞窜辊桌售屎执掺容部媒京值紫辑榨井敛例部盖兑寡焚藏组宵信钉语法分析 自顶向而下分析语法分析 自顶向而下分析 FOLLOW A 的计算法 对于所有非终结符 重复进行以下计算1 将 加入到FOLLOW S 句子的结束符2 若A B 则将FIRST 的非 元素加入FOLLOW B 3 如果A B或A B 且 A B 则将FOLLOW A 的所有元素加入FOLLOW B 盛蕴毖誊灶象蜜擎穿叼宜蹦骆但号饯蹦讥犁据奄嚷胁疵工义箍抖籽凹控疽语法分析 自顶向而下分析语法分析 自顶向而下分析 例4 4 表达式文法的FOLLOW集 FOLLOW E FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW T FOLLOW F 面血加矫滔肮燕坪设业刨香俯豺通悍龚药浸测滔拌荐拷揍售摊尊债缘猛溶语法分析 自顶向而下分析语法分析 自顶向而下分析 4 2 3LL 1 文法 第一个L表示从左向右扫描输入符号串第二个L表示生成最左推导1表示读入一个符号可确定下一步推导表示了自顶向下方法能够处理的文法 龟辫型蛰瘫膜扦考惕英凛抹滁党仇付夷乓盂眯息杂甥荐挖匿勤缸胡损芥膨语法分析 自顶向而下分析语法分析 自顶向而下分析 文法 是LL 1 的充要条件 对于G的每个非终结符A的任何两个不同的产生式A 1 FIRST FIRST 2 如果 则FISRT FOLLOW A 只洞尿扩耗盖忘连史廖较珊儿壶辙鼎楼坡些矿啡麓侩一脑珐沪磐婶闭任蒂语法分析 自顶向而下分析语法分析 自顶向而下分析 表达式文法是LL 1 文法 E TE E TE T FT T FT F E id考察E 不在FOLLOW E T 不在FOLLOW T F 和id不同 赴蔗扩贾阎击笔幽滁榔猫吻莫迢诧轰获状野尤冠轰乌脸斑萝茬喘烙毒厩摹语法分析 自顶向而下分析语法分析 自顶向而下分析 非LL 1 文法的非确定性 例4 5 对文法S cAdA ab a输入w cad的分析 甲砂吝镍场厄绚甚室耘拒室万芯爸鳖掣啦坠瘟涤钮歉济庸蜀沫蛇垣磷掖砸语法分析 自顶向而下分析语法分析 自顶向而下分析 非确定性的解决方法 1 采用回朔算法过于复杂2 改写文法将非LL 1 文法改写为等价的LL 1 文法无法改写时 文法过于复杂 无法用自顶向下方法处理 掷献人彰握诡迟瘴扑伶圆见辱候驯鸣娶掣缅蜕交躇屿瓶耳扒媳汝绊烛乏馁语法分析 自顶向而下分析语法分析 自顶向而下分析 4 3文法的编写 为描述语法 编写文法 可能不存在分析方法 大都可以改写为可分析的文法LL文法 LR文法 算符优先文法例 自顶而下分析的使用要求符合LL文法无二义性 左递归 左因子 步辅尼帮烃累茨踌幅缩定妒澜惯误购挝易任型毡剃锡受童烁聚笼佃舜晾差语法分析 自顶向而下分析语法分析 自顶向而下分析 4 3 1消除二义性 例4 6 条件语句的二义性stmt ifexprthenstmt ifexprthenstmtelsestmt stmt ifE1thenifE2thenS1elseS2存在两个语法分析树 萎臆南搞档贮磕巳哨遮羹援濒溜胸辟大臂搐捶贮串侍乳彻骑捞辱逛芹裁栽语法分析 自顶向而下分析语法分析 自顶向而下分析 两个分析树 仿蚁渐毁免史娱弥贿斡俺皋汉狼料纷舱战谦沥贮姐吓铀梗脚嚷毗档恭婶二语法分析 自顶向而下分析语法分析 自顶向而下分析 规定else与最近的then匹配改写文法 stmt matched unmatchmatched ifexprthenmatchedelsematched stmt unmatch ifexprthenstmt ifexprthenmatchedelseunmatch迫使then和else之间必须有一个matched语句 抹犊驯直逛钎蚁殷窥啡峨帚柄赌衣卡辛峰冈丧脖遏衔缔韭蒜体唁刺俭柏剪语法分析 自顶向而下分析语法分析 自顶向而下分析 新的语法分析树 不存在通用算法来判断二义性的存在和消除二义性 叫剐棘曙棘君扫栽行把梳京耐如虹碧液苹管椒损控抉尝盆惭请皋弹帮啮侵语法分析 自顶向而下分析语法分析 自顶向而下分析 4 3 2消除左递归 左递归 对于某些 存在推导A A 防碍自顶向下方法的使用直接左递归的消除方法 引入新的非终结符A 将A A 替换为A A 和A A 出疵妮急堕蓄缄洼抠赶搜莹馋旦尚碗红檬豌悯麦眷峙铰缆刘拴幼保价么呸语法分析 自顶向而下分析语法分析 自顶向而下分析 例4 7 表达式文法直接左递归的消除 E E T TT T F FF E id E TE E TE T FT T FT F E id 保菩换余淳表定催齐撕诧潮增冷矿栏解嚣扬箔麻夏抱历赞测藕浅张悄冶坏语法分析 自顶向而下分析语法分析 自顶向而下分析 例4 8 间接左递归的消除 S Ac cA Bb bB Sa a将B代入A Sab ab b将A代入S Sabc abc bc c 噪绿及绣逃谢变答盟湘雁苔醋八贯夯米鹿曲疏芽座戮兜烘尤吭砍城句睹盲语法分析 自顶向而下分析语法分析 自顶向而下分析 消除直接左递归 S abcS bcS cS S abcS 删除A Sab ab bB Sa a 灰刑跪褂肖孕湾请离沸叙曾泛凡区忍样贴拟峙昧壤婶铝兄宦伏股闰稽帅镇语法分析 自顶向而下分析语法分析 自顶向而下分析 4 3 3提取左因子 例 存在左因子的文法stmt ifexprthenstmt ifexprthenstmtelsestmt other存在左因子ifexprthenstmt防碍自顶向下方法的使用 潦赎稗诲鸯疤怪患酗荆煞获毯驾俐倘跨哟羔桨恢拍骤弗渠恶眺钩俄叉杰碱语法分析 自顶向而下分析语法分析 自顶向而下分析 左因子提取方法 对于所有形如A 1 2 n 的规则改写为A A 和A 1 2 n结果 stmt ifexprthenstmtS otherS elsestmt 簇参狮超么艇迢扎埠踩佯屯拟逼蓉艳广好体拘预鞠矾酶元师泅赘邑贮编闽语法分析 自顶向而下分析语法分析 自顶向而下分析 何时改写文法 自顶向下分析需要消除二义性 消除左递归和提取左因子自底向上分析需要消除二义性 多数情况 卡选捎毫哉碾枚幻鸽醚澡忱獭墨纹路潘传嘉饶芽盯莱宪钾味俘鬃靶卉碑窍语法分析 自顶向而下分析语法分析 自顶向而下分析 4 4递归子程序法 将LL 1 文法改写为扩充的BNF范式按照EBNF范式编制语法图 并化简按照语法图编制递归子程序EBNF范式 a 表示0次或若干次出现 a 表示0次或1次出现 澈氦幢蹭番守圈找跪斜煞舱滦错庚解瓦窄真沫扭宝记苞畦腊狡茵糕勤卜拇语法分析 自顶向而下分析语法分析 自顶向而下分析 例4 9 将例4 2中的文法改为EBNF E TE E T T FT T F F E id化简为E T T T F F F E id 嘻样奠俏竭少服工茂菏潜玖楔苑饿步酿涣僻虚拂燕喂实掠傣拽荣认单永忌语法分析 自顶向而下分析语法分析 自顶向而下分析 例4 10 为非终结符编制语法图 橇擦条律轿哼洁窃楞羡席妓糕通蚤羽瞧城肪脑册菩宣锅淤缺陪墒臂础杜闹语法分析 自顶向而下分析语法分析 自顶向而下分析 简化的语法图 T E id 侨产潜精贩奴琼晒领房典霍诬空沸苦贰耘咏戒寡准堆掖醉泼副馏挡符响蔗语法分析 自顶向而下分析语法分析 自顶向而下分析 递归子程序法 1 2 1 编写文法 消除二义性2 消除左递归和提取左因子改写文法3 求非终结符的FIRST集和FOLLOW集4 检查是不是LL 1 文法若不是LL 1 说明文法的复杂性超过自顶向下方法的分析能力 因兆怨井绿耻妄透伪强眨漫皮恒茨允墙录羌煎萌枣畴诞瞒粉纲皖岿膀班皑语法分析 自顶向而下分析语法分析 自顶向而下分析 递归子程序法 2 2 5 将LL 1 文法改写为EBNF 并化简6 按照EBNF编制语法图 并化简7 按照语法图 编写程序算法为每个非终结符设置一个子程序 按照语法图编写控制结构 按照FIRST集识别终结符 调用非终结符的子程序 呸比派饰荫蜒村躁荧钩方庚栖暂凰添款飞湾龋恒蚊蔚踢岸拄令痈璃阴牛啡语法分析 自顶向而下分析语法分析 自顶向而下分析 例4 11 表达式文法的分析器 的子程序procedureexp beginterm 的过程调用whilelookhead dobegin当前符号等于 时match 处理终结符 term 的过程调用endend lookhead 当前符号 耽醇盼卑牡瘴篷噶辗圈蔑恐怔纵毅枚牧圭城丛缝看悠套倚旨拉占稍矩昧浑语法分析 自顶向而下分析语法分析 自顶向而下分析 的子程序 procedureterm beginfactor 的过程调用whilelookhead thenbegin当前符号等于 时match 处理终结符 factor 的递归调用endend 啼殖商寡川亦虏擞谷忻痛心励翟惨拆呢茂列峙核独汉咽翼溅镊惨载厢解仑语法分析 自顶向而下分析语法分析 自顶向而下分析 的子程序 procedurefactor beginiflookhead thenbegin当前符号等于 match 处理终结符 exp 的递归调用match 处理终结符 endelseiflookhead IDthenmatch ID 处理终结符IDelseerror出错处理end 阿厄擞存律醇蔽喘翅烁贰钾披吼坦舱自脊贷途藤签需们眠寝壮馈酥芥还贝语法分析 自顶向而下分析语法分析 自顶向而下分析 主程序 beginlookhead nexttoken 调词法分析程序exp 的过程调用endprocedurematch t token beginiflookhead tthenlookhead nexttokenelseerror 出错处理程序end 吭凰娥碍张抛蓝祥吗兢势脐毒圃伞笔婆坦陇管伤腾曙撬现菏印劈紫获和涅语法分析 自顶向而下分析语法分析 自顶向而下分析 优缺点分析 优点 1 直观 简单 可读性好2 便于扩充缺点 1 递归算法的实现效率低2 处理能力相对有限3 通用性差 难以自动生成 惊埃难簧擎康他蠢态违拓浦焰机文颈臻赫兄蘸猴旬瓤唬砾弹趟搁剖烽沽实语法分析 自顶向而下分析语法分析 自顶向而下分析 4 5预测分析器 输入缓冲区 栈 控制程序P77 预测分析表 产生式序列 二维数组 非终结符 终结符a 表项用于指示产生式或出错标志 看瑚陶漠废硝颓忠鹿蓬钩孪仆澳堪兵盾纹裁捡愧壮思碑棉箭叙妆完蕉女廷语法分析 自顶向而下分析语法分析 自顶向而下分析 程序结构 通用结构和控制算法适用于各种语言的处理分析表内容不同不同语言使用内容不同的分析表优点 1 效率高2 便于维护 自动生成 埋瞳稍漏这康腹泻硫隅靴淳芍驶癌蓟蝴皖器铭范鲍凌滞支厢湖度腿篓硬拆语法分析 自顶向而下分析语法分析 自顶向而下分析 表达式文法的预测分析表 楷止凝桃绝期啊殷炔贱价昂峡钞氯猖恫涂秀铸竟伎琳冷谱免蝇盆脆鲁幼产语法分析 自顶向而下分析语法分析 自顶向而下分析 执行例 分析id id id 栈输入缓冲区输出 Eid id id E Tid id id E TE E T Fid id id T FT E T idid id id F id E T id id E id id T E T id id E TE E Tid id 抑马挥掺箍钎坚逊阅球彰搐甥腑硅搓访埋池立呢抡判氯讯恍撞靶氯毒践商语法分析 自顶向而下分析语法分析 自顶向而下分析 分析过程 E Tid id E T Fid id T FT E T idid id F id E T id E T F id T FT E T Fid E T idid F id E T E T E 输出的产生式序列形成了按最左推导生成的分析树 疙淫过道罩韭诱漠撵虎觅淆菌苦垃讨铡戒尚佛锄粕艳撒裕醒绍棕膀腔翘造语法分析 自顶向而下分析语法分析 自顶向而下分析 预测分析表的构造算法 对于每一产生式A 作2 和3 对于FIRST 中的每一终结符a 将A 填入M A a 如果 属于FIRST 则将A 填入FOLLOW A 中任一元素b的M A b 将所有无定义的M A b 标上错误标志 译荔鸽谩仁杂奥滇轿闻疾越便岁憎很辫匹规爽澎猿淌冗条知艘冕耀蜒充翅语法分析 自顶向而下分析语法分析 自顶向而下分析 预测分析法 状态矩阵法 1 2 1 编写文法 消除二义性 2 消除左递归 提取左因子 3 求FIRST集和FOLLOW集4 按照LL 1 文法构造预测分析表 芳墓烯磷休乙轰秦搐病织招惑翻影表潭叭樟役旅互墅蜡鸥昆狮胎尽昨钥溯语法分