编译原理---文法和语法分析

仅供参考

---

一、概述

文法：一种描述语言语法结构的形式规则。它用有限的规则把语言的全部句子（可能为无限）描述出来。（例如语文中的 主-谓-宾 就能描述很多个句子）

在本文中，你就会知道，文法是设立了规则，根据规则进行推导，就可以得到各种句型/句子

无穷句子的有穷表示：我们使用句子表述语言。如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了；但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

之前第三章中说的正则表达式，不也是用于描述的吗，跟文法有什么区别？
1）第三章是词法分析，是针对单词的，因为词法分析程序将读入的源程序字符切分成了一系列单词，我们要使用正则表达式去描述这些单词（字符串）
2）第四章是语法分析，是针对语句的，一个句子由多个单词组成，而文法是规则，只有这些单词符合文法，才能构成一个合法的句子

---

二、文法和语言

2.1 如何描述一种语言

如果语言是有穷的（含有穷个句子），可以将句子逐一列出来表示：外延法。
如果语言是无穷的（含无穷个句子），找出语言的有穷表示：内涵法。

语言的有穷表示有两个途经：
（1）生成方式 (文法)——用严格定义的文法规则来生成语言中的每个句子。
（2）识别方式 (自动机)——用一个过程，当输入的一任意串属于语言（定义的合法句子集）时，该过程经有限次计算后就会停止并回答“是”；若不属于，要么能停止并回答“不是”，要么永远继续下去。

2.2 文法的定义

文法是一个四元组，其形式为：G=(V_N,V_T,P,S)

1）V_N为非终结符号的集合
2）V_T为终结符号的集合
3）S为开始符，是一个非终结符，至少要在一条规则中作为左部出现。
4）P为规则（产生式）的集合
5）V_N∪ V_T = V         词汇表 V(或字母表Σ)
6）规则(重写规则、产生式或生成式)：是形如α—>β的(α,β)有序对，其中α为${\Sigma }^{+}$中的符号串，称为规则的左部，β为${\Sigma }^{\ast }$中的符号，称为规则的右部。—>读为“定义为”（实际意义是替换，也就是左边的 α 可以替换成右边的 β）

2.2.1 文法书写的约定

一般不显式表示文法的四元组，只写产生式。

1）第一条产生式的左部是开始符号；
2) 用大写字母表示非终结符号，小写字母表示终结符号。或者用尖括号括起来的是非终结符号(能表示有意义的助记符)，不用尖括号括起来的是终结符号。

2.2.2 推导的定义

（1）α→β是文法G的产生式，若有v,w满足：v = γαδ, w = γβδ, 其中γ,δ∈V*；则称v直接推导到w,记作 v => w，也称w直接归约到v

注意：γ,δ∈V*，是星闭包，所以γ，δ可以是空字符串

例子中，利用了S→0S1这个产生式，α为S，β为0S1；如果γ为0，δ为1，那么v = γαδ = 0S1， w = γβδ = 00S11，所以有 v => w
推导中左侧部分为0S1和β相同，但并不是β，而是由γαδ得到的，要注意区分

（2）

对于第二种推导，S=>0S1=>00S11=>000S111=>00001111，为什么最后一个式子没有S了？
我们不能只盯着S->0S1这个产生式，别忘了S->01

看到第三种推导不知道大家会不会有下面的疑惑（写的很丑，包容一下）
其实对于每一个文法都会有S->S，只是没有写出来而已；因为上面说过，产生式实际上就是一个替换，右边可以替换左边，那么自己肯定可以替换自己
同样的，自己肯定也能推导出自己；只要=>左右两边是一样的，都满足第三种推导

2.2.3 句型、句子的定义

从上述例子很清楚的看出，产生式相当于提供一个规则，指明了E可以替换成什么，T可以替换成什么，F可以替换成什么，根据产生式，才能把E推导出一个句子（算数表达式）

句子/句型可通过多种推导方式（过程）得到
句子也是句型的一部分

2.2.4 语言的定义

三、文法的类型

3.1 0型文法

或称短语文法。对任一产生式α→β，都有α，β∈(V_N∪V_T)*,且α至少含一个非终极符

3.2 1型文法

或称上下文有关文法。对任一产生式α→β，都有|β|≥|α|（长度关系）。（仅 S→ε除外，但文法开始符号S不能出现于产生式右部。）

3.3 2型文法

也称上下文无关文法(Context Free Grammar, CFG) 。对任一产生式α→β，都有α∈V_N，β∈(V_N∪V_T)*。

3.4 3型文法

或称正则文法。任一产生式α→β的形式都为A→aB 或 A→a（右线性文法），或都为A→Ba 或 A→a（左线性文法），其中A，B∈V_N ，a∈V_T。左线性或右线性通常只能满足其一。

3.5 总结

四、上下文无关文法及其语法树

首先，的明白语法树是干嘛的：可以直观地表示句型推导

1）语法树的根标记是S
2）语法树的每个结点都有一个标记（V中的符号）
3）如果某个结点至少有一个除了自己外的子孙，那么该结点的标记一定是非终结符
4）叶子结点（无子孙）的标记一定是终结符

五、规范推导和规范句型

（1）规范推导
最左（最右）推导：在推导的任何一步v=>w，其中v、w是句型，都是对v中的最左（右）非终结 符进行替换。上面例子中的1）是最左推导，2）是最右推导。

最右推导被称为规范推导

（2）规范句型

由规范推导所得的句型称为规范句型（例如： T+T 就不是规范句型。因为前一步进行了最左推导）

这里不要被上面语法树中展示的推导给带偏了，因为上面推导的结果全是终结符，那应该是句子而不是句型呀；那是因为我们想要他推导出这个结果，才会是这样，但是推导的结果也可以含有非终结符，结果也就是句型，而句型包含句子，所以都称为句型是没有问题的

（3）一个句型可对应多颗语法树，一个句型也可对应多个最左（最右）推导：

六、二义文法

若一个文法存在某个句子（句型）有两个不同的最左（右）推导，则称这个文法是二义的。

二义性文法像是一个非确定的自动机，两条以上路径可接收相同串

文法的二义性和语言的二义性（“能穿多少穿多少”）是两个不同的概念。

生成二义语言的任一文法都是二义文法。因为可能有两个不同的文法G和G′，其中G是二义的，而G′是非二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的

6.1 将二义文法改造为无二义文法

七、句型的分析

句型分析：识别一个符号串是否为某文法的句型，是构造某个推导的过程。

在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。

从左到右的识别算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次
识别右边的一个符号，直到分析结束。

7.1 分析算法的分类

7.1.2 自上而下分析法

（1）从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导
（2）语法树的构造过程：从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的所有叶子正好是输入符号串

7.1.2 自下而上分析法

（1）从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。
（2）语法树的构造过程：从输入符号串开始，以它做为语法树的叶子，自底向上地构造语法树，直到根。

7.2 句型分析有关问题

7.2.1 回溯

简单的说，回溯就是由于生产式选择不当，又要重新回去选择别的生产式（下面红箭头处就是发生了回溯）

什么引起了回溯（什么导致我们选错了生产式）：

解决办法：消除左递归、提取左因子

（1）解决办法—消除左递归

（2）解决办法—提取左因子