0. 引言

0.1 语法结构

程序设计语言源程序的构成：语法结构

一个实例

image.png|700

0.2 文法

一种用于描述程序设计语言语法的表示方法，能够自然地描述程序设计语言构造的层次化语法结构
image.png|700

1. 语法分析器

  • 输入：词法分析器输出的此法单元序列
  • 输出：语法树表示
  • 语法分析器功能：
    image.png|600
  • 语法分析器的类型：
    image.png|600

image.png|650
类型检查，语义分析，翻译生成中间代码等往往和语法分析过程交错完成，实践中往往和语法分析放入一个模块，图上用“前端的其余部分”表示上述活动

2. 上下文无关法 (Context Free Grammar, CFG)

上下文无关文法G是一个四元组G=(T,N,P,S)G=(T,N,P,S):

1.  T是**终结符号 Terminal**集合, 对应于词法分析器产生的词法单元
2.  N是**非终结符号 Non-terminal**集合
3.  P 是**产生式 Production**集合

image.png|500

image.png|700
终结符：不可以再进行推导，是不可拆分的最小元素
非终结符：可以进行拆分的元素

2.1 什么是上下文

image.png|700

文法的分类
  • 上下文有关文法

  • 上下文无关文法
    参考

    2.2 推导

    产生式又可称为重写规则（Rewriting rule）

  • 推导即是将某个产生式的左边替换成它的右边
  • 每一步推导需要选择替换哪个非终结符号，以及使用哪个产生式
    image.png|600

推导的一般性定义
image.png|600

2.2.1 句型/句子/语言

image.png|600

2.2.2 推导的问题

推导：从上层视角判断输入内容是否符合文法
从推导的角度看，语法分析的任务：

  • 推导过程中可能遇到两个问题：

    1. 每一步替换哪个非终结符号？
    2. 若以这个非终结符号为头的产生式有多个，用哪个产生式的右部替换？

    image.png|500

非终结符号的替换顺序

image.png|700

2.2.3 语法分析树

推导的图形表示形式
image.png|700

  • 有时允许树根不是开始符号（对应于某个短语）

  • 树的叶子组成的序列四根的文法符号的句型
    image.png|300

    2.2.4 推导和语法树

    对于推导中的每一个句型α1，都能构造出一个以α1 为结果的语法树

2.3 二义性

image.png|600
程序设计语言的文法通常都应该是无二义性的

  • 但有些二义性的情况可以方便文法或语法分析器的设计

    2.4 文法及其生成的语言

    语言是由闻法得开始符号出发，能够推导得到的所有句子的集合
    image.png|700

2.5 上下文无关文法和正则表达式

  • 上下文无关文法的表达能力更强
  • 每个正则表达式都可以用一个上下文无关文法来描述，反之不成立
  • 每个正则语言都是一个上下文无关语言， 反之不成立
    image.png|700

3. 文法的设计

image.png|700

  • 在进行高效的语法分析之前，需要对文法做以下处理：
    image.png|700

3.1 消除二义性

二义性的例子：
image.png|500

  • 一些二义性文法可以被改成等价的无二义性的文法
    image.png|700
  • 二义性的消除方法没有规律可循
  • 通常并不是通过改变文法来消除二义性

3.2 消除左递归

左递归的定义：
image.png|600
image.png|600

3.2.1 立即左递归的消除

image.png|700

示例：

image.png|600

3.2.2 消除多步左递归

  • 消除立即左递归的方法并不能消除因为两步或多步推导而产生的左递归
    image.png|500
消除算法
  • 不能含有回路（P→P）
  • 不能含有ε为右部的产生式
    image.png|700
    image.png|700
  • 内层循环的每一次迭代保证了Ai的产生式的右部首符号都比Aj更加靠后
  • 当内层循环结束时，Ai的产生式的右部首符号不先于Ai
  • 消除立即左递归就保证了Ai的产生式的右部首符号必然比Ai后。（不能有环和ε产生式）
  • 当外层循环结束时，所有的产生式都是如此。使用这些产生式当然不会产生左递归的情形
示例：

image.png|700

3.3 提取左公因子

在推导的时候，不知道该如何选择
image.png|700

方法：

image.png|600

例子：

image.png|600

4. 自顶向下分析技术

自顶向下分析可以被看作是为输入串构造语法分析树的问题，也可以看作一个寻找输入串的最左推导的过程

  • 最左推导：总是选择每个句型的最左非终结符进行替换
  • 问题：对于非终结符号 A，选择哪一个产生式
    image.png|700
    根据输入流中的下一个终结符，选择最左非终结符

4.1 预测分析法

image.png|700

  • 处理 LL 文法时需要考虑是否有左递归、是否需要提取公因子

    预测分析技术：

    一种确定的、无回溯的分析技术，在每一步选择正确的产生式
    比递归下降分析效率更高、准确性更高
    |300
    image.png|300
    image.png|600

  • 可以向前选择多个产生式

  • 一般情况下只需要向前一个符号 LL (1)

    • 提取左公因子后不会有两个相同的符号
    • LL (2)、LL (n) 效率会降低很多

4.1.1 First 和 Follow

image.png|600
定义 First 和 Follow：
image.png|600

4.1.1.1 First函数

  • First 函数的意义：
    image.png|600
  • First函数的计算：
    对于文法符号 X 的 FIRST (X)，通过不断应用下列规则，直到没有新的终结符号或者ε可以加入到任何 FIRST 集合为止
    image.png|700
    image.png|600
  • 所有的 First (x) 中都有ε时才将ε加入 First (x1x2x3... xn) 中
示例：

image.png|600
image.png|600

4.1.1.2 Follow 函数

image.png|700

  • Follow 的计算：
    image.png|600
示例：

image.png|700

4.2 LL (1) 文法

LL (1) 文法，第一个 L 表示自左向右扫描，第二个 L 指产生最左推导，而 1 则表示向前看一个输入符号
image.png|600
image.png|600

  • 对于 LL (1) 文法，可以在自顶向下分析过程中，根据当前输入符号来确定使用的产生式
    image.png|700

4.3 LL (1) 文法的预测分析技术

4.3.1 预测分析程序构成

image.png|400
总控程序：根据现行栈顶符号和当前输入符号，执行动作
分析表
分析栈：用于存放文法符号

  • 总控程序对于任何一种语言是通用的——数据与控制分离
  • 预测分析表
  • 将 First 和 Follow 集合中的信息放入一个预测分析表 M[A, a]，该预测表告诉我们当非终结符号为 A，当前输入符号为 a 时，要选择哪条产生式
    image.png|700
    image.png|700

4.3.1 预测分析表的构造

输入：文法 G
输出：预测分析表 M
image.png|700

例子：

image.png|700

4.3.2 非递归的预测分析

image.png|500
image.png|600

4.3.3 分析表驱动的预测分析器

image.png|600
image.png|600

5. 自底向上语法分析

image.png|600

  • 采用最左规约，即反向构造最右推导

    • 在每一步的归约中，一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号，一次归约实质上是一个推导的反向操作
  • 自底向上分析的过程
    image.png|500
    image.png|650
    规约的问题：
  • 选择哪部分进行归约?
  • 应用哪个产生式进行归约?

5.1 短语、直接短语和句柄

短语：

image.png|500

直接短语：

image.png|500

  • 短语代表了可规约的串

  • 直接短语代表了课立即规约的串

    句柄：

    一个句型的最左直接短语称为该句型的句柄

  • 句柄是最右推导的反向过程中被规约的那些部分
    image.png|500
    image.png|600

5.1.1 句柄剪枝

用句柄进行规约
image.png|300image.png|250

2017721743
2667519991

5.2 移入-规约

image.png|700
使用一个栈来保存归约/扫描移入的文法符号

  • 栈中符号（从底向上）和待扫描的符号组成了一个最右句型
  • 开始时刻：栈中只包含$，而输入为w$
  • 成功结束时刻：栈中$S，而输入$

  • 在分析过程中，不断地移入符号，并在识别到句型时进行归约

    主要分析动作

    image.png|500

5.2.1 移进/规约冲突

移入-归约技术并不能处理所有上下文无关文法
image.png|500

5.3 LR 分析法

image.png|500

优点：

image.png|500

  • 自底向上分析的关键是正确的识别句柄
  • 句柄是逐步形成的，用“状态”表示句柄识别的进展程度
    image.png|300
  • LR 分析器基于这些状态来构造自动机进行句柄识别

5.3.1 LR 分析器的结构

image.png|600

  • 包含一个与符号栈平行的状态栈
分析表的结构：

image.png|500
image.png|150 image.png|400

  • 每一行对应一个状态

  • ACTION 表每一列对应一个终结符与$，每一项表示一个动作

    • sn：表示移入，将当前输入符号移入分析栈，并进入到状态n
    • rn：表示规约，使用第n个产生式规约

5.3.2 LR (0) 项

image.png|500
项目描述了句柄识别的状态

5.3.3 LR (0) 自动机

规范LR(0)项集族提供构建LR(0)自动机的基础

  • LR(0)自动机可用于做出语法分析决定
  • LR (0) 自动机中每个状态代表了 LR (0) 项集族中的一个项集
    image.png|400

5.3.3.1 增广文法

image.png|500

5.3.3.2 文法中的项

image.png|200
image.png

  • 红色方框中的为规约项目，点在末尾
    后继项：同属于一个产生式，但是圆点的位置只相差一个符号
    image.png|300

image.png|500

CLOSURE (I) 的构造算法

把所有项目都作为自动机的状态，会使得自动机的状态过多，可以寻找等价的项目来减少自动机的项目
image.png|600
把所有等价的项目组成一个项目集，称为项目集闭包，每个项目及闭包对应着自动机的一个状态
例子：
image.png|600

内核项与非内核项

image.png|500

GOTO 函数

image.png|500

5.3.3.3 求 LR (0) 相集规范族的算法与构造自动机

image.png|600

自动机的构造方法

image.png|500
例子：
image.png|600
相应的分析表：
image.png|300

  • 1 号状态为接收状态，遇到$后完成接受
  • 4 号状态为规约状态，对应第三条产生式，采用第三条产生式进行规约
  • 5 号 6 号类似 4 号

5.3.3.5 LR (0) 自动机的作用

image.png|500
image.png|500
image.png|500