编译原理张晶版 第五章 自底向上优先分析法

辽宁工程技术大学第五章优先分析法第五章优先分析法（1）语法分析•推导：—自上而下的语法分析过程—预测分析程序，递归下降分析法（最左推导）—注：要求文法是LL(1)文法•归约：—自下而上的语法分析过程—简单优先分析法，算符优先分析法、LR分析法第五章优先分析法（2）一、自下而上的语法分析过程•1.自下而上的语法分析过程思想—自下而上的语法分析过程是一个最左归约的过程，从输入串开始。朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程—注意：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列•2.自下而上分析的PDA第五章优先分析法（3）a+b………#语法分析程序语法表输出带#—工作方式：“移进——归约”方式—即：自左至右把输入串的符号一个一个移进栈，在移进过程中不断查看栈顶符号串，一旦形成某个句型的句柄时，就将此句柄用相应的产生式左部替换（归约），若再形成句柄，就继续替换，直到栈顶不再形成句柄为止，然后继续移进符号，重复上面的过程直到栈顶只剩下文法的开始符号，输入串读完为止，这样就认为识别了一个句子。第五章优先分析法（4）注：1）初态时栈内仅有栈底符“#”，读头指在最左边的单词符号上.2）语法分析程序执行的动作：a)移进：读入一个单词并压入栈内，读头后移；b)归约：检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号.c)识别成功：移进—归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符.d)识别失败.一、自下而上的语法分析过程第五章优先分析法（5）例如：有文法如下：(1)SaAcBe(2)Ab(3)AAb(4)Bd问语句abbcde是不是该文法的合法语句?一、自下而上的语法分析过程第五章优先分析法（6）步骤栈输入串输出串动作0#abbcde#1#abbcde#移进2#abbcde#移进3#aAbcde#2归约4#aAbcde#移进5#aAcde#2,3归约6#aAcde#移进7#aAcde#移进8#aAcBe#2,3,4归约9#aAcBe#移进10#S#2,3,4,1归约11识别成功SaAcBeAbdb第五章优先分析法（7）二、确定的自下而上语法分析1.优先分析器（PrecedenceParser)•简单优先分析法•算符优先分析法2.LR分析器第五章优先分析法（8）5.1简单优先分析法一、基本思想1.相邻文法符号之间的优先关系•在句型中，句柄内各相邻符号之间具有相同的优先级，相同优先级用“”•由于句柄要先归约,所以规定句柄两端符号的优先级要比位于句柄之外的相邻符号的优先级高,优先级低于表示为“﹤”,优先级高于表示为“＞”•某句型中:N1…..Ni-1Ni……Nj＞Nj+1…..Nn.......第五章优先分析法（9）5.1简单优先分析法一、基本思想2优先分析法的基本思想•句型中的Ni…..Nj是句柄，语法分析程序可以通过寻找Ni-1﹤Ni和Nj＞Nj+1来确定句柄的头尾，从而确定句柄进行归约。..第五章优先分析法（10）5.1简单优先分析法二、简单优先文法1.定义：一个文法G，如果它不含e产生式，也不含任何右部相同的不同产生式，并且它的任何符号对（X，Y）——X，Y是终结符或非终结符——或者没有关系，或者存在优先级相同或低于、高于等关系之一，则这是一个简单优先文法。2.优先级别定义：•XY当且仅当G中含有形如P……..XY……..•XY当且仅当G中含有形如P…..XQ…..的产生式,其中QY……•XY,当且仅当文法G的终结符,G中P……QR……,且Q…..X,Y∈first(R).•＜＞•第五章优先分析法（11）•对任何X,若文法开始符号SX……,则#X;若有S…..X,则X#5.1简单优先分析法二、简单优先文法++•＜＞•三、简单优先分析的思想1、简单优先矩阵：根据优先关系的定义，将简单优先文法中各文法符号之间的这种关系用一个矩阵表示，称作简单优先矩阵第五章优先分析法（12）•PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入，直到最后栈内只剩下开始符号，输入串读到“#”为止，此时识别正确。四、简单优先分析法的优缺点优点：算法理解简单，技术简单缺点：适用范围小，分析尺寸太大5.1简单优先分析法第五章优先分析法（13）5.2算符优先分析法一、什么是算符优先分析法1.算符优先分析法：•所谓算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法.2.算符优先分析法的特点：•简单直观，特别方便于表达式分析，易于手工实现，是自下而上的归约过程，但未必按照句柄归约.3.算符优先分析法的关键：•规定算符（终结符）的优先级及结合性质•例如：8+7-6*5/3的运算第五章优先分析法（14）5.2算符优先分析法•例如：表达式文法：EE+E|E-E|E*E|E/E|(E)|i对这个二义文法可能会有好几个规范推导和归约，真正运算时也有几种不同结果，但若按算符优先顺序和结合规则的规定进行归约，句子的归约过程就是唯一的，运算结果也唯一.注：对所有的终结符定义某种优先关系，借助这种关系找出可归约的串，进行归约，达到自下而上分析的目的.第五章优先分析法（15）如：i+i-i*(i+i)归约过程如下：1）i+i-i*(i+i)设算数级别最高，最先归约2）E+i-i*(i+i)3)E+E-i*(i+i)+,-同级，先归约左边“+”4）E-i*(i+i)5)E-E*(i+i)-,×不同级，先归约右边“×”6)E-E*(E+i)7)E-E*(E+E)先算括号内，再算括号外8)E-E*(E)9)E-E*E先归约“×”，再归约“+”10)E-E11)E第五章优先分析法（16）1、确定运算符的优先级•算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作•要完成运算符间优先级的比较，可以先定义各种可能相继出现的运算符的优先级，并表示为矩阵的形式，使得能够在分析中通过查询矩阵元素而得到算符之间的优先关系5.2算符优先分析法二、算符优先分析技术的改进第五章优先分析法（17）2.对于任何两个可能相继出现的终结符a,b，若具有以下形式：“……..ab…….”,“….aQb….”,其中Q是某非终结符，则a,b之间的关系为：1）ab,a的优先级低于b2)ab,a的优先级等于b3)ab,a的优先级高于b4)若ab在任何情况下都不可能相继出现，则ab无关系5.2算符优先分析法二、算符优先分析技术的改进＞••＜.第五章优先分析法（18）5.2算符优先分析法+＊（）i#+＊()i#右符左符＞•＞•＞•＞•＞•＞•＞•＞•＞•＞•＞•＞•＞•＞•＞••＜•＜•＜•＜•＜•＜•＜•＜•＜•＜•＜•＜•＜.第五章优先分析法（19）•注：１）在此表中，＋包括－，＊包括／，“＃”是一个特殊符号，用于语句的开始符号和结束符号.•２）这张表满足是通常数学上的习惯约定，值得注意的是：－1).运算量i的优先级高于算符－2).语句开始和结束符号“＃”与终结符a相继出现时，应该有＃a或a#,以此来保证语句内先归约•（）表示括号是成对归约的•优先关系和代数中的大于小于关系不同,ab并不意味着ba终结符所处的左右位置很重要.5.2算符优先分析法.＞••＜•＜＞•第五章优先分析法（20）3、直观算符分析法5.2算符优先分析法二、算符优先分析技术的改进a+b………#直观算符优先法优先表OPND操作数Q#OPTR操作符p下推栈第五章优先分析法（21）3、直观算符分析法•1）直观算符分析法使用两个工作栈：一个算符栈（OPTR）存放运算符和括号，一个算量栈（OPND)用于存放操作数和运算结果；OPTR的栈顶符号用Q表示，OPND的栈顶符号用p表示•2）初态时，OPND为空，OPTR只有”#“•直观算符分析算法如下：5.2算符优先分析法二、算符优先分析技术的改进第五章优先分析法（22）OPND=“”;OPTR=“#”flag=true;advance;/*读入一个单词*/Whileflag{IfQ=“#”andSYM=“#”thenflag=false/*成功*/elseifQ=“(“andSYM=“)”then/*匹配括号对*/{OPTR栈顶出栈；advance}elseifSYM是算量then/*移进算量*/第五章优先分析法（23）{SYM入OPND栈；advance；}elseifQSYMthen/*移进算符*/{SYM入OPTR栈；advance；}elseifQSYMthen/*归约*/{OPND栈顶两个元素p1,p2弹出；弹出OPTR栈顶元素Q;将p1Qp2的结果入OPND栈；}elseERROR}}•＜＞•第五章优先分析法（24）4.此算法的优缺点•优点：1）简单明了，易于手工实现，适于分析各种算术表达式•2）使用此算法可以很方便地把表达式译成目标指令，只要在归约时把计算p1Qp2值改为生成相应指令（Q,p1,p2,T)即可缺点：1）算法采用两个栈，有时会把错误句子当成合法句子；而且。它也无法指出输入串出错位置2）对于含有单目正负号的算术表达式不好处理。因为负号的优先级高于加减法，低于乘除法，但负号的形式与减号相同，不容易识别。5.2算符优先分析法二、算符优先分析技术的改进第五章优先分析法第五章优先分析法（25）1.算符文法的定义—给定上下文无关文法G，若G中所有产生式右部都不包含两个相继的非终结符，则G为算符文法—注：算符文法保证了两个运算符之间只有一个操作数2.算符优先文法定义：•设G是一个不含有空串产生式的算符文法，并设a,b∈VT;P.Q,R∈VN定义关系：5.2算符优先分析法三、算符优先文法及优先表的构造第五章优先分析法（26）2.算符优先文法定义：•ab当且仅当G中含有形如P….ab….产生式，或者P…aQb….产生式；•ab当且仅当G中含有形如P...aR…产生式,其中Rb….或RQb…..;•ab当且仅当G中含有形如P…Rb…,产生式,其中R….a,或R….aQ.•若G中任何终结符序偶（a,b)至多满足上述关系之一，则称G为算符优先文法（OPG)5.2算符优先分析法三、算符优先文法及优先表的构造.•＜++＞•++第五章优先分析法（27）3.算符文法和算符优先文法定义的意义•这两个定义相当于对文法的句型和可归约的短语做了如下规定：—设A1A2…Ai-1AiAi+1…An是文法G的一个句型.—1.若Ai∈VN，则Ai-1,Ai-1∈VT,即不允许出现相继两个非终结符；—2.若B1B2…Bm是当前可归约短语，并可归约为Ai，则：5.2算符优先分析法三、算符优先文法及优先表的构造第五章优先分析法（28）a)B1B2…Bm中不能有相继两个非终结符且相邻的终结符优先级全相等；b)对于B1B2…Bm中首终结符b有Ai-1bc)对于B1B2…Bm中尾终结符b有bAi+1•注：实际上，可归约短语是某产生式右部符号串，所以通过检查G的每一个产生式的每个候选式。可以查找出任意优先级相同的终结符序偶，要找出所有满足关系和的终结符序偶，就要找出各非终结符P的首终结符集和尾终结符集。•＜＞••＜＞•第五章优先分析法（29）4.求各非终结符P的首终结符集和尾终结符集1）定义：•首终结符集FIRSTVT(P)=—{a|Pa….或PQa….,a∈VT;P,Q∈VN}•尾终结符集LASTVT(P)=—{a|P…..a或P….aQ,a∈VT;P,Q∈VN}•有了这两个集合后，就可以通过检查每个产生式的每个候选式，确定满足关系和的所有终结符序偶5.2算符优先分析法三、算符优先文法及优先表的构造•＜＞•++++第五章优先分析法（30）5.2算符优先分析法•例如：假定产生式右部有形如：….aP…串，则对于任何b∈FIRSTVT(P),有ab;•假定产生式右部有形如：…..Pb…..的串，则•对于任何a∈LASTVT(P),有ab;例：设文法G的产生式为：SaAcBeAAb|bBd计算每个非终结符的FIRSTVT与