编译 第四章 自顶向下的分析

第四章自顶向下的分析 学习目标 掌握LL 1 文法的判别 LL 1 分析 预测分析法 递归子程序的构造方法理解First集合 Follow集合 LL 1 文法了解回溯分析 自顶向下分析的错误恢复 自顶向下分析的语法树的构造 自顶向下的分析 定义分析是从文法的开始符号出发 通过在最左推导中描述出各个步骤来分析记号串输入 分析树的构造 将文法的开始符号作为语法树的根 向下逐步建立语法树 使语法树的末端结点符号串正好是输入符号串 例如G S cAdA abA a S 推导 cabd S cAd 串 cabd 的自顶向下的分析是 自顶向下分析的关键 不成功 不成功的原因是选错产生式A a S 输入串 cabd 的另一个自顶向下分析是 因此自顶而下分析的主要问题是推导时所选择的产生式 假定要被代换的最左非终结符号是B 且B有n条产生式 B A1 A2 An 那么如何确定用哪个右部去替代B 自顶向下的分析程序有两类回溯分析程序一个非终结符有一个以上的产生式并且根据当前的输入符号 分析程序无法确定选择哪个产生式它会尝试分析其他可能的输入 当一种可能失败时就要求输入中备份任意数量的字符 例如 文法G S xAyA ab a串 xay 的自顶向下分析 预测分析程序分析程序试图利用一个或多个先行记号来预测输入串中的下一个构造预测分析方法分为两类递归下降分析法LL 1 分析 4 1预测分析方法4 2LL 1 文法的判别4 3非LL 1 文法到LL 1 文法的等价转换4 4递归下降分析算法进行自顶向下分析4 5LL 1 分析4 6自顶向下分析的错误恢复 4 1预测分析方法 1预测分析的条件2先行符号集合的定义3LL 1 文法的定义 1预测分析方法的条件 输入字符串的分析从文法的开始符号开始出发如果能根据当前的输入符号 单词符号 唯一地确定选用哪个产生式进行推导 则分析是确定的 预测分析的条件预测分析要求文法必须是LL 1 文法什么是LL 1 文法 它的定义依赖先行符号集合 开始符号集合和后跟符号集合 2先行符号集合的定义 开始符号集合定义文法G VN VT P S VN VT FIRST a VT a 如果 则 FIRST 直观上说文法符号串 的开始符号集是由 推导出的开头的终结符 包括 组成 例如G S S ApS BqA aA cAB bB dB FIRST Ap a c FIRST Bq b d FIRST a a FIRST cA c FIRST b b FIRST dB d 若非终结符A有一个以上的产生式 A 但是FIRST FIRST 则文法可进行确定的分析 即根据当前输入符号可以确定选择哪个产生式进行推导 后跟符号集合定义文法G VT VN S P A VN FOLLOW A a VT S Aa 若S A 则 FOLLOW A 用来作为输入串的结束符 直观上说 非终结符A的后跟符号集是由句型中紧跟A后的那些终结符 包括 组成 例如G3 S S aA dA bAS S S FOLLOW S S aA abAS abbASS abbASaA abbASdFOLLOW S a d S aA FOLLOW A S abAS abAaA a FOLLOW A abAd d FOLLOW A FOLLOW A a d 非终结符A有两个产生式 A bAS和A 让 x 表示当前输入符号如果x FIRST bAS b 则选择A bAS进行推导如果x FOLLOW A a d 则选择A 进行推导由于FIRST bAS FOLLOW A 可确定选择哪个产生式进行推导 3LL 1 文法的定义 LL 1 文法一个文法是LL 1 文法 则需要满足下面的条件 每一个产生式A 1 2 n对于所有i和j 1 i j n i j First i First j 对于每一个非终结符A 如果First A 中包含 则First A Follow A 例如G S S aASS bA bAA First aAS a First b b First bA b First First A b Follow A a b 因为First A Follow A b G S 不是一个LL 1 文法 当最左边将被替换的非终结符是A并且当前的输入符号是 b 时 分析不能确定该为A选择哪个产生式进行推导 A bAorA 4 2LL 1 文法的判别 LL 1 文法的判别分为四步 计算能推出 的非终结符集计算每一个产生式的右边串 的FIRST 集合计算每个非终结符A的FOLLOW A 集合按照LL 1 文法的定义识别 1计算能推出 的非终结符集 可空的当存在一个推导A 时 非终结符A称作是可空的 算法让S表示所有能推导出 的非终结符集合首先 S Aj Aj 是一个产生式 对每一个产生式p Ap X1 Xn 如果X1 Xn S 则S S Ap 重复第二步的循环 直至S收敛 不再变化 为止 例如G S S AB bCA b B aD C AD bD aS c 非终结符集S 能推出 的非终结符集为 A B S 2计算每个产生式右部符号串 的FIRST 集 为每个文法符号A A VT VN 计算First A 的算法计算符号串 的First 算法 为每个文法符号A A VT VN 计算First A 的算法 对于所有a VT则First a a 对于所有A VN 若A 则First A elseFirst A 对于每一个产生式A X1 Xj Xn First A First A SectionFirst X1 Xj Xn 重复3直到每个符号的FIRST集合都不再增大为止 SectionFirst X1 Xj Xn First X1 First X2 First Xj First Xj 1 Xj 1是产生式右部中第一个不能推出 的符号IfX1不是可空的 X1 则SectionFirst X1 Xj Xn First X1 IfX1 Xn都是可空的 全可推出 则SectionFirst X1 Xn First X1 First X2 First Xn G S S AB bCA b B aD C AD bD aS c 第三次 第二次 第一次 A B C D a b S 初值 已求出能推出 的非终结符集为 A B S b b a b ac a ac 计算符号串 X1X2 Xn的First 算法 若X1不是可空的 X1 则FIRST FIRST X1 若Xj 1 j n 是可空的 则FIRST FIRST X1 FIRST Xj FIRST Xj 1 若Xi 1 i n 都是可空的 则FIRST FIRST X1 FIRST Xn 例如G S S AB bCA b B aD C AD bD aS c 非终结符的开始符号集合为 First S a b First A b First B a First C a b c First D a c 产生式右边符号串的开始符号集 S ABFIRST AB FIRST A FIRST B a b S bCFIRST bC b A FIRST A bFIRST b b C ADFIRST AD FIRST A FIRST D b a c D aSFIRST aS a 3计算每一个非终结符A的FOLLOW A 1 S是开始符号 则Follow S 对于所有A VN 并且A S Follow A 2 对于每个产生式B A 考察产生式右边每一个非终极符A Follow A Follow A First 若 First 则Follow B 也属于Follow A 3 重复2 直至对所有A VN Follow A 收敛为止 因为S S 所以 FOLLOW S 若b FOLLOW B 则S Bb 由于B A and 因此S Bb A b Ab 即S Ab b FOLLOW A G S 1 S AB 2 S bC 3 A b 4 A 5 B aD 6 B 7 C AD 8 C b 9 D aS 10 D c 非终结符的开始符号集 First S a b First A b First B a First C a b c First D a c D C B a A S 第二次 第一次 初值 c First集合与Follow集合的比较 可能是First集合的元素 但绝不会出现在Follow集合中非终结符 终结符的符号串 非终结符的符号串都存在First集合 而Follow集合仅为非终结符而定义Follow集合的定义运算在产生式的 右边 而First集合的定义运算在产生式的 左边 4按照LL 1 文法的定义判别 LL 1 的定义 对于每个产生式A 1 2 n First i First j 对于所有的i和j 1 i j n i j对于每一个非终结符A 若First A 包含 则First A Follow A G S S AB bCA b B aD C AD bD aS c S AB bC First AB a b First bC b First AB First bC b C AD b First AD b a c First b b First AD First b b 该文法不是LL 1 文法 4 3非LL 1 文法到LL 1 文法的转换 非LL 1 文法如果一个文法有左公共因子或左递归 或都存在 则它不是一个LL 1 文法然而 一个文法没有左公因子和左递归 则也不一定是LL 1 文法 左公共因子左公共因子是两个或多个文法规则选择共享一个公共的前缀串 正如规则A r由于First First r 因此它不是一个LL 1 文法 左递归一个文法是左递归的 如果它的产生式有下面的形式 A A A B B A a 被称为直接左递归 左递归仅发生在一单个非终结符的产生式中 b 被称为间接左递归 其中A B A 即A A 以直接左递归为例 若有产生式 A A A 其中 和 为任意符号串由于First A First 因此这不是一个LL 1 文法 非LL 1 文法到LL 1 文法的等价转换消除左递归提取左因子注意 变换后的文法不一定是LL 1 文法 文法不含左递归和左因子只是LL 1 文法的必要条件 1消除左递归 消除直接左递归简单形式A A 改写为A A A A 一般形式A A 1 A 2 A m 1 2 n改写为 A 1A 2A nA A 1A 2A mA 2提取左因子 简单形式A r改写为A r 让A 表示 r 得到A A A r 必须是与右边共享的最长串 一般情况A 1 2 n 改写为 A A A 1 2 n 例如G1 S aSb aS 提取左因子 S aS b 引进新的非终结符得 S aSS S b 4 4递归下降分析算法进行自顶向下分析 递归下降的主要思想将每一个非终结符A的文法规则看作将识别A的一个过程定义 A的文法结构右边指出这个过程的代码结构终结符对应输入的匹配非终结符对应调用其他过程选择对应代码中的替代情况 case或if语句 我们将讨论 构造递归下降分析器的基本方法一个更简单的方法是根据EBNF 构造递归下降分析算法的基本方法确定文法是否为LL 1 文法 例如文法GE E T TT T F FF E i 1 消除左递归后 我们得到文法G E TE E TE T FT F E i 2 First和Follow集合 E TE E TE T FT T FT F E iG 是LL 1 文法 2为G 构造递归下降分析器 当文法是LL 1 文法时 我们能为它构造递归下降分析器分析器包括一个主程序和一组递归程序 每个对应文法的一个非终结符 一个非终结符的过程构造用到的一些子程序 Match过程是用它的参数匹配当前的下一个记号 如果成功则前移 如果失败就表明错误Error过程会打印一个出错信息并退出用到的一些变量 TOKEN变量表示在输入中保存的当前下一个记号 若非终结符U的产生式是U x1 x2 xn 和x1 xn 则过程U的代码是 ifTOKENinFirst x1 thenp x1elseifTOKENinFirst x2 thenp x2else ifTOKENinFirst xn thenp xnelseERROR 若U的一个产生式是U 则修改代码ifTOKENinFirst xn thenp xnelseERROR为ifTOKENinFirst xn thenp xnelseifTOKENnotinFollow U thenERRORp x的代码是 其中x y1y2 ynbeginp y1 p y2 p ynend如果yi VN则p yi调用过程yi 否则 如果yi VT则p yi是match yi 1 programMAIN main beginGETNEXT TOKEN E callE ifTOKEN thenERRORend 例子 G 的递归下降分析程序 E TE E TE T FT T FT F E i 2 procedureE E TE beginT callT E callE end 3 procedureT T FT beginF callF T callT end 4 procedureE E TE beginifTOKEN then E TE beginmatch T callT E callE endelse E ifTOKEN andTOKEN thenERRORend 5 procedureT T FT beginifTOKEN then T FT beginmatch F callF T callT endelse T ifTOKEN andTOKEN andTOKEN thenERRORend 6 procedureF F E i beginifTOKEN then F E beginmatch E callE match endelse F i ifTOKEN i thenmatch i elseerror end 注意 提取左因子和消除左递归修改了文法 这些改变引起了分析程序的复杂化提取左因子和消除左递归能模糊语言结构的语义 例如 它们模糊了数学表达式中的结合性 E TE E TE T FT T FT F E i 例如 3 4 5 的分析树是 3 4 5 的语法树是 使用EBNF的更简单的方法EBNF的表示方法 扩展的BNF 用来表示重复例如 A A 可写为A 用来括起选项例如 if stmt if exp stmt if exp stmtelsestmt可写为 if stmt if exp stmt elsestmt 例子GE E T TT T F FF E i 将G改写为EBNF 记为G E T T T F F F E i 构造G 的递归下降分析算法 被翻译成代码的一个测试 被翻译成一个while循环 if stmt if exp stmt elsestmt 能被翻译为过程 ProcedureifStmt beginmatch if match Exp match Stmt iftoken else thenmatch else Stmt endif endifStmt E T T 1 procedureE beginT whiletoken domatch T endwhile end T F F 2 procedureT beginF whiletoken domatch F endwhile end 用到的子程序函数MakeOpNode接受作为参数的运算符记号并返回新建的语法树节点 leftChild t p或rightChild t p指出将一个语法树p的赋值作为语法树t的一个左子树或右子树 构造语法树的动作 functionE syntaxTree E T T vartemp newtemp syntaxTree begintemp T whiletoken donewtemp makeOpNode token match leftChild newtemp temp rightChild newtemp T temp newtemp endwhile returntemp end functionifStmt syntaxTree if stmt if exp stmt elsestmt vartemp syntaxTree beginmatch if match temp makeStmtNode if testChild temp Exp match thenChild temp Stmt iftoken else thenmatch else elseChild temp Stmt elseelseChild temp nil endif end 注意 将EBNF中的文法规则转变成代码的办法十分有效但是将原先在BNF中编写的文法转变成EBNF格式可能有些困难 递归下降分析算法的特点优点 功能强大灵活 允许编程者调整动作的安排适用于手工生成的分析器缺点 必须注意代码中的动作安排递归调用多 速度慢 占用空间多 4 5LL 1 分析 LL 1 文法的含义第一个L表示从左到右处理输入串第二个L表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式进行推导 类似地LL k 文法需要向前看K个符号才可以确定选用哪个产生式 4 5 1LL 1 分析的基本方法 LL 1 分析使用显式栈而不是递归调用来完成分析栈中保存分析中待匹配的信号分析程序是从开始符号放在栈中开始的成功分析后 栈和输入都为空 成功的LL 1 分析的一般示意法是 用来标记栈的底部和输入串的结束 例如S S S 串 的LL 1 分析为 6 5 4 3 match 2 S S S 1 分析程序的动作 输入 分析栈 解释 LL 1 分析程序parserparsesbyreplacinganonterminalonthetopofthestackbyoneofit schoiceinthegrammarrule两个基本的分析动作 Generate 应用文法的产生式A 将栈顶的非终结符A替换为串 反序入栈 Match 栈顶记号与下个输入记号匹配 出栈并读取下一个输入记号 4 5 LL 1 分析表 功能表示分析过程中 非终结符该选择哪条产生式进行推导 例如 LL 1 分析表由非终结符和终结符标记的二维表M N t 是分析过程中 针对当前的输入记号t 终结符或 N选择进行推导的产生式 若构造后 M N t 为空 则表示在分析中可能会发生的潜在的错误 分析表的构造为每个非终结符A和产生式选择A 重复下面两步 对于在First 中的每个记号 a 在M A a 的入口增加A 若 在First 中 对于在Follow A 中德每个元素 a 记号或 将A 加入到M A a 例如 数学表达式的文法E E T TT T F FF E i 1 消除左递归后的文法G E TE E TE T FT T FT F E i 2 非终结符的First集合和Follow集合 E TE E TE T FT T FT F E i F T T E E i 3 构造分析表 LL 1 文法如果与文法相关的LL 1 分析表入口最多只有一个产生式 则这个文法是LL 1 文法 4 5 3LL 1 分析算法 串 i i i 的分析过程 7 6 5 4 3 2 1 Action Input Stack Step 8 13 14 15 16 17 12 11 10 9 4 6自顶向下分析的错误校正 分析程序能判断出一个程序在语句构成上是否正确分析程序对于语法错误的反应通常是编译器使用中的主要问题 一般的语法错误开始和后跟符号错误程序 表达式及语句中开始和后跟符号例如 TINY语言 标识符和常数错误例如 const var procedure 后面不是标识符括号匹配错误例如begin end if then不匹配符号错误例如 赋值语句中的符号不是 错误处理给出有意义的错误信息选择合适的位置恢复分析 分析程序应该总是能分析尽可能多的代码 目的是在一次翻译中找到尽可能多的真实错误 错误处理的分类错误恢复 当错误反生后 分析程序能从一个合适的位置恢复分析错误修复 分析程序尝试从一个给定的错误程序中推导出一个正确的程序 4 6 1递归下降分析器的错误恢复 应急方式在复杂情况下 错误处理器可能要试图在大量的记号中找到一个恢复分析的位置 应急模式的基本机制为每个递归过程提供一