?? createt.h
字號:
#ifndef HEADER_CREATET
#define HEADER_CREATET
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include "LLTable.h"
typedef vector<vector<char> > Vec;
class First_Follow
{
vector<string> strToken;//文法表達式
vector<string> vt;//非終結(jié)符集合
vector<string> temp;//中間變量
Vec FIRST;//FIRST集合
Vec FOLLOW;//FOLLOW集合
public:
void Init();//初始化
void first();//求FIRST集合
void follow();//求FOLLOW集合
void createTable(Table lltable);//創(chuàng)建表
};
void First_Follow::Init()
{
ifstream in("a.txt");
for( string str; getline(in,str); )
strToken.push_back(str);//從文件中讀出文法存到strToken中
for( int i = 0; i < strToken.size(); i++)
{
int j = 0;
string s = "";//求非終結(jié)符
while( strToken[i][j] != '-' )//"->"以前為非終結(jié)符
{
s += strToken[i][j];
j++;
}
vt.push_back(s);//存到vt中
}
FIRST.resize(vt.size());//設(shè)置大小
FOLLOW.resize(vt.size());
FOLLOW[0].push_back('#');//置#于開始符號的FOLLOW集合中
temp = vt;
}
void First_Follow::first()
{
int i;
while( !temp.empty() )
{
for( i = 0; i < vt.size(); i++)
{
if( temp.back() == vt[i] )
break;
}
if( FIRST[i].size() == 0)//當前FIRST集合為空
{
int flag = 0;
for( int j = vt[i].size() + 2; j < strToken[i].size(); j++)
{
if( flag == 0 && ((strToken[i][j] > 'a' && strToken[i][j] < 'z') ||
strToken[i][j] == '+' || strToken[i][j] == '*' ||
strToken[i][j] == '(' || strToken[i][j] == ')' ||
strToken[i][j] == '$'))//是終結(jié)符號，則FIRST(X) = {X}
{
FIRST[i].push_back(strToken[i][j]);
}
else if( flag == 0 )//為非終結(jié)符號
{
string s = "";//存非終結(jié)符
s += strToken[i][j];
if( strToken[i][j+1] == '\'')
s += '\'';
for( int k = 0; k < vt.size(); k++)
{
if( vt[k] == s )//找到該非終結(jié)符的定義
{
if( FIRST[k].size() != 0)//FIRST[k]不為空，把FIRST[k]加到FIRST[i]中
{
for( int m = 0; m < FIRST[k].size(); m++ )
{
int flag1 = 0;
for( int n = 0; n < FIRST[i].size(); n++)
{
if( FIRST[i][n] == FIRST[k][m])//判斷要加入的元素是否已經(jīng)存在
{
flag1 = 1;//存在標志為置1
break;
}
}
if( flag1 == 0 || FIRST[k][m] != '$')//不存在,且不為'$'
FIRST[i].push_back(FIRST[k][m]);
}
}
else//FIRST[k]為空
{
temp.push_back(s);//s非終結(jié)符加到向量temp尾部
first();
for( int m = 0; m < FIRST[k].size(); m++ )//把FIRST[k]加到FIRST[i]中
{
int flag1 = 0;
for( int n = 0; n < FIRST[i].size(); n++)
{
if( FIRST[i][n] == FIRST[k][m])
{
flag1 = 1;
break;
}
}
if( flag1 == 0 || FIRST[k][m] != '$')
FIRST[i].push_back(FIRST[k][m]);
}
}
break;
}
}
}
if( strToken[i][j] == '|')//出現(xiàn)'|'則對應下一個表達式，flag恢復初始值
flag = 0;
else
flag = 1;
}
}
else
temp.pop_back();//求完FIRST(X)則刪除X
}
}
void First_Follow::follow()
{
temp = vt;
int i;
for( int i2 = 0; i2 < temp.size(); i2++)
{
for( i = 0; i < vt.size(); i++)
{
if( temp[i2] == vt[i] )
break;
}
for( int j = 0; j < strToken.size(); j++)
{
int k;
int flag = 0;
for( k = 3; k < strToken[j].length(); k++)//從文法中找非終結(jié)符vt[i][0]
{
if( strToken[j][k] == vt[i][0] )
{
if( vt[i].size() == 1 )//為X形式
{
if( strToken[j].length() > k + 1 && strToken[j][k+1] == '\'' )
continue;//X與X'不相等
flag = 1; //匹配后置1
k++;//指向下一個非終結(jié)符
break;
}
if( vt[i].size() == 2 )//為X'形式
{
if( strToken[j].length() > k + 1 && strToken[j][k+1] == '\'')
{
k += 2; //指向下一個非終結(jié)符
flag = 1;
break;
}
}
}
}
if(flag == 1)//已匹配
{
string s = ""; //A后面的字串
while( k < strToken[j].length() && strToken[j][k] != '|')
{
s += strToken[j][k];
k++;
}
if( s.length() == 0 )//s為空，即為B->@A的形式
{
if(FOLLOW[j].size() == 0)
{
temp.push_back(vt[i]);
break;
}
for( int m = 0; m < FOLLOW[j].size(); m++ )//FOLLOW[j]加入FOLLOW[i]中
{
int flag1 = 0;
for( int n = 0; n < FOLLOW[i].size(); n++)
{
if( FOLLOW[i][n] == FOLLOW[j][m])
{
flag1 = 1;
break;
}
}
if( flag1 == 0 )
{
FOLLOW[i].push_back(FOLLOW[j][m]);
}
}
}
else
{
if( s.length() == 1 &&
((s[0] > 'a' && s[0] < 'z') ||
s[0] == '+' || s[0] == '*' ||
s[0] == '(' || s[0] == ')' ||
s[0] == '$'))//s不為空，但是終結(jié)符，F(xiàn)IRST[s]加入FOLLOW[i]中
{
FOLLOW[i].push_back(s[0]);
continue;
}
for( int i1 = 0; i1 < vt.size(); i1++)//s為非終結(jié)符
{
if( vt[i1] == s )
{
int flag2 = 0;
for( int m = 0; m < FIRST[i1].size(); m++ )//將非'$'FIRST[s]加入到FOLLOW[i]中
{
int flag1 = 0;
if( FIRST[i1][m] == '$' )
flag2 = 1;
for( int n = 0; n < FOLLOW[i].size(); n++)
{
if( FOLLOW[i][n] == FIRST[i1][m])
{
flag1 = 1;
break;
}
}
if( flag1 == 0 && FIRST[i1][m] != '$')
FOLLOW[i].push_back(FIRST[i1][m]);
}
if( flag2 == 1)//如果'$'屬于FIRST[s],則將FOLLOW[j]加入到FOLLOW[i]中
{
if(FOLLOW[j].size() == 0)
{
temp.push_back(vt[i]);
break;
}
for( int m = 0; m < FOLLOW[j].size(); m++ )
{
int flag1 = 0;
for( int n = 0; n < FOLLOW[i].size(); n++)
{
if( FOLLOW[i][n] == FOLLOW[j][m])
{
flag1 = 1;
break;
}
}
if( flag1 == 0 )
FOLLOW[i].push_back(FOLLOW[j][m]);
}
}
break;
}
}
}
}
}
}
}
void First_Follow::createTable(Table lltable)
{
Init();
first();
follow();
for(int i = 0; i < FIRST.size(); i++)
{
int k = 3;
vector<string> t;
string s = "";
string str = "";
for( k = 2; k < strToken[i].length(); k++)
{
if( strToken[i][k] == '>')
break;
}
k++;
for( ; k < strToken[i].length(); k++)//將文法分成更小的表達式
{
if( strToken[i][k] == '|')
{
t.push_back(s);
s = "";
continue;
}
s += strToken[i][k];
}
t.push_back(s);
for(int j = 0; j < FIRST[i].size(); j++)
{
str = vt[i] + "->";
int flag = 0;
for( int m = 0; m < t.size(); m++)//查找表達式
{
if( FIRST[i][j] == t[m][0] )
{
str += t[m];
flag = 1;
break;
}
}
if( flag == 0 )
{
str += t[0];
}
if( FIRST[i][j] == '$' )
{
for( int l = 0; l < FOLLOW[i].size(); l++)
{//A->@ 加到M[A,a]中 ，a屬于FIRST(@)
lltable.Insert_Head(str,vt[i],FOLLOW[i][l]);
}
}
if( FIRST[i][j] != '$')//'$'屬于FIRST(@),b屬于FOLLOW(A),把A->@加到M[A,b]中
lltable.Insert_Head(str,vt[i],FIRST[i][j]);
}
}
}
#endif?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -