编译原理实习1报告
问题定义：
简单的文法分类。系统输入任意文法G的Vn，P和S，系统输出文法形式化表示G=(Vn，Vt，P，S)，文法的Chomsky类型（0型、1型、2型、3型）。为简单起见，文法符号都采用单字符符号。有多个候选式的产生式允许采用缩写形式(α::=β1|β2|β3|……|βn)。
需求分析：
输入：G[N]、Vn、P
输出：G[N] = (Vn，Vt，P，P0)和该文法的Chomsky类型。
用例图如下图所示：
根据输入和输出要求，可以得到以下需要解决的问题：
1.需要从输入数据中出起始状态P0；
2.需要从输入数据中提取出Vt集合；
3.需要从输入数据中得到该文法G[N]的Chomsky类型。
问题1：需要从输入数据中出起始状态P0。
分析：起始状态P0在输入数据G[N]中已经给出，根据定义和问题描述，起始状态P0仅包含一个字符，因此仅需出G[N]中’[’符号的位置，即可得到P0。
问题2：需要从输入数据中提取出Vt集合。
分析：终止符号集合需要根据Vn，从P中提取出来。P的输入格式为：
α::=β1|β2|β3|……|βn
终止符号有可能出现在左边α部分，也有可能出现在右边β部分。所以仅需确定字符串”::=”的位置，然后分别提取左边和右边部分，分别扫描字符，如果字符a不在Vn中，便将a加入Vt。右边部分扫描时需要排
除掉字符’|’。最后的结果便是最终确定的终结符号集合Vt。
问题3：需要从输入数据中得到该文法G[N]的Chomsky类型。
分析：文法Chomsky类型的判断方法如下图所示：
根据上图，出现3个问题，即3个文法类型判断条件：
判断条件1：左部是否是单个非终结符。
确定左部是否是单个非终结符，仅需确定每一个产生式的第一个字符是否在Vn中，并且字符串”::=”的起始位置在产生式的第二个字符位上，即左部长度只能为1。
判断条件2：右部是否是单一终结符或单一终结符跟着单一非终结符。
确定右部第一个字符是否是终结符，如果右部字符串长度为1，则结束判断，若是终结符，则为3型，否则为2型；如果右部长度为2，判断第二个字符是否是非终结符，是则非终结符为3型，否则为2型；如果
右部字符串长度大于2，则为2型。
判断条件3：对于每一个推导，左部长度均不大于右部长度。
比较每一个推导的左部长度和右部长度即可，若左部长度均不大于右部长度，则为1型；否则为2型。
设计：
类图如下所示：
说明：
Public:
Vn: 非终结字符
Vt: 终结字符
P: 产生式
NumOfVn: 非终结字符总数
NumOfVt: 终结字符总数
NumOfP: 产生式总数
P0: 起始状态
GetTypeOfGrammer(): 取得文法类型
Private:
Find(): 查字符是否在某字符串中
GetVt(): 提取Vt
GrammaticalJudgement(): 文法类型判断
SortVn():  将Vn按字典序排序
IfInVn(): 判断字符是否在Vn中
IfInVt(): 判断字符是否在Vt中
TypeOfGrammer(): 格式化输出
界面：
为方便调试，测试时加了一个产生式规则个数，最后已删去。
活动图如下所示：
初步文法判断即区分0、1型文法和2、3型文法，最终文法判断即确定最终文法类型，具体方法在分析部分已经给出。在文法判断过程中，需要判断字符是否在Vn 或Vt中，需要事先确定Vt和一些细节，以下是有关代码：
关于Vn、Vt的存储和查：
存储方式为一维线性空间。
经过快速排序sort(Vn,Vn+NumOfVn)；将线性空间中的字符按字典序排序。
排序时间复杂度为：O(N*LogN)。
查方式为2分查：
bool Find(char*ch, char x, int l) {
int low = 0, high = l-1, j = -1;
int m = (low + high) / 2;
while (low <= high && j == -1) {
if (x == ch[m])
j = m;
else if (x <ch[m])
high = m - 1;
else
low = m + 1;
}
if (j == -1) return false;
else return true;
}
查时间复杂度为：O(LogN)。
关于Vt的确定：
只用出左部和右部的符号中，不在Vn中的符号即可。由于’:’和’=’有可能在推导的左部或右部出现，所以不能以单独的字符来确定左部和右部：
G.NumOfVt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j <strstr(G.P[i],"::=")-G.P[i]; j++) {
//strstr(G.P[i],"::=")-G.P[i]用来确定左部的末端
if (G.P[i][j]!='|') {
if (!G.IfInVn(G.P[i][j])&&!G.IfInVt(G.P[i][j]))
G.Vt[G.NumOfVt++] = G.P[i][j];
}
}
字符串长度规则
for (int i = 0; i < n; i++)
//查右部是否有终结符号
for (int j = strstr(G.P[i],"::=")-G.P[i]+3; j <strlen(G.P[i]); j++) {
if (G.P[i][j]!='|') {
if (!G.IfInVn(G.P[i][j])&&!G.IfInVt(G.P[i][j]))
G.Vt[G.NumOfVt++] = G.P[i][j];
}
}
初步文法判断：左部是否是单个非终结符。
for (int i = 0; i < n; i++) {
for (int j = 0; j <strstr(G.P[i],"::=")-G.P[i]; j++)
if (!G.IfInVn(G.P[i][j])||j > 0)
//!G.IfInVn(G.P[i][j])限定是否是非终结字符；j > 0左部的长度。
flag23 = false;
}
最终文法判断：
if (flag23) {
for (int i = 0; i < n; i++) {
flagVt = false;
//3型文法的右部为单一终结符或者单一终结符跟单一非终结符，flagVt用来判断是否已经判断完第一个非终结符。
for (int j = strstr(G.P[i],"::=")-G.P[i]+3; j <strlen(G.P[i]); j++)
if (G.P[i][j]!='|') {
if (flagVt) {
if (!G.IfInVn(G.P[i][j])) {

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。