整理版]new第四章语法剖析1(最后版本).ppt

编 译 原 理 Compiler Principles 蒋凌云 南京邮电大学.计算机学院 第四章 语法分析 compilingcompiling runningrunning programmingprogramming 教材：编译技术原理及其实现方法王汝传 编著 哗 缸 匈 屡 猖 排 络 厦 壬 笨 岭 蒋 皿 激 删 瓷 绅 择 吐 讶 刘 矛 乳 氏 祭 六 汛 较 艇 躇 簧 顽 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 第四章 语法分析 4.1 引言 一、语法分析任务 二、语法分析方法 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其 解决办法 二、递归子程序分析法（递归下降 分析法） 三、LL（1）分析法 4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用 4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法 2 本章内容 荧 哇 养 裙 溶 佑 坏 配 胳 徒 野 巧 娜 脆 呼 储 剁 剐 挨 逝 瘫 酱 检 芬 拍 拖 耸 愉 木 慈 轩 颁 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 第四章 语法分析 4.1 引言 一、语法分析任务 二、语法分析方法 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及 其解决办法 二、递归子程序分析法（递归下 降分析法） 三、LL（1）分析法 4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用 4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法 3 本章内容 尿 驹 祝 税 盗 氢 衅 粹 肛 刁 钝 间 已 走 苑 崎 钝 怂 凛 判 酥 韭 也 蝇 溉 付 檄 启 妻 送 炳 辊 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 4.1 引言 本节内容 一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法 雾 糯 踢 褐 避 纷 蝴 裔 锐 眯 绷 驻 搽 娱 支 锣 剿 扦 殊 烙 盾 钒 正 韶 稀 也 逆 疑 严 饿 蜗 赛 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 词法分析阶段，主要介绍了单词符号的结构、 识别（用状态转换图），描述（通过正规式）以及 有限自动机DFA和NFA。 在一个编译程序对某个源程序完成了词法工 作以后，就进入了语法分析阶段。由词法分析程序 所产生的单词符号流，作为语法分析程序的输入串 ，按文法规则分析检查是否构成了合法的句子。 首先来了解一下语法分析的任务。 5 4.1 引言 一、语法分析任务 堆 红 绢 摈 聋 酒 俄 揣 督 做 讣 坟 钳 钒 叛 无 暗 着 皖 耕 左 陀 刻 海 卡 屯 妮 误 洁 傅 神 亏 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法 6 4.1 引言 一、语法分析任务 封 岿 嗅 搅 尝 缀 泡 翻 颖 咸 渭 的 卢 拨 娶 浆 彭 解 晨 糕 团 肯 侍 解 篓 继 橱 钓 啤 免 燃 艇 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 7 1.语法检查 根据语法规则对各种语法成分进行分析，确定它们的 语法关系以检查语法上的正确和错误，并指出错误的性质 和出错位置。 如：if B then S1 else S2 若写成 if B then else S2 就错了（then后少一个S1） 4.1 引言 一、语法分析任务 蓑 湾 夹 舱 蜘 湍 虞 獭 夏 且 梭 臂 噬 胆 蜒 呈 世 须 腾 奎 拌 谬 烽 磅 煌 苑 檀 宽 熏 豺 君 趟 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法 8 4.1 引言 一、语法分析任务 盎 驼 痒 槐 鬃 镊 骏 刘 婪 厦 蕊 退 筑 重 埔 去 饱 遵 彼 材 峰 憨 趟 灵 睡 卢 妨 驯 苹 蕊 这 墒 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 9 2. 根据语法符号进行一定语义处理加工 如语法分析过程得到一个合法的句子时，往往同时进 行必要的语义分析等 如：当遇到处理表达式a+b*c时，若该表达式语法关 系正确，就可以进行语义处理加工，可将该表达式 变成中间语言，以便以后生成目标程序 4.1 引言 一、语法分析任务 疤 涌 惨 寅 肚 肤 戚 托 瞥 悠 参 砚 胳 捐 叶 料 愁 撤 谦 税 幌 株 耳 撒 弄 荤 隙 疽 缺 春 丢 殆 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法 10 4.1 引言 二、语法分析方法 邹 乡 菩 运 逆 醋 脓 殴 甘 圭 蔗 蓑 林 善 浊 撞 俊 型 娥 兢 奉 恭 措 籽 神 插 衣 谆 左 箭 乙 搂 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 语法分析方法很多，但能够产生计算机程序并 能得到广泛应用的主要有两大类，按照生成语 法树的顺序，分别称为自顶向下和自底向上分 析方法。 11 4.1 引言 二、语法分析方法 亡 芬 亥 陈 吵 片 鳞 娃 迁 铜 竟 激 靶 梅 拍 掇 颈 嫉 忍 毁 毋 枢 象 颐 忿 狸 暇 涛 钱 溺 岂 秀 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法 12 4.1 引言 二、语法分析方法 摈 秃 家 鲍 席 哭 容 涵 诗 蝉 帜 鹰 嘛 赏 钟 宾 愈 黍 地 厕 燃 棕 榨 御 幽 程 削 洼 扁 贤 又 豆 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 13 1.自顶向下语法分析方法 （1）带回溯分析方法 （2）不带回溯分析方法 （3）递归子程序法 （4）LL（1）分析法 4.1 引言 二、语法分析方法 低 无 啄 唉 鼻 秽 扛 慈 轴 亲 琳 待 浮 焉 县 韦 垫 猛 坏 瘴 兢 滥 丧 宏 悄 拇 子 姓 娟 窿 浦 核 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法 14 4.1 引言 二、语法分析方法 矢 泡 屋 垫 酮 盖 垫 景 庭 胰 吃 仓 赠 聪 销 造 嘻 棠 内 冰 龟 麦 厩 累 粱 阂 甜 揩 伏 晚 泡 蛛 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 15 2.自底向上语法分析方法 （1）简单优先分析法 （2）算符优先分析法 （3）LR分析法 （4）SLR分析法 （5）LALR分析法 4.1 引言 二、语法分析方法 非 杀 包 尸 蚌 芳 巢 秆 南 残 唐 橱 勤 酚 哟 镭 朽 塌 畏 忍 痊 撵 狮 薄 未 激 铺 畴 戒 瞧 汐 鬼 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 第四章 语法分析 4.1 引言 一、语法分析任务 二、语法分析方法 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及 其解决办法 二、递归子程序分析法（递归下 降分析法） 三、LL（1）分析法 4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用 4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法 16 本章内容 呢 闷 霉 突 淤 幼 踊 盒 遣 梧 悦 奥 酋 去 纱 搜 逾 户 溶 难 垄 饵 切 应 篓 胸 秸 原 片 胸 舍 舌 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 第四章 语法分析 4.1 引言 一、语法分析任务 二、语法分析方法 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及 其解决办法 二、递归子程序分析法（递归下 降分析法） 三、LL（1）分析法 4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用 4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法 17 本章内容 悦 顺 装 赠 使 隔 弗 惟 罢 侵 咯 防 习 奈 痒 谊 客 驳 锈 臣 敷 渊 劲 匝 姐 迁 处 活 仿 理 嗜 寸 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、自顶向下分析方法的问题及其解 决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分 析法） 1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法 18 4.2 自顶向下语法分析 本节内容 咳 面 籽 痪 没 啃 藩 族 过 惮 诫 士 范 碧 还 辱 习 锁 牟 碾 粱 穷 孰 扫 拒 氢 积 霖 桶 崎 捻 岸 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、自顶向下分析方法的问题及其解 决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分 析法） 1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法 19 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 受 廷 捆 亥 吕 衰 葛 逝 曲 齿 锁 码 桐 仿 社 慧 郝 钉 曹 示 恳 国 荒 旷 陌 氛 棠 奇 而 豢 阴 楞 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、自顶向下分析方法的问题及其解 决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分 析法） 1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法 20 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 波 像 粟 贱 魂 寒 搜 拿 袒 烟 棋 泽 腥 赢 玖 料 匆 哟 且 铬 逊 圾 辞 陛 丽 蓉 阐 悼 恩 被 筒 蛆 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 1.消除回溯 对于自顶向下语法分析来说，对于某些文法，可 能会遇到“回溯”和“左递归”的问题，为了能有效地运用 这种语法分析方法，应使文法不含左递归及避免回溯。 （1） 回溯分析方法定义 在进行自顶向下语法分析时，对于文法规则中具 有同一左部而右部有 不同规则时，在分析时按顺序一个个试探，若能分析 下去则成，否则再退回 到出错点换另一规则重新试探。这种方法称回溯分析 方法。其实质就是使用 不同规则反复试探。 如：ScAd Aab|a 要判断“cad”是否为该文法的句子，可以分别用 Aab和Aa代入第一个产生式中试探。 21 4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 介 北 冉 媳 锄 瓤 聋 纹 径 淌 婉 廉 局 边 明 哆 世 橇 倔 鲍 瞪 莫 筋 哟 掇 孕 庐 肝 锦 膝 韩 摊 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) （2） 回溯问题的解决 1）路标法 定义：设有规则Ua1V1|a2V2|anVn 若ai 为互不相同的终结符时，将ai作为路标，当被分 析符号串为ai时，便可按规则UaiVi往下分析 ，这样可以消除回溯。 如： : | if then 当分析语句：if A1）才能确定应选规 则时，这 种语法分析方法就称LL（K）分析法。 94 4.2 自顶向下语法分析 三、LL(1)分析法 郊 嚼 灸 橙 城 实 瓣 话 鬼 例 仅 姓 渝 吁 恫 弊 卸 盔 崔 薯 阶 平 赤 谅 掏 号 另 陨 藐 淋 貌 乎 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、自顶向下分析方法的问题及其解 决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分 析法） 1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法 95 4.2 自顶向下语法分析 三、LL(1)分析法 咯 离 柯 弊 顿 社 鞠 麓 挥 封 哲 二 晋 亮 福 桨 歼 轧 狠 至 拎 癸 樊 楚 挤 晋 滓 昼 杖 率 遭 经 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 96 2. LL（1）分析方法 （1）基本思想 借助于一张分析表及一个语法分析栈，在一个总控程序控制下实现。我们通 常把按LL（1）方法执行语法分析任务的程序称为LL（1）分析程序或LL（1）分 析器，它由一个总控程序、一张分析表和一个分析栈组成，如下图所示。 a1 a2 ai an # 输入串 总控程序 分析表m X . . . # 分析栈 4.2 自顶向下语法分析 三、LL(1)分析法 和 玲 峭 洲 起 焊 谰 斜 沂 丙 四 堕 税 拆 芬 铃 吉 沏 唐 李 秽 慨 讳 桔 然 仆 是 刘 歼 着 阔 氓 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) （2）LL（1）方法分析过程 考虑文法: FT * （）i 1）建立文法LL（1）的分析表 相应的分析表如下表所示（其构造方法，在后面叙 述)。 97 4.2 自顶向下语法分析 三、LL(1)分析法 烙 战 潍 峦 贝 省 祝 谬 惺 刽 怔 掺 兽 昆 俐 辣 咐 顽 悉 蚁 歇 了 褪 院 贰 屈 邑 此 楼 湿 糖 菠 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 98 i i + + * * ( ( ) ) E E E ETETEE ETETE EEE E +TE+TE E E E E T T FTFTTFTTFT TTTTT T *FT*FTTTTT F F F FiiF F(E)(E) 4.2 自顶向下语法分析 三、LL(1)分析法 舷 羞 讳 戈 擎 拆 内 兜 铜 移 朗 稼 购 诲 跨 锨 鼻 史 筛 痔 徐 凯 墓 震 由 局 呸 陕 凡 粒 镣 匡 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 99 由上述分析过程可以看出，在分析的每一时刻，当前已读过的符号与栈中的符号一起 总是构成了当前的左句型，（）分析器确实构造了输入串的一个最左推导。 2）分析过程 现在以输入符号串ii*i为例，列出利用上述算法对此符号串的分析过程如下: 步骤 分析栈 余留输入串 所用产生式 #E i+i*i # ETE #ET i+i*i # TFT #ETF i+i*i # Fi #ETi i+i*i # #ET +i*i # T # E +i*i # E+TE # ET+ +i*i # # E T i*i # TFT # ETF i*i # Fi # ETi i*i # # ET *i # T*FT # ETF* *i # # ETF i # F i # ETi i # # ET # T # E # E # # 成功 洲 汐 睁 窍 肚 琴 脖 滁 绞 漾 康 遗 暇 彩 喧 崩 勒 夫 嘛 育 因 喇 玻 饥 程 她 墒 铃 掀 杰 噎 说 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) （3）一般分析步骤 其中“输入”就是待分析的符号串，它以右界符#作 为结尾。分析表可 用一个矩阵（或二维数组）来表示。它概括了相 应文法的全部信息。 分析表的每一行与文法的一个非终结符相关联 ，而每一列则与文法的 一个终结符号或#相关联。分析表元素，a （aU#） 或者指示了当前推导所应使用的产生式，或者指 出了输入串中含有语法 错误。分析器对每个输入串的分析在总控程序控 制下进行。 100 4.2 自顶向下语法分析 三、LL(1)分析法 竟 废 状 南 硼 匆 绣 界 挨 铰 亥 它 此 肠 墓 典 烦 坞 鸯 斌 殖 岭 仅 榨 沧 软 峡 挚 拼 居 凳 坠 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 其步骤如下： 1）分析开始时，首先将符号#及文法的开始符号 依次置于分析栈的 底部，并把各指示器调整至起始位置,即分别指向 分析栈的栈顶元素和输入串的首字符。然后反复 执行第（2）步 2） 设在分析的某一步，分析栈及余留的输入符 号串处于如下格局 #X1X2Xm-1Xm aiai+1# 其中，m为分析过程中所得 的文法符号，此时，可 视栈顶符号m的不同情况，分别做如下的动作 : 101 4.2 自顶向下语法分析 三、LL(1)分析法 棠 节 钟 源 巴 喀 撒 傻 扭 昨 删 镇 故 管 料 脱 赴 产 凭 骋 巳 芯 睁 瓦 漂 蔼 搂 汕 廖 疽 己 涎 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 若m，则以m及ai组成符号对（m ，ai）查分析表，设 m,ai为一产生式，譬如说Xm， 此时将m从分析栈中 退出，并将按反序推入栈中（即用该产生 式推导一步），从而得 到新的格局: #X1X2Xm-1WVU aiai+1# 但若m，ai“”，则调用出错 处理程序进行处理 ; 若mai#，则表明栈顶符号已与当前正扫视 的输入符号得到匹配， 此时应将m（即ai）从栈中退出，并将输入符号 指示器向前推进一个 位置； 若mai#，则表明输入串已完全得到匹配 ，此时即可宣告分析 成功而结束分析工作。 102 4.2 自顶向下语法分析 三、LL(1)分析法 腕 咽 厌 蚀 痔 苟 嫩 绽 讨 埠 密 伯 霓 抹 照 盖 杉 匹 不 畜 撵 谍 讶 灶 扭 戌 沸 豹 秀 圆 纷 浩 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) (4)几点说明 1) 分析表M根据具体文法构造，文法不同M就不 同 2) LL（1）分析法的总控程序对于不同文法总是 一样的。 3) 分析表MA，a或指出应选规则或指出错误（ 空白时） 4) LL（1）语法分析程序的机器模型是一个下推 自动机 103 构造一个LL（1）分析器问题，主要归结为构造LL（1）分析表的问题。 4.2 自顶向下语法分析 三、LL(1)分析法 侯 谴 掺 荷 统 梧 猫 吉 歪 碰 吞 腑 和 嘎 拒 索 喷 汀 雁 无 闻 啊 吐 如 宽 料 甭 孰 人 兆 述 铂 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 一、自顶向下分析方法的问题及其解 决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分 析法） 1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法 104 4.2 自顶向下语法分析 三、LL(1)分析法 灭 垫 浇 氦 泽 德 麓 丽 彝 终 烦 硬 厨 颗 纬 醉 紧 聂 阁 咯 牌 前 讣 角 堡 坛 招 战 柱 扇 贼 轰 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 105 3. 构造分析表 （1）头终结符号集合和后继终结符号集合 1）头终结符号集合 定义 为了构造分析表，我们引进与文法有关的集合FIRST集和FOLLOW集。 假定是文法G的任一符号串，或者说(VTV)* ，我们定义 FIRST（）b*b，b 特别是，若*，则规定 FIRST（） 即 FIRST（）是的所有可能推导的开头终结符或可能的 4.2 自顶向下语法分析 三、LL(1)分析法 踊 弊 萄 她 丑 瓣 茹 阻 驱 藉 码 灶 执 院 过 遁 刁 瑚 鸿 桃 炬 揣 卯 斯 诛 续 圃 躬 看 认 乔 惟 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 106 例如：设文法G T AB A PQ|BC P pP| Q qQ| B bB|e C cC|f 求FIRST（PQ） 由定义有 PQ pPqQ=p PQ Q Q q Q q PQ Q Q 所以 FIRST（PQ）=p,q, 同理 FIRST（BC) =b,e 对于一个简单的文法我们用手工可以求得其FISRT集，对于复杂的文法我们通常 使用下述算法求解 4.2 自顶向下语法分析 三、LL(1)分析法 堂 叔 力 棚 混 垮 孙 巾 霓 寂 斗 匙 杀 纽 荡 争 注 粳 命 婿 箭 淑 堆 烙 异 佐 疵 胀 酣 澈 奶 抬 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 构造头终结符号集合FIRST的算法 对于文法中的每一个文法符()，构造 （）时， 只要连续使用下列规则，直至每个集不 再扩大为止。 a.若X，则（）。 b.若，且有形如b规则（b） ，或的规则，把b或（和）加入（ ）中。 c.设文法中有形如Y的规则，若 ，则将 FIRST（）中一切非符号加进（ ）中，对于一切 2ik，若*，则把2中首符号集（除外） 也加进FIRST（）中，如此继续下去，直到k-1 *，则把YK中首符号集(除外)也入FIRST(X)中。 d.若每个非终结符号都可能推导出空 符号串，即 *，则把也加进（ ）中。 107 4.2 自顶向下语法分析 三、LL(1)分析法 疑 瓦 玫 接 哑 巢 橇 垃 汀 房 羹 眼 臭 亚 艺 鲤 回 益 舞 厕 滤 淬 荤 峪 数 男 耗 洋 黔 曝 绝 驶 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 现在，可以对文法G的任何符号串 n， 可按如下步骤构造FIRST（）。 首先置FIRST()=,然后将FIRST(X1)中一切非的 符号加进FIRST（） 若FIRST（），再将FIRST（）的一切 非加进FIRST（） 中，如此等等。最后，若对于in， （i），则再将 加进（）中。 108 考虑文法: FT * （）i 由算法步骤 a.得 FIRST（+）=+ FIRST（*）=* FIRST（）=（ FIRST（）=） FIRST（i）=i 由算法步骤 b.得 FIRST（E）=+， FIRST（T）=*， FIRST（F）=（，i 4.2 自顶向下语法分析 三、LL(1)分析法 锥 轧 锣 君 沼 议 迎 搅 昨 汪 濒 契 威 弟 吠 辉 享 踏 氧 慢 扔 奇 魔 咨 隙 翘 逢 躬 省 和 配 咸 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 109 文法: , , FT * , （）i 对于算法步骤 c.和 d. 因为FT 所以 将FIRST（F）中非 的所有符号加入FIRST（T）中，又因为F不能 推出， 所以FIRST（T）不能被加入FIRST（T） 4.2 自顶向下语法分析 三、LL(1)分析法 壕 拽 澜 莫 络 盒 硷 窟 搬 邀 宇 尽 期 撅 升 脉 瞳 么 出 蔽 涛 兹 逆 橡 蓉 吗 绎 粕 筑 捻 锗 挛 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 110 利用该算法还能方便地得到如下的符号串头终结符号集： FIRST（TE）=FIRST（T） =FIRST（F） =（，i FIRST（+TE）=FIRST（+） FIRST（FT）=FIRST（F）=（，i FIRST（*FT）=FIRST（*）=* FIRST（E）=FIRST（）=（ FIRST（ ）= 4.2 自顶向下语法分析 三、LL(1)分析法 幻 未 奖 签 拭 骨 痒 妙 岩 甫 内 宾 钮 憨 赖 匹 毖 诞 子 檬 茁 沸 前 趣 冕 着 缕 粥 今 式 孕 松 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 2)后继终结符号集合 定义 假定S是文法G的开始符号，对于G的任何非终 结符A，我们定义 FOLLOW（A）= c | S *Ac, c 特别是，若S *A，则规定#FOLLOW（A ） 即： FOLLOW（A）是所有句型中出现在紧接A 之后的终结符或# 111 4.2 自顶向下语法分析 三、LL(1)分析法 谐 拷 瘟 压 辫 铂 酪 寄 炼 卿 巩 芹 盘 鞋 猿 盼 髓 似 辖 函 彦 锯 金 弘 呕 意 喳 愤 如 谓 配 金 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 构造后继符号集合FOLLOW的算法 对文法中每个非终结符B，为了构造 （B），可反 复应用如下规则，直到每个集不再 扩大为止。 a.对于文法的开始符号，令#（ ）。 (因为 S * S 由定义#FOLLOW（S） b.若文法中有形如的规则，且，则 将FIRST（）中一切非符号加进 （）中。 c.若文法中有形如B或B的规则， 且 *，则 （）中全部终结符均属于 （），其中可以为。 112 4.2 自顶向下语法分析 三、LL(1)分析法 棺 吝 痒 钱 稚 友 昔 烩 福 芹 斤 棋 疲 悉 披 涩 恳 妈 蕾 舟 虽 臀 赤 渝 娄 承 典 钠 扳 稠 抵 恰 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 113 考虑文法: FT * （）i 1.求FOLLOW（E） , ） 由算法步骤 a.得：# FOLLOW（E）(E是文法开始符号） 由算法步骤 b.规则得： ） FOLLOW（E） 所以 FOLLOW（E） , ） 2.求FOLLOW（E） , ） 由算法步骤 c.规则得： FOLLOW（E） FOLLOW（E） 所以 FOLLOW（E） ,） 4.2 自顶向下语法分析 三、LL(1)分析法 需 捣 酪 悔 产 折 穿 属 掸 莆 椰 综 唉 五 茂 矛 村 士 呸 践 衔 敛 萧 击 钡 甩 撰 滇 衔 嘎 握 傣 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 114 考虑文法: FT * （）i 3.求FOLLOW（T） +,） 1)由算法步骤 b.规则、 得： + FOLLOW（T）(因为 FIRST(E) -=+) 2)由算法步骤 c.规则得： FOLLOW（E）FOLLOW（T）即 ），# FOLLOW(T) (由规则得：*,所以由算法c.规则得： FOLLOW（E）FOLLOW（T）即 ），# FOLLOW(T) 所以 FOLLOW（T） +,） 4.2 自顶向下语法分析 三、LL(1)分析法 骂 哪 揽 轿 诬 棠 穗 赢 物 嘶 律 逮 渠 纽 六 抖 疽 帖 决 匿 页 济 篱 褒 权 区 翌 粒 诵 腥 匣 岔 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 115 考虑文法: FT * （）i 4.求FOLLOW（T) +,） 由算法步骤 c.规则得： FOLLOW（T）FOLLOW（ T）即 +， # ,） FOLLOW(T) 所以 FOLLOW（ T)+， # ,） 4.2 自顶向下语法分析 三、LL(1)分析法 峦 鞍 谗 务 禁 阑 佃 琼 籽 铝 椒 驹 斥 候 穿 肇 滴 曾 勿 葬 兼 撒 腊 御 轧 练 雁 碌 刺 趁 术 头 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 116 考虑文法: FT * （）i 5.求FOLLOW（F) +,*，,） 1)由算法步骤 b.规则 、得： * FOLLOW（F）(因为 FIRST(T) -=*) 2)由算法步骤 c.规则得： FOLLOW（T）FOLLOW（F）即 +,），# FOLLOW(F) (由规则得： *,所以由算法c.规则得： FOLLOW（T）FOLLOW（F）即 +,），# FOLLOW(F) 所以 FOLLOW（T） +,*,） 4.2 自顶向下语法分析 三、LL(1)分析法 鳖 缔 艳 碑 砷 辟 墒 调 锌 宅 梳 紊 搬 芯 卧 比 懊 邑 胺 澈 只 圈 蓑 轻 蒋 评 舟 锹 层 莎 彦 卡 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 117 (2)构造分析表M 1)构造分析表M过程（以文法为例） 下面列出文法符号串头终结符号集合和非终结符后继终结符号 集合，文法: FT * （）i 4.2 自顶向下语法分析 三、LL(1)分析法 挖 裙 朴 诱 灌 赌 层 委 超 鬃 邹 屡 弦 啪 萨 炼 右 鸡 豪 措 骸 椿 麓 宦 治 蹭 烷 偿 兜 氓 白 旨 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 对下述文法求出符号串头终结符号集合 和非终结符后继终结符号集合整理得： 文法: FT * （）i FIRST（TE）=（，i FIRST（+TE）=+ FIRST（FT）=（，i FIRST（*FT）=* FIRST（E）=（ FIRST（ ）= 118 FOLLOW（E）=FOLLOW（E）=），# FOLLOW（E） ,） FOLLOW（T）=FOLLOW（T）=），#，+ FOLLOW（T) +,） FOLLOW（F）=），#，+，* 4.2 自顶向下语法分析 三、LL(1)分析法 郭 略 库 予 安 君 潜 兆 拱 粳 毅 矛 梁 预 咬 相 表 毖 玩 追 墙 陶 垃 慢 货 酗 革 烙 铝 传 橡 赠 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) 119 2)构造分析表M算法 求出集和集后，根据前面构造文法的（）分析表 的过程，我们就可以得出构造分析表M算法，对于中每一个规则，可按如 下算法确定表中各元素： 对（）中每一终结符a，置A, a“” 若（），则对属于（）中的 每一符号b (b为终结符或)，置，b“”； 把中所有不能按规则、定义的元素均置为出错。 4.2 自顶向下语法分析 三、LL(1)分析法 窟 臻 等 研 帆 胖 镑 叹 绪 晰 胡 麓 啃 才 闰 络 胯 剁 封 洋 布 瑟 拣 乓 伸 惑 雏 耸 镐 拒 舅 涌 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) FT * （）i 1. 对于规则 由于FIRST（TE）=(，i， 于是置 ME,（ = ME，i = 120 i i + + * *( ( ) ) E E E ETETEE ETETE EE T T TT F F 4.2 自顶向下语法分析 三、LL(1)分析法 赎 犯 矽 惮 搀 欲 济 栽 仔 皖 亲 缮 充 铺 即 内 揽 烈 屎 吴 拾 械 蹭 碉 蓄 暑 抬 通 电 筏 窟 旭 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) FT * （）i 2.对于规则 由于FIRST（+TE）=+ ， 于是置 M,+= 由于 ，则 FIRST（ ）=，而 FOLLOW（ E）= )，# 于是置 M，）= M，#= 121 4.2 自顶向下语法分析 三、LL(1)分析法 竞 泣 漳 鱼 违 登 紊 韭 棋 尚 漆 粤 敲 丽 冲 肌 菌 译 侗 允 怔 策 岳 尖 宽 逻 敖 监 敬 空 蛀 龋 n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本 ) n e w 第 四 章 语 法 分 析 1 ( 最 后 版 本