编译原理LL1文法
在上次介绍了词法分析之后，这次介绍如何将一个普通文法，消除左递归，提取左因子，从而得到LL1文法。先贴出最终的效果图 
这里给出具体的实现要求
1、将一个可转换非LL（1）文法转换为LL（1）文法，要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。
2、提取文法左因子算法：
1）对文法G的所有非终结符进行排序
2）按上述顺序对每一个非终结符Pi依次执行:
for( j=1； j< i-1；j++)
将Pj代入Pi的产生式（若可代入的话）；
消除关于Pi的直接左递归：
Pi -> Piα|β ，其中β不以Pi开头，则修改产生式为：
Pi —＞ βPi′
Pi′—＞ αPi′|ε
3）化简上述所得文法。
3、提取左因子的算法：
A —＞ δβ1|δβ2|…|δβn|γ1|γ2|…|γm
(其中,每个γ不以δ开头)
那么,可以把这些产生式改写成
A —＞ δA′|γ1| γ2…|γm
A′—＞β1|β2|…|βn
4、利用上述算法，实现构造一个LL（1）文法：
1）从文本文件g.txt中读入文法
2）设计函数remove_left_recursion（）和remove_left_gene（）实现消除左递归和提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子；
3）整理得到的新文法；
4）在一个新的文本文件newg.txt输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。
输入数据：
编辑一个文本文文件g.txt，在文件中输入如下内容：
S->Qc|c|cab;
Q->Rb|b;
R->Sa|a;
正确结果：
本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：
S- >Qc|cT;
T->@|ab; //由于无法输出ε，用@代替
Q->Rb|b;
R->bcaU|caU|cabaU|aU;
U->bcaU|@;
下面以C++代码实现
///////////////////////////////
/////Author:Jameslong
/////Date:4/20/2017
//////////////////////////////
#include<iostream>
#include <fstream>
#include<string>
#include<list>
using namespace std;
list<string> vf;
list<list<string>> ListVf;
list<list<string>>::iterator it_i;
list<list<string>>::iterator it_j;
list<string>::iterator it_k;
list<string>::iterator it_m;
char ch;//每个要比对的字符
string str = "";//每个要分析的单词
ifstream in;//文件输入流
char buf[1024]; //缓存
char *p;//指针，之所以用指针，是因为有回退的操作
//加载文件,并读到缓存
void infile(string filename){
p = buf;
memset(buf, 0, 1024);
in.open(filename);
while ((*p = in.get()) != EOF)
{
p++;
}
p = buf;//将指针移到缓存的首地址
}
//关闭文件
void closefile(){
in.close();
}
//获取缓存中当前指针所指字符，根据返回值判断是否到缓存结束，即文件结束（缓存要足够大）
int Getchar(){
if (*p != EOF){
ch = *p;
p++;
return 1;
}
else
return 0;
}
//若当前字符为空，或者为制表符（9）或者为换行符（10）或者为换页符（12）则取下一个字符，直到当前字符合法
void getBC(){
while (ch == ' ' || ch == 9 || ch == 10 || ch == 12)
Getchar();
}
//连接字符串
void Concat(){
str += ch;
}
//判断当前字符是否为|
bool isVerticalBar(){
return ch =='|';
}
//判断当前字符是否为;
bool isSemicolon(){
return ch == ';';
}
//代码异常出现
void procError(){
cout << "Something is wrong..." << endl;
}
//扫描得到文法的列表
int scan(){
if (!Getchar()) return 0;
getBC();
if (ListVf.empty()){
ListVf.push_back(vf);
//cout << "sizeof(listvf):" << ListVf.size() << endl;
}
if (ch == '-'){
ListVf.back().push_back(str);
str = "";
//cout << "插入成功么：" << ListVf.back().back()<<endl;
Getchar();
return 1;
}
else if (isSemicolon()){
ListVf.back().push_back(str);
//(ListVn.back()->data).insertAsLast(str);
str = "";
//cout << "插入成功么：" << ListVf.back().back() << endl;
ListVf.push_back(*new list<string>);
//cout << "新添加一个List" << endl;
}
else if (isVerticalBar()){
ListVf.back().push_back(str);
//ListVn.last()->data.insertAsLast(str);
//cout << "插入成功么：" << ListVf.back().back();
//cout << endl << "sizeof(listvn):"<<ListVf.size() << endl;
str = "";
}
else{
Concat();
//cout << str << endl;
}
return 1;
}
void show(){//显示文法
for (it_i = ListVf.begin(); it_i != ListVf.end(); ++it_i){
list<string>::iterator j = it_i->begin();
cout << *j << "->";
for (int i = 2; i < it_i->size();i++){
j++;
cout << *j << " | ";
}
j++;
cout << *j;
cout << ";"<<endl<<endl;
}
}
//消除左递归
int removeLeftRecursion(){
while (scan());
ListVf.pop_back();
cout << "----------------" << endl;
cout << "初始的文法：" << endl;
show();//显示初始文法
cout << "----------------" << endl;
list<string> vn;//非终结符集合
list<list<string>>::iterator it;
for (it = ListVf.begin(); it != ListVf.end(); ++it){//非终结符集合
vn.push_back(it->front());
}
list<string>::iterator it_vn;
cout << "非终结符集合" << endl;
for (it_vn = vn.begin(); it_vn != vn.end(); ++it_vn){
cout << *it_vn << " ";
}
cout << endl<<"----------------" << endl;
int i = 0;
for (it_i = ListVf.begin(); it_i != ListVf.end(); ++it_i){
for (it_j = ListVf.begin(); it_j != it_i; ++it_j){
it_k = it_i->begin();
for (it_k++; it_k != it_i->end();){
string str1 = *it_k;
string str2 = it_j->front();
if (str1.substr(0,1)==str2){//若Pi = pja
it_m = it_j->begin();
for (it_m++; it_m != it_j->end(); it_m++){
it_i->insert(it_k,*it_m+str1.substr(1,str1.length()));
}
it_k = it_i->erase(it_k);
for (int i = 0; i < it_j->size() - 1;i++){
it_k--;
}
}
else{
++it_k;
}
}
}
bool flag = false;
list<string>::iterator i = it_i->begin();
string str2 = "";
string str3 = "";
for (i++; i != it_i->end();++i){
if (i->substr(0,1) == it_i->front()){//扫描判断是否存在R->Ra...的情况
string s = i->substr(1, i->size());
*i = s;
str2 = s;
flag = true; break;
}
}
it_i->unique();//去重
if (flag){//若存在直接左递归，则消除之
list<string>::iterator j = it_i->begin();
str3 = it_i->front() + "'";//记录R'
for (j++; j != it_i->end(); j++){
*j = *j + it_i->front() + "'";
}
list<string> la;//添加R'生成式到文法
la.push_back(str3);
la.push_back(str2+str3);
la.push_back("@");
ListVf.push_back(la);
}
}
cout << "消除左递归后的文法：" << endl;
show();//显示消除左递归后的数值
cout << "----------------" << endl;
return 0;
}
int removeLeftGene(){
for (it_i = ListVf.begin(); it_i != ListVf.end(); ++it_i){
list<string>::iterator i = it_i->begin();
list<string>::iterator p = it_i->begin();
i++;
list<string> lm;
for (; i != it_i->end(); i++){
p = i;
if (i->at(0) > 'z' || i->at(0) < 'a')continue;
for (p++; p != it_i->end(); p++){
if (p->at(0) == i->at(0)){
if (p->at(p->size() - 1) >= 'a'&&p->at(p->size() - 1) <= 'z') {//末位是小写字母
if (lm.empty()){
if (i->size() > 1){
lm.push_back(i->substr(1, i->size() + 1));
}
if (p->size() > 1){
lm.push_back(p->substr(1, i->size() + 1));
}
lm.push_back("@");
lm.push_back(it_i->front()+"^");//没搞懂只能从后面pushS^
}else
lm.push_back(*p);
i = it_i->erase(i);
*i = i->substr(0, 1) + it_i->front() + "^";
}
else{ continue; }
}
else{ continue; }
}
if (!lm.empty()){
string s = lm.back();
lm.pop_back();
lm.push_front(s);
ListVf.push_back(lm);
}
}
}
cout << "提取左因子后的文法：" << endl;
show();//显示提取昨因子后的文法
cout << "----------------" << endl;
return 0;
}
int main(){
string filename = "./test.txt";
infile(filename);
removeLeftRecursion();
removeLeftGene();
closefile();
return 0;
}
这次主要使用了C++的list容器，对它的主要接口还是不太熟悉。以后在C++模块在详细研究和介绍。