第二章文法和语言|镜旅博客

@东明许 @软件工程@YA1714180

https://blog.csdn.net/weixin_30569001/article/details/95053339
https://blog.csdn.net/qq_39495105/article/details/85893564
https://www.docin.com/p-1323497964.html

一. 章节笔记

一. 文法的非形式讨论

1.文法

文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。

所谓文法是在 形式上 对句子结构的定义与描述，而未涉及语义问题。

2.语法规则

我们通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由……组成”。

例如：

<句子>::=<主语><谓语>

<主语>::=<代词>|<名词>

<代词> ::=你|我|他

<名词>::= 王民|大学生|工人|英语

<谓语>::=<动词><直接宾语>

<动词>::=是|学习

<直接宾语>::=<代词>|<名词>

3.由规则推导句子

有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。

推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。

<句子> => <主语><谓语>

<主语><谓语> => <代词><谓语>

…… ……

这种推导一直进行下去，直到所有带< >的符号都由终结符号替代为止。

说明：

(1) 有若干语法成分同时存在时，我们总是从 最左的语法成分进行推导，这称之为最左推导。类似地还有最右推导（一般推导、规范推导）。

(2) 除了最左和最右推导，还可能存在其它形式的推导。

(3) 从一组规则可推出不同的句子

4.语法树

我们用语法树来描述一个句子的语法结构。语法树的叶子节点是句子的单词，非叶子节点的是语法成分。

二. 文法和语言的形式定义

1.文法的形式定义

文法G =（VN，VT，P，Z）

VN：非终结符号集

VT：终结符号集

P：产生式或规则的集合

Z：开始符号（识别符号） Z∈VN

注：

①V＝VN ∪ VT 称为文法的字汇表

②规则：规则是一个有序对(U, x), 通常写为 U ::= x 或U→x（其中U∈VN，x∈V* 因此也有|U| = 1且|x| >= 0）

③给定一个文法，实际只需给出产生式集合，并指定识别符号。（识别符号一般约定为第一条规则的左部符号）

例：无符号整数的文法：

G[<无符号整数>]=（VN，VT，P，Z）

VN＝{<无符号整数>,<数字串>, <数字>}

VT = { 0, 1, 2, 3, … 9 }

P = {<无符号整数> → <数字串>

<数字串> → <数字串> <数字>

<数字串> → <数字>

<数字> →0

<数字> →1

…………

<数字> →9 }

Z = <无符号整数>

2.推导的形式定义

一步推导：

注：当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。

多步推导：

任意步推导：

规范推导：

直观意义上：规范推导＝最右推导

3.语言的形式定义

对于文法G[Z]：

（1）句型x：由开始符号Z经任意步推导得到x，且x∈V*；

（2）句子x：由开始符合Z经1多步推导得到x，且x∈VT*

（3）语言L：所有根据该文法推到得到的句子组成的集合

形式语言理论可以证明以下两点：

（1）G →L(G)：已知文法，求语言，通过推导；

（2）L(G)→G1，G2，……，Gn：已知语言，构造文法，无形式化方法，更多是凭经验。

等价文法：G和G’是两个不同的文法，若 L(G) = L(G’) ,

则G和G’为等价文法。

4.递归文法

①递归规则：规则右部有与左部相同的符号

对于 U::= xUy

若x=ε，即U::= Uy，左递归；

若y=ε，即U::= xU，右递归。

②递归文法：文法G，存在U ∈VN

if U=+=>…U…, 则G为递归文法(自嵌入递归)；

if U=+=>U…, 则G为左递归文法；

if U=+=>…U, 则G为右递归文法。

③左递归文法的缺点：不能用自顶向下的方法来进行语法分析

④递归文法的优点：可用有穷条规则，定义无穷语言

5.句型的短语、简单短语和句柄

给定文法G[Z], w::=xuy∈V+，为该文法的句型,

若 Z==> xUy, 且U=+=>u, 则u是句型w相对于U的短语；

若 Z==> xUy, 且U==>u, 则u是句型w相对于U的简单短语。

其中U ∈Vn，u ∈V+，x, y ∈V*

短语的直观理解：短语是前面句型中的某个非终结符所能推出的符号串。

句柄：任一句型的最左简单短语称为该句型的句柄

给定句型找句柄的步骤：短语-> 简单短语-> 句柄

注意：短语、简单短语是相对于句型而言。一个句型

可能有多个短语、简单短语，但句柄只能有一个。

三. 语法树与二义性文法

1.判断二义性文法：

依据：文法所能产生的句子，可以用不同的推导原则（使用产生式顺序不同）将其推导出来。如果文法是非二义性文法，那么语法树的生成规律不同，但最终生成的语法树形状完全相同；如果文法是二义性文法，那么最终生成的语法树形状有可能不相同。

方法1：若对于一个文法的某一句子存在两棵不同的语法树（或两个不同的 规范推导）；或者自底向上看，对于同一个规范句型，存在两个不同的句柄。则该文法是二义性文法，否则是无二义性文法。

方法2：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。

文法二义性的判定？？：在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。解决方法：提出一些限制条件，称为无二义性的充分条件。当文法满足这些条件时，就可以判定文法是无二义性的。

2.子树与短语

子树：子树由语法树中的某个结点（子树的根）连同它向下派生的部分所组成。

关系：某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。

3.规约：自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。

规范规约：对句型中最左简单短语（句柄）进行的规约称为规范规约。

注：规范规约与规范推导 互为逆过程。

规范句型：通过规范推导或规范规约所得到的句型称为规范句型。

四. 文法相关的其它知识

1. 句子的分析

句子的分析是词法分析和语法分析所要做的工作

任务：给定G[Z]: S ∈ VT, 判定是否有S ∈ L(G[E])

2. 文法的实用限制

有害规则：若文法中有如U::=U的规则，则这就是有害规则，它会引起二义性。（我推我自己）

多余规则：

（1）在推导文法的所有句子中，始终用不到的规则。即该规则的左部非终结符不出现在任何句型中。（用不到）

（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。（死胡同）

若某文法中无有害规则或多余规则，则称该文法是 压缩过的。

3. 文法的其他表示法

1.扩充的BNF表示：

BNF的元符号： <, >, ::=, |

扩充的BNF的元符号： <, >, ::=, |, {, }, [, ] (, )

{ t }：t可重复连接0到任意多次。如果有限制（上标m，下标n），则可重复连接n到m次。
[ t ]：t可有可无。
( )：元符号，注意不要与VT混淆。

2.语法图

3.文法和语言的分类

形式语言：用文法和自动机所描述的没有语义的语言。

语言定义：L(G[Z]) = { x | x∈Vt*, Z =+=> x }

文法定义：乔姆斯基将所有文法都定义为一个四元组：

G=（VN，VT，P，Z）

VN：非终结符号集

VT：终结符号集

P：产生式或规则的集合

Z：开始符号（识别符号） Z∈Vn

文法和语言分类

文法和语言分类：0型、1型、2型、3型

这几类文法的差别在于对产生式施加不同的限制。

注：

（1）2型文法与BNF表示相等价。

（2）3型语言（L3）又称正则语言、正则集合

（3）四种语言的关系：

二. 直播课笔记

教学目的、要求:

本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句炳的基本概念;掌握语言的求解方法、文法的二义性与递归性的判断方法及句型的分析方法。由于编译程序是将高级语言源程序转换成较低–级的目标程序或机器语言，因此为了构造程序设计语言的编译程序，熟悉高级程序语言的语法和语义是必须的。众所周知，任何一个程序设计语言都包含语法、语义和语用三个方面，而阐明语法的一个工具是文法，这是形式语言理论的基本概念之一一。本次课将介绍文法和语言的直观概念，重点介绍构成文法的基本单位“符号和符号串”的有关问题。

其中用到的EBNF元符号含义如下:

●<>:用尖括号括起来的中文字表示语法构造成分,或称语法单元;而用尖括号括. 起来的英文字表示一类词法单元。 ●::=:表示左部的语法单位由右部定义,可读作“定义为”。

●|:表示“或”,即多选项。

●{}:用花括号括起来的成分可以重复0次到任意多次。

●[]:用方括号括起来的成分为任选项，即出现一次或不出现。