编译原理 |
您所在的位置：网站首页 › 编译原理第3章文法和语言的关系 › 编译原理 |
编译原理
|
一、首先我们给出书中的代码，下面的代码将会是书中代码的实现 二、产生式的存储 产生式使用如下结构存储 struct node { string left; setright; };对产生式E’->#E#来说，left=E’ , right=#E# 其他数据结构： typedef pairPII; setnotend; setisend; string notendarr[1010]; char isendarr[1010]; bool F[1010][1010]; stackstk;三，输入处理 输入以一行字符串代表一个产生式，我们需要对这个字符串进行处理，把所有的非终结符剥离出来，把所有的终结符剥离出来。把产生式的左部剥离出来，把产生式的右部剥离出来。 这里直接给出字符串处理的代码 string str; printf("若一个非终结符可推出多个结果，请直接以 | 分隔，不必分开输入\n"); printf("输入产生式,以$为结束标志:\n"); while (cin >> str && str[0] != '$') { struct node N = mysplit(str); v.push_back(N); int pos = 0; for (int i = 0; i if (str[i] == '-' || str[i] == '>'||str[i]=='|')continue; if (!(str[i] >= 'A' && str[i] if (str[i] == '>')continue; if (str[i] == '-') { vleft = temp; temp = ""; continue; } if (str[i] == '|') { vright.insert(temp); temp = ""; continue; } temp += str[i]; } if (temp != "")vright.insert(temp); struct node N = { vleft,vright }; return N; }以书中例题为例，这里我们的测试文法如下 E'->#E# E->E+T E->T T->T*F T->F F->P↑F|P P->(E) P->i总之，经过上述代码处理，我们可以在数据结构中存储我们想要的值 (存储终结符)isend={↑，#，（，），*，+，i}; (存储非终结符)notend={E’,E,T,F,P}; (存储终结符的数组)isendarr,其值与isend相同，这里为了后续访问方便，需要从isend中复制过来 (存储非终结符的数组)notendarr,其值与notend相同,这里为了后续访问方便，需要从notend中复制过来 四、实现INSERT函数 首先，函数中的A是产生式左部，a是产生式右部的一部分。 我们需要根据A，找到非终结符中A的下标，这才是伪代码中的iA. 我们需要根据a,找到终结符中a的下标，这才是伪代码中的ja. 因此，我们直接遍历isendarr和notendarr就好了。 查找iA和ja的代码如下： int findia(string A) { for (int i = 1; i for (int i = 1; i int ia = findia(A); int ja = findja(a); if (F[ia][ja] == false) { F[ia][ja] = true; PII t = {A,a}; stk.push(t); } }这里的PII 见第一点的声明，stk就是伪代码中的栈。 五、实现主程序 初始化F这个布尔数组 for (int i = 1; i set::iterator it = v[i].right.begin(); for (it; it != v[i].right.end(); it++) { string temp = *it; char a; if (a=check(temp)) { if (a == EOF)continue; myinsert(v[i].left, a); } } }这里的check函数就是检查产生式是否形如伪代码中所示，其实现如下，若不和要求，返回EOF： char check(string str) { if (!(str[0] >= 'A' && str[0] PII t = stk.top(); string B = t.first; char a = t.second; stk.pop(); for (int i = 0; i string temp = *it; string ret = getnotend(temp); if(mycmp(ret,B)) myinsert(v[i].left,a); } } }这里如何判断产生式是形如A->B…呢，我们获取产生式右部的非终结符前缀，具体实现在getnotend函数中，比如A->E#E,前缀就是E, A->EE#E,前缀就是EE,然后与栈顶的值比较即可。 string getnotend(string str) { string ret = ""; for (int i = 0; i string left; setright; }; vectorv; int findia(string A) { for (int i = 1; i for (int i = 1; i int ia = findia(A); int ja = findja(a); if (F[ia][ja] == false) { F[ia][ja] = true; PII t = {A,a}; stk.push(t); } } node mysplit(string str) { string vleft; setvright; string temp = ""; for (int i = 0; i vleft = temp; temp = ""; continue; } if (str[i] == '|') { vright.insert(temp); temp = ""; continue; } temp += str[i]; } if (temp != "")vright.insert(temp); struct node N = { vleft,vright }; return N; } void init() { set::iterator it; int pos = 1; for (it = notend.begin(); it != notend.end(); it++) { string temp = *it; notendarr[pos++] = temp; } pos = 1; set::iterator it2; for (it2 = isend.begin(); it2 != isend.end(); it2++) { char temp = *it2; isendarr[pos++] = temp; } } char check(string str) { if (!(str[0] >= 'A' && str[0] string ret = ""; for (int i = 0; i if (s1.size() != s2.size()) return false; for (int i = 0; i string str; printf("若一个非终结符可推出多个结果，请直接以 | 分隔，不必分开输入\n"); printf("输入产生式,以$为结束标志:\n"); while (cin >> str && str[0] != '$') { struct node N = mysplit(str); v.push_back(N); int pos = 0; for (int i = 0; i if (str[i] == '-' || str[i] == '>'||str[i]=='|')continue; if (!(str[i] >= 'A' && str[i] set::iterator it = v[i].right.begin(); for (it; it != v[i].right.end(); it++) { string temp = *it; char a; if (a=check(temp)) { if (a == EOF)continue; myinsert(v[i].left, a); } } } while (stk.size() != 0) { PII t = stk.top(); string B = t.first; char a = t.second; stk.pop(); for (int i = 0; i string temp = *it; string ret = getnotend(temp); if(mycmp(ret,B)) myinsert(v[i].left,a); } } } printf("每个非终结符的FIRSTVT集合为：\n"); for (int i = 1; i if (F[i][j] == 1) cout |
【本文地址】
今日新闻 |
推荐新闻 |