I. 词法分析

词法分析器作用：

  1. 扫描源程序字符流
  2. 按照源语言的词法规则识别出各类单词符号
  3. 产生用于语法分析的记号序列
  4. 词法检查
  5. 创建符号表 — 为语法分析使用
  6. 接口：跳过注释、标注错误信息

一、词法分析程序与语法分析程序的关系

1.1 词法分析程序作为独立的一遍

1.2 词法分析程序作为语法分析程序的子程序

词法分析相当于函数，语法分析每一次需要记号时即调用词法分析函数获得记号。

这种操作的好处可以避免中间文件、省去取送记号的工作。

1.3 词法分析程序与语法分析程序作为协同程序

这种方法不常用。

二、词法分析程序的输入与输出

2.1 配对缓冲区

哨兵！！！(EOF)

把一个缓冲器分为大小相同的两半，每半各含N个字符，一般N=1KB或4KB。为了使得判断更为优化，在每个半区后面加上EOF。 这种做法是为了让缓冲区可以处理超出其范围的字符串。

2.2 词法分析程序的输出——记号

  1. 记号：某一类单词符号的类别编码，如id，num
  2. 模式：某一类单词符号的构成规则，如“有字母开头的字母字符串”
  3. 单词：某一类单词符号的具体实例，如hello
  • 记号的属性
    • 作用：记号影响语法分析的决策，属性影响记号的翻译。

三、记号的描述和识别

3.1 词法与正规文法

描述语言的标识符、常数、运算符和标点符号等记号的文法

3.2 记号的文法

  1. 标识符 描述标识符集合的正则表达式： 标识符的正规文法(右线性文法)
  2. 常数

    • 整数 描述整数结构的正则表达式：

    • 无符号数

  3. 运算符
  4. 分界符
  5. 关键字

四、词法分析程序的设计与实现

五、软件工具LEX

II. 语法分析

一、简介

  1. 语法分析程序的任务
  • 从源程序记号序列中识别出各类语法成分
  • 进行语法检查
  1. 三种分析器的关系
  2. 语法分析程序的作用
  • 输入：记号流/记号序列
  • 工作依据：语法规则
  • 功能：将记号组合成语法成分、语法检查
  • 输出：分析树
  • 错误处理
  1. 常用的分析方法：
  • 自顶向下的分析方法
  • 自底向上的分析方法

对输入符号串的扫描顺序：==自左向右==

  1. 错误恢复策略：
  • 紧急方式恢复： 抛弃出错的语法结构，方法简单，不会陷入死循环
  • 短语级恢复： 局部纠错，防止发生死循环
  • 出错产生式： 扩充文法，增加产生错误的产生式
  • 全局纠错： 时空代价太大，只有理论上的意义

二、自顶向下分析方法

1. 递归下降分析

为输入符号串建立一个最左推导序列的过程

  • 文法的==每一个非终结符号对应一个递归过程==，即可实现这种带回溯的递归下降分析方法。
  • 每个过程作为一个布尔过程，一旦发现它的某个产生式与输入串匹配，则用该产生式展开分析树，并返回true，否则分析树不变，返回false。

问题：回溯、穷举

2. 递归调用预测分析

  1. 如何克服回溯 让每一个候选式的开始符号各不相同

  2. 对文法的要求

    • 文法不含左递归
    • 非终结符号A的所有候选式的首符集两两互不相交

  3. 预测分析程序的构造

    • 预测分析程序的转换图
    • 转换图的工作过程
    • 转换图的化简
    • 预测分析程序的实现
      • 如果是终结符，则程序为==匹配该终结符==，输入指针移向下一个记号
      • 如果是非终结符，则程序为==调用==该非终结符所对应的子程序，输入指针不移动
      • 如果有两个以上的射出边，则使用==分枝语句==在程序中产生相应的分支部分

  4. LL(1)文法 (1) FIRST集合的构造 (2) FOLLOW集合的构造 (3) LL(1)文法的定义

3. 非递归预测分析

使用一张分析表和一个栈联合控制，实现对输入符号串的自顶向下分析。

  1. 预测分析程序的模型及工作过程

判断LL(1)文法的标准，用第一种方法更为简单

关键：决定哪个产生式运用于非终结符 模型:

  1. 预测分析控制程序 ==这个程序的执行直接看作业例题。==

  2. 预测分析表的构造方法

  3. 预测分析方法中的错误处理示例

  • 栈顶终结符与输入串的首字符不匹配： 解决方法：弹出栈顶的终结符号
  • 寻找的分析表表项为空： 解决方法：跳过剩余输入符号串中的若干个符号，直到可以继续进行分析为止(相当于丢掉该非终结符带来的一个树分支)
  1. 带有同步化信息的分析表 ==相当于通过FOLLOW集进行判断，若表项没有就加上synch==

三、自底向上分析方法

“可归约串”是句型的“最左素短语”。

  • 素短语：句型的一个短语，至少含有一个终结符号，并且除它自身之外不再含有其他更小的素短语。
  • 最左素短语：处于句型最左边的那个素短语。

1. “移进-归约”分析方法

  • 符号栈：存放文法符号
  • 分析过程： （1）把输入符号一个个地移进栈中。 （2）当栈顶的符号串形成某个产生式的一个候选式时，在一定条件下，把该符号串替换(即归约)为该产生式的左部符号。 （3）重复(2)，直到栈顶符号串不再是“可归约串”为止。 （4）重复(1)-(3)，直到最终归约出文法开始符号S。

2. 规范规约

最右推导的逆过程

最右推导又称规范推导，由最右推导得到的右句型也称为规范句型，规范推导的逆过程成为规范归约/最左规约。

规范规约的中心问题:如何寻找或确定一个右句型的句柄。

规范句型的特点：句柄之后没有非终结符号

3. “移进-归约”方法实现

  • 移进：把下一个输入符号移进到栈顶。
  • 归约：用适当的归约符号去替换这个串。
  • 接受：宣布分析成功，停止分析。
  • 错误处理：调用错误处理程序进行诊断和恢复。

两种冲突：

  • “移进-归约”冲突
  • “归约-归约”冲突

4. LR分析方法

4.1 LR分析程序

  1. LR分析程序的模型

这里需注意栈的存放方式是底$S_0X_1S_1…X_mS_m$顶

  1. 分析表的结构
  • 状态转换表$goto[S_m，X]$
  • 动作表$action[S_m，a_i]$
  1. 构造LR分析表的三种技术
  • 简单的LR方法（SLR)：易于实现，功能较弱
  • 规范的LR方法（LR(1))：功能最强，代价最大
  • 向前看的LR方法（LALR)：功能和代价介于两者之间，能分析大多数程序设计语言的结构，并且能比较有效地实现
  1. LR分析控制程序
  • 活前缀：一个规范句型的一个前缀，如果不含句柄之后的任何符号，则称它为该句型的一个活前缀。

该程序具体执行结合作业和例子进行复习

4.2 LR分析表构造

  1. SLR(1)分析表的构造 中心思想：为给定的文法构造一个识别它所有==活前缀==的DFA