编译原理头歌实验:实验4《算符优先分析法设计与实现》(C语言版)

本文主要是介绍编译原理头歌实验:实验4《算符优先分析法设计与实现》(C语言版),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

任务描述

本关任务:加深对语法分析器工作过程的理解;加强对算符优先分析法实现语法分析程序的掌握;能够采用一种编程语言实现简单的语法分析程序;能够使用自己编写的分析程序对简单的程序段进行语法翻译。

相关知识

为了完成本关任务,你需要掌握:用算符优先法编制语法分析程序。

自下而上的语法分析器

语法分析在编译中是一个重要的环节,语法分析可以分为自上而下分析和自下而上分析两种方式。

自下而上分析法是一种“移进-归约”法。这种方法的大意是,用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的一个候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

对于自下而上的分析法,边输入单词符号(移进符号栈),边归约。也就是在从左到右移进输入串的过程中,一旦发现栈顶呈现可归约串就立即进行归约。

在该类方法中有以下的几个处理:

  • 移进:指把输入串的一个符号移进栈。

  • 归约:指发现栈顶呈可归约串,并用适当的相应符号去替换这个串(这两个问题都还没有解决)。

  • 接受:指宣布最终分析成功,这个操作可看作是“归约”的一种特殊形式。

  • 出错处理:指发现栈顶的内容与输入串相悖,分析工作无法正常进行,此时需调用出错处理程序进行诊察和校正,并对栈顶的内容和输入符号进行调整。

算符优先法

算符优先分析法(Operator Precedence Parse)是一种移动归约分析方法,它是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。

算法优先关系构造的构造遵循以下的步骤:

首先对于优先关系进行如下定义:

  • a的优先级低于b
    a < b: 文法中有形如A→…aB…的产生式而B+b…或B+Cb…
  • a的优先级等于b
    a = b: 文法中有形如A→…ab…或者A→…aBb…的产生式
  • a的优先级高于b
    a > 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⇒+⋯a0​P⇒+…aQ}

  1. FIRSTVT(P)直接根据定义递归的构造即可:
  • 若有产生式 P→a⋯ 或 p→Qa⋯,则 a∈FIRSTVT(P)
  • 若有产式 P→Q⋯,若 a∈FIRSTVT(Q),则 a∈FIRSTVT(P)
  1. LASTVT(P)直接根据定义递归的构造即可:
  • 若有产生式 P→⋯ 或 p→⋯⋅a 则 a∈LASTVT(P)
  • 若有产式 P→⋯, 若 a∈LASTVT(Q) 则 a∈LASTVT(P)

利用FIRSTVT和LASTVT集合构造算法优先关系表:

 
  1. FOR 每个产生式 P->X1 X2 ……Xn
  2. DO FOR i:=1 TO n-1 DO
  3. IF X[i]和X[i+1]均为终结符
  4. THEN 置 X[i]=X[i+1]
  5. IF X[i]和X[i+2]均为终结符,X[i+1]为非终结符,i≤n-2,
  6. THEN 置 X[i]=X[i+2]
  7. IF X[i]为终结符, 但X[i+1]为非终结符
  8. THEN FOR FIRSTVT(X[i+1])中的每个a
  9. DO 置 X[i]<a
  10. IF Xi为非终结符, 但X i+1 为终结符
  11. THEN FOR LASTVT(X i )中的每个a
  12. DO 置 a>X[i+1]
实验步骤
  1. 对语法规则有明确的定义;
    该部分需要我们对输入文法进行构造,然后定义出算符之间的优先级,构造算符优先关系表,表的构造过程如上。
  2. 编写的分析程序能够对测试用例进行正确的语法分析;
    该部分需要我们对于输入的字符串进行逐一判断,并给出相应的解析过程,该过程是一个移进,归约,接受及出错处理的操作过程。
  3. 对于遇到的语法错误,能够做出简单的错误处理,给出简单的错误提示,保证顺利完成语法分析过程;

编程要求

根据提示,在右侧编辑器补充代码,运行程序,进行结果对比。

测试说明

平台会对你编写的代码进行测试.

#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);vector<string> 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) //获取终结符a,b的优先关系
{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;
}

这篇关于编译原理头歌实验:实验4《算符优先分析法设计与实现》(C语言版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/446992

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount