程序`语言`的定义

语言=语法+语义

语法

任何语言程序都可以看成是一定字符集（字母表)上的字符串。
语法使得这串字符形成一个形式上正确的程序。
语法=词法规则＋语法规则，例如:0.5*x1+c
0.5、x1、c、*、+是语言的单词符号
0.5*x1+c是语言的语法单位

词法规则

词法规则规定了字母表中哪些字符串是单词符号
单词符号一般包括:==常数、标识符、基本字算符、界限符==等。比如界限符 [](){}…… 再比如“:=”是赋值符号
我们用正规式和**==有限自动机==理论来描述词法结构和进行词法分析**。

语法规则

规定了如何从单词符号来形成语法单位：==表达式、子句、语句、函数、过程、程序==
现在多数程序语言使用**==上下文无关文法==来描述语法规则**。
语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据。

本章重点：有限自动机、上下文无关文法

刚刚判断了句子上构造是否有问题，但无法判断句子是否有意义，所有还需要语义

语义

对于一个语言来说，不仅要给出它的词法规则、语法规则，而且要定义它的单词符号、语法单位的意义。
离开语义，语言只是一堆符号的集合。
各种语言中有形式上完全相同的语法单位，含义却不尽相同。
对某种语言，可以定义一个程序的意义的一组规则称为语义规则。
目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义。

字母表与符号表

字母表

用符号表示，非空有穷集合

符号

是语言中最基本的不可再分的单位。

符号串

符号串是字母表中符号组成的有穷序列。
空串:不含有任何符号的串称作空串，记作ϵ/ε（\epsilon）

句子

句子是：字母表上符合某种规则构成的符号串。
必要条件：仅包含终结符的句型是句子

语言

字母表上句子（按某种规则构成的符号串）的集合。
- 用a,b,c…表示终结符;
- 用α,β,γ…表示符号串;
- 用A,B,C…表示非终结符（句子）。

符号串集合的运算

1、连接（乘积）运算：

下面的运行从语法上来说，是成立的，但从语义上不一定成立（但语义不是本书的重点）

注意：AB不等于BA

字母表的闭包和正闭包

1、闭包

2、正闭包

3、语言

是字母表上符合某种规则的语句组成，语言就是正闭包的子集

文法与语言的关系

文法

文法是描述语言（语言=语法+语义）的语法结构的形式**规则**。

下面有一些相关概念

非终结符

<整数>-> <数字><整数>|<数字>

出现在规则的左部、用<>括起来，表示一定语法概念的词。
非终结符集合用**V~n~**表示。

终结符

<数字> -> 0|1

语言中不可再分割的字符串(包括单个字符组成的串)。
注:终结符是组成句子的基本单位
终结符集合用**V~t~**表示。

开始符号

表示所定义的语法范畴的非终结符。
开始符号又称为识别符号

产生式

是用来定义符号串之间关系的一组(语法)规则。形式:A ->α (表示A产生α )

推导

从开始符号到句子

推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。
最左（右）推导:每次使用一个规则，以其右部取代符号串最左（右）非终结符。
注:最左推导和最右推导称为规范推导。

归约

从句子到开始符号

归约是推导的逆过程
即，从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程。
最左(右)归约是最右(左)推导的逆过程。
注:最左归约和最右归约称为规范归约。

句型、句子和语言

句型:

句型是从文法的开始符号S开始，每步推导（包括O步推导）所得到的字符串c。
记作:S->a，其中a∈ ( V,uVr )*

句子

是仅含终结符的句型。

举例

Young men like pop music ，尝试对其进行归约或推导

语法规则如下：

对上面的句子进行最左推导----最右归约

上图中在归约中，

<形容词><名词>可以归约为<宾语>，也可以归约为<主语>。

机器会随机选择一个归约的对象，并继续执行下去

假如，如果上图选择的不是归约为<宾语>，而且是归约到<主语>

但后面会发现，没有<动词><主语>的规则，所以需要回溯，重新归约为<宾语>

上图的树型

如果使用最左归约的方式，有以下的序号，很明显，是树的后序遍历

当然，还有其它的结果。但另外两种不符合语义

语言

文法规则扩充表示

元语言符号

4类文法

文法是一种**规则**，以下的所有文法都是规则

由V~T~ 终结符号、V~N~ 非终结符号、开始符号、规则组成

用a,b,c…表示终结符;
用α,β,γ…表示符号串;
用A,B,C…表示非终结符

0型文法

对产生式限制最少的文法，也叫短语文法

产生式的左边至少是一个非终结符
任何0型文法可以递归和枚举

1型文法

1型文法又叫长度增加文法

对终结符不能替换成空串

【上下有关文法】1型文法如何判断：

第一点：1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。

第二点：与2型文法第二点相同，即：产生式的右边可以含有若干个终结符和非终结符

1型文法举例

2型文法

2型文法又叫上下文无关文法，判断句子是否正确【使用下推自动机】

产生式左边一定是非终结符，只有一个非终结符
右边可以是终结符、非终结符、空串
对非终结符的替换不考虑上下文

【上下无关文法】2型文法如何判断：

第一点：与3型文法的第一点相同，即：左边必须有且仅有一个非终结符。

第二点：2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。

【上下文无关文法适合于语法分析】

2型文法举例

3型文法

3型文法又叫右线性文法，用于判断单词是否正确【使用有限自动机】

右线性文法：A-> αB 或 A-> α 。非终结符只能靠右
左线性文法：A-> Bα 或 A-> α 。非终结符只能靠左
非终结符不能在终结符的中间，如A-> αBγ ,或L~2~={a^n^ b^n^|n>=1}只能由 S->aSb|ab产生（是2型文法：上下文无关文法）

【正规文法】3型文法遵循的规范

第一点：左边必须只有一个字符，且必须是非终结符；

第二点：其右边最多只能有两个字符，且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时，此字符必须为终结符。【右边至少有一个终结符】

第三点：对于3型文法中的所有产生式，其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定。

如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须前面是终结符而后面是非终结符。

反之要么就全是：非终结符＋终结符。

如：S->aS|bS，不能是S->aS|Sb

【正规文法适合于词法分析】

3型文法举例

左边都是非终结符

不同文法的小结

由下图可见：0型文法的范畴是最大的

文法综合举例

对产生式的限制

在词法分析和语法分析中对产生式有限制不存在P->P产生式

P必须能推导出终结符串

题目

S-> aaS|a是什么型的，为什么
S-> aSb|ab是什么型的，为什么
S-> SaS|b是什么型的，为什么

答：三种文法都属于上下文无关文法,2型文法。

首先，应该明确，四种文法，从0型到3型，其规则和约定越来越多，限制条件也越来越多，所以，我们判断时可以从最复杂的3型进行判断，依次向下判断，如果不符合3型的，那再看是不是2型的，不是2型的，再看是不是1型的，当然，对于作题作的熟的朋友，不用这么复杂，可以一眼直接看出来。

依以上规则判断，所给的三个文法显然都不属于3型文法。因为明显产生式右边大于2个字符

依2型文法判断规则，满足。产生式左边只有一个非终结符，右边可以有多个字符。

依1型文法判断规则，满足。文法也是属于1型的。

最后是0型文法，这个就不用看了，只要能描述出来，都属于这个类型，即0型。

所以，取其最高的符合规则，最后的答案是其符合：上下文无关文法规则，即2型。

由语言写文法

例1

例2

上下文无关文法

正规文法（左侧）

如果是正规文法则一定是上下文无关文法

例3

或按右侧答案

例4

文法的简化

规则

查找有无形如P→P的产生式，若有则删除;
若某个产生式在推导过程中永远不会被用到，删除它;
若某个产生式在推导过程中不能从中导出终结符，删除它。
最后，整理所有剩余产生式，就得到简化的文法

例题

发现A->A ，删除
发现D->f ，从未没使用，删除
C->Cf，无法导出终结符，删除
那B->Ce，也无法导出终结符，删除
S->Ec，E从未出现，删除

结果：则为上图中的四个，注意：A->Ae 与 A->e 不能合并成A->ae

构造无空串产生式的上下文文法

举例

解释：

找到开始符号，如果这些开始符号经过一步或几步能到空串
用空串和其原型(这里S)代入，将新的产生式添加到P’ ，如S->a空bS|aSb空|aSbS|a空b空 ，右边的同理
增加一个S’作为新的开始符号，S'->空|S

结果如下：

语法树与文法的二义性

语法树

使用最左推导得到aabbab

对应的语法树为

概念

(1）子树:除叶子结点之外的任意结点连同它的所有子孙结点构成子树。
(2）修剪子树:剪去子树树根的所有孩子。
(3）句型:在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。
- 每一步的推导过程都是个句型
(4）短语:子树的末端符号自左到右遵成串，相对于子树树根而言称为短语。
- 简单短语（直接短语):若短语事某子树根经过1步推导得到的（只有儿子节点，没有孙子节点），则称之为该子树根的简单短语。
- 句型的短语:该句型中哪些符号串可构成某子树根的短语。
(5）句柄:句型中的最左简单短语，另外要求：节点必须为叶子，如下图中，只有A-a是句柄
- 现在变成aabbAb，那S-b S-a成为了句柄，如下图
- 现在变成aabSb，那B-b B-S成为句柄，（要找最左简单短语，右边的B-b虽然是简单短语，但不是最左）
- 现在变成aaBb，那B-b变成句柄
- 现在变成aaBB，那aBB变成句柄
- 现在变成aB,最终的句柄
注:句柄是最左归约时要寻找的简单短语。