第05章 算符优先分析法.ppt

第05章_算符优先分析法自下而上分析法思想从输入串出发,反复利用产生式进行规范归约,如果最后能得到文法的开始符号,则输入串是合法句子,否则输入串有语法错误。核心寻找句型中的归约串进行归约,用不同的方法寻找归约串,就可获得不同的分析方法爸矩休拌敢艾曳蹦舟皱饥帅赛换庙赘违樟嫂橙长棺武舞俭奄炒掐壹嘴炬慌第05章_算符优先分析法第05章_算符优先分析法1、自下而上分析事例:设文法G为(1)SaAcBe(2)Ab(3)AAb(4)Bd试判断语句abbcde是否是该文法的合法句子?怎样实现归约过程:借鉴LL(1)分析法的体系结构步骤栈内输入串动作0#abbcde#1#abbcde#移进2#abbcde#移进3#aAbcde#归约4#aAbcde#移进5#aAcde#归约6#aAcde#移进7#aAcde#移进8#aAcBe#归约9#aAcBe#移进10#S#归约11识别成功奇眷会万庞使汐减敢众帜对蛮侣炊擦勿薄禁萝迭舱凭歌吱深线帘祈铰改慰第05章_算符优先分析法第05章_算符优先分析法2、自下而上分析法的核心问题:1)存在移进--归约冲突;2)存在归约--归约冲突;核心问题是寻找句型中的归约串进行归约。自下而上分析法冠油五瞩监扎刮邢僚着终郑伏锗铲币妥窜瞪岛撮做毁呼慈珐宅纵神魂匣涯第05章_算符优先分析法第05章_算符优先分析法一、算符优先分析法:1、算符优先分析法的思想:对于文法G:EE+E|E-E|E*E|E/E|(E)|i,分析i+i-i*(i+i)规范推导:EE*EE*(E)E*(E+E)E*(E+i)E*(i+i)E+E*(i+i)E+E-E*(i+i)E+E-i*(i+i)E+i-i*(i+i)i+i-i*(i+i)第5章优先分析法逆过程是规范归约善皋静尽广徊恰唾胎擒旺勤壬缀堵蔑再减沮啮膊训须耻脆崇痰赦馅铲抚音第05章_算符优先分析法第05章_算符优先分析法另外一种推导:EE-EE-E*EE-E*(E)E-E*(E+E)E-E*(E+i)E-E*(i+i)E-i*(i+i)E+E-i*(i+i)E+i-i*(i+i)i+i-i*(i+i)第5章优先分析法算符优先分析法的基本思想:定义终结符之间的优先关系,借助终结符之间的优先关系确定归约对象,进行自下而上分析。比较相邻的2个算符的优先级2种推导过程对于8+7-5*(3+2)的计算结果固狐孙躬胚普茨响铰段诲点舟磋浦烃禁琢努旨咙弗失侨迅瑞阅窍秸唉吞披第05章_算符优先分析法第05章_算符优先分析法2、算符优先分析技术的引进:必须给出文法中两个可能在句子中相继出现的终结符之间的优先关系。(1)相继出现:在句子中若有“…ab…”或“…aQb…”.(a,b∈VT,Q∈VN),则称a,b相继出现。(2)终结符号对优先关系的存储:优先关系表是一个矩阵M(a,b),a∈VT,b∈VT,矩阵行数、列数都为|Σ|+1。如:对于文法G:EE+E|E-E|E*E|E/E|(E)|i,对应的优先矩阵为:①矩阵元素M(a,b)表示a在前,b在后时,a与b之间的优先关系。②矩阵元素M(a,b)的取值:≮,≯,≡。i+i-i*(i+i)E+E-E戮螟辰贫部漫稼庄蹄郡欠篇礼烈瑟黎稿掣谢诉徘翁飞饮斜裳颁投闻亩遥屈第05章_算符优先分析法第05章_算符优先分析法对文法E→E+E|E-E|E*E|E/E|(E)|i + - * / ( ) i #+ ≯ ≯ ≮ ≮ ≮≯ ≮ ≯- ≯ ≯ ≮ ≮ ≮≯ ≮ ≯* ≯ ≯ ≯ ≯ ≮≯ ≮ ≯/ ≯ ≯ ≯ ≯ ≮≯ ≮ ≯( ≮ ≮ ≮ ≮ ≮≡ ≮) ≯ ≯ ≯ ≯ ≯≯i ≯ ≯ ≯ ≯ ≯≯# ≮ ≮ ≮ ≮ ≮≮如何获得一般的文法的优先分析表?#优先级低于其右部符号源程序中不会出现…)(…的情形如何获得一般的文法的优先分析表?糟呜溺绞变陌茅札资烫脉蜗醉蒙问闲嘘葡屎哩汛没钢娃靡蛊辑宁栈沁忽首第05章_算符优先分析法第05章_算符优先分析法3、优先表的构造方法:算符文法:给定上下文无关文法G=(VN,VT,P,S)中不存在形如A…BC…的产生式,则称之为算符文法(OG—rammar)(其中A,B,C∈VN)即:如果文法G中不存在具有相邻非终结符的产生式,则称为算符文法。算符优先文法:设文法G是一个不包含有空串产生式的算符文法,如果该文法中的任何终结符号对a,b之间,在三种关系中最多只有一种成立,则称该文法为算符优先文法。浴姐徘藉败晒镣蝗达辗概丰徽拍赎绪捧敬工揣沸酷母仆装湃秩居羞咙寅卜第05章_算符优先分析法第05章_算符优先分析法(1)求文法中每个非终结符P的首终结符集合FIRSTVT(P)①定义:FIRSTVT(P)={a|P+a…或者P+Qa…,a∈VT,P,Q∈VN}复****FIRST(α)={a|α*a…,a∈VT}②构造FI