ch6自底向上算符优先语法分析.ppt

自底向上算符优先语法分析 第6章 1 主要内容 规范归约 自上而下的算符优先分析方法及其相关概念 重点掌握 掌握自下而上分析的基本思想 规范规约的概念及过程 算符优先文法 算符优先关系的判定 最左素短语 句柄的定义与判定 构造算符优先关系表 能用算符优先分析法进行表达式分析 6 1自底向上优先分析概述 2 G E i P E P E E EE E EE E E i 最左推导 E E E E E E E E i E E i i E i i i最右推导 E E E E i E E i E i i i i i 例 判定输入串 i i i是否是下述文法的句子 结论 自上而下语法分析采用最左推导 每一步推导使用哪个产生式要视当前非终结符匹配输入字符串中的哪个符号来确定 自下而上语法分析是最右推导的逆过程 由输入符号串反向推导到文法的开始符号 3 自下而上的语法分析 实现思想 移进 归约 方法设置一个栈 将输入符号逐个移进栈中 栈顶形成某产生式的右部时 句柄 就用左部去代替 称为归约 重复这一过程 直到栈中只剩下文法的开始符号 就确认输入串是文法的句子 分析成功 否则出错 语法树 从树叶开始 逐步向上归约构造分析树 直到形成根结点 是推导的逆过程 核心寻找句柄进行规约 用不同的方法寻找句柄 就可获得不同的分析方法 4 最左推导 Left mostDerive 每一步推导都替换当前句型的最左边的非终结符 其逆过程称为最右归约最右推导 Right mostDerive 每一步推导都替换当前句型的最右边的非终结符 其逆过程称为最左归约 规范归约 得规范句型 例 设有文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d使用最右推导 因为SaAcBeaAcdeaAbcdeabbcde 所以abbcde是文法G的句子 5 步骤动作 1 S aAcBe 2 A b 3 A Ab 4 B d 最左归约过程是最右推导的逆过程 对输入串abbcde的归约过程如下 该分析过程反复执行 移进 和 归约 两个动作 直到栈中只有开始符号为止 a b A c S b d B e A 6 语法分析树的生成演示 abbcde A A B S A b A Ab B d S aAcBe 1 S aAcBe 2 A b 3 A Ab 4 B d 7 规范归约分析过程具有如下特点 从输入串的开始依次读入单词 移进栈中 一旦发现可归约串 某个产生式的右端 就立即归约 归约就是将栈顶的一串符号用文法产生式的左部代替 归约可能重复多次 若最终能归约成文法的开始符号 则分析成功 由于总是将句型的最左边的可归约串替换成非终结符 该方法与最右推导对应 关键是如何判断可归约串 8 问题的提出 在构造语法树的过程中 何时归约 当可归约串出现在栈顶时就进行归约 如何知道在栈顶符号串中已经形成可归约串 如何进行归约 不同的自下而上的分析方法对可归约串的定义是不同的 但分析过程的一个共同特点是 边移进边归约 9 规范归约的概念 有文法G 开始符号为S 如果有S x y 则x y是文法G的句型 x y是任意的符号串如果有S xAy 且有A 则 是句型x y相对于非终结符A的短语如果有S xAy 且有A 则 是句型x y相对于A 的直接短语位于一个句型最左边的直接短语称为句柄 注意 规范规约中每次归约的部分必须是句柄 最右推导 关键的问题是如何识别句柄 10 例 考虑如下文法 求句型i1 i2 i3的短语 直接短语和句柄 E T E TT F T FF i E 因此 短语有 i1 i2 i3 i1 i2 i1 i2 i3直接短语有 i1 i2 i3句柄是 i1 E F i2 i3E i1 F i3E i1 i2 F E T i3 T T F i1 i2 E i1 i2 i3 F i 11 从语法分析树来识别 一棵子树是由树的某个结点连同它的所有子孙组成的 子树的所有端末结点自左至右排列成一个相对子树根的短语 直接短语 只有父子两代结点形成的短语 句柄 最左子树的直接短语 从语法树可以看出 i1 i2 i3 i1 i2 i1 i2 i3是句型i1 i2 i3的短语直接短语有 i1 i2 i3句柄是 i1 E T E TT F T FF i E 句型i1 i2 i3的语法树如图 12 对下述文法 求句型E T F i的短语 直接短语 句柄 E T E TT F T FF i E 短语有 i T F E T F E T F i直接短语有 i T F句柄是 T F 练习 13 给定右边的文法 用句柄对符号串abbcde进行归约 用句柄对句子进行归约的过程与用移进 归约过程是一致的 使用归约的产生式及其顺序是一致的 1 S aAcBe 2 A b 3 A Ab 4 B d 2 A b 3 A Ab aAbcde aAcde 4 B d 1 S aAcBe aAcBe S 14 练习 使用下述文法对句型i1 i2 i3进行规范归约 E T E TT F T FF i E i1 i2 i3 F i2 i3 T i2 i3 T F i3 T i3 E i3 E F E T E 15 规范归约分析中栈的使用 1 句型表示 符号栈内容 输入缓冲区内容 当前句型 2 分析器结构 能够到达终态 分析成功 不能到达终态 分析失败 16 例2 有文法 E E T TT T F FF E i对输入串id1 id2 id3的规范归约过程 17 动作栈输入缓冲区1 准备 id1 id2 id3 2 移进 id1 id2 id3 3 归约F id F id2 id3 4 归约T F T id2 id3 5 归约E T E id2 id3 6 移进 E id2 id3 7 移进 E id2 id3 8 归约F id E F id3 9 归约T F E T id3 10 移进 可规约 E T id3 11 移进 E T id3 12 归约F id E T F 13 归约T T F T F E T 14 归约E E T E 15 接受 所得的结果是 用产生式序列表示语法分析树 id1 id2 id3 F T E F T F T E 1 E T E T 2 T F T F 3 F i E 18 练习 给出句型 a a a 的规范归约过程 给定文法G S S a T T T S S 19 dodo将输入串最左边的符号移入栈内 while 栈顶没有出现可归约串 do归约可归约串 while 栈顶还有可归约串 while 文法开始符号没有出现在栈顶或者没有发现错误 规约算法描述 20 分析成功的条件 栈顶为文法开始符号 输入符号串为空 注意 该过程并未涉及如何在栈里找可归约串 实际上 不同的找可归约串的方法 构成了不同的分析方法 移进 归约 分析法用栈实现的特点 可归约串必定位于栈顶 即可归约串之后就是剩余的输入串 栈内符号串与剩余输入串正好构成一个句型 21 分析器的四种动作 1 移进 将下一输入符号移入栈2 归约 当栈顶出现句柄 用产生式左侧的非终结符替换栈顶的句柄3 接受 分析成功 是归约的一种特殊情况4 出错 栈顶的内容与输入符号相悖 进行出错处理 决定移进和归约的依据是什么 22 移进归约分析中的问题 1 移进 归约冲突在分析到某一步时 既可以移进 又可以归约p18上例第10 步可以移进 也可以按产生式E E T进行归约 2 归约 归约冲突存在两个可选的句柄 可对栈顶符号进行归约例如上述第13 步 可以用T F进行归约 又可以按T T F进行归约 本章所给两种处理以上冲突的方法 23 优先分析法有两种 简单优先分析法 规范归约 文法按一定规则规定文法符号 终结符和非终结符 的优先关系 算符优先分析法 不规范归约 规定算符 终结符 之间的优先关系 24 6 2简单优先分析 简单优先分析法的思想是利用终结符和非终结符之间的优先关系确定句柄 是规范规约 25 6 2 1简单优先关系 对于文法G中的任意两个符号X和Y按其在句型中可能会出现的相邻关系来确定他们之间的优先关系 X和Y可以是非终结符也可以是终结符 1 X优先性等于Y 记作XY 当且仅当G中存在规则A XY 2 X优先性低于Y 记作XY 当且仅当G中存在规则A XB 且B Y 3 X优先性高于Y 记作XY 当且仅当G中存在规则A BD 且B X D Y 26 简单优先关系矩阵 例6 2教科书p104 设有文法G S S bAbA B aB Aa 27 6 2 2简单优先文法定义 一个文法是简单优先文法必须满足如下两个条件 1 在文法符号集V中的任意两个符号最多只有一种优先关系 2 文法中任意两个产生式没有相同的右侧 28 6 2 3简单优先分析算法 根据优先关系矩阵和文法构造算法如下 1 将输入符号串a1a2 an 存入符号栈T中 直到遇到栈顶符号ai的优先级下一个待输入符号的优先级为止 2 栈顶当前符号ai为句柄尾由此向左找句柄的头符号ak 即找到ak 1ak为止 3 由句柄ak ai在文法的产生式中找右部为ak ai的产生式 若找到用左部代替右部 否则不是句子 4 重复上述步骤直到规约完输入符号串栈中只剩文法输入符号 29 分析b aa b过程 设有文法G S S bAbA B aB Aa 30 6 3算符优先分析 算符优先分析法的思想源于表达式的分析 是利用相邻终结符号之间的关系来寻找可归约串 将句型中的终结符号当作 算符 借助于算符之间的优先关系确定规约子串 分析过程是自下而上的归约过程 不是一种严格的规范归约 31 6 3 1算符优先关系的定义 在一个符号串中 任意两个相邻终结符号a和b之间 只可能存在三种优先关系 1 a优先性等于b 记作ab 2 a优先性高于b 记作ab 3 a优先性低于b 记作ab 另一种情况是 a与b不可能相邻 即此符号串不是句型 出错 如果以上四种关系中的任意两种都不会同时成立 则可以根据终结符号之间的归约关系进行语法分析 32 1 算符文法 文法G中没有P QR P Q R属于非终结符 的产生式 不存在具有相邻非终结符的产生式 2 算符优先关系的定义 文法G是一个不含 产生式的算符文法 定义终结符a b之间的优先关系 ab G中有P ab 或P aQb 产生式 ab G中有P aR 的产生式 且R b 或R Qb 注意ab相邻或只隔一个非终结符 ab G中有P Rb 的产生式 且R a或R aQ 注意ab相邻或只隔一个非终结符 6 3 2算符优先文法的定义 33 例1 E E E E E E i就不是算符优先文法 因为 E E E E E E则有 由规则2 又因为 E E E E E E则有 由规则3 所以不是算符优先文法 仅是算符文法 3 算符优先文法算符文法G的任何终结符a b之间要么没有优先关系 若有优先关系 至多有 中的一种成立 则G为一算符优先文法 34 课堂练习 对右边的文法G 计算终结符 和 之间的优先关系 E E TT T FF P FP E 因为 E E T T T F 所以 E T 所以 规则3 因为 T T F F P F 所以 T F 所以 规则3 因为 P E E E T 所以 规则3 因为 F P F P E 所以 规则3 因为 F P F F P F 所以 规则2 35 6 3 3算符优先关系表的构造 用表格形式来表示各终结符号的优先关系 这种表称为优先表 构造优先关系表的方法 按照定义手工计算 使用算法例 P E E T TT T F FF E i求算符优先关系表 36 由F E 得 例 P E E T TT T F FF E i求算符优先关系表 终结符 终结符 对于结束符 和其它终结符a之间若有关系 则必有 计算方法是拓展成E E 37 注意 a b之间未必有优先关系 在优先表中 空白部分是一种错误关系相同的终结符之间的优先关系不一定是如果有a b 不一定有b a 不具对称性 如果有ab 不一定有ba 不具对称性 因为只定义相邻运算符之间的优先关系 a b相邻时 不一定b a相邻 如果有ab bc不一定有ac 38 算符优先关系表的自动构造算法 1 FirstVT集定义 对每个非终结符P FirstVT P a P a 或P Qa a为终结符 P Q为非终结符 由优先性的定义和FirstVT集合的定义可以得出 若存在某个产生式 Q aP 对所有 b FirstVT P 都有 a b 39 构造FirstVT集算法 按照下面两条规则来构造FirstVT集 若有产生式P a 或P Qa 则a FirstVT P 若有产生式P R 若a FirstVT R 则a FirstVT P 所有终结符 所有非终结符 数组值为真假 为真的条件是c FirstVT Q 通过构造一个二维数组F来实现 数组F的每一行反映任何一个非终结符P的FirstVT集中的元素 步骤 1 先用 规则进行初始化 40 2 使用 规则对数组F进行修改 修改方法是 1 用一个栈 将所有F数组中值为真的元素F P a 的符号对 P a 压入堆栈 2 对栈施行如下操作 若栈不空 将栈顶符号对出栈 记为 Q a 检查所有的产生式 若有形为 P Q 的产生式 且F P a 为假 则置F P a 为真 将 P a 压入堆栈 3 重复这一过程 直到栈空 41 例 求文法各非终结符的FirstVT 定义数组 E E T TT T F FF E i 从而得到 FirstVT E i FirstVT T i FirstVT F i 42 课堂练习 FirstVT S a FirstVT T a 计算FirstVT 给定文法G S S a T T T S S 43 求FirstVT集的伪代码描述 Beginfor对每个非终结符P和终结符adoF P a falsefor对每个形如P a 或P Qa 的产生式doInsert P a whilestack非空begin栈顶项出栈 记为 Q a for对每条形如P Q 的产生式doinsert P a end end PROCEDUREinsert P a IFnotF P a thenbeginf p a true P a 进栈end 对数组初始化 应用规则1 应用规则2 44 用关系图法求FIRSTVT集合 P113图6 5 45 2 求LastVT集定义 LastVT P a P a或P aQ a为终结符 P Q为非终结符 构造LastVT集算法如下 46 构造LastVT集算法 按照下面两条规则来构造LastVT集 若有产生式P a或P aQ 则a LastVT P 若有产生式P R 若a LastVT R 则a LastVT P 所有终结符 所有非终结符 数组值为真假 为真的条件是c LastVT Q 通过构造一个二维数组F来实现 数组F的每一行反映任何一个非终结符P的LastVT集中的元素 步骤 1 先用 条规则进行初始化 47 2 使用 规则对数组F进行修改 修改方法是 1 用一个栈 将所有F数组中值为真的元素F P a 的符号对 P a 压入堆栈 2 对栈施行如下操作 若栈不空 将栈顶符号对出栈 记为 Q a 检查所有的产生式 若有形为 P Q的产生式 且F P a 为假 则置F P a 为真 将 P a 压入堆栈 3 重复这一过程 直到栈空 48 练习 LastVT S a LastVT T a 计算LastVT 给定文法G S S a T T T S S 49 3 构造优先关系表的算法如果每个非终结符的FirstVT和LastVT集均已知 则可根据定义构造优先关系表 构造思路 1 若产生式是形如 P ab 或P aQb 的形式 则有ab 2 若产生式右部是 aR 的形式 则对于每个b FirstVT R 都有ab 3 若产生式右部有 Rb的形式 则对于每个a LastVT R 集 都有ab 50 for每个形如P X1X2 Xn的产生式dofori 1ton 1dobeginifXi和Xi 1都是终结符thenXi Xi 1ifiXi 1 end 优先关系表构造算法伪代码 同一产生式中的相邻符号1 同一产生式中的相邻符号2 a出现在其它产生式中 通过计算得到 51 练习 FirstVT S a FirstVT T a LastVT S a LastVT T a 的FirstVT和LastVT集 构造优先关系表 给定文法G S S a T T T S S 52 6 3 4算符优先分析算法 原理 通过比较相邻终结符间的优先关系来实现实现机制 仍然采用 移进 归约 方式 不断移进输入符号 识别可归约串 并进行归约 分析方法 根据优先性 低于 来识别句柄的头 根据优先性 高于 来识别句柄的尾 各种优先关系已经存于优先关系表中 53 几个定义 1 算符优先分析过程 不是严格的规范归约 每次归约的符号串 不一定是规范归约中的 句柄 不能识别只由一个非终结符组成的句柄 是当前句型的最左素短语 2 句型的素短语 是一个短语 至少含有一个终结符 且除自身外 不再包含任何其它更小的素短语 3 句型的最左素短语 是指位于句型最左边的那个素短语 54 例 给定右边文法的一个句型 T F i求其短语 素短语 最左素短语 E T E TT F T FF i E 短语有 i T F T F i素短语有 i T F最左素短语是 T F 55 练习 给定文法G E 求句型T T F i的短语 素短语 最左素短语 根据语法树可知 句型 T T F i 的短语有 T 相对非终结符E的短语T F 相对非终结符T的短语T T F 相对非终结符E的短语i 相对非终结符P F T的短语T T F i 相对非终结符E的短语 根据素短语的定义可知 i和T F为素短语 其中 T T F 含T F素短语 T T F i 含T F素短语 和T 不含终结符 也不是素短语T F为最左素短语 E E T TT T F FF E i 56 设算符文法G的句型的一般形式为 N1a1N2a2 Nnan Ni VN ai VT 它的最左素短语是满足下列条件的最左子串 NiaiNi 1ai 1 NjajNj 1其中 ai 1 ai ai ai 1 aj 1 aj aj aj 1 该定理说明了最左素短语与周围符号之间的关系 定理 57 符号栈内容 输入缓冲区内容 当前句型 N1a1N2a2 NnanNn 1 ai为终结符 Ni为可有可无的非终结符 句型的一般形式 分析时句型表示 3 算符优先分析 58 分析模型 59 过程 1 从左向右扫描输入符号并移入堆栈 并查优先矩阵 直至找到满足aj aj 1时为止 2 再从aj开始往左扫描堆栈 直至找到某个i 满足ai 1ai为止 3 NiaiNi 1ai 1 NjajNj 1形式的子串即为最左素短语 应被归约 算符优先分析过程 开始 分析栈中为 输入缓冲区为 输入串 结束 输入缓冲区为 分析栈中为 S 分析成功否则失败 60 表达式i i i的算符优先过程 E E T TT T F FF E i 例 给定文法G E 61 top 1 s top a 下一个输入符号 doIfs top VtTHENj topELSEj top 1 WHILEs j aDOBEGINREPEATq s j IFs j 1 VtTHENj j 1elsej j 2 UNTILs j q 把s j 1 s k 归约为某个N 将N入栈 top j 1 ENDIFs j aORs j aTHENBEGINtop top 1 s top a END ELSEerror a 下一个输入符号 while a 流程图 P117 栈顶符号s j 与即将输入的符号a进行比较 栈顶符号优先性低于或等于输入符号a 则移进a 向前查找最左素短语的头 j记录可归约串的头 进行归约 S表示堆栈 top记录栈顶位置 j记录栈顶符号位置 62 算符优先分析不是严格的规范归约不对文法的非终结符定义优先关系 无法发现由单个非终结符组成的 可归约串 即无法使用单非产生式 如 T F 进行归约 算符优先分析比规范归约过程要快 跳过了所有的单非终结产生式 可能将本来不是句子的输