编译原理自底向上优先分析.ppt

《编译原理自底向上优先分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章自顶向下语法分析方法复习11语法分析：自顶向下：确定分析和不确定分析自底向上：算符优先分析和LR分析第5章概念22FirstFollowSelectLL(1)文法第5章操作33用关系图计算First、Follow计算Select判断是否LL(1)文法消除左递归、提取左公共因子生成LL(1)分析表编写递归子程序、构造预测分析器递归子程序部分44G[E]:E→TE’E’→+TE’

2、εT→FT’T’→*FT’

3、εF→(E)

4、i55voidE(void){T();E’();}voidE’(void){if(sym==‘+’){sym=getchar();T();E’();}

5、请同学们写出T’和F的程序66voidT(void){F();T’();}voidT’(void){if(sym==‘*’){sym=getchar();F();T’();}77voidF(void){if(sym==‘i’)sym=getchar();elseif(sym==‘(‘){sym=getchar();E();if(sym==‘)’)sym=getchar();elseERROR();//报告出错}//endofelseifelseERROR();//报告出错}第六章自底向上优先分析886.1自底向上分析概述6.2算符优先分析法介绍6.3算符优先分析法6.4简单

6、优先方法6.1自底向上分析99若采用自左向右的描述和分析输入串,那么自底向上的基本算法是：从输入符号串开始，通过重复查找当前句型的句柄(最左简单短语)，并利用有关规则进行规约，若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子，否则有语法错误。基本算法思想:1010分析过程是重复一下步骤：1、找出当前句型的句柄x（或句柄的变形）2、找出以x为右部的规则X::=x3、把x规约为X，产生语法树的一枝关键：找出当前句型的句柄x(或其变形），这不是很容易。算符优先分析法LR分析法6.1.1移进—规约分析（Shift-reduceparsing)1111#S.R.P

7、#符号栈输入串要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约。1212分析过程：把输入符号串按描述顺序一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。#S.R.P#符号栈输入串1313例：G[S]:S→aAcBeA→bA→AbB→d

8、输入串为abbcde，检查是否是该文法的合法句子。若采用自底向上分析，即能否一步步规约当前句型的句柄，最终规约到识别符号S。先设立一个符号栈，我们统一符号“#”作为待分析的符号串的左右分界符。作为初始状态，先将符号串的分界符推进符号栈，作为栈底符号。分析过程如下表:1414步骤符号栈输入符号串动作123456789101112##a#ab#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#S#aAabbcde#bbcde#bcde#bcde#cde#cde#de#e#e####准备.初始化移进移进规约(A→b)移进规约(A→Ab)移进移进规约(B→d)移进规约(S→

9、aAcBe)成功例：G[S]:S→aAcBeA→bA→AbB→d1515这一方法简单明了,不断地进行移进规约,关键是确定当前句型的句柄.说明:(1)例子的分析过程是一步步地规约当前句型的句柄该句子的唯一语法树为:aAcBeAbbdS注意两点：（a）栈内符号串+未处理输入符号串=当前句型（b）句柄都在栈顶实际上，以上分析过程并未真正解决句柄的识别问题1616(2)未真正解决句柄的识别.上述分析过程的怎样识别句柄的，主要看栈顶符号串是否形成规则的右部。这种做法形式上是正确的，但在实际上不一定正确。举例的分析过程可以说是一种巧合。因为不能认为:对句型xuy而言若有U→u，即Uu

10、就断定u是简单短语，u就是句柄，而是要同时满足ZxUy*6.2算符优先分析介绍(Operator-PrecedenceParsing)17171)这是一种经典的自底向上分析法，简单直观，并被广泛使用，开始主要是对表达式的分析，现在已不限于此。可以用于一大类上下无关的文法.运算法则:1.乘除的优先大于加减2.同优先级的运算符左大于右3.括号内的优先级大于括号外于是：4+8-6/2*3运算过程和结果唯一。2)称为算符优先分析是因为这种方法是仿效算术式的四则运算而建立起来的，作算术式的四则运算时，为了保证计算结果和过程