编译原理2——词法分析&语法分析

第三章 词法分析

单词的描述

• 正则表达式（RE）
  • 可以由较小的正则表达式按照规则递归地构建，每个正则表达式定义一个语言。
• 正则语言：可以用RE定义的语言叫做正则语言或正则集合
• 正则文法与正则表达式等价

单词的识别

• 有穷自动机（FA）

  • 离散的输入输出信息&又穷数目的内部状态
  • 系统只需根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为

• FA模型：输入带、读头、有穷控制器

• FA的表示：转换图
• FA定义（接收）的语言

• 最长字串匹配原则

• FA的分类：

  • 确定的FA（DFA）
    • $M = (S, \sum, \delta,s_0,F)$
      • S：有穷状态集
      • $\sum$：输入字母表（不包括$\varepsilon$）
      • $\delta$：转换函数：将$S \times \sum$ 映射到$S$
      • $s_0$：开始状态
      • $F$：接收（终止）状态集合
  • 非确定的FA（NFA）
    • $M = (S, \sum, \delta,s_0,F)$
    • $\delta$：转换函数：将$S \times \sum$ 映射到 $2S$
  • 带有”$\varepsilon-$边”的NFA
    • $\delta$：转换函数：将$S \times （\sum \cup\{\varepsilon\}$ 映射到$2S$
• 子集构造法：从NFA构造等价DFA

错误处理

• 错误类型：
  • 单词拼写错误
  • 非法字符
• 错误检测：对应信息为空且不是终止，进入错误处理

• 错误处理：查找最近的终态对应字符

  • 找到将前面识别为一个单词，并从该字符后重新识别
  • 找不到则进行错误恢复

• 错误恢复：恐慌模式

词法分析器生成工具Lex

第四章 语法分析

语法分析 上

主要任务：根据给定文法识别输入句子各个成分以构造分析树

大部分程序设计语言的语法构造可以用CFG来描述，CFG以token作为终结符

语法分析的种类

• 自顶向下的分析——推导
• 自底向上的分析——归约

自顶向下的分析

替换哪个非终结符？用哪个候选式替换？

• 最左推导：总是选择每个句型的最左非终结符进行替换
  • 对应最右归约
• 最右推导：总是选择每个举行的最右非终结符进行替换
  • 对应最左归约

自底向上的分析中总是采用最左归约，因此最左归约成为规范归约，而最右推导则相应称为规范推导

自顶向下的语法采用最左推导

• 递归下降分析（可能需要回溯，效率较低）

  • 同一非终结符的多个候选式存在共同前缀，将导致回溯现象

  • 左递归文法会陷入无限循环

    • 直接左递归和间接左递归

    • 消除直接左递归——代价：引进了一些非终结符和空产生式

      

  • 提取左公因子——意义：推迟决定，做出更正确的选择

• 预测分析（不需要回溯、确定的自顶向下分析方法）

预测分析法

• S_文法：简单的确定性文法（不包含空产生式）

  • 右部终结符开始且部首终结符不同

• Follow集（后继符号集）：对于非终结符A，可能在某个句型种紧跟在A后面的终结符的集合

  • 若A为某个句型的最右符号，则将 ‘$’ 加入

• Select集（可选集）：可以选用该产生式进行推导时对应的输入符号的集合

• q_文法

  • 每个产生式右部以终结符开始或为空，左部相同的产生式select集不相交

• First集（串首终结符集）：可从给定文法符号串推导出的所有串首终结符构成的集合

• Select集计算：

  

• LL（1）文法

  

• LL(1)文法的分析方法：

  • 递归的预测分析法：为每个非终结符编写对应的过程

  • 非递归的预测分析法（表驱动的预测分析）：构造自动机

  • 预测分析法的实现步骤：构造文法、改造文法、求三个集、构造分析表、实现分析过程

  • 错误检测：

    • 栈顶终结符与输入不匹配
    • 预测结果为空

  • 错误恢复：恐慌模式+同步词法单元

    

语法分析 中

自底向上的语法分析

最左归约（反向构造最右推导）

• 通用框架：移入-归约分析
  • 对输入串从左到右扫描，将零个或多个输入符号移到栈的顶端，直到可以发生规约，则归约。
  • 循环直到检测到错误或栈中包含开始符号且输入缓冲区为空
• 句柄——句型的最左直接短语
• 移入-归约的四种动作：移入、归约、接收、报错

LR分析法

三种状态——移进状态、待约状态、规约状态

LR分析器总体结构

算法过程

LR（0）分析

• 右部某位置标有圆点的产生式称为相应文法的一个LR（0）项目
  • 项目描述了句柄识别的状态
  • 空产生式只有一个项目$A\rightarrow ·$
• 增广文法：如果G是一个以S为开始符号的文法，则G的增广文法G‘就是增加新开始符号S’，并增加$S’\rightarrow S$
  • 目的：使文法开始符号仅出现在一个产生式的左边，使分析器只有一个接受状态。
• 后继项目：同一个产生式的项目，圆点位置只差一个符号
• 项目集闭包：等价的项目组成
  • 每个项目集闭包对应自动机的一个状态
• CLOSURE函数
• GOTO函数
• 冲突：移入/归约冲突和归约/归约冲突
  • LR（0）文法不能解决所有文法（CFG不是LR（0）文法）

语法分析 下

SLR分析

• 移入/归约冲突：移入项目的移入符号在规约项目规约后的follow集中

LR（1）分析

• 对于某个产生式的归约，在不同的使用位置要求不同的后继符号

  • 在特定位置，A的后继符号集合使FOLLOW（A）的子集

• 展望符

  • 继承的后继符和自生的后继符
• 如果除展望符外，两个LR（1）项目集相同，则称这两个是同心的

LALR分析

二义性文法的LR分析

• 二义性文法都不是LR的
  • 使用优先级和结合性解决
• 应该保守使用二义性文法，且有严格控制

LR分析中的错误处理

• 错误检测——分析表中的报错条目

• 错误恢复：

  • 恐慌模式

    

  • 短语层次

    • 检查每一个报错条目后手动判断可能的错误因素并构造恢复过程

---