《chap4-1自顶向下语法分析》由会员分享，可在线阅读，更多相关《chap4-1自顶向下语法分析（53页珍藏版）》请在金锄头文库上搜索。
1、2020 4 29 1 检查由扫描器输出的单词符号序列是否符合该语言的文法 句子 扫描器 分析器 语义处理 单词符号 分析树 源程序 分析器的输入 Token序列分析器的输出分析树出错处理分析方法自顶向下 递归下降 预测分析 自底向上 算符优先 LR分析器 第四章语法分析 2020 4 29 2 4 1自顶向下的分析方法 基本思想寻找输入符号串最左推导试图根据当前输入单词判断使用哪个产生式基本过程从根开始 按与最左推导相对应的顺序 构造输入符号串 Token 的分析树 2020 4 29 3 1 重要概念 推导 依据 最左 Left most 推导 最左分析左句型最左推导对应最右归约最右 Ri
2、ght most 推导 最右分析规范推导 规范句型 右句型 最右推导对应最左归约 规范归约 自顶向下语法分析要解决的问题是 2020 4 29 4 候选式的确定 给定文法S cAdA ab a 句子cad是该文法定义语言的句子SScAdcAdaba产生式 候选式 的选择 当要进行关于某个语法变量的推导时 希望能够根据当前符号确定候选式 2020 4 29 5 带回溯的自顶向下分析思想 给定文法G S 和输入串W 从S出发自顶向下构造语法树 若存在某条推导路径 使得S W 则W语法正确 若尝试所有推导路径 都无法得到S W 则W语法错误 不确定的自顶向下分析需作回溯 效率很低 2020 4 29
3、 6 2 确定的自顶向下分析思想 基本思想 每一步根据当前输入符号可唯一确定某条规则用于推导 由根向下构造语法树 构造最左推导 推导出的终结符是否与当前输入符匹配 2020 4 29 7 确定的自顶向下分析思想 例1 S pA 1 qB 2 A cAd 3 a 4 输入串 pccadd分析结论 语法正确且分析过程的每一步都唯一原因 本文法的非终结符 的候选都以终结符开头 且两两不同 p qA c a 2020 4 29 8 例2 S Ap 1 Bq 2 A a 3 cA 4 B b 5 dB 6 输入串 ccap分析结论 语法正确且分析过程的每一步都唯一原因 本文法的A和B的候选以终结符开头
4、且两两不同 A a cB b d 并且对于S FIRST p FIRST Bq a c b d 定义 FIRST a a a VT V 若 则规定 FRIST 2020 4 29 9 例3 S aA 1 d 2 A bAS 3 4 输入串 abd分析结论 W语法正确且分析过程的每一步都唯一原因 S a dA b FOLLOW A b a d 定义 FOLLOW A a S A 且a FRIST V V 2020 4 29 10 我们希望 从左到右扫描输入串 寻找它的一个最左推导对于G的每个非终结符A的任何两个不同的候选式A 1 FIRST FIRST 2 如果 则FISRT FOLLOW A
5、文法 是LL 1 的充要条件第一个L 从左到右扫描输入串第二个L 生成的是最左推导1 向前看一个输入符号 2020 4 29 11 3 LL 1 文法的判别 1 对于A Vn 计算First A 2 对于A Vn 计算Follow A 3 对于A 计算FIRST FIRST FIRST follow A 若 成立 2020 4 29 12 1 若 则 First A 2 若A B 则FIRST A FIRST A FIRST B 若A a 则FIRST A FIRST A a 3 若A B 及A a 且 则类似于步骤2处理 求FIRST A 的算法 2020 4 29 13 FIRST F i
6、d 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 例 2020 4 29 14 例 S A bCA bB aDC AD bD aS c NFirst N Sa b Ab Ba Ca b cDa c 2020 4 29 15 求FOLLOW A 的算法 对于所有非终结符 重复进行以下计算1 将 加入到FOLLOW S 为句子的结束符2 若A B 则FOLLOW B FOLLOW B FIRST 3 如果A B或
7、A B 且 A B 则FOLLOW B FOLLOW B FOLLOW A 2020 4 29 16 FOLLOW E FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW T FOLLOW F E TE E TE T FT T FT F E id 例 2020 4 29 17 NFollow N S Aa c B C D 例 S A bCA bB aDC AD bD aS c 2020 4 29 18 对于A 计算交集 S A bCA bB aDC AD bD aS c NFirst N Sa b Ab Ba Ca b cDa c Follow N a c F
8、irst AB First A First B b b a First bC b b a b b G 不是LL 1 文法 2020 4 29 19 4 非LL 1 文法到LL 1 文法的变换 LL 1 文法的性质 LL 1 文法是无二义的LL 1 文法不含左递归LL 1 文法不含公共左因子 2020 4 29 20 1 消除左递归 直接左递归A A 间接左递归A A 例 S AaA Sb无法根据左递归文法进行自顶向下的分析左递归的消除方法将A A 替换为A A 和A A 2020 4 29 21 例 表达式文法直接左递归的消除 E E T TT T F FF E id E TE E TE T
9、FT T FT F E id 2020 4 29 22 间接左递归的消除 S Ac cA Bb bB Sa a将B的定义代入A产生式得 A Sab ab b将A的定义代入S产生式得 S Sabc abc bc c消除直接左递归 S abcS bcS cS S abcS 删除 多余的 产生式 A Sab ab b和B Sa a结果 S abcS bcS cS S abcS 2020 4 29 23 消除左递归的一般方法 已知左递归产生式组A A 1 A 2 A n 1 2 m替换为产生式组A 1B 2B nBB 1B 2B nB 其中 B为新变量 相当于A 2020 4 29 24 将产生式 变
10、换为 BB 例 S ifCtS ifCtSeSC b提左因子得 S ifCtSAA eS C b 2 提取左因子 2020 4 29 25 左因子提取方法 将形如A 1 2 n 1 2 m的规则改写为A A 1 2 m和A 1 2 n 2020 4 29 26 注意 文法G S 中消除了左递归和公共左因子后并不能保证其一定变换为LL 1 文法 需进行判别后才能下结论 2020 4 29 27 G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F i 例 G E E E T TT T F FF i E G E 是否为LL 1 文法 2020 4 29
11、 28 G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F i 各非终结符的FIRST集合如下 FIRST E i FIRST E FIRST T i FIRST T FIRST F i 各非终结符的FOLLOW集合为 FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F 2020 4 29 29 G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a E TE FIRST TE FOLLOW E T FT FIRST FT FOLLOW T F E aFIRST
12、 E FIRST a a 所以G E 是LL 1 的 2020 4 29 30 习题 1 改写以下文法 消除左递归并判断改写后的文法是否LL 1 文法 M MaH HH b M M b2 判断以下文法是否LL 1 文法 求该文法中各非终结符的FIRST集和FOLLOW集 并构造预测分析表 a A baB b S bA aB Abb aA bBB bB 3 判断该文法是否LL 1 文法 如不是 请将其改写为LL 1 文法 a S A BA aA aB bB bb S i E E E S E S SC E E T TT T F FF E i 2020 4 29 31 确定的自顶向下分析方法 递归子
13、程序法预测分析方法 2020 4 29 32 4 1 2递归子程序法 方法 对于每一A Vn 构造一个子程序 设A 对 中各个符号X 若X Vt 则匹配当前输入符号a 判断 a 若X Vn 则转而调用 所对应的子程序 语法分析开始时 调用开始符号 对应的子程序 2020 4 29 33 递归子程序法 例 G E E TE E TE T FT T FT F E F i ProcedureE T E ProcedureT F T ProcedureE ifsym then advance T E ProcedureT ifsym then advance F T 2020 4 29 34 递归子程
14、序法 例 G E E TE E TE T FT T FT F E F i ProcedureF ifsym i thenadvanceelseifsym then advance E ifsym thenadvanceelseerror1 elseerror2 2020 4 29 35 递归子程序法 ProcedureF ifsym i thenadvanceelseifsym then advance E ifsym thenadvanceelseerror1 elseerror2 ProcedureE T E ProcedureT F T ProcedureE ifsym then adv
15、ance T E ProcedureT ifsym then advance F T i1 i2 i3的分析过程 2020 4 29 36 语法图和递归子程序法 例表达式文法的描述 T E E T E E T E 语法图的化简 2020 4 29 37 T T E 语法图的化简 2020 4 29 38 简化的语法图 T E id 2020 4 29 39 的子程序 E T E T procedureE beginT 的过程调用whilelookhead dobegin当前符号等于 时match 处理终结符 T 的过程调用endend lookhead 当前符号 例简单算术表达式的分析器 T
16、E 2020 4 29 40 的子程序 T F T F procedureT beginF 的过程调用whilelookhead thenbegin当前符号等于 时match 处理终结符 F 的递归调用endend 2020 4 29 41 的子程序 F E id procedureF beginiflookhead thenbegin当前符号等于 match 处理终结符 E 的递归调用match 处理终结符 endelseiflookhead idthenmatch id 处理终结符idelseerror出错处理end 2020 4 29 42 主程序 beginlookhead nexttoken 调词法分析程序E 的过程调用endprocedurematch t token beginiflookhead tthenlookhead nexttokenelseerror出错处理程序end 2020 4 29 43 4 1 3预测分析法 系统维持一个分析表和一个分析栈 根据当前扫描到的符号 选择当前语法变量 处于栈顶 的候选式进行推导 希望找到相应的输入符号串的最左推导 如图所示
