软件设计师教程学习笔记（二）程序设计语言基础知识_文法和语言的形式描述

1、文法和语言的形式描述

概念：

1、∈：属于

2、⊆：包含于

A ⊆ B即A含于B（或B包含A），A是B的子集
如果A是B的子集，但B中至少有一个元素不属于A，那么A就是B的真子集

3、∅：空集

4、产生式：由条件和动作组成的指令，-> ，展开产生式=>

5、终结符：不能单独出现在推导式左边的符号，也就是说终结符不能再进行推导。

终结符是一个形式语言的基本符号，它们不能被分解成更小的单位。确切地说，一个语法的规则不能改变终结符。
x -> xa
x -> ax
在这种语法之中，a是一个终结符，因为没有规则可以把a变成别的符号。
不过，有两个规则可以把x变成别的符号，所以x是非终结符。
一个形式语法所推导的形式语言必须完全由终结符构成。
1
2
3
4
5
6

6、非终结符：不是终结符的都是非终结符。非终结符可理解为一个可拆分元素，而终结符是不可拆

分的最小元素。产生式左边必为非终结符。
非终结符是可以被取代的符号。一个形式文法中必须有一个起始符号；这个起始符号属于非终结符的集合。
参考：https://blog.csdn.net/qq_40147863/article/details/88770715

7、文法

VN，非空有限集，其元素皆为非终结符
VT，非空有限集，其元素皆为终结符
VN∩VT=∅，VN、VT不含公共元素
V=VN∪VT，V为文法G的词汇表，V中的符号为文法符号
P是产生式的有限集合，产生式α（左部）→β（右部），α∈V+ ，且α至少包含一个非终结符，β∈V*。
若干个产生式的左部相同时，α→β1，α→β2，……α→βn，可简写为α→β1|β2……|βn
βi（1<=i<=n）为α的一个候选式
S∈VN，称为开始符号，它至少在一条产生式中作为左部出现。

0型文法：即短语文法，限制最少的文法，一般的文法，至少是0型文法。 对应图灵机。
1型文法：即上下文有关文法，每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。即左边长度小于右边 （在这里虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法）对应线性界限自动机。
2型文法：即上下文无关文法，它对应于下推自动机，左边只有一个非终结符。对应非确定的下推自动机。
3型文法：即正规文法，它对应于有限状态自动机。在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）中的其中一个。A -> a、A -> Ba、A ->a B（大写字母表示非终结符，小写字母表示终结符） 对应有限自动机。
关系：层层包含：3属于2属于1属于0

8、单值映射：对于集合A中的任何一个元素，在集合B中都有唯一的元素与它对应。

9、确定的有限自动机DFA

10、不确定的有限自动机NFA

11、DFA转NFA

1、首先确定初态：0状态为起点，通过路径ε可以到达的状态，此例中q0=ε-closure({0})={0}（包含自身）
2、通过相应路径（包括通过相应路径后，可以通过ε路径到达的状态，不包括通过ε前的状态），第一次出现的集合为DFA的一个状态，包含终态5的集合为DFA的一个终态，∅则舍去。

根据上表得状态转换矩阵：

转换成DFA：

例2（转自：）：https://blog.csdn.net/yf289178199/article/details/80172617

I0=ε-closure({X})={X,5,1}
ε-closure(Move(I0,a))=ε-closure({5,3})={5,3,1}=I1 
ε-closure(Move(I0,b))=ε-closure({5,4})={5,4,1}=I2
ε-closure(Move(I1,a))=ε-closure({5,2,3})={5,2,3,1,6,Y}=I3 
ε-closure(Move(I1,b))=ε-closure({5,4})={5,4,1}=I2 
ε-closure(Move(I2,a))=ε-closure({5,3})={5,3,1}=I1 
ε-closure(Move(I2,b))=ε-closure({5,2,4})={5,2,4,1,6,Y}=I4
ε-closure(Move(I3,a))=ε-closure({5,2,3,6})={5,2,3,1,6,Y}=I3 
ε-closure(Move(I3,b))=ε-closure({5,4,6})={5,4,6,1,Y}=I5
ε-closure(Move(I4,a))=ε-closure({5,3,6})={5,3,1,6,Y}=I6 
ε-closure(Move(I4,b))=ε-closure({5,2,4,6})={5,2,4,6,1,Y}=I4
ε-closure(Move(I5,a))={5,3,1,6,Y}=I6 
ε-closure(Move(I5,b))={5,2,4,6,1,Y}=I4
ε-closure(Move(I6,a))={5,3,1,2,6,Y}=I3        
ε-closure(Move(I6,b))={5,4,6,1,Y}=I5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

10、NFA转正规式

11、正规式转NFA

例（转自：https://www.jianshu.com/p/de84d27264cc）：

q0={0,1,3,4,5,6,7,9}

根据上表得状态转换矩阵：

12、DFA最小化

1、去除多余状态：
从这个状态没有通路到达终态：S1
从开始状态出发，任何输入串也不能到达的那个状态：S2

2、合并等价状态：
两个状态s和t等价的条件：
兼容性（一致性）条件——同是终态或同是非终态
传播性（蔓延性）条件——对于所有输入符号，状态s和状态t必须转换到等价的状态里。

DFA的最小化—例子，第一步都是固定的。分成终态和非终态：
１．将Ｍ的状态分为两个子集一个由终态k1=｛Ｃ，Ｄ，Ｅ，Ｆ｝组成，一个由非终态k2=｛Ｓ，Ａ，Ｂ｝组成。
２．考察｛Ｓ，Ａ，Ｂ｝是否可分。

因为Ａ经过a到达C属于k1.而S经过a到达A属于k2。B经过a到达A属于k2，所以K2继续划分为{S，B}，{A}。
３．考察｛Ｓ，Ｂ｝是否可再分：
B经过b到达D属于k1。S经过b到达B属于k2，所以S，B可以划分。划分为{S},{B}
４．考察｛Ｃ，Ｄ，Ｅ，Ｆ｝是否可再分：
因为Ｃ，Ｄ，Ｅ，Ｆ经过a和b到达的状态都属于｛Ｃ，Ｄ，Ｅ，Ｆ｝=k1所以相同，所以不可再分。
５．｛Ｃ，Ｄ，Ｅ，Ｆ｝以｛Ｄ｝（C、D、F都可以）来代替则。

（转自：https://www.cnblogs.com/cute/p/4021689.html）

2、语法分析

1、上下文无关文法：