Chomsky文法类型判断及消除文法左递归-安大编译原理全部实验
安 徽 大 学
实验一
名称 Chomsky文法类型判断(Recognizing the type of the Chomsky grammar)
一、背景资料
1956年，N.Chomsky首先对形式语言进行了描述。N.Chomsky在对某些自然语言进行研究的基础上，提出了一种用于描述语言和文法的数学系统，按照对文法规则的不同定义形式，对语言和文法分成了4类，对每一类语言，让它与一种特定种类的自动机那样的识别器联系起来。形式语言理论的形成与发展，对计算机科学的发展是一个推动，在程序设计语言的设计与编译实现以及计算复杂性等方面都有着重大影响。 二、实验目的要求
输入:一组任意的规则。
输出:相应的Chomsky 文法的类型。
三、实验原理
1(0型文法(短语文法)
如果对于某文法G，P中的每个规则具有下列形式:
u:: = v ，*其中u?V，v?V，则称该文法G为0型文法或短语文法，简写为PSG。
0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L。这种文法由于没有其他任何限制，0
因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机(Turning)来识别。
2(1型文法(上下文有关文法)
如果对于某文法G，P中的每个规则具有下列形式:
xUy:: = xuy ，*其中U?V;u?V;x，y?V，则称该文法G为1型文法或上下文有关文法，也称上下文敏感文法，简写N
为CSG。
1型文法的规则左部的U和右部的u具有相同的上文x和下文y，利用该规则进行推导时，要用u替换U，必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。
1型文法所确定的语言为1型语言L，1型语言可由线性有界自动机来识别。 1
3(2型文法(上下文无关文法)
如果对于某文法G，P中的每个规则具有下列形式:
U :: = u ，其中U?V;u?V，则称该文法G为2型文法或上下文无关文法，简写为CFG。 N
按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非终结符U所在的上下文，总能
用u替换U，或者将u归约为U，显示了上下文无关的特点。
2型文法所确定的语言为2型语言L，2型语言可由非确定的下推自动机来识别。 2
一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引
起了人们较大的兴趣与重视。
4(3型文法(正则文法，线性文法)
如果对于某文法G，P中的每个规则具有下列形式:
U :: = T 或 U :: = WT
其中T?V;U,W?V，则称该文法G为左线性文法。 TN
如果对于某文法G，P中的每个规则具有下列形式:
U :: = T 或 U :: = TW
其中T?V;U, W?V，则称该文法G为右线性文法。 TN
左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。
按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终
结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。
3型文法所确定的语言为3型语言L，3型语言可由确定的有限状态自动机来识别。 3
在常见的程序设计语言中，多数与词法有关的文法属于3型文法。
可以看出，上述4类文法，从0型到3型，产生式限制越来越强，其后一类都是前一类的子集，而描述
语言的功能越来越弱，四类文法及其表示的语言之间的关系可表示为:
0型,1型,2型,3型;即L, L, L, L0123
四、仪器
微机
五、实验步骤(包括操作方法、数据处理)Chomsky文法类型判断
#include
#include
using namespace std;
#define MAXS 50
int NONE=1;
int RELEFT=1;
string strings,noend,end;
int N;
struct STR
{
string left;
string right;
};
//输出四元组
void print(STR *p)
{
int i;
cout<"<='A'&&p[i].left[j]<='Z'))
{
if(noend.find(p[i].left[j])>100)
noend+=p[i].left[j];
}
else
{
if(end.find(p[i].left[j])>100)
end+=p[i].left[j];
}
}
for(j=0;j<(int)p[i].right.length();j++)
{
if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z'))
{
if(end.find(p[i].right[j])>100)
end+=p[i].right[j];
}
else
{
if(noend.find(p[i].right[j])>100)
noend+=p[i].right[j];
}
}
}
}
//删除无用产生式
void useless(STR *p)
{
int i,j,k;
string vn;
vn+=p[0].left;
for(j=0;j='A'&&p[i].right[k]<='Z'&&vn.find(p[i].right[k])>100)
vn+=p[i].right[k];
}
//cout<100)
{
for(i=0;i"<100)
{
noend+=vn;
break;
}
}
return vn;
}
//消除直接左递归
void releft(STR *p,int i) {
int j,k;
char c;
for(j=0;j"<"<"<"<='A'&&p[i].left[j]<='Z') //有否非终结符
flag++;
}
if(flag>0)
{
flag=0;
count++;
}
else
break; //左部没有非终结符，结束
}
if(count==N)
return 1; //属于0型文法 else
{
cout<0)
{
cout<='A'&&p[i].left[0]<='Z')) //左部不属于一个字符或
不属于非终结符
{
flag++;
break;
}
}
else
flag--;
if(flag>0)
{
cout<='A'&&p[i].right[0]<='Z'))
//右部字符个数不是1或2，或首字符是非终结符
{
flag++;
break;
}
else
if((p[i].right.length()==2)&&!(p[i].right[1]>='A'&&p[i].right[1]<='Z')) //第二个字符不是非
终结符
{
flag++;
break;
}
}
else
flag--;
if(flag>0)
{
cout<>N;
STR *p=new STR[MAXS]; for(i=0;i>strings;
getlr(p,i);
}
three(p);
VNVT(p);
if(NONE)
print(p);
}
////////////////////////////////////////////////////////////////
测试数据:
//3型文法
9
S-0A
S-1B
S-0
A-0A
A-0S
A-1B
B-1B
B-1
B-0
//2型文法，不含左递归
4
S-aA
S-d
A-bAS
A-#
//2型文法，含左递归，可消除
6
S-Qc
S-c
Q-Rb
Q-b
R-Sa
R-a
//2型文法，含左递归，可消除，有无用产生式
4
S-B3
B-S5
B-2
A-3
//2型文法，含左递归，不能消除
6
S-Qc
S-c
Q-Q
Q-Rb
Q-b
Q-#
//1型文法 3
A-kL
La-K0a
K-6as
//0型文法 4
fQg-f8A9g tA-tkQ
9Q1-9P21
P-#
//不是0型文法
3
wer-3
rtG-uy
rt-y
六、注意事项
? 文法的输入应简便。
? 指明是哪一类Chomsky 文法，并给出相应的四元组形式:G=(V，V，P，S)。 NT
说明:简单起见， 可以不考虑0型文法类。
七、思考题
3型文法和DFA、NFA、正规式的关系如何,
实验 二
名称 消除文法的左递归(Removing the left recursion of the grammar)
一、背景资料
一个文法是含有左递归的，如果存在非终结符P
，
,PPα
含有左递归的文法将使上述的自上而下的分析过程陷入无限循环，即当试图用P
去匹配输入串时，就会出现在没有吃进任何输入符号的情况下，又得重新要求P
去进行新的匹配。因此，使用自上而下分析法必须消除文法的左递归性。
二、实验目的要求
输入:任意的上下文无关文法。
输出:消除了左递归的等价文法。
三、实验原理
1(直接左递归的消除
消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为
P?Pα / β
其中，β是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非
直接左递归形式: P?βP’
P’?αP’ / ε
这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。
设有简单表达式文法G[E]:
E?E+T/ T
T?T*F/ F
F?(E)/ I
经消除直接左递归后得到如下文法:
E?TE’
E’ ?+TE’/ ε
T?FT’
T’ ?*FT’/ ε
F?(E)/ I
考虑更一般的情况，假定关于非终结符P的规则为
P?Pα / Pα /„/ Pα / β/ β/„/β 12n1 2 m
其中，α(I,1，2，„，n)都不为ε，而每个β(j,1，2，„，m)都不以ij
P开头，将上述规则改写为如下形式即可消除P的直接左递归:
P?β P’/ β P’/„/β P’ 1 2 m
P’ ?αP’ / α P’ /„/ α P’ /ε 12n
2(间接左递归的消除
直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法G[S]:
S?Qc/ c
Q?Rb/ b
R?Sa/ a
虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有
,,,SQcRbcSabc
,,,QRbSabQcab
,,,RSaQcaRbca
就显现出其左递归性了，这就是间接左递归文法。
消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。
，
,如果一个文法不含有回路，即形如PP的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。
消除左递归算法:
(1) 把文法G的所有非终结符按任一顺序排列，例如，A，A，„，A。 12n
(2) for (i,1;i<=n;i++)
for (j,1;j<=i,1;j++)
{ 把形如A?Aγ的产生式改写成A?δγ /δγ /„/δγ iji12k
其中A?δ /δ /„/δ是关于的A全部规则; j12kj
消除A规则中的直接左递归; i
}
(3) 化简由(2)所得到的文法，即去掉多余的规则。
利用此算法可以将上述文法进行改写，来消除左递归。
首先，令非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q中的相关规则中，则Q的规则变为Q?Sab/ ab/ b。
代换后的Q不含有直接左递归，将其代入S，S的规则变为S?Sabc/ abc/ bc/
c。
此时，S存在直接左递归。在消除了S的直接左递归后，得到整个文法为:
S?abcS’/ bcS'/ cS'
S’ ?abcS'/ ε
Q?Sab/ ab/ b
R?Sa/ a
可以看到从文法开始符号S出发，永远无法达到Q和R，所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法G[S]为:
S?abcS'/ bcS’/ cS'
S' ?abcS'/ ε
当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R，那么最后得到的文法G[R]为: R?bcaR'/ caR'/ aR’
R' ?bcaR'/ ε
容易证明上述两个文法是等价的。
四、材料、试剂及仪器
微机
五、实验步骤(包括操作方法、数据处理)
消除左递归算法:
(4) 把文法G的所有非终结符按任一顺序排列，例如，A，A，„，A。 12n
(5) for (i,1;i<=n;i++)
for (j,1;j<=i,1;j++)
{ 把形如A?Aγ的产生式改写成A?δγ /δγ /„/δγ iji12k
其中A?δ /δ /„/δ是关于的A全部规则; j12kj
消除A规则中的直接左递归; i
}
(6) 化简由(2)所得到的文法，即去掉多余的规则。
利用此算法可以将上述文法进行改写，来消除左递归。
六、注意事项
指明是否存在左递归，以及左递归的类型。对于直接左递归，可将其改为直接右递归;对于间接左递归(也称文法左递归)，则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。(应该有n～种)
七、思考题
实验 三
由正规(则)文法构造正规(则)式 名称 (Generating regular expression based on the given canonical grammar) 一、背景资料
一个文法可以定义某种语言，而一个特定的语言也可以由文法来描述。但文
法与语言之间并不存在一一对应的关系。
形式语言理论已经证明:
(1) 给定一个文法，就能从结构上惟一地确定其语言，即
G?L(G)
(2)给出文法后，语言也就相应地确定了，其语言可以是有限的，也可以是无限的。
二、实验目的要求
输入:任意的正规文法。
输出:相应的正规式。
三、实验原理
3型文法,正则文法～线性文法,
如果对于某文法G，P中的每个规则具有下列形式:
U :: = T 或 U :: = WT
其中T?V;U,W?V，则称该文法G为左线性文法。 TN
如果对于某文法G，P中的每个规则具有下列形式:
U :: = T 或 U :: = TW
其中T?V;U, W?V，则称该文法G为右线性文法。 TN
左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。
按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。
3型文法所确定的语言为3型语言L，3型语言可由确定的有限状态自动机3
来识别。
程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文法描述如下:
<标识符>::=<字母>/<标识符><字母>/<标识符><数字>
显然，该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法——正则表达式。正则表达式又称为正则式，每个正则表达式描述的集合称为正则集。
之所以采用正则表达式来描述，主要基于以下几点原因:
(1) 词法规则简单，无需上下文无关文法那样严格的表示法，用正则式
表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更
为容易;
(2) 从正则式构造高效识别程序比上下文无关文法更容易;
(3) 可以从某个正则式自动地构造识别程序，它可以识别用该正则式表
示的字符串集合中的字符串，从而减轻后面要介绍的词法分析时的工作
量。
(4) 可用于其他各种信息流的处理，例如，已经应用于某些模式识别问
题、文献目录检索系统以及正文编辑程序等。
正则表达式和正则集
设有字母表?。?上的正则表达式和它所表示的正则集递归地定义如下:
(1) ε和Φ都是?上的正则表达式，它们所表示的正则集分别为{ε}和
Φ，其中ε是空串，Φ是空集;
(2) 任意的a??是正则表达式，它所表示的正则集是{a};
(3) 如果e和e是?上的任意的正则表达式，且分别表示的正则集为L12
(e)和L(e)，则: 12
, e/e也是正则表达式，表示的正则集为L(e/ e),L(e)?L(e)。 121 212
, ee也是正则表达式，表示的正则集为L(e e),L(e)L(e)。 1 21212***, (e)也是正则表达式，表示的正则集为L((e)),L(e)。 111
定义中(1)和(2)定义了原子正则表达式，而(3)则表明字母表?上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。
正则表达式的性质
如果两个正则表达式e和e表示的正则集相同，即值相等，则称它们是等12
价的。记为e,e。 12
正则表达式与正则文法的关系
一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号Φ外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于<数字> ::= 0/1/2/…/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/…/9所定义的字符串集合是相同的。正则集Φ，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。
四、材料、试剂及仪器
微机
五、实验步骤(包括操作方法、数据处理)
六、注意事项
要求:输出界面为:
正规文法 正规式
七、思考题
实验 四
不确定有限状态自动机的确定化(Affirmation of the indefinitely finite 名称 automata)
一、背景资料
有限自动机(FA)可以看作是由一个带有读头的有限控制器和一条字符输入带组成，如图所示。
a a a b b b c c … …
输入带
控制器
FA的示意图
控制器的读头从左至右顺次扫描输入带，每当从输入带上读到一个符号时，
便引起控制器状态的改变，同时读头右移一个符号位。
控制器包括有限个状态，状态和状态之间存在转换关系。当处于某个状态，读入一个字符时，则使状态改变为另一个状态，从而形成状态转换，改变后的状态称为后继状态。状态转换后的后继状态有三种可能情况:(1)后继状态为自身;(2)后继状态为一个;(3)后继状态为若干个。
某个有限自动机，如果每次状态转换的后继状态都是惟一的，则称它是确定有限自动机(DFA);如果转换后的后继状态并不都是惟一的，则称它是不确定有限自动机(NFA)。
有限自动机的开始工作状态称为初始状态，结束工作的状态称为终止工作状态或接收状态。如果把上一小节中的状态转换图的各个结点看成是某一个状态，初始结点为初始状态，终止结点为终止状态，并且每一条边表示一个转换关系，这样一个有限自动机的工作状态就可以采用状态转换图来描述了，从而可以把前面的图看成是一个有限自动机。
对于上图，有限自动机处在初始状态0，当读入符号a后，自动机便从状态
0转换到后继状态1中，再读入一个符号b后，自动机便从状态1转换到后继状态2。当自动机读入一个符号串，自动机则从初始状态开始，经过一系列状态转换，最终若能够到达终止状态，则称这一符号串被该自动机所接收或识别，否则不能被该自动机所接收。
二、实验目的要求
输入: 非确定有限(穷)状态自动机。
输出: 确定化的有限(穷)状态自动机
三、实验原理
一个确定的有限自动机(DFA)M可以定义为一个五元组，M,(K，?，F，S，Z)，其中:
(1) K是一个有穷非空集，集合中的每个元素称为一个状态;
(2) ?是一个有穷字母表，?中的每个元素称为一个输入符号;
(3) F是一个从K×??K的单值转换函数，即F(R，a),Q，(R，Q?K)表示当前
状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态;
(4) S?K，是惟一的初态;
(5) Z,K，是一个终态集。
由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每
个状态对字母表中的任一输入符号，最多只有一个后继状态。
对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。若M的初态结点同时又是终态结点，则称ε可为M所接受(或识别)，DFA M所能接受的全部字符串(字)组成的集合记作L(M)。
一个不确定有限自动机(NFA)M可以定义为一个五元组，M,(K，?，F，S，Z)，其中:
(1) k是一个有穷非空集，集合中的每个元素称为一个状态;
(2) ?是一个有穷字母表，?中的每个元素称为一个输入符号;
(3) F是一个从K×??K的子集的转换函数;
,(4) SK，是一个非空的初态集;
,(5) ZK，是一个终态集。
由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是:
(1)NFA的初始状态S为一个状态集，即允许有多个初始状态;
(2)NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。
因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。
对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记(ε除外)连接形成的字符串可为M所接受。NFA M所能接受的全部字符串(字)组成的集合记作L(M)。
由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。
设M和M是同一个字母集?上的有限自动机，若L(M),L(M)，则称有1212限自动机M和M等价。 12
由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等价。DFA是NFA的特例，因此对于每一个NFA M总存在一个DFA M，使得L(M)121,L(M)。即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有2
限自动机来接受该语言。
NFA确定化为DFA
同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。
下面介绍一种NFA的确定化算法，这种算法称为子集法:
(1) 若NFA的全部初态为S，S，„，S，则令DFA的初态为: 12n
S,[S，S，„，S]， 12n
其中方括号用来表示若干个状态构成的某一状态。
(2) 设DFA的状态集K中有一状态为[S，S，„，S]，若对某符号a??，在NFAii+1j’’’中有F({ S，S，„，S }，a)={ S，S，„，S } ii+1jii+1k’’’则令F({ S，S，„，S }，a)={ S，S，„，S }为DFA的一个转换函数。ii+1jii+1k’’‘若[ S，S，„，S ]不在K中，则将其作为新的状态加入到K中。 ii+1k
(3) 重复第2步，直到K中不再有新的状态加入为止。
(4) 上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表
仍然是NFA的字母表?。
(5) DFA中凡是含有NFA终态的状态都是DFA的终态。
对于上述NFA确定化算法——子集法，还可以采用另一种操作性更强的描述方式，下面我们给出其详细描述。首先给出两个相关定义。
假设I是NFA M状态集K的一个子集(即I?K)，则定义ε-closure(I)为:
(1) 若Q?I，则Q?ε-closure(I);
(2) 若Q?I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’?ε
-closure(I)。
状态集ε-closure(I)称为状态I的ε闭包。
假设NFA M,(K，?，F，S，Z)，若I?K，a??，则定义I,ε-closurea(J)，其中J是所有从ε-closure(I)出发，经过一条a弧而到达的状态集。
NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。
四、材料、试剂及仪器
微机
五、实验步骤(包括操作方法、数据处理)
六、注意事项
? 实现计算闭包closure(I)的算法;
? 实现转换函数move(q，a)的算法;
? 输出界面如下:
NFA的 图形形式
DFA的图形形式
七、思考题
实验 五
名称 DFA的最小化(Minimizing definitely finite automata ) 一、背景资料
NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。
二、实验目的要求
输入: DFA。
输出: 最小化的DFA。
三、实验原理
所谓自动机的化简问题即是对任何一个确定有限自动机DFA M，构造另一个确定有限自动机DFA M’，有L(M),L(M’)，并且M’的状态个数不多于M的状态个数，而且可以肯定地说，能够找到一个状态个数为最小的M’。
下面首先来介绍一些相关的基本概念。
设S是自动机M的一个状态，从S出发能导出的所有符号串集合记为(LS)。 iii
设有两个状态S和S，若有L(S),L(S)，则称S和S是等价状态。 ijijij
下图所示的自动机中L(B),L(C),{1}，所有状态B和状态C是等价状态。
0 A B
1 1
C D 1
又例如终态导出的符号串集合中必然包含空串ε，而非终止状态导出的符号串集合中不可能包含空串ε，所以终态和非终止状态是不等价的。
对于等价的概念，我们还可以从另一个角度来给出定义。
给定一个DFA M，如果从某个状态P开始，以字符串w作为输入，DFA M将结束于终态，而从另一状态Q开始，以字符串w作为输入，DFA M将结束于非终止状态，则称字符串w把状态P和状态Q区分开来。
把不可区分开来的两个状态称为等价状态。
设S是自动机M的一个状态，如果从开始状态不可能达到该状态S，则称iiS为无用状态。 i
设S是自动机M的一个状态，如果对任何输入符号a都转到其本身，而不i
可能达到终止状态，则称S为死状态。 i
化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去，也就获得了状态数最小的DFA。
下面具体介绍DFA的化简算法:
(1) 首先将DFA M的状态划分出终止状态集K和非终止状态集K。 12
K,K?K 12
由上述定义知，K和K是不等价的。 12
(2) 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。
设第i次划分已将状态集划分为k组，即: (i)(i)(i) K,K?K?„?K12k(i)对于状态集K(j=1,2,„,k)中的各个状态逐个检查，设有两个状态j(i)K’、 K’’?K，且对于输入符号a，有: jjj
F(K'，a),Kjm
F(K''，a),K jn
如果K和K属于同一个状态集合，则将K’和K’’放到同一集合中，mnjj
否则将K’和K’’分为两个集合。 jj
(3) 重复第(2)步，直到每一个集合不能再划分为止，此时每个状态集合
中的状态均是等价的。
(4) 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其
他一切等价状态。
(5) 若有无关状态，则将其删去。
根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自
动机的状态最少的自动机。
四、材料、试剂及仪器
微机
五、实验步骤(包括操作方法、数据处理)
六、注意事项
要求: ? 实现子集划分算法;
? 输出界面如下:
DFA的图形形式
最小DFA的图形形式
七、思考题
实验 六
名称 计算first集合和follow集合(Computing the first set and follow set) 一、背景资料
如果一个文法具有以下两个特点:
(1) 每个产生式的右部都由终结符开始;
(2) 如果两个产生式有相同的左部，那么他们的右部则由不同的终结符开始。
显然对于这样的文法，其推导过程完全可以根据当前的输入符号，决定选哪 个产生式往下推导，分析过程是惟一确定的，可以采用不带回溯的自上而下的预测分析方法。
如果两个产生式的左部相同，而右部都由非终结符开始，例如，存在A?α / β, α 和β均以非
终结符开始，那么就很难决定何时使用A?α 选项，何时使用A?β选项。 二、实验目的要求
输入:任意的上下文无关文法。
输出:所输入的上下文无关文法一切非终结符的first集合和follow集合。
三、实验原理
设文法G[S],(V，V，P，S)，则首字符集为: NT
**, FIRST(α),{a | αaβ，a?V，α,β?V }。 T
*
,若αε，ε?FIRST(α)。
由定义可以看出，FIRST(α)是指符号串α能够推导出的所有符号串中处于串首的终结符号
组成的集合。所以FIRST集也称为首符号集。
设α,xx…x，FIRST(α)可按下列方法求得: 12n
令FIRST(α),Φ，i,1;
(1) 若x?V，则x?FIRST(α); iTi
(2) 若x?V; iN
,? 若εFIRST(x)，则FIRST(x)?FIRST(α); ii
? 若ε?FIRST(x)，则FIRST(x),{ε}?FIRST(α); ii
(3) i,i+1，重复(1)、(2)，直到x?V，(i,2，3，…，n)或x?V且若εFIRST,iTiN
(x)或i>n为止。 i
当一个文法中存在ε产生式时，例如，存在A?ε，只有知道哪些符号可以合法地出现在非终
结符A之后，才能知道是否选择A?ε产生式。这些合法地出现在非终结符A之后的符号组成的集
合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。
设文法G[S],(V，V，P，S)，则 NT
FOLLOW(A),{a | S… Aa …，a?V}。 ,T
*
,若S…A，#?FOLLOW(A)。
由定义可以看出，FOLLOW(A)是指在文法G[S]的所有句型中，紧跟在非终结符A后的终
结符号的集合。
FOLLOW集可按下列方法求得:
(1) 对于文法G[S]的开始符号S，有#?FOLLOW(S);
*(2) 若文法G[S]中有形如B?xAy的规则，其中x，y?V ，则FIRST(y),{ε}?FOLLOW
(A);
(3) 若文法G[S]中有形如B?xA的规则，或形如B?xAy的规则且ε?FIRST(y)，其中
*x，y?V ，则FOLLOW(B)?FOLLOW(A);
四、材料、试剂及仪器
微机
五、实验步骤(包括操作方法、数据处理)
#include
#include
//产生式
struct css{
char left;
char zhuan;//用“-”表示箭头
char right[20];
};
//空标志
struct kong
{
int kongzuo;
int kongyou;
};
struct biaoji//第三步扫描式子的右部标记号
{
int r[100];
};
struct first//初步求first集合时用
{ char fjihe[200];
};
struct first2//保存最终的first集合 { char fjihe2[200];
};
struct follow//初步求follow集合时用 { char fow[200];
};
struct follow2//保存最终的follow集合 { char fow2[200];
};
void main()
{ int i,n,k;//产生式条数
css shizi[100];
kong kongshi[100];
cout<<"请输入产生式的条数n(n<100):"<>n;
cout<<"请从开始符输入产生式(空用“#”表示，产生式由字母组成):"<>shizi[i].left>>shizi[i].zhuan>>shizi[i].right;
}
int l,m,j,h,g,f;
for(l=0;l='a' && shizi[l].right[m]<='z' )
{
kongshi[l].kongyou=0; break;
}
}
for(j=0;j<=n;j++)
for(h=0;h='a' && shizi[a3].right[0]<='z')
{
linshi2[0]=shizi[a3].right[0];
strcat(fji[a3].fjihe,linshi2);
}
else { if(kongshi[a3].kongzuo==1)
{ strcat(fji[a3].fjihe,"#");
}
}
}
for(a5=0;a5<=n;a5++)
for(a6=0;shizi[a5].right[a6]!='\0';a6++)
if(shizi[a5].right[a6]>='A' && shizi[a5].right[a6]<='Z')
{ if(shizi[a5].right[0]>='a' && shizi[a5].right[0]<='z')break;
for(a7=0;a7='A'&&shizi[b2].right[b3]<='Z')
if(shizi[b2].right[b3+1]>='a'&&shizi[b2].right[b3+1]<='z')
{ linshi5[0]=shizi[b2].right[b3+1];
linshi5[1]='\0';
for(b9=0;b9='A'&&shizi[b2].right[b3+1]<='Z')
{ for(b4=0;b4
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
推导的逆过程，所以LR的分析过程是一种规范归约过程。
LR分析方法的基本思想是，在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号这3方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。
LR分析法的基本思想是符合哲理的。所以，这种分析法也是非常一般的。因此，实现起来也就非常困难。作为归约过程的“历史”材料的积累虽不困难(实际上，这些材料都保存在分析栈中)，但是，“展望”材料的汇集却是一件很不容易的事情。这种困难不是理论上的，而是实际实现上的。因为，根据历史推测未来，即使是推测未来的一个符号，也常常存在着很多可能性 。所以，当把“历史”和“展望”材料综合在一起时，复杂性就大大增加。如果简化对“展望”材料的要求，我们就可能获得实际可行的分析算法。
LR分析法比起自上向下的LL分析法和自下向上的优先分析方法对文法的限制要少得多，也就是说，对于大多数用无二义性上下文无关文法描述的语言都
可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快、准确、及时地指出出错位置的优点。LR分析法的一个主要缺点是，若用手工构造分析程序，则工作量相当大，因此，必须求助于自动产生这种分析程序的产生器。这种产生器称为LR分析程序自动产生器。本章我们将讨论这样一类产生器，利用这种产生器，我们不仅能自动产生一大类上下文无关文法的LR分析程序，还能指出文法含二义的情形或难于分析的特殊结构。
二、实验目的要求
输入:任意的压缩了的上下文无关文法。
输出:相应的LR(0)分析表。
三、实验原理
对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一个重要概念——文法的规范句型“活前缀”。
这种句柄之后不含任何符号的前缀称为活前缀。
在LR分析工作过程中的任何时候，栈里的文法符号(自栈底而上)XX„12X应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型(如果整m
个输入串确实构成一个句子)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。
对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号(自栈底而上)始终构成活前缀。
,假若一个文法G的拓广文法的活前缀识别自动机中的每个状态(项目集)G
不存在下述情况:(1)既含移进项目又含归约项目;(2)含有多个归约项目，则称G是一个LR(0)文法。该自动机的状态集合即为该文法的LR(0)项目集规范族。
构造识别文法活前缀DFA有3种方法:
(1)根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA;
(2)求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA;
(3)使用闭包函数(CLOSURE)和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。
符号串的前缀是指该符号串的任意首部，包括空串ε。例如，对于符号串abc，其前缀有ε，a，ab，abc。如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。
活前缀与句柄的关系如下:
(1)活前缀已含有句柄的全部符号，表明产生式A?β的右部β已出现在栈顶。
(2)活前缀只含句柄的一部分符号，表明A?ββ的右部子串β已出现121在栈顶，期待从输入串中看到β推出的符号。 2
(3)活前缀不含有句柄的任何符号，此时期望A?β的右部所推出的符号串。
在文法G的每个产生式的右部(候选式)的任何位置上添加一个圆点，所构成的每个产生式称为LR(0)项目。如产生式A, xyz有如下项目:A,.xyz，A,x.yz，A,xy.z，A,xyz.。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别(出现在栈顶)，可以用这种标有圆点的产生式来确定。
(1)A?β.刻划产生式A?β的右部β已出现在栈顶。
(2)A?β.β刻划A?ββ的右部子串β已出现在栈顶，期待从输入串12 121
中看到β推出的符号。 2
(3)A?.β 刻划没有句柄的任何符号在栈顶，此时期望A?β的右部所推出
的符号串。
(4)对于A?ε的LR(0)项目只有A?(。
G=VVSP 设文法(，，，)是一个上下文无关文法，若存在一个规范推导TN
*,SAwwAPA=(其中)，则称项目对活前缀是有,,,,,,,,,,,•,,,,1212121rmrm
LR(0) 效的，即有效项目。
从直观意义上讲，一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别，LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。
不同的LR(0)项目，反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同，将其分为四类:
(1)归约项目:
表现形式:A?a.
这类LR(0)项目表示句柄a恰好包含在栈中，即当前栈顶的部分内容构成了所期望的句柄，应按A?a进行归约。
(2)接受项目:
表现形式:?a. S
其中是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目，表S
示分析栈中内容恰好为a，用?a进行归约，则整个分析成功。 S
(3)移进项目:
表现形式:A?a.b,(b,V) T
这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分析栈。
(4)待约项目:
表现形式:A?α.Bβ (B,V) N
这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。
在给出LR(0)项目的定义和分类之后，我们从这些LR(0)项目出发，来构造能识别文法所有前缀的有限自动机。其步骤是:首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有限自
动机。
由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机的方法:
,(1)规定含有文法开始符号的产生式(设?A)的第一个LR(0)项目(即S
,?.A)为NFA的惟一初态。 S
(2)令所有LR(0)项目分别对应NFA的一个状态且LR(0)项目为归约项目的对应状态为终态。
(3)若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的圆点只相差一个位置，即:
若i为X?XX?„X?X„X，j为 X?XX„X?X„X，则从状态12i-1in 12ii+1ni引一条标记为X的弧到状态j。 i
(4)若状态i为待约项目(设X?α?Aβ)，则从状态i引ε弧到所有A??r的状态。
为了使“接受”状态易于识别，我们通常将文法G进行拓广。
,假定文法G是一个以S为开始符号的文法，我们构造一个，它包含了整G
,,个G，但它引进了一个不出现在G中的非终结符，并加进一个新产生式?S，SS
,,,以?S为开始符号。那么，我们称是G的拓广文法。 SGG
,这样，便会有一个仅含项目?S的状态，这就是惟一的“接受”态。 S
如果I是文法G,的一个项目集，定义和构造I的闭包CLOSURE(I)如下:
(1) I的项目都在CLOSURE(I)中。
(2) 若A?,.B,属于CLOSURE(I)，则每一形如B?.,的项目也属于
CLOSURE(I)。
(3) 重复(2)直到CLOSURE(I)不再扩大。
定义转换函数如下:
GO(I，X)= CLOSURE(J)
其中:I为包含某一项目集的状态，X为一文法符号，J={ A?,X ., | A?,.X ,?I}。
圆点不在产生式右部最左边的项目称为核，惟一的例外是S′?.S，因此用GOTO(I，X)状态转换函数得到的J为转向后状态闭包项目集的核。
使用闭包函数(CLOSURE)和转换函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，步骤如下:
(1) 置项目S′?.S为初态集的核，然后对核求闭包CLOSURE({S′
?.S})得到初态的闭包项目集。
(2) 对初态集或其他所构造的项目集应用转换函数GO(I，X)=
CLOSURE(J)求出新状态J的闭包项目集。
,3, 重复(2)直到不出现新的项目集为止。
计算LR(0)项目集规范族C={I，I , ... In }的算法伪代码如下: 01
Procedure itemsets(G’);
Begin C := { CLOSURE ({S’,.S})}
Repeat
For C 中每一项目集I和每一文法符号X
Do if GO(I,X) 非空且不属于C
Then 把 GO(I,X) 放入C中
Until C 不再增大
End;
一个项目集可能包含多种项目，若移进和归约项目同时存在，则称移进-归约
冲突，若
归约和归约项目同时存在，则称归约-归约冲突。下面看一个具体的例子:
我们希望能根据识别文法的活前缀的DFA建立LR分析器，因此，需要研究这个DFA的每个项目集(状态)中的项目的不同作用。
我们说项目A?β.β对活前缀αβ是有效的，其条件是存在规范推导121
。一般而言，同一项目可能对几个活前缀都是有效的(当一个,S,A,,,,,,,12
项目出现在几个不同的集合中时便是这种情形)。若归约项目A?β.对活前缀1,,,,,是有效的，则它告诉我们应把符号串归约为A，即把活前缀变成αA。111
,,若移进项目A?β.β对活前缀是有效的，则它告诉我们，句柄尚未形成，121
因此，下一步动作应是移进。但是，可能存在这样的情形，对同一活前缀，存在若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同，互相冲突。这种冲突通过向前多看几个输入符号，或许能够获得解决。
对于每个活前缀，我们可以构造它的有效项目集。实际上，一个活前缀γ的有效项目集正是从上述的DFA的初态出发，经读出γ后而到达的那个项目集(状态)。换言之，在任何时候，分析栈中的活前缀XX„X的有效项目集正是栈12m
顶状态S所代表的那个集合。这是LR分析理论的一条基本定理。实际上，栈m
顶的项目集(状态)体现了栈里的一切有用信息——历史。
前面我们已经对LR(0)文法进行了定义,下面我们来看一下LR(0)分析表是如何构造的。
对于LR(0)文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。下面是构造LR(0)分析表的算法。
假定C={I, I,…，In}，令每个项目集I的下标k为分析器的一个状态，因此，01k
G'的LR(0)分析表含有状态0，1，…，n。令那个含有项目S'?(S的I的下标kk为初态。ACTION子表和GOTO子表可按如下方法构造:
(1)若项目A?α.aβ属于I且GO (I, a)= I, a为终结符，则置ACTION[k, kkj
a]为“把状态j和符号a移进栈”，简记为“s”; j
(2)若项目A?α(属于I，那么，对任何终结符a，置ACTION[k，a]为“用k
产生式A?α进行规约”，简记为“r”;其中，假定A?α为文法G'的第j个产j
生式;
(3)若项目S'?S(属于I, 则置ACTION[k, #]为“接受”，简记为“acc”; k
(4)若GO (I, A)= I, A为非终结符，则置GOTO[k, A]=j; kj
(5)分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一个LR(0)文法，LR(0)文法是无二义的。
例如，文法G(E)的拓广文法如下:
(0)S'?E
(1)E?aA
(2)E?bB
(3)A?cA
(4)A?d
(5)B?cB
(6)B?d
该文法的LR(0)分析表如表所示。
ACTION GOTO State A b C D # E A B 0 S2 S3 1 1 acc 2 S4 S10 6 3 S5 S11 7 4 S4 S10 8 5 S5 S11 9 6 r1 R1 r1 r1 r1 7 r2 R2 r2 r2 r2 8 r3 R3 r3 r3 r3 9 r4 R4 r4 r4 r4 10 r5 R5 r5 r5 r5 11 r6 R6 r6 r6 r6
四、材料、试剂及仪器
微机
五、实验步骤(包括操作方法、数据处理)
六、注意事项
以表格形式输出，界面如下:
action goto
I
a1 „ # A1 „ An
0
?
n
七、思考题
实验 八
名称 基本块的划分(Dividing the basic block ) 一、背景资料
编译程序所生成的目标代码是依据程序设计语言结构的一般情况而设计的，不能依据特定源程序的具体上下文情况来生成目标代码。当然这种只依据共性，不考虑个性特征的设计必然会导致目标代码的质量低下，无法与手工产生目标代码的质量相比，但是其代码生成的效率比手工产生目标代码的效率要高。 所谓优化，是指在不改变程序运行效果的前提下，对被编译的程序进行变换，使之能生成更加高效的目标代码。这里所说的效率是指空间效率和时间效率。它是针对提高目标程序生成的质量而言的，而质量通常指目标程序所占的存储空间的大小和运行时间的长短。优化的目的是要使存储空间减少而又尽可能使程序的运行速度提高，常常后者更被关注。这里所指的变换，是通过重排、删除、合并或改变程序等手段，使程序产生形式上的变动。通常，程序所占存储空间少和程序运行时间短是一对相互冲突和相互制约的指标，往往是采用折中的
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
或者根据实际情况而偏向其中某一个指标。
一般对同一个程序来讲，进行优化与不进行优化产生的目标程序质量相差很大，所以优化及优化的效果是编译器的重要性能指标。当然，实施优化时还必须
考虑优化的代价，否则也会影响编译器的质量。
当然，要改进、提高程序的运行效率，还有很多其他途径，例如，通过改进算法、利用系统提供的程序库、进行编译时刻优化与进行源程序级程序等价变换等。
二、实验目的要求
输入:任意的四元式序列。
输出:相应的基本块的划分。
三、实验原理
基本块是一个连续的四元式序列，即控制流从其第一个四元式进入，而从最后一个四元式离开，其间没有停止，也没有分支。从源程序角度看，它是指程序中的一组顺序执行的语句序列，它只有一个入口和一个出口，入口就是它的第一个语句或称入口语句，出口就是它的最后一个语句或称出口语句。执行一个基本块时，只能从它的入口进入，从出口退出。这表明基本块的结构特征是:在块内，语句是无转移的顺序执行。
那么对于一个给定的程序，如何来确定基本块呢,下面，我们来介绍确定基本块的方法和步骤:
(1)确定每个基本块的入口语句。根据基本块的结构特点，它的入口语句是下列3种类型的语句之一:
? 程序的第一个语句;
? 由条件转移语句或无条件转移语句转移到的语句;
? 紧跟在条件转移或无条件转移后面的语句。
(2)根据确定的基本块的入口语句，构造其所属的基本块，即: ? 由该入口语句直到下一个入口语句的前一条语句之间的所有语句构成一个基本块;
? 由该入口语句到一转移语句(包括该转移语句)之间的所有语句构成一个基本块;
? 由该入口语句到程序中停止或暂停语句(包括该停止或暂停语句)之间的所
有语句构成一个基本块。
(3)凡是未包含在基本块中的语句，都是程序的控制流不可到达的语句，直接从程序中删除。
到此，可以实现把一个程序划分为若干个基本块，如果程序中还存在不属于任何基本块的语句，则说明这些语句永远不会被执行，因此可以将它们删除，不影响程序执行的结果。
四、材料、试剂及仪器
微机
五、实验步骤(包括操作方法、数据处理)
六、注意事项
七、思考题
浙公网安备 33021202002483