编译原理笔记（5）

1. 自下而上的语法分析

   • 从输入串开始逐步进行归约，直到文法的开始符号
     • 归约：根据产生式规则，把产生式的右部替换成左部符号
   • 从语法树的叶子节点开始进行构造语法树
   • LR 分析法、算符优先分析法

2. 自下而上的语法分析需要注意的部分

   • 核心为识别可归约串
   • 分析树和语法树可能不同

3. 短语

   • 如果文法的开始符号 S 可以推出一个句型，句型中一个非终结符 A，可以经过至少一步推出字符序列 b ，则称 b 为文法的一个短语
   • 形象上，将句型的语法树画出，该语法树的任意子树的叶子结点从左至右排列，组成的字符序列都是句型的短语
   • 短语是针对句型而言的

4. 直接短语

   • 若 A 一步推出了字符序列 b ，则 b 称为直接短语
   • 形象上，语法树的两层子树的叶子结点从左至右排列，组成字符序列为句型的直接短语
   • 最左直接短语称为句柄

5. 终结符的优先关系

   • 任何两个相继出现的终结符 a 、b 终结符都有可能存在下列关系：

     

   • 算符优先是左右顺序严格的，也即

     
     这意味着左侧的终结符 a 优先级低于右侧的终结符 b

   • 同一个终结符在左侧和右侧时，优先级也会不同，如

     

6. 算符文法

   • 一个文法的右部中，不存在连续出现的非终结符，我们称该文法为算符文法

7. 算符优先文法

   • 一个算符文法中，左侧的终结符 a 和右侧的终结符 b 只有一种优先级关系，则我们称该文法为算符优先文法

8. FirstVT 集合 和 LastVT 集合

   • 
   • 

9. 构造优先关系表的算法

   

10. 素短语

• 至少含有一个终结符，且不含有更小的素短语的短语称为素短语
• 首先只含有一个终结符的短语为素短语
• 接着遍历每个短语，判断每个短语是否满足以上条件
• 最左侧的素短语称为最左素短语

11. 算符优先分析过程

栈	关系	当前字符	字符串	操作
#…
#…a	a<b	b	b…	移进
#…ab	b=c	c	c…	移进
#…	…	…	…	…
#…abc	c>d	d	d…	规约
#…	…	…	…	…
#S#	…	…	…	结束

12. 算符优先分析树、规范规约树、语法树
    • 语法树有可能为最左推导、最右推导对应的语法树
    • 规范规约的语法树则为最右推导对应的语法树，过程中规范规约的目标是当前句型的句柄（最左直接短语，包含单独一个的非终结符）
    • 而算符优先分析树，过程中的目标是最左素短语（至少包含一个终结符，单独一个非终结符不符合）
    • 综上所述，算符优先分析的对象为句型中的最左素短语，规范规约的对象为句型中的句柄，由于这个区别导致二者的画出的树不同。