编译原理复习笔记————第四章：语法分析

编译原理之——语法分析

语法分析的功能、基本任务

• 功能：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查
• 任务：识别符号串S是否为某语法成分

自顶向下分析

基本思想

一般过程

消除左递归

消除直接左递归

1. 使用扩充的BNF表示来改写文法

   BNF是什么：

   

   例：

   

   • 规则一：

     

   • 规则二：

     

2. 将左递归改为右递归

   • 规则三：

     

例：

消除回溯

1. 改写文法

   

递归子程序法（递归下降分析法）

具体做法：对语法的每一个非终结符都编一个分析程序，当根据文法和当时的输入符号预测到要用某个非终结符区匹配输入串时，就调用该非终结符的分析程序

LL分析法

由三部分构成：

• 分析表
• 符号栈
• 执行程序

例：

分析表的构造

• FIRST集：简单来说就是某个符号中的第一个终结符（无论是直接出现在该符号中还是间接出现在该符号中）

  

  • 构造算法：

    

    

• FOLLOW集：简单来说就是紧跟着某个符号的终结符（无论是直接出现在该符号后面还是间接出现在该符号后面）

  注：FOLLOW中不能有ε

  

  • 构造算法：

    

• 分析表

  • 构造算法：

    

    能用上述算法构造分析表的文法为LL（1）文法

LL（1）文法

• 定义：分析表中无两条以上规则

• 充要条件：

  

• 如果文法有左递归或二义性，则必不是LL（1）文法

自底向上分析（重点）

基本思想

分析过程：

移进–规约分析

分析过程

例：

算符优先分析

仿效四则运算过程，预先规定相邻终结符之间的优先 关系，然后利用这种优先关系来确定句型的“句柄”， 并进行规约

算法：当栈顶项(或次栈顶项)终结符的优先级大于栈外的终结符的优先级则进行规约，否则移进

例：

算符优先文法（OPG）

• 算符文法（OG）：两个非终结符不能相邻

• 优先关系：

  

• 算符优先文法（OPG）：任意两个终结符之间只有一种优先关系

例：

构造优先关系矩阵

• 构造FIRSTVT（U）的算法

  

• 构造LASTVT（U）的算法

  

最左素短语

LR分析法

LR分析器

• 活前缀：

  

• 状态转移表（GOTO表）

• 分析动作表（ACTION表）

  • 移进：s
  • 规约：r
  • 接收：acc
  • 出错：error

例：

构造LR分析器

例：

LR（0）文法

SLR文法（SLR文法必定是LALR文法和LR文法）

规范LR文法

LALR文法

附图：各文法对比