一个人能建设一个公司网站吗,上海网站建设 报价,网站开发维护公司,wordpress接入外网域名任务描述
本关任务#xff1a;加深对语法分析器工作过程的理解#xff1b;加强对算符优先分析法实现语法分析程序的掌握#xff1b;能够采用一种编程语言实现简单的语法分析程序#xff1b;能够使用自己编写的分析程序对简单的程序段进行语法翻译。
相关知识
为了完成本…任务描述
本关任务加深对语法分析器工作过程的理解加强对算符优先分析法实现语法分析程序的掌握能够采用一种编程语言实现简单的语法分析程序能够使用自己编写的分析程序对简单的程序段进行语法翻译。
相关知识
为了完成本关任务你需要掌握用算符优先法编制语法分析程序。
自下而上的语法分析器
语法分析在编译中是一个重要的环节语法分析可以分为自上而下分析和自下而上分析两种方式。
自下而上分析法是一种“移进归约”法。这种方法的大意是用一个寄存符号的先进后出栈把输入符号一个一个地移进到栈里当栈顶形成某个产生式的一个候选式时即把栈顶的这一部分替换成归约为该产生式的左部符号。
对于自下而上的分析法边输入单词符号移进符号栈边归约。也就是在从左到右移进输入串的过程中一旦发现栈顶呈现可归约串就立即进行归约。
在该类方法中有以下的几个处理 移进指把输入串的一个符号移进栈。 归约指发现栈顶呈可归约串并用适当的相应符号去替换这个串这两个问题都还没有解决。 接受指宣布最终分析成功这个操作可看作是“归约”的一种特殊形式。 出错处理指发现栈顶的内容与输入串相悖分析工作无法正常进行此时需调用出错处理程序进行诊察和校正并对栈顶的内容和输入符号进行调整。
算符优先法
算符优先分析法(Operator Precedence Parse)是一种移动归约分析方法它是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。
算法优先关系构造的构造遵循以下的步骤
首先对于优先关系进行如下定义
a的优先级低于ba b 文法中有形如A→…aB…的产生式而Bb…或BCb…a的优先级等于ba b 文法中有形如A→…ab…或者A→…aBb…的产生式a的优先级高于ba b 文法中有形如A…Bb…的产生式,而B…a或B…aC算符的优先关系是有序的 如果a b不能推出b a 如果a b有可能b a 如果a b b c不一定a c 根据这个大小关系的定义我们知道为了确定两个终止符的优先关系我们需要知道它的在所有的产生式中和前后非终止符的关系那么我们做一个如步骤二的预处理。
定义并构造FIRSTVT和LASTVT两个集合
FIRSTVT(P){a∣P⇒a⋯或P⇒Qa⋯}
LASTVT(P){a∣P⇒⋯a0P⇒…aQ}
FIRSTVT(P)直接根据定义递归的构造即可:
若有产生式 P→a⋯ 或 p→Qa⋯则 a∈FIRSTVT(P)若有产式 P→Q⋯若 a∈FIRSTVT(Q)则 a∈FIRSTVT(P)
LASTVT(P)直接根据定义递归的构造即可
若有产生式 P→⋯ 或 p→⋯⋅a 则 a∈LASTVT(P)若有产式 P→⋯, 若 a∈LASTVT(Q) 则 a∈LASTVT(P)
利用FIRSTVT和LASTVT集合构造算法优先关系表: FOR 每个产生式 P-X1 X2 ……Xn DO FOR i:1 TO n-1 DO IF X[i]和X[i1]均为终结符THEN 置 X[i]X[i1] IF X[i]和X[i2]均为终结符,X[i1]为非终结符,i≤n-2, THEN 置 X[i]X[i2] IF X[i]为终结符, 但X[i1]为非终结符 THEN FOR FIRSTVT(X[i1])中的每个a DO 置 X[i]a IF Xi为非终结符, 但X i1 为终结符 THEN FOR LASTVT(X i )中的每个aDO 置 aX[i1]
实验步骤
对语法规则有明确的定义 该部分需要我们对输入文法进行构造然后定义出算符之间的优先级构造算符优先关系表表的构造过程如上。编写的分析程序能够对测试用例进行正确的语法分析 该部分需要我们对于输入的字符串进行逐一判断并给出相应的解析过程该过程是一个移进归约接受及出错处理的操作过程。对于遇到的语法错误能够做出简单的错误处理给出简单的错误提示保证顺利完成语法分析过程
编程要求
根据提示在右侧编辑器补充代码运行程序进行结果对比。
测试说明
平台会对你编写的代码进行测试.
#include iostream
#include fstream
#include sstream
#include vector
#include stack
#include iomanip
using namespace std;
string V[100][2]; //存储拆分后的文法
int vi 0; //存储拆分后有多少行
int t 0;
int s 0;
int l;
int r;
string FIRSTVT[20][2]; //存储firstvt集
string LASTVT[20][2]; //存储lastvt集
string str; //存储输入文法
string str_a #; // 下堆栈
string str_b; // 剩余输入串
string analysis_table[100][5]; // 文法分析过程
char table[100][100]; // 算符优先关系表
void init_string(string a) // 删除字符串的第一个元素
{for (int i 1; i a.length(); i){a[i - 1] a[i];}
}
bool is_CHAR(char c) // 判断是否为大写字母
{if (c A c Z){return true;}else{return false;}
}
bool is_in(int i, string x) // 判断从字符串x从最好一个开始算起连续的i个字符是否含有非大写字母
{bool flag false;for (int j 0; j i; j){if (!is_CHAR(x[x.length() - j - 1])){flag true;}}return flag;
}
void split(string a) // 拆分文法使其不含有
{for (int i 3; i a.length(); i){V[vi][0] a[0];while (a[i] ! | i a.length()){V[vi][1] a[i];i;}vi;}
}
void read_file(string file_path) //按行读取文件
{fstream f(file_path);vectorstring words;string line;while (getline(f, line)){words.push_back(line);}cout 输入文法: endl;for (int i 0; i words.size(); i){cout words[i] endl;split(words[i]);}
}
int find_index(char a) //寻找字符a在firstvt或者lastvt中的位置
{for (int i 0; i t; i){if (FIRSTVT[i][0][0] a){return i;}}return -1;
}
int find_table_index(char a) //寻找字符a在算符优先关系表中的位置
{for (int i 0; i s; i){if (table[i][0] a){return i;}}return -1;
}
void get_start() //获取非终结符
{for (int i 0; i vi; i){bool flag true;for (int j 0; j t; j){if (FIRSTVT[j][0] V[i][0]){flag false;}}if (flag){FIRSTVT[t][0] V[i][0];LASTVT[t][0] V[i][0];t;}}
}
/********Beign********/
/*构造firstvt,lastvt*/
void add_firstvt(string b, int a) //判断字符串b是否在序号为a的firstvt中没有则加入
{for (int s 0; s b.length(); s){bool flag true;char c b[s];if (c Z c A){continue;}for (int i 0; i FIRSTVT[a][1].length(); i){if (c FIRSTVT[a][1][i]){flag false;}}if (flag){FIRSTVT[a][1] c;}}
}
void add_firstvt(char c, int a) //判断字符c是否在序号为a的firstvt中没有则加入
{bool flag true;for (int i 0; i FIRSTVT[a][1].length(); i){if (c Z c A){continue;}if (c FIRSTVT[a][1][i]){flag false;}}if (flag){FIRSTVT[a][1] c;}}
void add_lastvt(string b, int a) //判断字符串b是否在序号为a的lastvt中没有则加入
{for (int s 0; s b.length(); s){bool flag true;char c b[s];if (c Z c A){continue;}for (int i 0; i LASTVT[a][1].length(); i){if (c LASTVT[a][1][i]){flag false;}}if (flag){LASTVT[a][1] c;}}
}
void add_lastvt(char c, int a) //判断字符串c是否在序号为a的lastvt中没有则加入
{bool flag true;for (int i 0; i LASTVT[a][1].length(); i){if (c Z c A){continue;}if (c LASTVT[a][1][i]){flag false;}}if (flag){LASTVT[a][1] c;}
}
string get_cur_firstvt(char c, int a) //获取当前字符的firstvt并放入序号为a的firstvt中
{string temp;for (int i 0; i vi; i){if (c V[i][0][0]){if (!(V[i][1][0] Z V[i][1][0] A)){add_firstvt(V[i][1][0], a);}else{if (c ! V[i][1][0]){temp get_cur_firstvt(V[i][1][0], find_index(V[i][1][0]));add_firstvt(temp, a);}if (V[i][1].length() 2){if (!(V[i][1][1] Z V[i][1][1] A)){add_firstvt(V[i][1][1], a);}}}}}return FIRSTVT[a][1];
}
string get_cur_lastvt(char c, int a) //获取当前字符的lastvt并放入序号为a的lastvt中
{string temp;for (int i 0; i vi; i){int s V[i][1].length();if (c V[i][0][0]){if (!(V[i][1][s - 1] Z V[i][1][s - 1] A)){add_lastvt(V[i][1][s - 1], a);}else{if (c ! V[i][1][s - 1]){temp get_cur_lastvt(V[i][1][s - 1], find_index(V[i][1][0]));add_lastvt(temp, a);}if (V[i][1].length() 2){if (!(V[i][1][s - 2] Z V[i][1][s - 2] A)){add_lastvt(V[i][1][s - 2], a);}}}}}return LASTVT[a][1];
}
/*********End*********/
void get_firstvt() //获取所有文法的firstvt
{for (int i 0; i t; i){get_cur_firstvt(FIRSTVT[i][0][0], i);}
}
void get_lastvt() //获取所有文法的lastvt
{for (int i 0; i t; i){get_cur_lastvt(LASTVT[i][0][0], i);}
}
void print_firstvt(string t, string a) //打印非终极符为t的firstvt
{cout FIRSTVT( t ) {;for (int i 0; i a.length(); i){if (i a.length() - 1){cout \ a[i] \;}else{cout \ a[i] \ , ;}}cout } endl;
}
void print_lastvt(string t, string a) //打印非终结符为t的lastvt
{cout LASTVT( t ) {;for (int i 0; i a.length(); i){if (i a.length() - 1){cout \ a[i] \;}else{cout \ a[i] \ , ;}}cout } endl;
}
/********Beign********/
/*构造算符优先表*/void init_table() //初始化算符优先关系表
{table[0][0] \\;for (int i 0; i vi; i){for (int j 0; j V[i][1].length(); j){bool flag true;for (int k 0; k s 1; k){if (table[k 1][0] V[i][1][j] || (V[i][1][j] Z V[i][1][j] A)){flag false;}}if (flag){table[s 1][0] V[i][1][j];table[0][s 1] V[i][1][j];s;}}}for (int l 1; l s 1; l){for (int i 1; i s 1; i){table[l][i] ;}}
}void get_table() //生成算符优先关系表
{for (int i 0; i vi; i){for (int j 0; j V[i][1].length(); j){//abif (!(V[i][1][j] Z V[i][1][j] A) !(V[i][1][j 1] Z V[i][1][j 1] A) j 1 V[i][1].length()){table[find_table_index(V[i][1][j])][find_table_index(V[i][1][j 1])] ;}//aQbif ((!(V[i][1][j] Z V[i][1][j] A)) (V[i][1][j 1] Z V[i][1][j 1] A) (!(V[i][1][j 2] Z V[i][1][j 2] A)) j 2 V[i][1].length()){table[find_table_index(V[i][1][j])][find_table_index(V[i][1][j 2])] ;}//aQif ((!(V[i][1][j] Z V[i][1][j] A)) (V[i][1][j 1] Z V[i][1][j 1] A) j 1 V[i][1].length()){for (int k 0; k FIRSTVT[find_index(V[i][1][j 1])][1].length(); k){table[find_table_index(V[i][1][j])][find_table_index(FIRSTVT[find_index(V[i][1][j 1])][1][k])] ;}}//Qaif ((V[i][1][j] Z V[i][1][j] A) !(V[i][1][j 1] Z V[i][1][j 1] A) j 1 V[i][1].length()){for (int k 0; k LASTVT[find_index(V[i][1][j])][1].length(); k){table[find_table_index(LASTVT[find_index(V[i][1][j])][1][k])][find_table_index(V[i][1][j 1])] ;}}}}
}
/*********End*********/
void print_table() //打印算符优先关系表
{for (int i 0; i s 1; i){for (int j 0; j s 1; j){cout table[i][j] ;}cout endl;}
}
char get_relationship(char a, char b) //获取终结符ab的优先关系
{return table[find_table_index(a)][find_table_index(b)];
}
bool is_reduce() //判断是否可以规约
{for (int i 0; i vi; i){int count 0;int f str_a.length() - 1;for (int j V[i][1].length() - 1; j 0 f 0; j--, f--){if (is_in(V[i][1].length(), str_a)){if (is_CHAR(str_a[f]) is_CHAR(V[i][1][j])){count;}else if (str_a[f] V[i][1][j]){count;}}else{continue;}}if (count V[i][1].length()){r i;return true;}}return false;
}
void analyze_input_string() // 生成算符优先文法的分析过程
{analysis_table[0][0] 步骤;analysis_table[0][1] 下堆栈;analysis_table[0][2] 优先关系;analysis_table[0][3] 剩余输入串;analysis_table[0][4] 移进或规约;str_b str;char relationship;l 1;int x;stringstream ss;while (true){ss l;int index str_a.length() - 1;analysis_table[l][0] ss.str();analysis_table[l][3] str_b;analysis_table[l][1] str_a;ss.clear();ss.str();if (is_CHAR(str_a[index])){for (int i str_a.length() - 1; i 0; i--){if (!is_CHAR(str_a[i])){index i;break;}}}relationship get_relationship(str_a[index], str_b[0]);analysis_table[l][2] relationship;if (relationship ){if (str_a[index] # str_b[0] #){analysis_table[l][4] 完成;break;}else{analysis_table[l][4] 移进;str_a str_b[0];analysis_table[l 1][1] str_a;init_string(str_b);}}else if (relationship ){analysis_table[l][4] 移进;str_a str_b[0];analysis_table[l 1][1] str_a;init_string(str_b);}else if (relationship ){if (is_reduce()){analysis_table[l][4] 规约;str_a[str_a.length() - V[r][1].length()] V[r][0][0];str_a.erase(str_a.length() - V[r][1].length() 1, V[r][1].length() - 1);}else{cout 输入串非法 endl;exit(-1);}}l;}
}
void print_analyze_process() //打印算符优先文法的分析过程
{cout 算符优先分析过程 endl;cout setw(12) analysis_table[0][0] setw(16) analysis_table[0][1] setw(16) analysis_table[0][2] setw(24) analysis_table[0][3] setw(20) analysis_table[0][4] endl;for (int i 1; i l; i){cout.width(10);cout analysis_table[i][0];cout.width(12);cout analysis_table[i][1];cout.width(10);cout analysis_table[i][2];cout.width(20);cout analysis_table[i][3];cout analysis_table[i][4];cout endl;}
}
int main(int argv, char *arg[])
{cout.setf(std::ios::left);read_file(/data/workspace/myshixun/in.txt);cout 拆分后文法: endl;for (int i 0; i vi; i){cout V[i][0] - V[i][1] endl;}cout 非终结符: endl;get_start();for (int j 0; j t; j){cout FIRSTVT[j][0] endl;}cout FIRSTVT: endl;get_firstvt();for (int k 0; k t; k){print_firstvt(FIRSTVT[k][0], FIRSTVT[k][1]);}cout LASTVT: endl;get_lastvt();for (int k 0; k t; k){print_lastvt(LASTVT[k][0], LASTVT[k][1]);}cout 算符优先关系表 endl;init_table();get_table();print_table();cout 请输入文法并以#结束: endl;cin str;analyze_input_string();print_analyze_process();return 0;
}
