编译原理自顶向下语法分析方法.ppt

第四章自顶向下语法分析方法 学习目标 掌握 LL 1 文法的判别 预测分析法 递归子程序的构造方法理解 LL 1 文法了解 不确定的自顶向下分析 语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子 自顶向下基本思想 从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子 分类 回顾 自上而下的分析方法 定义 从文法的开始符号出发 反复使用文法的产生式 寻找与输入符号串匹配的推导 语法树的构造 将文法的开始符号作为语法树的根 向下逐步建立语法树 使语法树的末端结点符号串正好是输入符号串 自上而下分析的主要问题选定产生式 例文法G S cAdA abA a识别输入串w cabd是否为该文法的句子 S cabd S cAd 回顾 自上而下的分析方法 S 成功 不成功 cad S cAd 4 1确定的自顶向下分析思想4 2LL 1 文法的判别4 3某些非LL 1 文法到LL 1 文法的等价变换4 4不确定的自顶向下分析思想4 5确定的自顶向下分析方法 本章内容 4 1确定的自顶向下分析思想 1确定分析的条件2开始符号集FIRST 的定义3后跟符号集FOLLOW A 的定义4选择集合SELECT A 的定义5LL 1 文法的定义 1 确定分析的条件 从文法的开始符出发 如能根据当前的输入符号 单词符号 唯一地确定选用哪个产生式进行推导 则分析是确定的 例1设有文法G1 S S pA qBA cAd aB dB b若输入串W pccadd 自顶向下的推导过程为 S S pA pcAd pccAdd pccadd G1 S 有如下特点 1 每个产生式的右部由终结符开头 2 同一非终结符的不同产生式的右部由不同的终结符开头 对于这种文法 在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导 即分析过程是确定的 例2 设有文法G2 S 为 S Ap BqA a cAB b dB S ccap S cAp ccAp Ap 该例说明 当 1 产生式右部以终结符或非终结符开头 无空产生式 2 同一非终结符的不同产生式的右部由不同的符号开头 若输入串W ccap 自顶向下的推导过程为 对于这种文法 在推导过程选用哪个产生式不直观 关键是判断产生式右部推出的开始符号 集 分析过程可能是确定的 例3 设有文法G3 S S aA dA bAS 若输入串W abd 自顶向下的推导过程为 S abd S abAS abS 文法的特点 包含空产生式 aA 对于空产生式左部的非终结符 关键是判断该非终结符的后跟符号 集 分析过程可能是确定的 要进行确定的自顶向下的分析 文法要满足一定的限制 即文法是LL 1 文法先研究三个定义开始符号集FIRST后跟符号集FOLLOW选择集合SELECT 2 开始符号集FIRST 的定义 定义 设G VN VT P S 是上下文无关文法 VN VN VT FIRST a a VT且 a 若 则规定 FIRST 直观上说文法符号串 的开始符号集是由 推导出的所有的终结符开头和可能的 组成 例文法G2 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 结论一针对无空产生式的文法G 同一非终结符的任两个产生式的右部串的First集无交集 即可进行确定的自顶向下分析 3 后跟符号集FOLLOW A 的定义 定义设G VT VN P S 是上下文无关文法 B xAy A B VNx y VN VT FOLLOW A a S Aa a VT 若有S A 则规定 FOLLOW A 注 输入串 做为输入串的结束符 直观上说 非终结符A的后跟符号集是由句型中紧跟A后的那些终结符 包括 组成 例 文法G3 S S aA dA bAS 由S S得 FOLLOW S 由S aA abAS abbASS abbASaA得a FOLLOW S abbASd得d FOLLOW S FOLLOW S a d 由S aA得 FOLLOW A 由S abAS abAaA得a FOLLOW A abAd得d FOLLOW A FOLLOW A a d FOLLOW A FOLLOW S 解释当A面对应输入符a 在自顶向下的分析中应选择这样的产生式A i i可导出空串 进行推导 若a First i 则A i可选因 i可能导出空串 A自动获得匹配 输入符a有可能与A后的一个符号匹配 故当a Follow A 时 产生式A i亦可选 结论一针对无空产生式的文法G 同一非终结符的任两个产生式的右部串的First集无交集 即可进行确定的自顶向下分析 结论二 例 文法G3 S S aA dA bAS S aA S d A bAS A First aA a First d d First bAS b First Follow A a d a d a d 回顾 开始符号集FIRST 的定义 定义 设G VN VT P S 是上下文无关文法 A A VN VN VT FIRST a a VT且 a 若 则规定 FIRST 直观上说文法符号串 的开始符号集是由 推导出的所有的终结符开头和可能的 组成 回顾 后跟符号集FOLLOW A 的定义 定义设G VT VN P S 是上下文无关文法 B xAy A B VNx y VN VT FOLLOW A a S Aa a VT 若有S A 则规定 FOLLOW A 注 输入串 做为输入串的结束符 直观上说 非终结符A的后跟符号集是由句型中紧跟A后的那些终结符 包括 组成 4 选择集合SELECT A 的定义 定义对给定的上下文无关文法的产生式A A VN V 若 则SELECT A FIRST 若 则SELECT A FIRST FOLLOW A 解释A的产生式A 1 2 3 A面对应输入符a 在自顶向下的分析中 对于A i且 i 若a First i 则A i可选对于A j且 j 若a First j Follow A 则A j可选 例 G3 S S aAS dA bASA SELECT S aA FIRST aA a SELECT S d FIRST d d SELECT A bAS FIRST bAS b SELECT A FIRST FOLLOW A a d 若 则SELECT A FIRST 若 则SELECT A FIRST FOLLOW A 结论三同一非终结符的不同产生式A 与A 若SELECT A SELECT A 则一定可以进行确定的自顶向下分析 5 LL 1 文法的定义 定义 上下文无关文法为LL 1 文法的充分必要条件是 对每个非终结符A的两个不同产生式A 与A 满足SELECT A SELECT A LL 1 文法的含义是 第一个L 从左到右扫描输入串第二个L 分析过程用最左推导 1 表明只需向前看1个输入符号便可以决定选哪个产生式进行推导 类似地 LL k 文法则需要向前看k个输入符号才可以确定选用哪个产生式 例有文法G S 为 S aASS bA bAA SELECT S aAS a SELECT S b b SELECT A bA b SELECT A a b 由于SELECT A bA SELECT A b 所以文法G S 不是LL 1 文法 当A遇输入符b时 不能确定选A bA还是A 去推导 4 2LL 1 文法的判别 要判别一个上下文无关文法是否是LL 1 文法分为五步 1 求能推出 的非终结符集2 计算每个产生式右部 的FIRST 集3 计算每个非终结符A的FOLLOW A 集4 计算每个产生式A 的SELECT A 集5 按LL 1 文法的定义判别 1 求出能推出 的非终结符集 算法描述 用T表示能推出 的非终结符集令T Aj Aj 产生式集 对于产生式Ap A1 An若A1 An T 则T T Ap 重复 直至T收敛 不再变化 为止 例G S S AB bCA b B aD C AD bD aS c 非终结符集T 能推出 的非终结符集T为 A B S 2 计算每个产生式右部 的FIRST 集 对每个a VT First a a 对每个A VN 若A 则当前First A 否则当前First A 对每个产生式A X1 Xj Xn First A First A SectionFirst X1 Xj Xn SectionFirst X1 Xj Xn First X1 First X2 First Xj First Xj 1 Xj 1是产生式右部中第一个不能推出 的符号 首先对文法符号X X VT VN 求FIRST X 对每个产生式A X1 Xj Xn做 First A First A SectionFirst X1 Xj Xn 其中SectionFirst X1 Xj Xn First X1 First X2 First Xj First Xj 1 Xj 1是产生式右部中第一个不能推出 的符号若X1 则SectionFirst X1 Xj Xn First X1 若X1 Xn全可推出 则SectionFirst X1 Xn First X1 FIRST Xn 重复3直到每个符号的FIRST集合都不再增大为止 例G S S AB bCA b B aD C AD bD aS c First集 3 First集 2 First集 1 A B C D a b S First集 0 已求出能推出 的非终结符集T为 A B S b b a b ac a ac 敛 敛 敛 敛 敛 敛 敛 c 敛 c c c c 结论 文法符号的First集合如下 First S a b First A b First B a First C a b c First D a c First a a First b b First c c 利用求出每个文法符号的FIRST集求符号串的FIRST集 设右部串 X1X2 Xn当X1 则FIRST FIRST X1 若对任何j 1 j n 都有 FIRST Xj Xj 1为X1X2 Xn中第一个推不出 的符号 则FIRST FIRST X1 FIRST Xj FIRST Xj 1 若对所有i 1 i n 都有 FIRST Xi 则FIRST FIRST X1 FIRST Xn FIRST AB FIRST A FIRST B a b FIRST bC FIRST b b FIRST FIRST b b FIRST AD FIRST A FIRST D b a c FIRST aS FIRST a a 例G S S AB bCA b B aD C AD bD aS c 已求出非终结符的First集合如下 First S a b First A b First B a First C a b c First D a c 产生式右部符号串的开始符集合为 S ABS bCA A bC ADD aS 要判别一个上下文无关文法是否是LL 1 文法分为五步 1 求能推出 的非终结符集T2 计算每个产生式右部 的FIRST 集3 计算每个非终结符A的FOLLOW A 集4 计算每个产生式A 的SELECT A 集5 按LL 1 文法的定义判别 要判别一个上下文无关文法是否是LL 1 文法分为五步 1 求能推出 的非终结符集T2 计算每个产生式右部 的FIRST 集3 计算每个非终结符A的FOLLOW A 集4 计算每个产生式A 的SELECT A 集5 按LL 1 文法的定义判别 3 计算每个非终结符A的FOLLOW A 集 1 对所有A VN 令Follow A 对开始符S 令Follow S 因为S S 显然 FOLLOW S 2 对每条产生式B xAy 考察产生式右部的每一非终结符A x y V 若y 则Follow A Follow A First y 否则Follow A Follow A First y Follow B 3 重复2 直至对所有A VN Follow A 收敛为止 若a FOLLOW B 则表明S Ba 由于B xAy 且y 则有S Ba xAya xAa 即S xAa 所以a 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集合如下 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 Follow集 2 Follow集 1 Follow集 0 c 敛 敛 敛 敛 敛 结论 Follow S Follow A a c Follow B Follow C Follow D 4 计算每个产生式A 的SELECT A 集 按定义计算SELECT A 若右部串 则SELECT A FIRST 若右部串 则SELECT A FIRST FOLLOW A SELECT S AB SELECT S bC SELECT A SELECT A b SELECT B aD SELECT B SELECT C AD SELECT C b SELECT D aS SELECT D c 例G S S AB bCA b B aD C AD bD aS c SELECT S AB FIRST AB FOLLOW S b a SELECT S bC FIRST bC b SELECT A FIRST FOLLOW A a c SELECT A b FIRST b b SELECT B aD FIRST aD a SELECT B FIRST FOLLOW B SELECT C AD FIRST AD b a c SELECT C b FIRST b b SELECT D aS FIRST aS a SELECT D c FIRST c c FIRST AB a b FIRST bC b FIRST FIRST b b FIRST aD a FIRST AD b a c FIRST aS a 5 按LL 1 文法的定义判别 产生式的select集如下 SELECT S AB b a SELECT S bC b SELECT A a c SELECT A b b SELECT B SELECT B aD a SELECT C AD b a 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 所以文法G S 不是LL 1 文法 对每个非终结符A的任两个产生式A 与A 满足SELECT A SELECT A 要判别一个上下文无关文法是否是LL 1 文法分为五步 1 求能推出 的非终结符集T2 计算每个产生式右部 的FIRST 集3 计算每个非终结符A的FOLLOW A 集4 计算每个产生式A 的SELECT A 集5 按LL 1 文法的定义判别 go 由每个产生式的select集构造LL 1 分析表 例G S S AB bCA b B aD C AD bD aS c试判断该文法是否为LL 1 文法 back 非终结符集T 能推出 的非终结符集T为 A B S 1 求能推出 的非终结符集T back 2 计算每个产生式右部 的FIRST 集 FIRST AB FIRST A FIRST B a b FIRST bC b FIRST FIRST b b FIRST AD FIRST A FIRST D b a c FIRST aS a FIRST aD a back 3 计算每个非终结符A的FOLLOW A 集 back 4 计算每个产生式A 的SELECT A 集 back SELECT S AB FIRST AB FOLLOW S b a SELECT S bC FIRST bC b SELECT A FIRST FOLLOW A a c SELECT A b FIRST b b SELECT B aD FIRST aD a SELECT B FIRST FOLLOW B SELECT C AD FIRST AD FIRST A FIRST A b a c SELECT C b FIRST b b SELECT D aS FIRST aS a SELECT D c FIRST c c SELECT S AB b a SELECT S bC b SELECT A a c SELECT A b b SELECT B SELECT B aD a SELECT C AD b a c SELECT C b b SELECT D aS a SELECT D c c 由每个产生式的select集构造LL 1 分析表 S AB S AB S AB S bC A A A A b B aD B C AD C AD C b C AD D aS D c 5 按LL 1 文法的定义判别 back 根据LL 1 文法的定义判别 由于SELECT S AB SELECT S bC b SELECT C AD SELECT C b b 所以文法G S 不是LL 1 文法 习题 判别文法G S 是否为LL 1 文法S aSb PP bP P Pc QcQ aQ Q aQ First 2 First 1 P P Q Q S First 0 a First P 敛 b 敛 b First Q 敛 a 敛 a 敛 1 2 ab 敛 b 敛 ab 敛 a 敛 a 敛 ab 敛 ab 敛 习题 判别文法G S 是否为LL 1 文法S aSb PP bP P Pc QcQ aQ Q aQ 2 FIRST aSb FIRST a a FIRST P b FIRST bP FIRST b b FIRST Pc FIRST P b FIRST Qc FIRST Q a FIRST aQ FIRST a a FIRST aQ FIRST a a FIRST Follow 2 Follow 1 P P Q Q S Follow 0 b 收敛 bc bc c 收敛 c 收敛 收敛 收敛 习题 判别文法G S 是否为LL 1 文法S aSb PP bP P Pc QcQ aQ Q aQ 3 SELECT S aSb a SELECT S P b SELECT P bP b SELECT P Pc b SELECT P Qc a SELECT Q aQ a SELECT Q aQ a SELECT Q c 构造LL 1 分析表 根据LL 1 定义判断 文法G S 是LL 1 文法 FIRST aSb FIRST a a FIRST P b FIRST bP FIRST b b FIRST Pc FIRST P b FIRST Qc FIRST Q a FIRST aQ FIRST a a FIRST aQ FIRST a a FIRST 4 5 LL 1 分析表 4 3非LL 1 文法到LL 1 文法的等价变换 非LL 1 文法含有左公共因子的文法若文法中含有形如 A r的产生式 称文法含有左公共因子 显然 SELECT A SELECT A r 文法不是LL 1 文法 stmt ifexprthenstmt ifexprthenstmtelsestmt other 句型ife1thenife2thens1elses2 推导一stmt ife1thenstmt ife1thenife2thens1elses2 悬空else问题 推导二stmt ife1thenstmtelses2 ife1thenife2thens1elses2 stmt ifexprthenstmt ifexprthenstmtelsestmt other stmt matched stmt unmatched stmtmatched stmt ifexprthenmatched stmtelsematched stmt otherunmatched stmt ifexprthenstmt ifexprthenmatched stmtelseunmatched stmt 含有左递归的文法文法中只要含有下列形式的产生式 则称文法含有左递归 A A A B B A 在a 中含有左递归的产生式 称为直接左递归在b 中虽然没有含左递归的产生式 但A B A 即A A 称为间接左递归 以直接左递归为例 若有如下产生式A A A 其中 和 为任意语法符号串 不难证明有下面关系式 Select A A First A First Select A First 故A A 和A 的Select集相交 不是LL 1 文法 对非LL 1 文法进行等价变换提取左公共因子消除左递归注意 变换后的文法不一定是LL 1 文法 文法不含左递归和左公共因子只是LL 1 文法的必要条件 1提取左公共因子 将产生式A r等价变换为 A r r 引入一新非终结符A 表示 即得A A A r一般形式 若A 1 2 n 提取左公共因子 即得A A A 1 2 n若在 i中仍含有左公共因子 可再次提取 例文法G1 S aSb aS 提取左因子得 S aS b 引进新非终结符S 得 S aSS S b 2 消除左递归 消除直接左递归文法G S Sa b可改写成S bS S aS 一般情形 含直接左递归的文法G A A 1 A 2 A m 1 2 n消除左递归后改写成 A 1A 2A nA A 1A 2A mA 消除间接左递归将间接左递归变成直接左递归 再消除算法步骤 把文法的所有非终结符按任一顺序排列 如 A1 A2 Ai Ak An从A1开始 按以下顺序处理Ak消除左部为Ak的产生式的直接左递归若左部为Ak的产生式的右部为非终结符Ai i k 开头 Ak Ai 则用左部为Ai的所有产生式的右部分别代替Ak Ai 中的Ai 转至 直至A1 An的消除工作全部完成 退出2 去掉无用产生式 例文法G 1 S Qc c 2 Q Rb b 3 R Sa a 将非终结符排序 R Q S对R 产生式 3 不含直接左递归 所以保持不变对Q 把 3 代入 2 得 2 Q Sab ab b 无直接左递归对S 把 2 代入 1 得 1 S Sabc abc bc c 有直接左递归 消除直接左递归得S abcS bcS cS S abcS 处理结果为 R Sa aQ Sab ab bS abcS bcS cS S abcS 由于Q R是不可到达的非终结符 其产生式应删除 最终得文法G S abcS bcS cS S abcS 示例说明 当非终结符顺序为R Q S 消除左递归的最终结果为 S abcS bcS cS S abcS 若非终结符顺序为S Q R 则消除左递归的最终结果为 S Qc cQ Rb bR bcaR caR aR R bcaR 结论 当非终结符的排序不同时 结果的产生式形式不同 但它们是等价的 LL 1 文法任两个产生式A 都满足下列条件 FIRST FIRST 若 那么FIRST FOLLOW A LL 1 文法有一些明显的性质没有公共左因子不是二义的不含左递归 4 4不确定的自顶向下分析思想 不确定的自顶向下分析也称带回溯的自顶向下分析定义 不确定是指某个非终结符有多条产生式 而面临当前输入符无法唯一确定选用哪条产生式进行推导 只好逐个试探 当分析不成功时 则推翻分析退回到适当位置重新试探其余候选可能的推导 直到把所有可能的推导序列都试完仍不成功 才能确认输入串不是该文法的句子 不确定的下推自动机理论 PDA deabc WXm 1 q 输入串 栈 自动机 读指针 X Z pi 不确定的下推自动机理论 deabc Stack q deabc Stack hi 移动 构形 q w h q a Z pi hi PDA的形式定义PDA与上下文无关语言的重要理论PDA与CFG的对应关系从CFG到PDA的构造举例 PDA的形式定义PDA与上下文无关语言的重要理论PDA与CFG的对应关系从CFG到PDA的构造举例 例文法G S S 0S1 c 1 构造其PDA规则 2 写出输入串00c11被接收的移动序列 例1 设有文法S xAyA ab a 对输入串w xay 推导树为 由于A的两条产生式 A ab和A a右部First集交集不为空 从而引起回溯 例2文法G S aASS bA bASA 输入串w ab 推导树为 由于A的产生式A 右部能 且Follow A First bAS b 从而引起回溯 例3文法G S SaS b输入串w baa 推导树为 由于文法含有左递归而引起回溯 4 5确定的自顶向下分析方法 确定的自顶向下分析方法有 LL 1 预测分析器 predictiveparser LL 1 递归子程序分析器 recursive descentparser 两种方法都要求文法是LL 1 文法 4 5确定的自顶向下分析方法 确定的自顶向下分析方法有 LL 1 预测分析器 predictiveparser LL 1 递归子程序分析器 recursive descentparser 两种方法都要求文法是LL 1 文法 4 5 1LL 1 预测分析器 一个预测分析器由三个部分组成 预测分析程序 控制分析过程的进行 分析栈 存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号 开始时放入 和文法开始符 结束时栈应是空的 预测分析表 是一个二维表 元素M A a 的内容是当非终结符A面临输入符号a 终结符或 时应选取的产生式 当无产生式时 元素M A a 为出错处理 error 构造预测分析表步骤 1 把文法转变为LL 1 文法 2 求出每条产生式的SELECT集 3 依照SELECT集把产生式填入分析表横坐标 终结符与 纵坐标 非终结符交点M A a A 放入M A a 若a SELECT A 无产生式的M A a 标记出错 例 算术表达式文法GE E T TT T F FF E i 1 消除G的左递归得到文法G E TE E TE T FT T FT F E i 2 求出每个产生式的select集 G 是LL 1 文法SELECT E TE i SELECT E TE SELECT E SELECT T FT i SELECT T FT SELECT T SELECT F E SELECT F i i F E F i F T T T FT T T T FT T FT T E E E TE E E i E TE E TE 3 依照选择集合把产生式填入分析表 注 表中空白处为出错 预测分析程序 上托栈顶符放入X N Y Y N N N N Y Y Y 把 和文法开始符S压入分析栈 当前输入符送a 把产生式右部反序进栈 X VT X X a X a 读下一输入符到a M X a 有产生式 出错 结束 出错 预测分析程序工作过程 输入串i i i 的分析过程 7 6 5 4 3 2 1 所用产生式 剩余输入串 分析栈 步骤 8 13 14 15 16 17 12 11 10 9 4 5 2递归子程序法 第三次实验 1实现思想对文法中的每个非终结符编写一个递归过程 识别由该非终结符推出的串 当非终结符有多个产生式时 按当前输入符属于哪个产生式的SELECT集可唯一确定选择哪个产生式进行匹配 当识别到终结符时 与当前输入符号匹配 并读取下一输入符 当识别到非终结符时 则调用该非终结符相应的过程 定义当一个文法满足LL 1 条件时 就为它构造一个不带回溯的自顶向下的分析程序这个分析程序由一组递归过程组成每个过程对应文法的一个非终结符这样的一个分析程序称为递归下降分析器 2构造文法G 的递归下降分析器 组成 递归下降分析器由一个主程序main和每个非终结符对应的一个递归过程组成 用到的一些子过程 过程getnext负责读入下一个TOKEN字过程error 负责报告语法错误约定 变量TOKEN存放已读入的TOKEN字过程进入时变量TOKEN存放了一个待匹配的TOKEN字退出过程时 变量TOKEN中仍存放着一个待匹配的TOKEN字 非终结符相应的分析子程序的构造方法对于每个非终结符U 编写一个相应的子程序P U 对于产生式U x1 x2 xn x1 xn 关于U的子程序P U 按如下方法构造 if TOKEN first x1 p x1 elseif TOKEN first x2 p x2 else if TOKEN first xn p xn elseERROR 如果U还有空产生式U 则算法中的语句 if TOKEN first xn p xn elseERROR 改写为if TOKEN first xn p xn elseif TOKEN follow U ERROR 对于符号串x y1y2 ynp x 的含义为 main p y1 p y2 p yn 如yi VN 则P yi 就代表调用yi的子程序 如yi VT 则P yi 为如下述代码if TOKEN yi getnext TOKEN elseERROR 例 算术表达式文法GE E T TT T F FF E i 1 消除左递归得G E TE E TE T FT T FT F E i 2 求出G 的选择集合SELECT E TE i SELECT E TE SELECT E SELECT T FT i SELECT T FT SELECT T SELECT F E SELECT F i i G 是LL 1 文法 1判断是否可以应用递归子程序法 1 chTOKEN main 主程序 getnext TOKEN E TOKEN 转匹配E TE if TOKEN ERROR 构造文法G E TE E TE T FT T FT F E i的递归下降分析器 2 E TOKEN 匹配E TE T TOKEN 转匹配T FT E TOKEN 转匹配E TE 3 E TOKEN 匹配E TE if TOKEN 选择产生式E TE getnext TOKEN 匹配 读入下一个Token字 T TOKEN 转匹配T FT E TOKEN 转匹配E TE else E 对应的语句 if TOKEN 构造文法G E TE E TE T FT T FT F E i的递归下降分析器 4 T TOKEN 匹配T FT F TOKEN 转匹配F E i T TOKEN 转匹配T FT 构造文法G E TE E TE T FT T FT F E i的递归下降分析器 5 T TOKEN 匹配T FT if TOKEN 选择产生式T FT getnext TOKEN 匹配 读下一TOKEN字 F TOKEN 转匹配F E i T TOKEN 转匹配T FT else T 对应的语句 if TOKEN 构造文法G E TE E TE T FT T FT F E i的递归下降分析器 6 F TOKEN 匹配F E i if TOKEN 选择产生式F E getnext TOKEN 匹配 读下一TOKEN字 E TOKEN 转匹配E TE if TOKEN getnext TOKEN 匹配 读下一TOKEN字 elseERROR else 选择产生式F i if TOKEN i getnext TOKEN elseERROR 构造文法G E TE E TE T FT T FT F E i的递归下降分析器 特点 优点 简单直观 易于构造缺点 对文法要求高 必须满足LL 1 文法 递归调用多 速度慢 占用空间多实用性 许多高级语言 如Pascal c等编译系统常常采用此方法 实验三 语法分析 实验目的设计编制一个递归下降分析程序 实现对词法分析程序所提供的单词序列进行语法检查和结构分析 加深对构造自顶向下的语法分析器的原理和技术理解与应用 实验三 语法分析 实验要求利用C语言编制递归下降分析程序 并对C语言的简单子集进行分析 设计语言文法 运用递归下降分析技术 设计和实现语法分析器 具有出错处理功能 待分析的C语言子集的语法 以扩充的BNF方法描述如下 1 main 2 3 4 5 ID 6 if if else 7 while 8 ii i 9 i 10 本章小结 两种自顶向下分析方法 递归子程序法预测分析法一种文法 LL 1 文法判别方法非LL 1 到LL 1 的转换