《编译原理》第二章 文法和语言

第二章文法和语言本章讲述目前广泛使用的上下文无关文法。

即用上下文无关文法作为程序设计语言语法的描述工具。

阐明语法的一个工具是文法。

本章将介绍文法和语言的概念。

本章重点：上下文无关文法及其句型分析中的有关问题。

第一节文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。

是汉语的一个句子。

汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：〈句子〉∷＝〈主语〉〈谓语〉〈主语〉∷＝〈代词〉|〈名词〉〈代词〉∷＝我|你|他〈名词〉∷＝王明|大学生|工人|英语〈谓语〉∷＝〈动词〉〈直接宾语〉〈动词〉∷＝是|学习〈直接宾语〉∷＝〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。

这些规则成为我们判别句子结构合法与否的依据。

一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。

我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉⇒〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。

比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉⇒〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：〈句子〉⇒〈主语〉〈谓语〉⇒〈代词〉〈谓语〉⇒我〈谓语〉⇒我〈动词〉〈直接宾语〉⇒我是〈直接宾语〉⇒我是〈名词〉⇒我是大学生符号⇒的含义是，使用一条规则，代替⇒左边的某个符号，产生⇒右端的符号串。

显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。

编译原理系列之⼆⽂法和语⾔
⽂法和语⾔
ε，｛ε｝，Ø三者之间的区别：
ε是⼀个终结符推导出的结果，表⽰⼀个不包含任何字符的序列。

Ø是不包含任何元素的空集{}，表⽰不存在匹配⽂法的句⼦。

｛ε｝是任意⼀个符号串集合的0次幂，表⽰⼀个由空字组成的集合。

句⼦与句型：
如果符号串x是由起始符号推导出的，则称x是⽂法G[S]的句型。

如果x中只包含终结符，则称x是⽂法G[S]的句⼦。

⽂法描述的语⾔是该⽂法⼀切句⼦的集合。

四种⽂法：
0型⽂法：α→β，其中α⾄少包含⼀个⾮终结符。

1型⽂法（上下⽂有关⽂法）：α→β，其中|β|≥|α|，S→ε除外。

2型⽂法（上下⽂⽆关⽂法）：a→β，其中a是⼀个⾮终结符。

3型⽂法（规范⽂法）：A→a或A→aB.
4种⽂法是逐渐增加限制的，所以规范⽂法⼀定是0型⽂法、1型⽂法、2型⽂法，上下⽂⽆关⽂法也⼀定是0型⽂法、1型⽂法...
规范推导：
最右推导为规范推导，由规范推导推出的句型称为右句型或规范句型。

⽂法的⼆义性：
⼀个句型可能对应多个语法树，⼀个句型可能对应多个最左/最右推导。

如果⼀个⽂法中的某个句⼦可以对应两个不同的语法树，则称这个⽂法是⼆义的。

两个不同的⽂法可能是⼀样的语⾔。

如果⼀种语⾔的所有⽂法都是⼆义的，则称此语⾔先天⼆义。

判定⼀个⽂法是否是⼆义的是递归不可解的。

《编译原理》第2章文法和语言的形式定义编译原理是计算机科学中的一门重要课程，它研究的是将高级程序语言翻译成机器语言的方法和技术。

在编译原理中，文法和语言的形式定义是非常重要的概念，本文将围绕这个主题展开详细的讨论。

第2章《文法和语言的形式定义》主要介绍文法和语言的概念、应用及其形式定义的方法。

文法是描述语言结构和语法规则的形式化产物，而语言则是文法所描述的符号集合。

在编译原理中，我们需要通过形式定义的方式来描述和理解程序语言的结构和规则。

下面将对文法和语言的形式定义进行详细解释。

1.文法的定义文法是由产生式（Production）组成的四元组(G,N,P,S)，其中：-G：表示文法-N：表示非终结符集合，即一组可以推导出或展开的符号。

-T：表示终结符集合，即不再进行推导或展开的符号。

-P：表示产生式规则集合，是一组指定如何生成目标符号串的规则。

-S：表示一个特殊的非终结符，称为开始符号或起始符号，表示文法的初始状态。

文法的定义可以采用两种形式：巴科斯-诺尔范式（Backus-Naur Form，BNF）和扩充背景文法表达式（Extended Backus-Naur Form，EBNF）。

BNF是最常用的文法定义方法，它使用产生式规则来描述语言的结构和规则。

2.产生式的定义产生式规定了如何用一个符号串替换或展开另一个符号串。

一个产生式由一个非终结符和一个由非终结符和终结符组成的字符串组成。

例如，产生式A->BC，表示用符号串BC替换非终结符A。

产生式可以有多个产生式体，每个产生式体之间使用“，”符号分隔。

例如，产生式A->B，C，表示非终结符A可以被替换成非终结符B或C。

产生式体中可以使用如下符号：-终结符：表示语法中不再与其他符号进行推导的符号，如数字、运算符、关键字等。

-非终结符：表示语法中可以被进一步推导的符号。

-空串：表示不产生任何字符的特殊终结符。

-ε：表示空串。

3.语言的定义语言是符合一些特定文法规则的所有符号串的集合。