编译原理文法知识
今天来学习一下编译原理的文法相关知识。这是属于计算机的基础内容,还是比较有用的一块内容,比较类似于数据结构,但是针对计算机的低级语言。一般来讲比较难以理解,暂时就只是了解一下吧。OK开始:
文法是一个四元组:G = {VT,VN,S,P}
其中VT是一个非空有限的符号集合,它的每个元素成为终结符号。VN也是一个非空有限的符号集合,它的每个元素称为非终结符号,并且VT∩VN=Φ。S∈VN,称为文法G的开始符号。P是一个非空有限集合,它的元素称为产生式。所谓产生式,其形式为α→β,α称为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且α、β∈(VT∪VN)*,α≠ε,即α、β是由终结符和非终结符组成的符号串。开始符S必须至少在某一产生式的左部出现一次。另外可以对形式α→β,α→γ的产生式缩写为α→β|γ,以方便书写。
注:一般以大写字母表示非终结符,以小写字母表示终结符。
著名语言学家Noam Chomsky(乔姆斯基)根据对产生式所施加的限制的不同,把文法分成四种类型,即0型、1型、2型和3型。
0型文法
设G={VT,VN,S,P},如果它的每个产生式α→β是这样一种结构:α∈(VT∪VN)* 且至少含有一个非终结符,而β∈(VT∪VN)*,则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是:0型文法的能力相当于图灵机(Turing)。或者说,任何0型文语言都是递归可枚举的,反之,递归可枚举集必定是一个0型语言。0型文法是这几类文法中限制最少的一个,所以一般见到的至少是0型文法。
1型文法
1型文法也叫上下文有关文法,此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
注意:虽然要求|β|>=|α|,但有一特例:α→ε也满足1型文法。
如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a,则不符合1型文法。
2型文法
2型文法也叫上下文无关文法,它对应于下推自动机。2型文法是在1型文法的基础上,再满足:每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。
如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求,因为其α=Ab,而Ab不是一个非终结符。
3型文法
3型文法也叫正规文法,它对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB(右线性)或A→α|Bα(左线性)。
如有:A->a,A->aB,B->a,B->cB,则符合3型文法的要求。但如果推导为:A->ab,A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说,例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结符+一个终结符”的形式(即为aB)就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc的形式就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。
一些相关的定义:
1、当G为2型或3型文法时,命题“L(G)是空集、有限集或无限集”才是可判断的。
2、当G1和G2都是3型文法时,命题“L(G1)=L(G2)”才是可判断的。
3、最左/右推导:推导的每一步都对最左/右的非终结符使用推导公式
4、若S可以推出mAn,而A可以推出a,则称a是非终结符号A的、句型mAn的短语。若存在A=>a,则为直接短语。
5、一个句型的最左直接短语称为该句型的句柄
6、素短语是一个短语,它至少包含一个终结符,并除自身外不包含其他的素短语。
*************************************************************************
注:此类问题可以用语法树来判定,规则如下
1.每个句型对应一棵语法树
2.每棵语法树的所有叶子结点从左到右排列构成一个句型
3.每棵语法树的子树的叶子结点从左到右排列构成一个短语
4.每棵语法树的简单子树(只有父子两层结点)的叶子结点从左到右排列构成一个简单(直接)短语
5.每棵语法树的最左简单子树(只有父子两层结点)的叶子结点从左到右排列构成句柄
6.素短语是至少包含一个终结符的短语,但它不能包含其它素短语
7.最左推导:在每个推导过程中,总是首先考虑对当前最左边的非终结符号进行推导
8.最右推导:在每个推导过程中,总是首先考虑对当前最右边的非终结符号进行推导
举例如下:
Vt={a,b,d,(,)}.Vn={S,T},S是开始符
S -> a|b|(T)
T -> TdS|S
句型(Sd(T)db)是S的一个_____,其中___是句柄;____是最左素短语;____是该句型的直接短语,_____是短语。
语法树如下:
S
/ | \
( T )
/ | \
T d S
/ | \ |
T d S b
| /|\
S ( T )
1.首先在T->S之后还有一个S-b的推导,所以该句型不是最左推导,只是一个简单的推导
2.再看直接短语,有S,(T),b这3个,其余子树均大于或等于3层
3.句柄为最左直接短语,即S
4.素短语在短语中从左往右找,S不是排除,Sd(T)包含了(T),排除,最后剩下
(T)为最左素短语
5.短语很多,直接从备选答案里找即可
*************************************************************************
-------------------------------------------------------------------------------
有限状态自动机
注:说明一点,只要是有限状态自动机,则必定符合3型文法,且可用正则表达。
一个确定的有限状态自动机M(记做DFA)是一个五元组:M=(∑,Q,q0,F,δ)
其中:
(1) Q是一个有限状态合集
(2) ∑是一个字母集,其中的每个元素称为一个输入符号
(3) q0∈Q,称为初始状态
(4) F∈Q,称为终结状态集合
(5) δ是一个从Q×∑(Q与∑的笛卡尔积)到Q的单值映射:
δ(q,a)=q* (q,q*∈Q, a∈∑)
以上式子表示当前状态为q,输入符号a时,自动机将转换到下一个状态q*,q*称为q的一个后继。
若Q={q1,q2,...,qn
},∑={a1,a2,...,an},则(δ(qi,aj))n×m是一个n行m列矩阵,称为DFA的状态转换矩阵,或称转换表。
有限状态自动机可以形象地用状态转换图表示,举例如下:
DFA M=({S,A,B,C,f},{1,0},S,{f
},δ)
其中:δ(S,0)=B, δ(S,1)=A, δ(A,0)=f, δ(A,1)=C, δ(B,0)=C, δ(B,1)=f, δ(C,0)=f
, δ(C,1)=f
则对应的状态转换图如下所示:
其中圈表示状态结点,双圈表示终结状态结点,而边表示状态的转换,代表映射。边上的符号表示此转换需要输入的符号,代表映射的输入。
对于∑上的任何字符串w∈∑*,若存在一条从初始结点到终态结点的路径,在这条路径上的所有边的符号连接称的符号串恰好是w,则w被DFA所识别(或接受、读出)。DFA所能识别的符号串的全体记为L(M),称为DFA所识别的语言。
NFA介绍
之前介绍的是确定的有限自动机,即一个状态对于待定的输入字符有一个确定的后继状态。而当一个状态对于特定的输入字符有一个以上的后继状态时,我们称该有限自动机为非确定有限自动机(记做NFA),其形式定义也是M=(∑,Q,q0,F,δ),且前面的字符定义均和DFA相同,但是δ:Q×∑对应所有Q的任意子集。
在NFA中能够识别的路径与DFA中定义也相同。
对任何一个NFA,都存在一个DFA*使L(M*)=L(M),这时我们称M*与M等价。构造与M等价的M*的基本方法是让M*的状态对应于M的状态集合。即如果δ(q,a)={q1,q2,...,qn},则把{q1,q2,...,qn}看作M*的一个状态,即M*中的状态集合Q*的一个元素。
正则表达式的转换
DFA和NFA和正则式的转换比较模式化,看一个例子就明白了,具体的方法可以看下面这篇博客:
****************************************************************************************
版权声明:可以任意转载,但转载时必须标明原作者charlee、原始链接
http://tech.idv2.com/2006/05/08/parse-regex-with-dfa/
以及本声明。
程序编译的第一个阶段是词法分析,即把字节流识别为记号(token)流,提供给下一步的语法分析过程。而识别记号的方法就是正则表达式的分析。本文介绍利用有限自动机分析表达式的方法。
概念
-
记号
-
有字母表中的符号组成的有限长度的序列。记号s的长度记为|s|。长度为0的记号称为空记号,记为ε。
-
有限自动机(Finite State Automaton)
-
为研究某种计算过程而抽象出的计算模型。拥有有限个状态,根据不同的输入每个状态可以迁移到其他的状态。
-
非确定有限自动机(Nondeterministic Finite Automaton)
-
简称NFA,由以下元素组成:
-
1. 有限状态集合S;
-
2. 有限输入符号的字母表Σ;
-
3. 状态转移函数move;
-
4. 开始状态 sSUB{0};
-
5. 结束状态集合F,F ∈ S。
-
自动机初始状态为sSUB{0},逐一读入输入字符串中的每一个字母,根据当前状态、读入的字母,由状态转移函数move控制进入下一个状态。如果输入字符串读入结束时自动机的状态属于结束状态集合F,则说明该自动机接受该字符串,否则为不接受。
-
确定有限自动机(Deterministic Finite Automaton)
-
简称DFA,是NFA的一种特例,有以下两条限制:
-
1. 对于空输入ε,状态不发生迁移;
-
2. 某个状态对于每一种输入最多只有一种状态转移。
将正则表达式转换为NFA(Thompson构造法)
算法
算法1 将正则表达式转换为NFA(Thompson构造法)
输入 字母表Σ上的正则表达式r
输出 能够接受L(r)的NFA N
方法 首先将构成r的各个元素分解,对于每一个元素,按照下述规则1和规则2生成NFA。 注意:如果r中记号a出现了多次,那么对于a的每次出现都需要生成一个单独的NFA。
之后依照正则表达式r的文法规则,将生成的NFA按照下述规则3组合在一起。
规则1 对于空记号ε,生成下面的NFA。
规则2 对于Σ的字母表中的元素a,生成下面的NFA。
规则3 令正则表达式s和t的NFA分别为N(s)和N(t)。
a) 对于s|t,按照以下的方式生成NFA N(s|t)。
b) 对于st,按照以下的方式生成NFA N(st)。
c) 对于s*,按照以下的方式生成NFA N(s*)。
d) 对于(s),使用s本身的NFA N(s)。
性质
算法1生成的NFA能够正确地识别正则表达式,并且具有如下的性质:
-
N(r)的状态数最多为r中出现的记号和运算符的个数的2倍。
-
N(r)的开始状态和结束状态有且只有一个。
-
N(r)的各个状态对于Σ中的一个符号,或者拥有一个状态迁移,或者拥有最多两个ε迁移。
示例
利用算法1,根据正则表达式 r=(a|b)*abb 可以生成以下的NFA。
将NFA转化为DFA
算法
使用以下的算法可以将NFA转换成等价的DFA。
算法2 将NFA转化为DFA
输入 NFA N
输出 能够接受与N相同语言的DFA D
方法 本算法生成D对应的状态迁移表Dtran。DFA的各个状态为NFA的状态集合,对于每一个输入符号,D模拟N中可能的状态迁移。
定义以下的操作。
操作
|
说明
|
ε-closure(s)
|
从NFA的状态s出发,仅通过ε迁移能够到达的NFA的状态集合
|
ε-closure(T)
|
从T中包含的某个NFA的状态s出发,仅通过ε迁移能够到达的NFA的状态集合
|
move(T, a)
|
从T中包含的某个NFA的状态s出发,通过输入符号a迁移能够到达的NFA的状态集合
|
令 Dstates 中仅包含ε-closure(s), 并设置状态为未标记;
while Dstates中包含未标记的状态T do
begin
标记T;
for 各输入记号a do
begin
U := ε-closure(move(T, a));
if U不在Dstates中 then
将 U 追加到 Dstates 中,设置状态为未标记;
Dtrans[T, a] := U;
end
end
ε-closure(T)的计算方法如下:
将T中的所有状态入栈;
设置ε-closure(T)的初始值为T;
while 栈非空 do
begin
从栈顶取出元素t;
for 从t出发以ε为边能够到达的各个状态u do
if u不在ε-closure(T)中 then
begin
将u追加到ε-closure(T)中;
将u入栈;
end
end
示例
将上面生成的NFA转化为DFA。
最初,Dstates内仅有ε-closure(0) = A = {0, 1, 2, 4, 7}。然后对于状态A,对于输入记号a,计算 ε-closure(move(A, a)) = ε-closure(move({0, 1, 2, 4, 7}, a)) = ε-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8},即 B={1, 2, 3, 4, 6, 7, 8}, Dtran[A, a]=B。对于状态A,由输入记号b能够到达的仅有4->5,因此 C = ε-closure({5}) = {1, 2, 4, 5, 6, 7},即 Dtran[A, b] = C。
以此类推,可得到以下的状态和Dtran。
A = {0, 1, 2, 4, 7} D = {1, 2, 4, 5, 6, 7, 9}
B = {1, 2, 3, 4, 6, 7, 8} E = {1, 2, 4, 5, 6, 7, 10}
C = {1, 2, 4, 5, 6, 7}
状态
|
输入符号
|
a
|
b
|
A
|
B
|
C
|
B
|
B
|
D
|
C
|
B
|
C
|
D
|
B
|
E
|
E
|
B
|
C
|
由此得出DFA如下图所示。
NFA和DFA的效率
给定正则表达式r和输入记号序列x,判断r是否能够接受x。
使用NFA的情况下,由正则表达式生成NFA的时间复杂度为O(|r|),另外由于NFA的状态数最多为r的2倍,因此空间复杂度为O(|r|)。由NFA判断是否接受x时,时间复杂度为O(|r|×|x|)。因此,总体上处理时间与 r、x的长度之积成比例。这种处理方法在x不是很长时十分有效。
如果使用DFA,由于利用DFA判断是否接受x与状态数无关,因此时间复杂度为O(|x|)。但是DFA的状态数与正则表达式的长度呈指数关系。例如,正则表达式 (a|b)*a(a|b)(a|b)...(a|b),尾部有 n-1 个 (a-b)的话, DFA最小状态数也会超过 2SUP{n}。