网络编程 第5章.ppt

1 第五章 语法分析 2 语法分析是编译程序的核心部分 目前语法分析常用的方法有自顶向下 自上而下 分析和自底向上 自下而上 分析两大类 本章将主要介绍确定的自顶向下分析思想和对文法的要求 本章主要介绍内容为 LL 1 文法的定义和判别非LL 1 文法的等价变换确定的自顶向下分析方法递归子程序法预测分析方法 本章内容 3 学习目标 确定的自顶向下分析方法虽对文法有一定的限制 但由于实现方法简单 直观 便于手工构造或自动生成语法分析器 因而仍是目前常用的方法之一 能够对一个给定的文法判断是否是LL 1 文法 能构造预测分析表 能用预测分析方法判断给定的输入符号串是否是该文法的句子 能对某些非LL 1 文法做等价变换 消除左递归 提取左公共因子可能会变成LL 1 文法 这样可扩大自顶向下分析方法的应用 4 重点 LL 1 文法的定义和判别 非LL 1 文法的等价变换 预测分析方法难点 对一个文法如何判断是否是LL 1 文法 因为在判断LL 1 文法时 用到文法符号串的开始符号集合 FIRST集 和非终结符后跟符号集合 FOLLOW集 的计算 而初学者往往会因概念不清或不够细心计算错误这两个集合 从而导致判断和分析结果的错误 5 知识体系 基本问题 提取左公因子 分析方法 消除左递归 直接左递归的消除间接左递归的消除 递归子程序法 满足的条件递归子程序的构造递归子程序分析过程 LL 1 分析法 满足的条件LL 1 分析表的构造LL 1 分析过程 不确定方法 回溯算法 确定方法 自上而下语法分析 6 前言 语法分析是编译过程的核心部分 1 语法分析的任务 按照文法 从源程序符号串中识别出各类语法成分 同时进行语法检查 为语义分析和代码生成做准备 分析器的输入 单词符号分析器的输出 分析树出错处理 定位 续编译2 语法分析程序的定义 执行语法分析任务的程序称为语法分析程序 也称为语法分析器 它是编译程序的主要部分之一 扫描器 分析器 语义处理 单词符号 分析树 7 3 语法分析方法 递归子程序 预测分析 LL 算符优先 LR 0 SLR 1 LR 1 LALR 自顶向下 自底向上 不确定法 回溯 确定法 CFG的改造 消二义性 左递归 提左因子 8 4 常用文法 没有一种方法能有效分析所有上下文无关文法存在无法处理的 型文法 CFG 每种方法能够处理一部分上下文无关文法每种方法都有适用范围常用文法 LL文法和LR文法都是2型文法即上下文无关文法的子集 无二义性 可用不同的文法来描述同一语言对于不同的文法 可用不同的分析方法LL文法 递归下降分析法 预测分析法LR文法 LR分析法LL文法多用于编译的手工实现LR文法多用于编译的自动生成 9 5 自顶向下分析法 面向目标的分析方法 从推导的角度看 从识别符号出发 试图推导出与输入符号串相同的符号串 一般来讲 构造出的推导是最左推导 从语法树的角度看 从根结点 试图自上而下的画一个语法树 其末端节点正好与输入符号串相同 要点 由根向下构造语法树构造最左推导推导出的终结符是否与当前输入符匹配讨论前提输入的是符号序列 不对符号构造情况感兴趣 10 5 1带回溯的自顶向下的分析方法 1 思路 对任一输入符号串 通过一切可能的办法 从树根结点 识别符号 出发 根据文法自上而下地为输入串建立一棵语法树 或者说 从识别符号开始 根据文法试图为输入串建立一个推导序列 2 特点 是自顶向下分析的一般方法 分析过程的本质是一种试探过程 11 3 例题 假定有文法G S 1 S cAd 2 A ab a对输入串w cad 要求自上而下地构造w的语法树 解决过程 b c A d a S a 从文法的开始符号出发 反复使用不同的产生式谋求匹配输入串w 当用某个非终结符号的候选式进行匹配失败时 则推翻分析退回到适当位置再重新试探其它候选式 直到把所有可能的推导序列都试探完仍不成功才能确认输入串不是该文法的句子而报错 称为带回溯的自顶向下分析 回溯需要推导记住现场 浪费了大量的时间和空间 12 5 2确定的自顶向下分析思想 构造推导的关键问题 找出选择一个非终结符号的候选式的方法 确定的自顶向下的分析方法在推导过程中 可以完全根据向前 右 看符号唯一决定选择哪个产生式往下推导 因此 分析过程是完全确定的 这种分析称为确定的自顶向下分析方法 13 特征 根据向前看符号为当前要处理的非终结符选择产生式要求 文法是LL 1 的第一个L从左到右扫描输入串第二个L生成的是最左推导1向前看一个输入符号 lookahead 确定分析程序的实现技术1 递归下降子程序2 预测分析程序 14 例 构造最左推导 确定的自顶向下分析 S Ap BqA a cAB b dB输入串 w ccap 结束符 S Ap cAp ccAp ccap S 语法树 15 原因前提 文法中无空产生式 观察 S Ap BqA a cAB b dB在文法中 对于每个非终结符A的定义A 1 2 n任给i j 1 i j n ij 从 i和 j推导出来的第一个终结符号集合 称为开始符号集FIRST 不相交 即 FIRST i FIRST j 结论在推导过程中完全可以根据向前看符号是属于哪个产生式右部的开始符号集合而决定选择相应的产生式进行推导 因此 分析过程是完全确定的 16 总结 为了实现不带回溯的自顶向下分析 对2型文法来说 需要满足下述两个条件 文法是非左递归的因含有左递归的文法会使自顶向下的分析过程陷入无限循环 对文法的任一非终结符号 若其规则右部有多个选择 候选式 时 那么 各选择所推出的终结符号串的开始符号集合要两两不相交 17 方法 一 提取左公因子二 消除左递归消除直接左递归消除间接左递归 5 3CFG 型文法 的改造非LL 1 文法到LL 1 文法的等价变换 18 文法G的产生式A 1 r存在左因子 影响分析 遇到 时难以判断用哪一个产生式进行匹配 推导 若A 1 r改写成 A 1 r 或引入新非终结符A A A 1 r一般 A 1 2 n r1 rm改写成 A A r1 rmA 1 2 n若 1 2 n仍有公共左因子 可再次提取 直到无公共左因子为止 一 提取左因子 19 例 1 S aSb 2 S aS 3 S 提取 1 2 的左公因子最终得 S aSAA b S 20 例 S iEtS iEtSeS aE b其中 i t e分别表示if then和else E和S分别表示表达式和语句 提取了公共左因子之后 文法变为S iEtSS aS eSE b于是 对于输入i 我们可以展开S为iEtSS 直到iEtS分析完毕再去决定把S 展为eS或 21 隐式左公因子 有些产生式右部以非终结符开始方法 对右部以非终结符开始的产生式 用其相同左部而右部以终结符开始的产生式进行相应的替换 例 S aSd AcA aS b把A的产生式代入S中 S aSd aSc bc提取左因子 S aSA bcA d cA aS bA的产生式是多余的 需删除 最终 S aSA bcA d c 22 也存在某些文法不能在有限步骤内提取左公因子的 例 1 S Ap Bq 2 A aAp d 3 B aBq e用 2 3 右部替换 1 中的A B 1 S aApp aBqq dp eq 2 A aAp d 3 B aBq e提取 1 S a App Bqq dp eqS aS dp eqS App Bqq继续 无休止在有限步骤内不能改写成无公共左因子的文法 说明 1 有些文法在有限步骤内不能改写成无公共左因子的文法 2 一个文法提取公共左因子后不一定为LL 1 文法 23 二 消除左递归 一 左递归的定义一个文法G 若存在下列产生式时A A 其中 A VN V 直接左递归 A B 1B A 2A B VN 1 2 V 间接左递归 则称G是左递归的 24 二 左递归文法不适于用来构造自顶向下分析因为 通过下面的例子 S Sa b 1 FIRST Sa FIRST b 2 由S产生的句子是 ban n 0 例如 对于输入baaa 从左到右扫描输入串 S 若用这样的产生式构造递归预测分析 那么一进入这种过程不匹配任何输入符号 直接执行递归调用 形成自己调用自己的死循环 S 25 1 简单左递归A A 消除左递归改写为右递归 A A A A 2 一般左递归A A 1 A 2 A m 1 2 n消除左递归改写为右递归 A 1A 2A nA A 1A 2A mA 例如 E E T TT T F FF E id E TE E TE T FT T FT F E id 三 消除直接左递归 26 五 消除文法中一切左递归的算法要求无环路 即无A A的推导算法步骤如下 1 把非终结符按某一顺序排序为A1 A2 An2 for i 1 i n i 处理全部非终结符 for j 1 j i l j if Aj 1 2 k Ai Aj 把Ai Aj 改写成Ai 1 2 k 消除关于Ai产生式的直接左递归 3 化简由 2 所得到的文法 四 消除间接左递归 非终结符置换 例如A3 A1b则改写A3 即左部非终结符下标 右部时 改写 27 注 1 此算法适用于消除不含形如P P的产生式 也不含以 为右部的产生式的文法2 这里第二步所做的工作是 a 若产生式右部最左符号是非终结符且其序号大于左部的非终结符 则不处理 b 若序号小于左部的非终结符 则将这序号小的非终结符用其右部串来取代 直到这种情况全部处理完 最后消除新的直接左递归 28 解 1 非终结符号排序为S Q R2 对S Q的序号大于S的序号 不处理 对Q R的序号大于Q的序号 不处理 对R S的序号1小于R的序号3 所以改写R Sa将 1 式的右部取代S 得到 R Qca ca a 记为 4 式 此时 4 式中Q的序号2小于R的序号 所以改写R Qca 将Q Rb b的右部取代Q 得到R Rbca bca ca a 记为 5 式 5 式中出现直接左递归 消除直接左递归R bca ca a R R bcaR 最终文法为 S Qc cQ Rb bR bca ca a R R bcaR 例 对下面文法消除左递归 G s 1 S Qc c 2 Q Rb b 3 R Sa a 29 非终结符号排序为Q R S把 2 右部代入 1 4 S Rbc bc c把 3 右部代入 4 5 S Sabc abc bc c消除直接左递归S abc bc c S S abcS 文法为 S abc bc c S S abcS Q Rb bR Sa aQ R无用 删除 例G s 1 S Qc c 2 Q Rb b 3 R Sa a 结果 S abc bc c S S abcS 30 5 4LL 1 文法判定 一 FIRST和FOLLOW集1 FIRST集例 若有文法G S S pA qBA cAd a若输入串w pccadd 则构造最左推导的过程如下 S pA pcAd pccAdd pccadd S 每个产生式的右部都由终结符号开始 且两个相同左部产生式的右部由不同的终结符组成 因此 分析过程唯一确定 31 例 若有文法G S S Ap BqA a cAB b dB若输入串w ccap 则构造最左推导的过程如下 S Ap cAp ccAp ccap S 对于从S出发选择哪个产生式 需要知道 Ap或Bq它们 的开始符号集合是什么 若c是包含在Ap的开始符号集合中 且不包含在Bq的开始符号集合中 则选择S Ap往下进行推导因此 分析过程也唯一确定 32 FIRST集定义 设G S VT VN S P 是上下文无关文法FIRST a a a T 若 则规定 FIRST FIRST 包含了 对应的推导的所有可能的第一个终结符号 选择产生式的依据 a 33 下面考虑有 产生式会出现的情况 例 若有文法G S 其产生式如下 S aA dA bAS 若输入串w abd 则构造最左推导的过程如下 S aA abAS abS abd S d是句型abAS中紧跟随非终结符A的终结符号 因此 可以正确的分析下去 2 FOLLOW集 34 把紧跟非终结符A的终结符号集记作FOLLOW A 结论在构造最左推导的过程中 使用A 候选式替换A去推导的条件 向前看符号a不出现在A的所有非空候选式的FIRST集合中 向前看符号a应该出现在FOLLOW A 中 当文法中有形如A 的产生式时 不同时推导出空时 设 推导不出空 推导出空 则A的替换可唯一确定的条件 FIRST FIRST FOLLOW A 35 FOLLOW集定义设G S VT VN S P 是上下文无关文法 A VN S是开始符号 则定义一 FOLLOW A a S Aa a VT 若有S A 则规定 FOLLOW A 定义二 FOLLOW A a S A 且a VT a FIRST VT V 若S A 且 则 FOLLOW S 作为输入串的结束符 S Aa 36 二 FIRST集的求法 从左向右看 难点 定义令G S VT VN S P 则FIRST a a a VT V 若 则 FIRST 对每一文法符号X 计算FIRST X 过程如下 a 若X VT 则FIRST X X b 若X VN 且有产生式X a a VT 则把a加入到FIRST X 中 c 若X VN 若X 也是一条产生式 则把 加到FIRST X 中 37 d 若X VN 有产生式X Y1Y2 Yn Y1 Yi都是非终结符 对于任何j 1 j i 1 FIRST Yj 都含有 则把FIRST Yj 中的所有非 元素都加到FIRST X 中 FIRST Yi 的元素加入到FIRST X 特别地 若所有的FIRST Yj j 1 2 n 均含有 则把 FIRST Yj 中的所有非 元素都加到FRIST X 中 反复使用 a d 直到FIRST X 不再增大为止 38 FIRST A FIRST B b b a b b a a FIRST A FIRST D b a b c a c a c 例 文法G S 其产生式如下 求文法符号的FIRST集S AB bCA bB aDC AD bD aS c步骤如下 1 可产生空串的非终结符 A B S 2 计算FIRST集 39 例表达式文法的语法符号的FIRST集 FIRST F id FIRST T FIRST F id FIRST E FIRST T id FIRST E FIRST T FIRST FIRST FIRST FIRST FIRST id id 表达式文法为 E TE E TE T FT T FT F E id 40 一个符号串的FIRST集若 V X1X2 Xn 当X1不能 则置FIRST FIRST X1 若对任何j 1 j i 1 2 i n FIRST Xj 即Xi不能 Xj能 1 j i 1 i 1则FIRST FIRST Xj FIRST Xi j 1当所有FIRST Xj 1 j n 都含有 时 n则FIRST FIRST Xj j 1 41 FIRST AB FIRST A FIRST B b a FIRST bC b FIRST FIRST b b FIRST aD a FIRST AD FIRST A FIRST D b a c FIRST aS a FIRST c c 例 文法G S 其产生式如下 求文法符号的FIRST集S AB bCA bB aDC AD bD aS c 1 可产生空串的非终结符 A B S 2 计算FIRST集 步骤如下 42 计算过程如下 a 设S为开始符号 则 FOLLOW S b 若有产生式A B 则FIRST 加至FOLLOW B C 若 即 FIRST 可理解为A B 则FIRST 和FOLLOW A 加至FOLLOW B 三 FOLLOW集求法 从右向左看齐 难点 43 例 文法G S 的产生式如下 求非终结符的FOLLOW集S AB bCA bB aDC AD bD aS c FOLLOW D FIRST B FOLLOW S FIRST D FOLLOW S FOLLOW S FOLLOW B FOLLOW C a c 1 计算可产生空串的非终结符 A B S 2 计算FOLLOW集 步骤如下 44 例表达式文法的语法变量的FOLLOW集 FOLLOW E FOLLOW E FOLLOW E FOLLOW E FOLLOW T FIRST E FOLLOW E FOLLOW T FOLLOW T FOLLOW T FOLLOW F E TE E TE T FT T FT F E id 45 四 可选集SELECT 综合上述情况定义选择集合SELECT如下 给定上下文无关文法的产生式A A VN V 则SELECT A FIRST 则SELECT A FIRST FOLLOW A 本书采用SELECT A FIRST FOLLOW A 46 可产生空串的非终结符 A B SSELECT S AB FIRST AB FOLLOW S a b SELECT S bC b SELECT A FIRST FOLLOW A a c SELECT A b b SELECT B FIRST FOLLOW B SELECT B aD a SELECT C AD FIRST AD a b c SELECT C b b SELECT D aS a SELECT D c c 例 文法G S S AB bCA bB aDC AD bD aS c 47 五 LL 1 文法 定义5 4一个上下文无关文法G是LL 1 文法的充要条件是 对于G的每个非终结符号A的任何两个不同产生式A A 满足 SELECT A SELECT A 其中 不同时推导出 LL 1 文法的性质 LL 1 文法是无二义的LL 1 文法不含左递归非LL 1 语言是存在的存在一种算法 它能判定任一文法是否LL 1 文法不存在算法 能判定上下文无关语言能否由LL 1 文法产生 48 例 文法G S 其产生式如下 S AB bCA bB aDC AD bD aS c在求出的FIRST和FOLLOW集的基础上求SELECT集SELECT S AB a b SELECT S bC b SELECT A a c SELECT A b b SELECT B SELECT B aD a SELECT C AD a b c SELECT C b b SELECT D aS a SELECT D c c SELECT S AB SELECT S bC b SELECT C AD SELECT C b b 此文法不是LL 1 文法 49 5 5递归下降分析技术 前提LL 1 文法实现思想 识别程序由一组函数组成 每个函数对应于一个非终结符号 每一个函数的功能是 选择正确的右部 扫描完相应的字 在右部中有非终结符号时 调用该终结符号对应的函数来完成 50 产生式类型 1 或 运算 对于非终结符号U u1 u2 un处理的方法如下 U ch 当前符号 if ch可能是u1字的开头 处理u1的程序部分 elseif ch可能是u2字的开头 处理u2的程序部分 elseerror 但有某个右部的开头是非终结符号时 需要用LL K 方法判断什么时候使用这个右部 当存在空规则的时候 可以把error 替代为 return 这样的处理使发现错误的情况比较晚 约定 进入这个过程时 对于U的第一个符号已经被读到当前符号 离开这个程序的时候 下一个符号已经被读到当前符号 51 产生式类型 2 连接 运算 对于非终结符号u1 x1x2 xn的处理方法如下 处理x1的程序 处理x2的程序 处理xn的程序 如果右部为空 则不处理 52 说明 对于右部中的每个符号xi如果xi为终结符号 判断是否与向前看符号匹配 if x 向前看符号 NextChar 前进一个字符return else出错处理如果xi为非终结符号 直接调用相应的过程xi 说明 NextChar为前进一个字符函数 53 递归下降技术 实例 文法E E T TT T FF E i消左递归得到E TE E TE T FT T FT F E i 54 对应于改写后的文法中的每个非终结符号 都有一个函数 对于产生式E TE 用E1表示E E if 当前符号是T的开始符号 T E1 elseerror 55 对于产生式E TE 用E1表示E E1 if ch NextChar 前进一个字符T E1 elsereturn E TE 56 递归分析程序的主程序 假设识别符号对应的过程为Z 那么相应的主程序为 GetSymbol 首先需要读入一个符号 以满足约定 Z 57 递归分析程序的运行 栈底 E T 输入 i i i F 过程调用栈 T E a a E T F T F E T a F 调用 进入 返回 58 递归下降分析程序是一种适合手工编写分析程序的方式 优点 实现思想简单明了 程序结构和语法规则有直接的对应关系 因为每个过程表示一个非终结符号的处理 添加语义加工工作比较方便 需要书写程序的语言支持递归调用 如果递归调用机制是高效的 那么分析程序也是高效的 缺点 递归算法的实现效率低处理能力相对有限通用性差 难以自动生成 递归子程序法总结 1 编写文法 消除二义性 2 消除左递归 提取左因子 3 求FIRST集 FOLLOW集和SELECT集 4 检查是不是LL 1 文法若不是LL 1 说明文法的复杂性超过自顶向下方法的分析能力5 直接根据每个语法变量的产生式设计相应的程序 60 前提LL 1 文法1 基本思想根据文法G 构造一张分析表M 表中元素M A a 存放是被选择的产生式 正确分析情况 分析表项M A a A a 表示 面对非终结符号A和向前看符号a应选择产生式A a进行分析 是出错处理程序入口 分析出现错误 为简单起见 一般用空表示 整个分析是在分析表M的驱动下完成的 本节主要围绕LL 1 分析表展开讨论 5 6预测分析方法 61 2 非递归预测分析程序的模型 重点掌握 1 预测分析程序 2 先进后出栈 3 预测分析表 1 3 2 控制程序是依据分析表和分析栈联合控制输入字符串的识别和分析 它在任何时候都是依据当前分析栈的栈顶符号和当前输入字符来执行控制功能 对不同文法 控制程序是相同的 62 前提 此文法为LL 1 文法算法非递归预测分析表的构造分析表是一个二维数组M A a 其中A是非终结符号 a是终结符号或是符号 1 对文法G的每个产生式A 执行第2步 2 对每个终结符号a SELECT A 把A 加至M A a 中 M A a 内容为一条关于A的产生式 其中 a为VT或 3 把所有无定义的M A a 标上错误标记或用空白表示 3 非递归预测分析表的构造 63 例 文法G E 其产生式如下 E E T TT T F FF i E 1 消除左递归E TE E TE T FT T FT F i E 2 求FIRST和FOLLOW集可推导出空串的非终结符 E T i i i 64 SELECT E TE i SELECT E TE SELECT E SELECT T FT i SELECT T FT SELECT T SELECT F i i SELECT F E 此文法为LL 1 文法 65 TE TE TE FT FT FT E i 3 构造LL 1 分析表 SELECT E TE i SELECT E TE SELECT E SELECT T FT i SELECT T FT SELECT T SELECT F i i SELECT F E SELECT E TE i SELECT E TE SELECT E SELECT T FT i SELECT T FT SELECT T SELECT F i i SELECT F E 66 X VN S 进栈 当前输入符送a 上托栈顶符号放入X 若产生式为X X1X2 Xn按逆序即Xn X2X1入栈 出错 X X VT X a M X a 是产生式吗 出错 X a 读入下一个符号 结束 是 是 是 是 否 否 否 否 否 是 4 非递归预测分析程序的控制程序 初始格局 S 输入串 终止格局 67 1 E 2 3 T F 4 E TE T FT i F i i匹配 5 T 6 E 7 8 E T E TE 匹配 E T 9 T F T FT F i 10 E T i匹配 11 i 12 E T FT 匹配 13 14 15 16 E T F F i E T i匹配 E E T T E 17 接受 对输入串i i i 进行分析 E T i i i i i i i i i i i i i i i i i i i i i i i i i i i i E E T E T E E T T F i 68 i i i i i i i i i i i i 1 E E T 2 3 E T F 4 E TE T FT E T i F i i匹配 5 E T T 6 E 7 8 E T E TE 匹配 E T 出错 对输入串i i进行分析 预测分析法 状态矩阵法 总结 1 编写文法 消除二义性 2 消除左递归 提取左因子 3 求FIRST集 FOLLOW集和SELECT集 4 检查是不是LL 1 文法若不是LL 1 说明文法的复杂性超过自顶向下方法的分析能力5