编译原理实验2——消除语法中的左递归（C++实现）
首先给出书中算法的截图：
步骤一：处理生产输入
所有产品都存储在一个结构中：
struct node
{
string left;
set<string>right;
};
正如你所看到的，left代表作品的左侧部分，right代表作品的右侧部分，并且它是一个集合。
例如S->Qc|c，程序中，左=S，右=Qc,c
输入结果保存在一个数据结构中，命名为v
输入函数为：
void getproduction()
{
printf("若一个非终结符可推出多个结果，请直接以 | 分隔，不必分开输入\n");
printf("输入产生式,以$为结束标志:\n");
string str;
while (cin >> str && str[0] != '$')
{
vector<node>ret = mysplit(str);
v.push_back(ret[0]);
}
}
由于输入的是一整行字符串，所以我们需要根据字符剥离出产生式左右部分的结果，并在这里调用()函数。 下面是()函数的具体代码。
vector<node> mysplit(string str)
{
string vleft;
set<string>vright;
string temp = "";
for (int i = 0; i < str.size(); 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);
vector<node>ret;
struct node N = {vleft,vright};
ret.push_back(N);
return ret;
}
代码原理很简单。 它直接遍历字符串，遇到-、>、|等特殊字符时向左或向右插入。
步骤2：获取所有非终结符号并对其进行排序
void getnotend()
{
set<string>tempset;
for (int i = 0; i < v.size(); i++)
{
tempset.insert(v[i].left);
}
set<string>::iterator it = tempset.begin();
for (it; it != tempset.end(); it++)
{
notend.push_back(*it);
}
}
() 函数获取所有非终结符号。 直接遍历v中保存的所有产生式的左边部分，存入set中。
（v是保存所有产生式的变量名，是一种类型）
所有非终结符都存储在 中，它们被定义为类型
第三步：两层for循环，这里封装成()函数。
void myoperate()
{
for (int i = 0; i < notend.size(); i++)//FOR i:=1 TO N DO
{
for (int j = 0; j < i; j++)//FOR j:=1 TO i-1 DO
{
int posi=-1, posj=-1;
for (int k = 0; k < v.size(); k++)
{
if (v[k].left == notend[i])/*遍历所有产生式，找到第i个非终结符在所有产生式中的位置*/
{
posi = k;
break;
}
}
for (int k = 0; k < v.size(); k++)/*遍历所有产生式，找到第i个非终结符在所有产生式中的位置*/
{
if (v[k].left == notend[j])
{
posj = k;
break;
}
}
if (posi == -1 || posj == -1)continue;/*如果找不到，就不执行下面的代码。例如：非终结符S在v中是第3个，非终结符R在v中是第1个，则posi=3,posj=1*/
set<string>::iterator it = v[posi].right.begin();
set<string>::iterator it2 ;
set<string>tempset;
for (it; it != v[posi].right.end(); it++)
{
string tempstr = *it;
string ss;
if (tempstr.find(notend[j]) != -1)
{
for (it2 = v[posj].right.begin(); it2 !=v[posj].right.end(); it2++)
{
ss = tempstr;
ss = myreplace(ss, notend[j], *it2);
tempset.insert(ss);
}
}
}
vector<string>temv;
for (it = v[posi].right.begin(); it != v[posi].right.end(); it++)
{
string str = *it;
if (str.find(notend[j]) != -1)
temv.push_back(str);
}
for (int x = 0; x < temv.size(); x++)
{
it = v[posi].right.find(temv[x]);
if (it != v[posi].right.end())
v[posi].right.erase(it);
}
for (it = tempset.begin(); it != tempset.end(); it++)
v[posi].right.insert(*it);
erasedirect(posi);
}
}
}
这里给出了这个函数的解释。 代码中使用了很多临时变量来记录信息。 但总体思路是这样的：
就拿书上给的例子来说，有一个语法：
(1)S->Qc|c
(2) Q->Rb|b
(3) R->Sa|a
找到消除左递归的最终语法。
由于代码中的下标是从0开始的，所以当i=2且j=0时，我们看(1)和(3)的产生式。 我们取产生式 (3) 的所有右侧并得到 Sa 和 a。 对于右边的每个部分，如果它有第j个非终结符号，则可以替换从第j个终结符号导出的所有结果。
比如我们取出Sa，发现它有第j个非终结符S，那么所有能从S导出的结果都可以转移到Sa上，Sa就可以变成Qca和ca。 然后，我们取出a，发现它没有S，就跳过它。 最后是R->Qca|ca|a，这就是书上的答案。
代码中已经考虑了一些细节，具体请参考代码。
第四步：消除Ai中的所有直接左递归
首先，书中定义了直接左递归：
A->Aa1|Aa2|…|Aam|b1|b2|b3|b3
然后，我们看看生产是否满足这个形式
一、如何确定b1、b2、b3？
如果右边没有大写字母，可以认为是b1,b2,b3
因此，我们有以下函数：
bool allend(string str)
{
for (int i = 0; i < str.size(); i++)
{
if (str[i] >= 'A' && str[i] <= 'Z')
return false;
}
return true;
}
如何判断右侧部分与左侧部分是否以相同的字符串开头？
首先给出c++字符串搜索函数find()和rfind()。
find()可以从前往后查找，找到第一个匹配的字符串，并返回下标。 如果没有找到，则返回-1
rfind() 可以从后向前查找，找到第一个匹配的字符串，并返回下标。 如果没有找到，则返回-1
然后，我们可以从前往后查找，再从后往前查找。 如果遇到的第一个匹配字符是下标0，则表示匹配
A->Aa 这种形式。 例如A->AabcA，find()的结果是0，rfing()的结果是4。
消除所有直接左递归的代码如下：
void erasedirect(int posi)
{
set<string>::iterator it = v[posi].right.begin();
bool flag = true;
for (it; it != v[posi].right.end(); it++)
{
string str = *it;
if ((str.find(v[posi].left) == str.rfind(v[posi].left) && str.find(v[posi].left) == 0) || allend(str))
flag = true;
else
{
flag = false;
break;
}
}
if (!flag)return;
vector<string>va, vb;
for (it = v[posi].right.begin(); it != v[posi].right.end(); it++)
{
string str = *it;
if (str.find(v[posi].left) == -1)
{
vb.push_back(str);
}
else
{
str.erase(0, v[posi].left.size());
va.push_back(str);
}
}
v[posi].right.clear();
for (int i = 0; i < vb.size(); i++)
{
v[posi].right.insert(vb[i] + v[posi].left+"'");
}
set<string>ans;
for (int i = 0; i < va.size(); i++)
{
ans.insert(va[i] + v[posi].left + "'");
}
ans.insert("Σ");
struct node N = { v[posi].left + "'",ans };
v.push_back(N);
}
首先，我们判断Ai的产生是否满足A->Aa|b的形式。 如果不是，flag=false，直接终止操作。 否则，继续。
当我们确定Ai导出的公式都是Aa或b后，我们就可以遍历Ai的所有右边部分，取出Aa存入va，取出b存入vb，然后串接起来得到非的答案 只需在终止符上添加一个笔划即可。
最后给出完整的可运行代码：
#include测试用例是书中原标题：
(1)S->Qc|c
(2) Q->Rb|b
(3) R->Sa|a
找到消除左递归的最终语法。
给定输入：
S->Qc|c
Q->Rb|b
R->Sa|a
$
运行结果：
这个答案和书上给出的不一样。 这是因为（非终结符号）中的排序结果是按照字典序从小到大排列的，结果是Q、R、S。
下面我们强制输入顺序为S、Q、R。我们只需要将获取非终结符的函数()注释掉，手动给出顺序S、Q、R即可。
结果和书上给出的结果一样！
书中也给出了R、Q、S的顺序，我们也会验证一下。
答案还是一样！
