4-第四章_自上而下语法分析.ppt

第4章自上而下语法分析 4 1引言4 2LL 1 分析法4 3递归下降分析程序4 4预测分析程序4 5构造预测分析表4 6LL 1 分析中的错误处理 4 1引言 1 任务 给定一个上下文无关文法 判定一个单词符号串能否构成该文法的一个合法的语法单位 句子 即 给定一个串 判定 是否是句子 自上而下语法分析 从树根开始构造语法树 即寻找推导序列S 因为推导过程中可以参考当前输入符号 所以一般采用最左推导 E T 语法树 FT FT FT aT aF aa 例 G E E TE TT FT FF F a输入串 aa最左推导 递归下降分析 采用程序语言的递归功能 为每一个非终结符写一个分析子程序 预测分析 分析表 栈 分析算法 预测分析法 LL 1 分析 自下向上 递归下降分析法 无回溯 语法分析 带回溯 自上而下 2 语法分析程序 左递归 若存在形如 PP 的推导 称文法是左递归的 左递归文法中 若存在形如 P P 的产生式 称此产生式是左递归的 称此文法是直接左递归的 否则称文法是间接左递归的 3 自上而下语法分析的主要问题 例 G1 E E E T TT T F FF E i 有产生式 E E T G1是直接左递归文法 G2 S S Qc cQ Rb bR Sa a没有左递归产生式 但有 S Qc Rbc Sabc G2 S 是间接左递归文法 例 G E E E T TT T F FF E i输入串 i i iE E T T T F T i T 回溯 对左递归文法 分析过程会出现无限循环 自上而下语法分析要求 文法不能是左递归的 E T T F T F F T i F T i i T i E T T T F T F F F F F i F F i i F i i i 例 G S S xAyA 输入串 x yS xAy x y发现错误 回溯 x y 回溯 若推导时发现错误 可后退若干步 回到某一个中间状态 重新选择其他侯选式 为了回溯 必须纪录当时推导所作的选择 以及每一步有多项选择时的状态 代价大 可能要将所有可能都试一遍 效率低 只讨论不带回溯的自上而下语法分析法 因此 要检查文法是否符合此要求符合要求 LL 1 文法不符合要求 改造文法 若还不行 重写文法 例 G S S xAyA G S S xAyA BB 输入串 x yS xAy x By x y 提取公共左因子 例 G E E E T TT T F FF E i 输入串 i i iE TE FT E iT E i FT E i iT E i i FT E i i iT E i i iE i i i G E E TE E TE T FT T FT F E i 消除左递归 4 2LL 1 分析法 LL 1 分析法的含义 LL 1 自上而下分析是从左向右扫描输入串 LL 1 分析过程中将采用最左推导 LL 1 只需查看一个 当前 符号便可决定如何推导 即选择哪个产生式进行推导 的语法分析法 LL 1 文法 可采用LL 1 分析法进行分析的文法 LL K 文法 可采用LL K 分析法 需向前查看K个符号才可确定选用哪个产生式 进行分析的文法 1 消除左递归 消除直接左递归若有产生式 A A 且 A VN V 所能产生的语言L n n 0 改成等价形式 A A A A 一般方法 A A 1 A 2 A m 1 2 n其中 i j不以A开头改为 A 1A 2A nA A 1A 2A mA 例 G E E E T TT T F FF E i G E E TE E TE T FT T FT F E i 例 G A A Axt Ayy ac b q G A A acA bA qA A xtA yyA 输入串 acxtA acA acxtA acxt 消除间接左递归通过替换 将间接左递归文法变为直接左递归文法 消除直接左递归 例 G S S Qc cQ Rb bR Sa aR的产生式代入Q Q Sab ab bQ的产生式代入S S Sabc abc bc c得G1 S S Sabc abc bc cQ Rb bR Sa a 消除其中关于S的直接左递归 得G2 S S abcS bcS cS S abcS Q Rb bR Sa a Q R是不可达非终结符 不出现在句型中的非终结符 删去 G3 S S abcS bcS cS S abcS 例 G S S Qc cQ Rb bR Sa aS代入R R Qca ca aR代入Q Q Qcab cab ab b得G1 S S Qc cQ Qcab cab ab bR Sa a 消除间接左递归时 代入非终结符的顺序不同 产生的文法可能不同 但是是等价的 消除G1 S 关于Q的直接左递归 得G2 S S Qc cQ cabQ abQ bQ Q cabQ R Sa a R是不可达非终结符 删去 得 G3 S S Qc cQ cabQ abQ bQ Q cabQ 例 输入串cabc 2 提取左公共因子 A 1 2 n即 有公共左因子 推导至A时 不仅需要关心当前输入符号 的首符 还要关心 之后是什么 否则可能要回溯变换为 A A A 1 2 n 例 S ifEthenSelseS ifEthenS变换为 S ifEthenSS S elseS 例 G A A V E 赋值语句 着重左部 V i elist i 公共左因子elist elist i E 直接左递归E i 解 A V EV iV 提取公共左因子V elist 输入串 i i i iA V E iV E i elist E i Eelist E i ielist E i i ielist E i i i E i i i i elist Eelist 消除左递归elist ielist E i 是句子 某些情况下 无左递归 无公共左因子 但分析句子时 仍有困难 例1 G S S Ax ByA yB x输入串 xyS 难以确定S选择哪个候选式例2 G A A Ba dB abc 输入串 aS Ba abca 回溯 a 对VT a a FIRST a a FIRST x x FIRST y y 对VN A y FIRST A y B x FIRST B x S Ax yx S By xy FIRST S y x 例 G S S Ax ByA yB x则 VN S A B VT x y 3 定义集合 VT FIRST x x FIRST y y VN FIRST A y FIRST B x FIRST S y x VT VN Ax yx FIRST Ax y By xy FIRST By x 输入串 yxS Ax yx 例 G S S Ax ByA yB x则 VN S A B VT x y FIRST a a a VT V 若 则 FIRST 3 定义集合 文法G S A VN 随符集FOLLOW定义为 FOLLOW A a S Aa a VT 若S A 则 FOLLOW A FOLLOW A 是所有句型中出现在A之后的终结符 或 S S FOLLOW S 例 G A A Ba dB abc A A FOLLOW A A Ba FOLLOW B a 定义 一个上下文无关文法是LL 1 文法的充要条件是 1 文法中每个非终结符A的候选式的终结首符集两两不相交 即 若 A 1 2 n则 FIRST i FIRST j 1 i j n i j2 对于文法中每个非终结符A A 1 2 n若 FIRST i 1 i n则 FIRST A FOLLOW A 4 判定文法是否为LL 1 的充分必要条件 5 LL 1 语法分析方法 若当前要匹配的非终结符为A 当前输入符号为a A的产生式定义 A 1 2 n若 a FIRST i 则用 i替换A 若 a不属于任何一个候选式的终结首符集 则 若 某个FIRST i 且a FOLLOW A 则让A与 匹配 否则 报 语法错误 说明 通过FIRST FOLLOW集合 作上述检查比较麻烦 后面引入 预测分析表 LL 1 分析表 方便此工作 例 G S S At BA y B xCtC z FIRST S y t x FIRST A y FIRST B x FIRST C z FIRST At y t FIRST xCt x FOLLOW S FOLLOW A t FOLLOW B FOLLOW C t 判定LL 1 FIRST At FIRST B FIRST y FIRST FIRST z FIRST A FIRST A FOLLOW A C FIRST C FOLLOW C 文法是LL 1 的 输入串 tS Att FIRST At t t不属于First y First 但A 且t FL A 输入串 xytS Bx FIRST B xCt y不属于First z First C 但y不属于FL C 4 3递归下降分析程序 1 工作原理 对文法中的每一个非终结符A 编写一个递归子程序 根据A的候选式来编写 若候选式中当前符号为终结符a 则检查输入串 若当前输入符号亦为a 则接受此符号 读入下一个输入符号 否则报错 若候选式中当前符号为非终结符P 则调用关于P的分析子程序 这一组子程序 称为 递归下降分析器 语法分析主程序 调用文法开始符号S的子程序 S的子程序执行完 则分析正常结束 若分析过程中发现错误 报 语法错 递归下降语法分析器的性能评价优点 很方便的构造语法分析程序 限制 编写 编译程序的语言 必须有递归功能 且递归的内部实现效率较低 速度慢 占用空间多 2 辅助内容 SYM 变量 存放输入串中的当前单词符号 词法分析的结果 ADVANCE 过程 接受当前符号 并从输入串中读入一个新的符号 放入SYM ERROR 过程 错误处理子程序 例 S E ProcedureSBeginIfSYM ThenBeginADVANCE E IFSYM ThenADVANCEElseERROREndElseERROREnd 3 编写递归下降分析程序 SYM 存放输入串中的当前单词符号 ADVANCE 接受当前符号 并从输入串中读入一个新符号放入SYM ERROR 错误处理程序 例 E TE E TE ProcedureEBeginT E End ProcedureE BeginIfSYM ThenBeginADVANCE T E EndEnd SYM 存放输入串中的当前单词符号 ADVANCE 接受当前符号 并从输入串中读入一个新符号放入SYM ERROR 错误处理程序 例 G S 递归下降语法分析程序 S E E TE E TE T FT T FT F E i ProcedureEBeginT E End ProcedureE BeginIfSYM ThenBeginADVANCE T E EndEnd ProcedureSBeginIfSYM ThenBeginADVANCE E IFSYM ThenADVANCEElseERROREndElseREEOREnd ProcedureTBeginF T End ProcedureT beginIfSYM ThenBeginADVANCE F T endEnd ProcedureFBeginIfSYM i ThenADVANCEElseIfSYM ThenBeginADVANCE E IfSYM ThenADVANCEElseERROREndElseERROREnd 这一组程序统称为 递归下降分析器 例 G S S E E TE E TE T FT T FT F E i 4 递归下降分析过程 例 输入串 i i 输入串 i i 续 S结束 输入串为空 分析结束 是句子 5 扩充的BNF范式及相应的递归下降程序 增加元符号 原来已经有 a 表示a可重复0 n次 a 表示a的出现可有可无 例 G S S E E E T TT T F FF E i G S S E E T T T F F F E i G S S E E T T T F F F E i S F的产生式不变 与前面的递归下降程序相同 ProcedureEBeginT WhileSYM doBeginADVANCE T End End 递归下降分析程序 ProcedureTBeginF WhileSYM doBeginADVANCE F End End 6 细化的递归下降程序 做法 用First Follow集合细化递归下降程序 优点 改进后的递归下降程序执行效率高 某些文法必须使用细化的递归下降程序 普通 ProcedureABegin End 细化 ProcedureABeginIfSYMINFirst then ElseERROREnd 细化方式一 若A 引入FIRST集进行检查 细化方式二 A 1 2 n且 FIRST A 检查a FOLLOW A 若不属于 则报错 ProcedureABeginIfSYMINFirst 1 then 1 ElseIfSYMINFirst n then nEnd 普通递归下降程序 细化 ProcedureABeginIfSYMINFirst 1 then 1 ElseIfSYMINFirst n then nElseIfsymINFollow A ThenElseERROREnd 例 G S S E E TE E TE T FT T FT F E i ProcedureEBeginIfSYM i ORSYM ThenBeginT E EndElseERROREnd ProcedureEBeginT E End 细化方式1 E TE ProcedureE BeginIfSYM ThenBeginADVANCE T E EndEnd ProcedureE BeginIfSYM ThenBeginADVANCE T E EndElseIfsymINFollow E ThenElseERROREnd 等价 细化方式2 Ifsym orsym ThenElseERROR Ifsym andsym ThenERROR 输入串 ii ProcedureEBeginT E End ProcedureFBeginIfSYM i ThenADVANCEElseIfSYM ThenBegin EndElseERROREnd ProcedureTBeginF T End 执行 S E T F报错 ProcedureEBeginIfSYM i ORSYM ThenBeginT E EndElseERROREnd 执行 S E报错 运行效率高 细化方式 普通递归程序 4 4预测分析程序 预测分析表 栈 标准分析算法进行语法分析 1 预测分析表 LL 1 分析表 矩阵M A a 其中 A VN a VT或为结束符 M A a 一条产生式 表示 当前要推导的非终结符A 遇到输入符号为a时 应选用的产生式 M A a 出错标志 空 则A不该遇到输入符号a 2 分析算法 栈中放入 及文法开始符号S 设栈顶符号为X 当前输入符号为a 重复以下工作 若X a 分析结束 识别出句子 若X VT 且X a 则 将X出栈 输入符号前移 接收一个符号 若X VT 且X a 出错处理 若X VN 且M X a X X1X2 Xk 则 将X出栈 产生式右部反序入栈 入栈顺序为 Xk X2X1 若X VN 且M X a 为报错标识 出错处理 例 输入串 i i 例 输入串 i i 4 5构造预测分析表 First a a VTFirst a a 特别 First 1 计算FIRST集 FIRST a a a VT V 若 则 FIRST 分三步计算First a a VTFirst X X VNFirst VN VT 符号串 FIRST X X VN若有 X a a VT 则 a FIRST X 若有 X 则 FIRST X 若有 X Y 且Y VN 则 FIRST X FIRST X FIRST Y 若有 X Y1Y2 Yi 1Yi YK Yj VN FIRST Yj 1 j i 1则 FIRST X FIRST X FIRST Yi 若有 X Y1Y2 YK Yj VN FIRST Yj 1 j k则 FIRST X FIRST X 重复以上步骤 直至每个FIRST集不再增大为止 G A A BCD iB i C i D i VT i VN A B C D a VTFirst i i First First First First X VNFirst B First C First D First A First i First B First C First D i FIRST VN VT 只需计算某些 1 是产生式的候选式 2 是产生式的候选式中 某一VN之后的串 设 X1X2 XNFIRST FIRST X1 若 FIRST Xj 1 j i 1则 FIRST FIRST FIRST Xi 若 FIRST Xj 1 j N则 FIRST FIRST G A A BCD iB i C i D i a VT X VN VN VT First BCD First B First C First D First CD First C First D First i First i First i First D First i First 已知 2 计算FOLLOW集 定义 G S A VNFOLLOW A a S Aa a VT 求法 FOLLOW S S为文法的开始符号 若有产生式A B 则 FOLLOW B FOLLOW B FIRST 若有产生式A B 或A B 且 FIRST FOLLOW B FOLLOW B FOLLOW A 重复以上步骤 直至每个FOLLOW集合不再增大为止 G A A BCD iB i C i D i X VN V FOLLOW S 若A B FL B FL B First A BCDA BCD 若A B 或A B 且 First FL B FL B FL A A BCDA BCDA BCD 3 构造预测分析表 基本思想设 栈顶符号为A 当前输入符号为a 若A 是一个产生式 且a First 那么选择 取代A匹配成功的希望最大 故 M A a 元素为 A 若A 且 First a Follow A 则栈顶的A应被 匹配 此时输入符号不前进 让A的随符与输入符号进行匹配 这样输入串匹配成功的可能最大 故M A a 元素为A 构造算法对文法中的每一条产生式A 执行 对 a First 在M A a 中加入A 若 First 对每个a Follow A 在M A a 中加入A 把所有无定义的M A a 都填上 出错标志 说明 用此算法可以为任意文法G构造其分析表M 若M不包含有多重入口 也称 重定义项 即 某个表项中填有一个以上的产生式 则文法是LL 1 文法 对非LL 1 文法 如 二义文法 或没有消除左递归和提取左因子的文法 构造出的M包含有多重入口 G A A BCD iB i C i D i 没有多重入口 是LL 1 文法 输入串 i i A BCD CD iD i i 例 判断文法G S 是否为LL 1 文法 S ifCthenSelseS ifCthenS otherC b 为方便描述 更名 令 if ithen telse eother a文法简化为G1 S S iCtSeS iCtS aC b 改造文法 提取公共左因子 将文法改写成 G2 S S iCtSS aS eS C b 求首符集和随符集 G2 S S iCtSS aS eS C b 判定方法1 根据定义 First iCtSS First a i a First eS First e 对 S First S Follow S e e e 此文法不是LL 1 文法 G2 S S iCtSS aS eS C b 判定方法2 构造预测分析表 其中M S e 是二重的 此文法不是LL 1 文法 如果令M S e 只含S eS 则意味着坚持把else和最近的then相结合 此时 是LL 1 文法 例 高级语言控制语句的递归下降分析程序 G2 S S iCtSS aS eS C b 预测分析表 else和最近的then相结合 其中 if ithen telse eother a ProcedureCBeginIfSYM b ThenADVANCEElseERROREnd 细化的递归下降程序 ProcedureS BeginIfSYM else ThenBeginADVANCE SEndElseIfsym ThenERROREnd ProcedureSBeginIfSYM if ThenBeginADVANCE C IfSYM then ThenBeginADVANCE S S EndElseERRORENDELSEIfsym a ThenADVANCEElseERROREnd G2 S S iCtSS aS eS C b if ithen telse eother a 4 6LL 1 分析中的错误处理 在编译过程中系统发现的错误主要有两类 语法错误 语义错误语法错误 指语法结构错误 主要有 1 错误种类 预测分析算法 出错情况 栈中放入 及文法开始符号S 设栈顶符号为X 当前输入符号为a 重复以下工作 若 X VT 且X a 分析结束 识别出句子 若 X VT 且X a 将X出栈 输入符号前移 接收一个符号 若 X VT 且X a 出错处理 若X VN 且M X a X X1X2 Xk 则 将X出栈 产生式右部反序入栈 入栈顺序为 Xk X2X1 若X VN 且M X a 为报错标识 出错处理 2 发现错误的时机 出错情况 设 栈顶符号为X 当前输入符号为aX VT 但 X aX VN 但 M X a 中为空但同一个错误形式 可以被理解成不同的错误原因 例 G E E TE E TE T FT T FT F