第05章_算符优先分析法.pptVIP

第1页，共30页，星期日，2025年，2月5日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识别成功第2页，共30页，星期日，2025年，2月5日2、自下而上分析法的核心问题：1)存在移进--归约冲突;2)存在归约--归约冲突;核心问题是寻找句型中的归约串进行归约。自下而上分析法第3页，共30页，星期日，2025年，2月5日一、算符优先分析法：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章优先分析法逆过程是规范归约第4页，共30页，星期日，2025年，2月5日另外一种推导：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)的计算结果第5页，共30页，星期日，2025年，2月5日2、算符优先分析技术的引进：必须给出文法中两个可能在句子中相继出现的终结符之间的优先关系。(1)相继出现：在句子中若有“…ab…”或“…aQb…”.(a,b∈ＶT,Q∈ＶN),则称a，b相继出现。(2)终结符号对优先关系的存储：优先关系表是一个矩阵M(a,b),a∈ＶT,b∈ＶT,矩阵行数、列数都为|Σ|+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第6页，共30页，星期日，2025年，2月5日对文法E→E+E|E-E|E*E|E/E|(E)|i + - * / ( ) i #+ ≯ ≯ ≮ ≮ ≮≯ ≮ ≯- ≯ ≯ ≮ ≮ ≮≯ ≮ ≯* ≯ ≯ ≯ ≯ ≮≯ ≮ ≯/ ≯ ≯ ≯ ≯ ≮≯ ≮ ≯( ≮ ≮ ≮ ≮ ≮≡ ≮) ≯ ≯ ≯ ≯ ≯ ≯i ≯ ≯ ≯ ≯ ≯ ≯# ≮ ≮ ≮ ≮ ≮≮如何获得一般的文法的优先分析表？#优先级低于其右部符号源程序中不会出现…)(…的情形如何获得一般的文法的优先分析表？第7页，共30页，星期日，2025年，2月5日3、优先表的构造方法：算符文法：给定上下文无关文法G=（VN，VT，P，S）中不存在形如A?…BC…的产生式，则称之为算符文法(OG—OperatorGrammar)(其中A,B,C∈ＶN)即：如果文法Ｇ中不存在具有相邻非终结符的产生式，则称为算符文法。算符优先文法:设文法G是一个不包含有空串产生式的算符文法,如果该文法中的任何终结符号对a,b之间,在三种关系中最多只有一种成立,则称该文法为算符优先文法。第8页，共30页，星期日，2025年，2月5日(1)求文法中每个非终结符P的首终结符集合FIRSTVT(P)①定义：FIRSTVT(P)={a|P?+a…或者P?+Qa…,a∈ＶT,P,Q∈ＶN}