实验一：FOLLOW集

2024-01-30 09:44
文章标签 实验 follow

本文主要是介绍实验一：FOLLOW集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

核心操作

//FOLLOW集
//#表示结束标志
set<char> Follow[255];

1.follow 函数
*初始化: 首先将文法的开始符号的 FOLLOW 集合中加入特殊结束符号#。
*迭代更新: 函数使用一个while 循环来反复更新 FOLLOW 集合，直到没有新的元素被添加到任何 FOLLOW 集合中
*处理每个产生式:
*遍历每个非终结符的产生式，对于产生式中的每个符号，特别是非终结符，需要更新其 FOLLOW 集合。
*如果产生式中的某个非终结符后面紧跟着终结符，则将该终结符加入非终结符的 FOLLOW 集合。
*如果非终结符后面是另一个非终结符，则将后者的 FIRST 集合（除去空串）加入前者的 FOLLOW 集合。
*如果非终结符后面的符号串的 FIRST 集合包含空串，或者该非终结符是产生式的最后一个符号，则将产生式左侧非终结符的 FOLLOW 集合加入该非终结符的 FOLLOW 集合。
*更新检查: 检查在每次迭代后 FOLLOW 集合的大小是否发生变化，以决定是否继续迭代。
2.输出 FOLLOW 集合: print_follow 函数用于打印每个非终结符的 FOLLOW 集合。

具体实现

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
using namespace std;//G文法结构体
struct G {int Vt_number;int Vn_number;int P_number;set<char> Vt;set<char> Vn;char S;vector<string> P[255];
}G_instance;//打印文法
void printG() {cout << "Vt is:";for (auto i = G_instance.Vt.begin(); i != G_instance.Vt.end(); i++) {cout << *i << " ";}cout << endl;cout << "Vn is:";for (auto i = G_instance.Vn.begin(); i != G_instance.Vn.end(); i++) {cout << *i << " ";}cout << endl;for (auto i = G_instance.Vn.begin(); i != G_instance.Vn.end(); i++) {if (!G_instance.P[*i].empty()) {for (auto p = G_instance.P[*i].begin(); p != G_instance.P[*i].end(); p++) {cout << *i << "->" << *p << endl;}}}
}//FIRST集
set<char> First[255];set<char> first_string_set;
void first_string(string str) {first_string_set.clear();for (int i = 0; i < str.length(); i++) {set<char> temp_first_sub_string;set_union(temp_first_sub_string.begin(), temp_first_sub_string.end(), First[str[i]].begin(), First[str[i]].end(), inserter(temp_first_sub_string, temp_first_sub_string.begin()));if (First[str[i]].find('$') != First[str[i]].end() && i != str.length() - 1) {temp_first_sub_string.erase('$');set_union(temp_first_sub_string.begin(), temp_first_sub_string.end(), first_string_set.begin(), first_string_set.end(), inserter(first_string_set, first_string_set.end()));}else {set_union(temp_first_sub_string.begin(), temp_first_sub_string.end(), first_string_set.begin(), first_string_set.end(), inserter(first_string_set, first_string_set.end()));break;}}
}void check() {for (auto vn = G_instance.Vn.begin(); vn != G_instance.Vn.end(); vn++) {if (!G_instance.P[*vn].empty()) {for (auto p = G_instance.P[*vn].begin(); p != G_instance.P[*vn].end(); p++) {first_string(*p);set_union(first_string_set.begin(), first_string_set.end(), First[*vn].begin(), First[*vn].end(), inserter(First[*vn], First[*vn].begin()));}}}
}void first() {//flag为1表示first集有更新//      0表示first集无更新int flag = 1;while (flag == 1) {flag = 0;for (auto i = G_instance.Vn.begin(); i != G_instance.Vn.end(); i++) {//遍历非终结符号*i的产生式//*p为当前的产生式int len = First[*i].size();if (!G_instance.P[*i].empty()) {for (auto p = G_instance.P[*i].begin(); p != G_instance.P[*i].end(); p++) {//首字符为终结符号if (G_instance.Vt.find((*p)[0]) != G_instance.Vt.end()) {First[*i].insert((*p)[0]);}else {//首字符为非终结符号for (int index = 0; index < (*p).length(); index++) {//temp为FIRST(Y_k)set<char> temp;set_union(temp.begin(), temp.end(), First[(*p)[index]].begin(), First[(*p)[index]].end(), inserter(temp, temp.begin()));if (temp.find('$') != temp.end() && index != (*p).length() - 1) {temp.erase('$');set_union(First[*i].begin(), First[*i].end(), temp.begin(), temp.end(), inserter(First[*i], First[*i].end()));}else {set_union(First[*i].begin(), First[*i].end(), temp.begin(), temp.end(), inserter(First[*i], First[*i].end()));break;}}}}}int new_len = First[*i].size();if (new_len > len) {flag = 1;}}}//终结符号的first集for (auto i = G_instance.Vt.begin(); i != G_instance.Vt.end(); i++) {First[*i].insert(*i);}check();
}//打印first集
void print_first() {for (auto i = G_instance.Vn.begin(); i != G_instance.Vn.end(); i++) {cout << "first(" << *i << "):";for (auto item = First[*i].begin(); item != First[*i].end(); item++) {cout << *item << " ";}cout << endl;}
}//FOLLOW集
//#表示结束标志
set<char> Follow[255];
void follow() {Follow[G_instance.S].insert('#');//flag为1表示FOLLOW集有更新//		0			 无更新int flag = 1;while (flag == 1) {flag = 0;for (auto i = G_instance.Vn.begin(); i != G_instance.Vn.end(); i++) {//遍历非终结符号*iif (!G_instance.P[*i].empty()) {for (auto p = G_instance.P[*i].begin(); p != G_instance.P[*i].end(); p++) {//*p为当前非终结符号*i->产生式*pfor (int j = 0; j < (*p).length(); j++) {char temp_vn = (*p)[j];int len = Follow[temp_vn].size();if (G_instance.Vn.find(temp_vn) != G_instance.Vn.end()) {//当前字符为产生式中最后一个字符if (j == (*p).length() - 1) {set_union(Follow[temp_vn].begin(), Follow[temp_vn].end(), Follow[*i].begin(), Follow[*i].end(), inserter(Follow[temp_vn], Follow[temp_vn].end()));}else {string temp_string = (*p).substr(j + 1, (*p).length() - j - 1);//后继first集中包含空first_string(temp_string);if (first_string_set.find('$') != first_string_set.end()) {first_string_set.erase('$');set_union(first_string_set.begin(), first_string_set.end(), Follow[temp_vn].begin(), Follow[temp_vn].end(), inserter(Follow[temp_vn], Follow[temp_vn].end()));set_union(Follow[temp_vn].begin(), Follow[temp_vn].end(), Follow[*i].begin(), Follow[*i].end(), inserter(Follow[temp_vn], Follow[temp_vn].end()));}else {//后继first集不含空set_union(first_string_set.begin(), first_string_set.end(), Follow[temp_vn].begin(), Follow[temp_vn].end(), inserter(Follow[temp_vn], Follow[temp_vn].end()));}}}if (len < Follow[temp_vn].size()) {flag = 1;}}}}}}
}void print_follow() {for (auto i = G_instance.Vn.begin(); i != G_instance.Vn.end(); i++) {cout << "follow(" << *i << "):";for (auto item = Follow[*i].begin(); item != Follow[*i].end(); item++) {cout << *item << " ";}cout << endl;}
}//SELECT集
string M[255][255];
void select() {//初始化Mfor (int i = 0; i < 255; i++) {for (int j = 0; j < 255; j++) {M[i][j] = "";}}for (auto i = G_instance.Vn.begin(); i != G_instance.Vn.end(); i++) {//遍历非终结符号*iif (!G_instance.P[*i].empty()) {for (auto p = G_instance.P[*i].begin(); p != G_instance.P[*i].end(); p++) {//*p为当前非终结符号*i->产生式*pset<char> select;first_string(*p);if (first_string_set.find('$') != first_string_set.end()) {set_union(Follow[*i].begin(), Follow[*i].end(), select.begin(), select.end(), inserter(select, select.end()));}first_string_set.erase('$');set_union(first_string_set.begin(), first_string_set.end(), select.begin(), select.end(), inserter(select, select.end()));for (auto select_ = select.begin(); select_ != select.end(); select_++) {M[*i][*select_] = *p;}cout << "SELECT(" << *i << "->" << *p << "):";for (auto p_s = select.begin(); p_s != select.end(); p_s++) {cout << *p_s << " ";}cout << endl;}}}
}void print_select(int sum) {ofstream p;string file_path = "output" + to_string(sum) + ".csv";p.open(file_path, ios::out | ios::trunc);p << "Vn" << ",";set<char> input_set;set_union(input_set.begin(), input_set.end(), G_instance.Vt.begin(), G_instance.Vt.end(), inserter(input_set, input_set.begin()));input_set.erase('$');input_set.insert('#');for (auto vt = input_set.begin(); vt != input_set.end(); vt++) {p << *vt << ",";}p << endl;for (auto vn = G_instance.Vn.begin(); vn != G_instance.Vn.end(); vn++) {p << *vn;for (auto vt = input_set.begin(); vt != input_set.end(); vt++) {if (M[*vn][*vt] != "") {p << "," << *vn << "->" << M[*vn][*vt];}else {p << "," << " ";}}p << endl;}p.close();
}void clear() {G_instance.P_number = 0;G_instance.Vn_number = 0;G_instance.Vt_number = 0;G_instance.S = ' ';for (int i = 0; i < 255; i++) {G_instance.P[i].clear();Follow[i].clear();First[i].clear();}G_instance.Vn.clear();G_instance.Vt.clear();first_string_set.clear();for (int i = 0; i < 255; i++) {for (int j = 0; j < 255; j++) {M[i][j] = "";}}
}int main() {string file_path = "./FIRST-FOLLOW.txt";ifstream file(file_path);string arr[100];int count = 0;int sum = 0;while (getline(file, arr[count]) && count < 100) {if (arr[count].empty()) {clear();G_instance.P_number = count;G_instance.S = arr[0][0];for (int i = 0; i < count; i++) {int len = arr[i].length();string str = arr[i];G_instance.Vn.insert(str[0]);G_instance.P[str[0]].push_back(str.substr(2, len - 2));for (int index = 0; index < len; index++) {if ((str[index] >= 'a' && str[index] <= 'z') || str[index] == '$') {G_instance.Vt.insert(str[index]);}}}G_instance.Vt_number = G_instance.Vt.size();G_instance.Vn_number = G_instance.Vn.size();printG();cout << endl;count = 0;first();print_first();follow();print_follow();select();sum++;print_select(sum);cout << endl;}else {count++;}}file.close();return 0;
}

这篇关于实验一：FOLLOW集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/659837。

相关文章

STM32(十一)：ADC数模转换器实验

STM32(十一)：ADC数模转换器实验

AD单通道： 1.RCC开启GPIO和ADC时钟。配置ADCCLK分频器。 2.配置GPIO，把GPIO配置成模拟输入的模式。 3.配置多路开关，把左面通道接入到右面规则组列表里。 4.配置ADC转换器， 包括AD转换器和AD数据寄存器。单次转换，连续转换；扫描、非扫描；有几个通道，触发源是什么，数据对齐是左对齐还是右对齐。 5.ADC_CMD 开启ADC。 void RCC_AD
阅读更多...
HNU-2023电路与电子学-实验3

HNU-2023电路与电子学-实验3

写在前面： 一、实验目的 1.了解简易模型机的内部结构和工作原理。 2.分析模型机的功能，设计 8 重 3-1 多路复用器。 3.分析模型机的功能，设计 8 重 2-1 多路复用器。 4.分析模型机的工作原理，设计模型机控制信号产生逻辑。 二、实验内容 1.用 VERILOG 语言设计模型机的 8 重 3-1 多路复用器； 2.用 VERILOG 语言设计模型机的 8 重 2-1 多
阅读更多...
61.以太网数据回环实验（4）以太网数据收发器发送模块

61.以太网数据回环实验（4）以太网数据收发器发送模块

（1）状态转移图： （2）IP数据包格式： （3）UDP数据包格式： （4）以太网发送模块代码： module udp_tx(input wire gmii_txc ,input wire reset_n ,input wire tx_start_en , //以太网开始发送信
阅读更多...
LTspice模拟CCM和DCM模式的BUCK电路实验及参数计算

LTspice模拟CCM和DCM模式的BUCK电路实验及参数计算

关于BUCK电路的原理可以参考硬件工程师炼成之路写的《 手撕Buck！Buck公式推导过程》.实验内容是将12V~5V的Buck电路仿真,要求纹波电压小于15mv. CCM和DCM的区别: CCM:在一个开关周期内，电感电流从不会到0. DCM:在开关周期内，电感电流总会到0. CCM模式Buck电路仿真: 在用LTspice模拟CCM电路时,MOS管驱动信号频率为100Khz,负载为10R（可自
阅读更多...
HCIA--实验十：路由的递归特性

HCIA--实验十：路由的递归特性

递归路由的理解 一、实验内容 1.需求/要求： 使用4台路由器，在AR1和AR4上分别配置一个LOOPBACK接口，根据路由的递归特性，写一系列的静态路由实现让1.1.1.1和4.4.4.4的双向通信。 二、实验过程 1.拓扑图： 2.步骤： （下列命令行可以直接复制在ensp） 1.如拓扑图所示，配置各路由器的基本信息： 各接口的ip地址及子网掩码，给AR1和AR4分别配置
阅读更多...
OpenGL/GLUT实践：流体模拟——数值解法求解Navier-Stokes方程模拟二维流体（电子科技大学信软图形与动画Ⅱ实验）

OpenGL/GLUT实践：流体模拟——数值解法求解Navier-Stokes方程模拟二维流体（电子科技大学信软图形与动画Ⅱ实验）

源码见GitHub：A-UESTCer-s-Code 文章目录 1 实现效果2 实现过程2.1 流体模拟实现2.1.1 网格结构2.1.2 数据结构2.1.3 程序结构1) 更新速度场2) 更新密度值 2.1.4 实现效果 2.2 颜色设置2.2.1 颜色绘制2.2.2 颜色交互2.2.3 实现效果 2.3 障碍设置2.3.1 障碍定义2.3.2 障碍边界条件判定2.3.3 障碍实现2.3.
阅读更多...
pta-2024年秋面向对象程序设计实验一-java

pta-2024年秋面向对象程序设计实验一-java

文章申明:作者也为初学者,解答仅供参考,不一定是最优解; 一:7-1 sdut-sel-2 汽车超速罚款（选择结构） 答案: import java.util.Scanner;         public class Main { public static void main(String[] arg){         Scanner sc=new Scanner(System
阅读更多...
如何校准实验中振镜频率的漂移

如何校准实验中振镜频率的漂移

在实验过程中，使用共振扫描振镜（如Cambridge Technology的8kHz振镜）时，频率漂移是一个常见问题，尤其是在温度变化或长期运行的情况下。为了确保实验的准确性和稳定性，我们需要采取有效的校准措施。本文将介绍如何监测、调节和校准振镜频率，以减少漂移对实验结果的影响。 1. 温度管理和稳定性控制 振镜的频率变化与温度密切相关，温度的升高会导致机械结构的变化，进而影响振镜的共
阅读更多...
实验C语言“union”的最基础语法

实验C语言“union”的最基础语法

目标 最近在看Rust的“菜鸟教程”，看到 Rust 枚举类 时我发现它所定义的“枚举类”虽然也能像C语言枚举类那样使用，但是多了些功能：对于某个枚举的成员，还可以附带独特的数据，这让我想起了C语言中的union。 而我事实上对union没有使用经验，我自己写程序的时候不用它，看其他的项目的程序时印象里也没见过它。所以我对union的设计意图理解不深（可能只是为了节省内存？）。本篇的目标是对其
阅读更多...
Oracle高级压缩和透明数据加密组合实验

Oracle高级压缩和透明数据加密组合实验

本文参考了实验DB Security - Advanced Compression with Transparent Data Encryption(TDE)，其申请地址在这里。 本文只使用了实验中关于高级压缩和在线重定义的部分。并对要点进行说明及对实验进行了简化。 准备：环境设置 原文中的实验环境实际上是改自Oracle示例Sample Schema，其实唯一的改动就是去掉了SALES表中
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2