简单优先和算符优先分析方法课件.ppt

1,编译原理,主 讲：温 璞责任教师：蒋慧平,2,第六讲简单优先和算符优先分析方法,3,本讲主要内容,简单优先文法及其分析算法算符优先文法及其分析算法优先函数的构造,4,简单优先文法,之所以称为简单是因为在可能称为句柄的那些符号串两边各取一个符号就能帮助判断它是否是句柄,5,简单优先分析算法描述,6,例6.13 运用简单优先分析算法检查(a),a)是否是文法G42的一个句子,文法G42S：S(R)|a| RTTS,T|S,7,简单优先分析方法的局限性只适用于简单优先文法一般的程序设计语言不是简单优先文法不实用，因为存在于两个符号之间的优先关系常多于一种算符优先方法对以上情况有所改善,8,算符优先分析方法,算符优先分析方法根据算符之间的优先关系来设计的一种字下而上语法分析方法有利于表达式的分析不是一种规范归约法算符优先分析就是：定义算符之间（终结符）的某种关系，借助于这种优先关系寻找“可归约串”并进性归约,9,算符优先文法,算符文法终结符之间存在的三种优先关系,10,算符优先文法,11,例6.15,文法G44S：EE+T|T TT*F|FF(E)|i,12,OPG优先关系的构造,定义如下集合它们的传递闭包定义如下,13,14,15,算法描述,16,例6.16,文法G44S：EE+T|T TT*F|F F(E)|i,17,例6.16,文法G44S：EE+T|T TT*F|F F(E)|i,18,19,由于未对非终结符定义算符优先关系，所以不能使用算符优先关系去查找由单个非终结符组成的句柄引入素短语概念替代简单优先关系中的句柄概念，进行规约,20,素短语及句型的分析,21,示例,22,算符优先分析算法,23,24,25,26,文法G44S：EE+T|T TT*F|F F(E)|i,27,28,优先函数,在实际实现算符优先分析算法时，一般不直接用前述的优先表，而是用两个优先函数f和g.把每个终结符与两个自然数相对应,29,使用优先函数优点可减少优先矩阵的存储空间便于比较运算使用优先函数缺点原先不存在优先关系的两个终结符，由于与自然数相对应，变得可比较了。可能会掩盖输入串的某些错误.优先函数构造方法：Bell法和Floyd法,30,优先函数构造：Bell方法,31,优先函数构造：Floyd方法,32,小结,简单优先分析方法简单优先关系矩阵计算句柄的寻找算符优先分析方法算符优先关系计算最左素短语的寻找构造优先函数的两个方法Bell法和Floyd法,33,The End. Thanks!,