search

Genluo / Precipitation-and-Summary

梳理体系化的知识点&沉淀日常开发和学习
MIT License
16 stars 1 forks source link

《编译原理》第四章 语法分析 #91

Open Genluo opened 4 years ago

Genluo commented 4 years ago

语法分析器从词法分析器中获得一个由词法单元组成的串，并验证这个串可以由源语言的文法生成，我们期望语法分析器能够以易于理解的方式报告语法错误，并且能够错能从常见的错误中恢复并继续处理程序剩余的部分。概念上来讲，对于良构的程序，语法分析器构造出一颗语法分析树，并把它传给编译器的其他部分进一步处理，处理文法的语法分析器可以分为三种类型：通用的、自顶向下、自底向上的。

在实践过程中，语法分析可能包含多个任务，比如将不同的词法单元信息收集到符号表中，进行类型检查和其他类型的语义分析，以及生成的中间代码，这些任务需要结合后面的的语法制导翻译将这些中间过程结合到语法分析过程中，这一节我们仅仅学习如果通过词法单元组成的串构造出语法分析树

语法错误的处理类型

常见的程序不同层次的错误：

语法分析器中错误处理需要做到的：

1、错误恢复策略

恐慌模式的恢复

使用这个方法的时候，语法分析器一旦发现错误就不断丢弃输入中的符号，一次丢弃一个符号，直到找到同步语法单元集合中的某个元素为止，要求编译器设计者必须为源语言选择适当的同步词法单元

短语层次的恢复

当发现一个错误时，语法分析器可以在余下的输入上进行局部性纠正，也就是说他可能将余下输入的某个前缀替换为另一个串，使的语法分析器可以继续分析

错误产生式

通过预测可能遇见的常见错误，我们可以在当前语言中加入特殊的产生式，这些产生式能够含有错误的构造，从而基于增加了错误产生式文法构造得到一个语法分析器

全局纠正

理想的情况下我们希望编译器在处理一个错误输入串时通过最少的改动将其转化为语法正确的串。有些算法可以选择一个最小的改动序列，得到开销最低的全局性纠正方法，给定一个不正确的输入x和文法G，这些算法将找出一个相关串y的语法分析树，使得将x转化为y所需要的插入、删除和改变的词法单元数量最少。遗憾的是，从空间和时间角度来看，实现这些方法一般来说开销很大，因此这些技术仅仅具有理论价值

上下文无关法

1、正式定义

一个上下文无关文法由终结符号、非终结符号、一个开始符号的一组产生式组成

终结符号：是组成串的基本符号

非终结符号：表示串的集合的语法变量

开始符号：在一个文法中，某个非终结符号被指定为开始符号，这个符号表示的串集合就是这个文法生成的语言，首先列出开始符号的产生式

产生式：一个文法的产生式描述了将终结符号和非终结符组合成串的方法，每个产生式由下列元素组成：

  1. 一个被称为产生式头部和左部的非终结符号，这个产生式定义了这个头所代表的串集合的一部分
  2. 符号-> 有时候也使用：：=来替代
  3. 一个由零个或者多个终结符号与非终结符号组成的产生式体或右部

2、推导

将产生式看做重写规则，就可以从推导的角度精确的描述构造语法分析树的方法，从开始符号出发，每次重写步骤把一个非终结符号替换为它的某个产生式的。这个推导思想对应于自顶向下构造语法分析树的过程，但是推导概念所给出的精确性在讨论自顶向上的语法分析过程中尤其有用

  1. 在最左推导过程中，总是选择每个句型的最左非终结符号
  2. 在最右推导中，总是选择最右边的非终结符号，有时候也称之为“规范推导”

3、语法分析树和推导

语法分析树是推导的图形表示形式，它过滤掉了推导过程中的对非终结符号应用产生式的顺序。语法分析树的每个内部节点表示一个产生式的应用。该内部节点的标号是此产生式中的非终结符号A，这个节点的子节点的标号从左到右组成了在推导过程中替换这个A的产生式体，每一颗语法分析树都和唯一的最左推导及唯一的最右推导相关联

4、证明文法生成的语言（归纳法）

证明文法G生成语言L的过程可以分为两个部分，1.证明G生成的每个串都在L中，并且反向证明L中的每个串都确实能由G生成

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

文法式比正则表达式表达能力更强的表示方法，每个可以使用正则表达式描述方法都可以使用文法来描述，反之则不行

设计文法

  1. 如何在词法分析器和语法分析器之间分配工作
  2. 如何消除文法中的二义性
  3. 消除左递归和提取左公因子-用于改写文法、使的这些文法适用于自顶向下的语法分析

1、词法分析和语法分析

为什么使用正则表达式来定义一个语言的词法语法

  1. 将一个语言的语法结构分为词法和非词法两部分可以很方便的将编译器前端模块化，将前端分解为两个大小适中的组件
  2. 一个语言的词法规则通常很简单，我们不需要使用像文法这样的功能强大表示方法来描述这些规则
  3. 和文法相比，正则表达式通常提供了更加简洁且易于理解的表示词法单元的方法
  4. 根据正则表达式自动构造得到的词法分析器的效率要高于根据任意文法自动构造得到的分析器

自顶向下的语法分析

自顶向下语法分析可以被看做是为输入串构造语法分析的问题，它从语法分析器的根节点开始，按照先根次序创建这颗语法分析树的各个结点，自顶向下的语法分析也可以被看作寻找输入串的最左推导的过程

根据一个文法的FIRST和FOLLOW集合，我们将构造出“预测分析表”，他说明了如何在自顶向下语法分析过程中选择产生式，这些集合可以被用作自底向上语法分析

1、FIRST和FOLLOW

在自顶向下的语法分析过程中，FIRST和FOLLOW使得我们可以根据下一个输入信号来选择应用那个产生式，在恐慌模式的错误恢复中，由FOLLOW产生的词法单元集合可以作为同步词法单元

FIRST（a）被定义为可从a推导的到的串的首符号集合，其中a是任意的文法符号串，计算过程：P140

对于非终结符号A，FOLLOW（A）被定义为可能在某些句型中紧跟在A右边的终结符号的集合，计算过程P140

2、LL(1)文法

对于称之为LL(1)的文法，我们可以构造出预测分析器，即不需要回溯的递归下降语法分析器，LL(1)中第一个L代表从左向右扫描输入，第二个L表示产生的最左推导，而1则表示在每一步中只需向前看一个输入符号来决定语法分析动作

预测分析器的转化图和词法分析器的转化图是不同的。分析器的转化图对每个非终结符号都有一个图，图中边的标号可以是词法单元，也可以是非终结符号。词法单元上的转化表示当该词法单元是下一个输入符号时我们应该执行这个转化，非终结符号A上的转化表示对A的过程的一次调用

3、非递归的预测分析

具体实现过程算法在P144

4、预测分析中的错误恢复

发现错误：当栈顶的终结符号和下一个输入符号不匹配时，或者当非终结符号A处于栈顶，a是下一个输入符号，并且M[A,a]为error（即相应的语法分析表条目为空）时，预测语法分析过程就可以检测到语法分析错误

恐慌模式

  1. 首先将FOLLOW（A）中的所有符号都放到非终结符号A的同步集合中。如果我们不断忽略一些词法单元，指导碰到了FOLLOW（A）中的某个元素，然后将A从栈中弹出，那么很可能语法分析过程就能够继续进行
  2. 只使用FOLLOW（A）作为A的同步集合是不够的，我们可以把较高层构造的开始符号加入到较低层构造的同步集合中去，比如我们可以把语句的国际案子加入到生成表达式的非终结符号的同步集合中去
  3. 如果我们把FIRST（A）中的符号加入到非终结符号A的同步集合中，那么当FIRST（A）中的某个符号出现在 输入中时，我们就有可能根据A继续进行语法分析
  4. 如果一个非终结符号可以生产空串，那么可以把推导出空的产生式当作默认值使用，这么做可能会延迟对某些错误的检测，但是不会使的错误被漏检。
  5. 如果栈顶的一个终结符号不能和输入匹配，一个简单的想法是将该终结符号弹出栈，并发出一个消息称已经插入了这个终结符号，同时继续进行语法分析。从效果上看，这个方法是将所有其他词法单元的集合作为要给词法单元的同步集合

短语层次的恢复

实现方法是在预测语法分析表的空白条目中填写指向处理例程的指针。这些例程可以改变、插入或者删除输入中的符号，并发出适当的错误消息。它们也可能执行一些出栈操作。

自底向上的语法分析

本节将介绍一个被称之为移入-归约语法分析的自底向上语法分析的通用框架

1、归约

在每个归约步骤中，一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号

2、句柄剪枝

“句柄”是和某个产生式体匹配的子串，对他的归约代表了相应的最右推导中的一个反向步骤，也就代表着归约使用的产生式的子串，如果一个文法是无二义性的，那么该文法的每个最右句型都有且只有一个句柄

3、移入-归约语法分析技术

这是自底向上语法分析的一种形式，它使用一个栈来保存文法符号，并用一个输入缓冲区来存放将要进行的语法分析的其余符号，我们将看到，句柄被识别之前，总是出现在栈的顶部，一个移入-归约语法分析器可能产生下面几种动作：

这个分析过程有一个重要的性质：句柄总是出现在栈的顶端，绝不会出现在栈的中间

4、移入-归约语法分析中的冲突

这种情况是即使知道了栈中的所有内容以及接下来的K个输入符号，我们仍然无法判断应该进行移入还是归约操作，或者无法在多个可能的归约方法中选择正确的归约动作（归约/归约冲突）

LR语法分析技术介绍：简单的LR技术

目前最流行的自底向上语法分析器都基于所谓的LR（K）语法分析的概念，其中“L”表示对输入进行从左到右的扫描，“R”表示反向构造出一个最右推导序列，而K表示在做语法分析决定时向前看K个输入符号，k=0和k=1这两种情况具有实践意义

1、为什么使用LR语法分析器

LR方法的主要缺点就是为一个典型的程序设计语言文法手工构造LR分析器的工作量非常大，我们需要一个特殊的工具，即一个LR语法分析器生成工具

2、项和LR(0)自动机

为了构造一个文法的规范LR（0）项集族，我们定义了一个增广文法和两个函数：CLOSURE和GOTO，详细算法见P156

直观来讲，CLOSURE（I）中的项A->a·Bp表明语法分析的某点上，我们认为接下来可能会在输入中看到一个能够从Bp推导得到的子串

第二个有用的函数是GOTO(I, X)，其中I是一个项集而X是一个文法符号，直观来讲，GOTO函数被定义一个文法的LR（0）自动机的转化。这个自动机的状态对应于项集，而GOTO（I，X）描述了当输入为X时离开状态I的转化

3、LR语法分析算法

一个LR语法分析器由一个输入、一个输出、一个栈、一个驱动程序和一个语法分析表，这个语法分析表示整个分析算法的核心，这个表包含两部分ACTION和GOTO。

4、构造SLR语法分析表

给定一个文法G，我们通过添加新的开始符号得到增广文法，我们根据新的增广文法构造出增广文法的规范项集族C以及GOTO函数，然后使用一个算法就可以构造出这个语法分析表中的ACTION和GOTO条目，这个算法要求知道输入文法的每个非终结符号A的FOLLOW（A），算法详细看P161

更加强大的LR语法分析器

更加强大在于在输入中向前看一个符号，有两种不同的方法

1、规范LR（1）项

将项的一般形式变为[A->a·b, c]，其中A->ab是一个产生式，c是一个终结符号或者右端结束标志$，当b不为空时，向前看符号没有任何作用，但是如果b为空，则代表着只要在下一个输入符号为c才进行归约

2、规范LR（1）项集

需要改造两个过程：CLOSURE和GOTO,相关改造算法见P167

3、规范LR（1）语法分析表

和前面一样，构造LR（1）的ACTION和GOTO函数的规则

4、构造LALR语法分析表

这个方法经常在实践中使用，因为用这种方法得到的分析表比规范LR分析表小很多，而且大部分常见的程序设计语言构造都可以方便的使用一个LALR文法表示，详构造算法见P171