编译原理清华大学第6章自底向上优先分析法详解.ppt

第6章 自底向上优先分析(Bottom-up Parsing);自底向上分析的一般过程：; 给定句型找句柄的步骤： 短语 简单短语 句柄;句型的短语、简单短语和句柄;例：给定文法G： E→T | E+T | E－T T→F | T*F | T／F F→i | (E) 符号串（T+i）*i－F是文法G的一个句型，求其短语、简单短语和句柄。;其简单短语有4个： 1. E? (E +i) *i－F,E?T 则有： T 2. E? (T +F) *i－F,F?i 则有： 第一个i 3. E? (T +i) *F－F,F?i 则有： 第二个i 4. E? (T +i) *F－T,T?F 则有：F 句柄有1个： T;例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E)并假定输入串为（i+i)*i，考察自底向上的分析过程。;分析过程图表：;6.2 简单优先方法(Simple-precedence Parsing);这种方法的基本思想为：;(1) 有形如 U→… SiSj…的产生式;Sj…;… Si;… Si;6.2.3 优先关系：; 在实际使用这些优先关系去识别句子时，我们希望采用一种简洁的方法去表示这些关系，优先关系矩阵是一种常用的方式。;优先关系矩阵：;构造优先关系矩阵的一种简便方法：;6.2.4 简单优先文法的分析方法：;(2) 简单优先文法的句柄;(3) 分析算法的要点：;(4) 语法分析程序：;此五部分是语法分析所涉及到的几部分;6.3 算符优先分析 ( Operator-precedence Parsing ); 在分析到第6步时，栈顶的符号串为E+E，若只从移进-归约的角度讲，栈顶已出现了产生式(1)的右部，可以进行归约，但从通常四则运算的习惯来看应先乘后加，所以应移进，这就提出了算符优先的问题。 ;表达式的文法按公认的计算顺序规定优先级和结合性如下： ① ↑优先级最高。遵循右结合。 ② *,/ 优先级其次。服从左结合。 ③ +，- 优先级最低。服从左结合。 ④ 对(，)规定括号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号。 对于句子括号#号规定与它相邻的任何运算符的优先性都比它大。此外，对运算对象的终结符i其优先级最高。 ;综上所述，对表达式运算符的优先关系构造如表6.4。 ; 很显然所给表达式文法是二义性的，但人为直观地给出运算符之间的优先关系，由优先关系表6.4可知这种优先关系是唯一的，有了这个优先关系表对前面表达式的输入串i1+i2*i3归约过程就能唯一确定了，也就是说在表6.3分析到第(6）步时，栈中出现了#E+E，可归约为E，但当前输入符为*，由于规定 + ＜· *，所以应移进。 ;6.3.1 算符优先文法及优先表构造 ;(2)算符优先关系的定义;(3) 算符优先文法的定义 ;(4) 算符优先关系表的构造 ;例6.5：现在可用上述算法计算下列表达式文法的算符优先关系。 若有表达式文法为： (0)? E′→#E# (1)? E→E+T (2)?? E→T (3) T→T*F (4)??T→F (5)? F→P↑F|P (6)?? P→(E) (7) P→i ;为了求＜·和·＞关系 ，需先由定义6.2计算每个非终结符的FIRSTVT集合和LASTVT集合，结果为： FIRSTVT(E′)={#} FIRSTVT(E)={+，*，↑，(，i} FIRSTVT(T)={*，↑，(，i} FIRSTVT(F)={↑,(，i} FIRSTVT(P)={(，i} LASTVT(E′)={#} LASTVT(E)={+，*，↑，)，i} LASTVT(T)={*，↑，)，i} LASTVT(F)={↑，)，i} LASTVT(P)={)，i} 在计算每个非终结符的FIRSTVT集合和LASTVT集合时，可先考虑文法中含有E→T，T→F，F→P形式的产生式，由定义6.2的推论可知P的FIRSTVT集合和LASTVT集合也属于F的FIRSTVT集合和LASTVT集合，同样F的也属于T的，T的也属于E的。集合中的其它元素可根据定义由产生式直接计算。 ;然后逐条扫描产生式寻找终结符在前非终结符在后的相邻符号对和非终结符在前终结符在后的相邻符号对，即产生式右部有形如