程序员经验分享-hwhale

（编译原理）正规文法转正规式（原代码）

2023-05-16

（编译原理）正规文法转正规式

一、实验要求

  • 输入：正规文法
  • 输出：正规式
    例：
    输入：S->aB B->b 输出：ab
    输入：S->aS S->b 输出：a*b
    输入：S->a S->b 输出：S->a|b

二、实验原理

1、正规文法

在编译原理当中，正规文法指的是3型文法，她所满足的条件为：文法左部只有一个非终结符，右部要么一个单终结符，要么一个终结符配一个非终结符（统一非终结符的位置，都在终结符左部或右部），但右部字符数不超过两个。
如：S->a S->aA A->b 满足3型文法条件
而S->a S->aA A->b S->Sd 不满足，须将S->Sd改为S->dS或S->aA改为S->Aa才满足要求

具体文法分类请看小编另一篇博客https://blog.csdn.net/ScottWei_007/article/details/88768019

2、正规式

正规式是用来描述语言单词的表达式。一般来说，正规式由操作符和字母组成，操作符包括： （ ） （） （）、 ∗ * ∗、 ∣ | ∣和 ⋅ · ⋅组成，字母是则是终结符的小写字母构成。
操作符的优先级由高到低为：（）、 ∗ * ∗ 、 ⋅ · ⋅、 ∣ | ∣

a ⋅ b a·b a⋅b
a ∗ b a*b a∗b
a b ab ab

有限次的上述三种操作的表达式即为正规式。

三、算法设计

注：小编采用的是右递归推导，即右部非终结符在终结符右侧

  1. 对所有正规文法进行如下操作：
  • 合并所有左部非终结符相同，右部只有一个终结符的正规文法(S->a S->b合并为S->a|b)
  • 合并所有左部非终结符相同，右部终结符相同且和左部非终结符相同的正规文法(S->aS S->bS 合并为S->aS|bS)
  • 合并所有左部非终结符相同，右部终结符相同但和左部非终结符不相同的正规文法(S->aB S->bB合并为S->aB|bB )
  • 进行文法整理（S->aB|bB S->aS|bS 整理为S->(a|b)B S->(a|b)S）
  1. 对右部只有一个终结符的正规文法L，遍历文法，若找到右部非终结符和左部非终结符不相等，且右部非终极符和L左部非终结符相同，则进行合并。（A->b S->aA 合并为S->ab）
  2. 对右部只有一个终结符的正规文法L，遍历文法，若找到右部非终结符和左部非终结符相等，且右部非终极符和L左部非终结符相同，则进行合并。（S->b S->aS 合并为S->a*b）
  3. 若所有文法右边都不含非终结符，进行合并输出，否则转至步骤1。

四、实验过程

1、定义

构建结构体进行存储字符串，定义全局变量和函数的调用

//定义全局变量 
struct Rule{
	char str[10];//存储正规文法 
	char right[100];//存储正规文法右边 
	char left;//存储正规文法左边 
}r[10];

int n;//全局变量，表示输入的正规文法行数 
//函数调用 
void Init();
//Max1~Max4为正规文法到正规式的转换函数 
void Mix1();
void Mix2();
void Mix3();
void Mix4();
void Mix();

2、初始化

输入字符串，获取字符串左右两部分内容便于操作

//初始化，输入正规文法 
void Init(){
	cout<<"输入正规文法："<<endl;
	int i,j=0; 
    for(i=0;;i++){//输入正规文法，'#'停止 
    	cin>>r[i].str;
    	if(r[i].str[j]=='#')
    	break;
	}
	n=i;
	for(i=0;i<n;i++){//记录每行的文法的左部和右部 
		int k=0;
		for(j=3;j<strlen(r[i].str);j++)
		r[i].right[k++]=r[i].str[j];
		r[i].left=r[i].str[0];
	}
	cout<<"输出正规式:"<<endl;
}

3、转换

void mix1()进行算法设计步骤1的前三步操作
void mix2()进行算法设计步骤1的第四步操作
void mix3()进行算法设计步骤2的第操作
void mix4()进行算法设计步骤3的操作
void mix()进行算法设计步骤4的操作
代码段太长，请看源代码内容

4、主函数

进行函数调用并执行转换，输出最终结果。

//主函数 
int main(){
	Init();//初始化 
	Mix1();//进行转换	
}

五、源代码和实验截图

代码已经过编译运行，可直接使用。

#include<iostream>
#include<iomanip>
#include<string.h>
using namespace std;

//定义全局变量 
struct Rule{
	char str[10];//存储正规文法 
	char right[100];//存储正规文法右边 
	char left;//存储正规文法左边 
}r[10];

int n;//全局变量，表示输入的正规文法行数 
//函数调用 
void Init();
//Max1~Max4为正规文法到正规式的转换函数 
void Mix1();
void Mix2();
void Mix3();
void Mix4();
void Mix();

//初始化，输入正规文法 
void Init(){
	cout<<"输入正规文法："<<endl;
	int i,j=0; 
    for(i=0;;i++){//输入正规文法，'#'停止 
    	cin>>r[i].str;
    	if(r[i].str[j]=='#')
    	break;
	}
	n=i;
	for(i=0;i<n;i++){//记录每行的文法的左部和右部 
		int k=0;
		for(j=3;j<strlen(r[i].str);j++)
		r[i].right[k++]=r[i].str[j];
		r[i].left=r[i].str[0];
	}
	cout<<"输出正规式:"<<endl;
}

//正规文法到正规式的转换1 
void Mix1(){//合并文法中形如S->aS S->bS为S->aS|bS;S->aB S->bB为S->aB|bB;S->a S->b为S->a|b ;即合并左部相同、右部相同的部分，以及右部单个字符 
	int i,j;
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(r[i].left==r[j].left&&r[i].right[1]==r[j].right[1]&&r[i].left!='\0'){//并左部相同、右部相同的部分
				strcat(r[i].right,"|");
				strcat(r[i].right,r[j].right);
				r[j].left='\0';
				memset(r[j].right,0,sizeof(r[i].right));
			}
			if(r[i].left==r[j].left&&strlen(r[i].right)==1&&strlen(r[j].right)==1&&r[i].left!='\0'){//合并右部单个字符  
				strcat(r[i].right,"|");
				strcat(r[i].right,r[j].right);
				r[j].left='\0';	
				memset(r[j].right,0,sizeof(r[i].right));		
			}
		}
	}
	Mix2();	
}

//正规文法到正规式的转换2 
void Mix2()//合并Mix1中S->aS|bS为S->(a|b)S ;S->aB|bB为S->(a|b)B 
{
	int i,j,k;
	for(i=0;i<n;i++){
		if(strlen(r[i].right)>2&&r[i].right[1]>='A'&&r[i].right[1]<='Z'){
			k=0;
			char a[100]={};//使用中间数组，将需保留内容存入其中，最后再存入结构体中 
			a[k++]='(';
			for(j=0;j<strlen(r[i].right);j=j+3){//存储需保留的值 
     			a[k]=r[i].right[j];
     			a[k+1]='|';
     			k=k+2;
     		}
     		a[k-1]=')';
     		a[k++]=r[i].right[1];
     		memset(r[i].right,0,sizeof(r[i].right));
     		strcpy(r[i].right,a);//存入结构体 
		}
	}
	Mix3();
}

//正规文法到正规式的转换3 
void Mix3(){//合并类似S->a|b S->(a|b)S 为S->(a|b)*(a|b) ,采用右递归 
	int i,j,temp;
	for(i=0;i<n;i++){
		temp=0;
		for(j=0;j<strlen(r[i].right);j++){//先寻找S->a|b,即右边无非终结符 
			if(r[i].right[j]>='A'&&r[i].right[j]<='Z')
			temp=1;
		}
		if(temp==0){//然后在寻找与其左部有相同非终结符且右部也相同非终结符的文法 
			for(j=0;j<n;j++){
				int length=strlen(r[j].right);
				if(r[j].right[length-1]==r[j].left&&r[j].right[length-1]==r[i].left&&r[j].left!='\0'){//将两个文法进行合并 
					r[j].right[length-1]='\0';
					if(strlen(r[i].right)==1|strlen(r[i].right)==2){
	    				strcat(r[j].right,"*");
						strcat(r[j].right,r[i].right);
	    			}
	    			if(strlen(r[i].right)>2){
	    				strcat(r[j].right,"*(");
	    				strcat(r[j].right,r[i].right);
	    				strcat(r[j].right,")");
					}
					r[i].left='\0';
					memset(r[i].right,0,sizeof(r[i].right));
				}
			}
		}
	}
	Mix4();
}

//正规文法到正规式的转换4 
void Mix4(){//合并类型S->aA A->(b|a) 为S->a(b|a) 
	int i,j,temp,k;
	for(i=0;i<n;i++){
		temp=0;
		for(j=0;j<strlen(r[i].right);j++){//先寻找S->a|b,即右边无非终结符 
			if(r[i].right[j]>='A'&&r[i].right[j]<='Z')
			temp=1;
		}
		if(temp==0){//然后在寻找右部与其左部有相同非终结符但左部不相同非终结符的文法 
			for(j=0;j<n;j++){
				int length=strlen(r[j].right);
				if(r[j].right[length-1]==r[i].left&&r[j].left!='\0'){//进行合并 
					r[j].right[length-1]='\0';
					k=0;
					for(int m=0;m<strlen(r[i].right);m++)//判断操作符是否都为乘法 
					if(r[i].right[m]=='*'|r[i].right[m]=='|')
					k=1;
	    			if(strlen(r[i].right)>2&&k==1){//若都为乘法，则在合并时可以不用加括号 
	    				strcat(r[j].right,"(");
	    				strcat(r[j].right,r[i].right);
	    				strcat(r[j].right,")");
					}
					else
					strcat(r[j].right,r[i].right);
					r[i].left='\0';
					memset(r[i].right,0,sizeof(r[i].right));
				}
			}
		}
	}
	Mix();	
} 

//正规文法到正规式的转换5 
void Mix(){//进行最后的判断和循环 
	int i,j,temp=0;
	for(i=0;i<n;i++){//判断是否所有文法右边均不含非终结符 
		for(j=0;j<n;j++){
			if(r[i].right[j]>='A'&&r[i].right[j]<='Z')
			temp=1;
		}
	}
	if(!temp){//若都不含非终结符，进行合并输出 
		for(i=0;i<n-1;i++){
			for(j=i+1;j<n;j++){
				if(r[i].left==r[j].left&&r[i].left!='\0'){
					strcat(r[i].right,"|");
					strcat(r[i].right,r[j].right);
					r[j].left='\0';
					memset(r[j].right,0,sizeof(r[j].right));
				}
			}
		}
	}
	if(temp)//若含非终结符，调至Min1循环执行 
	Mix1(); 
	else{
	for(i=0;i<n;i++)//输出正规式 
	cout<<r[i].right<<endl;
    }
}

int main(){
	Init();//初始化 
	Mix1();//进行转换	
}

结果展示：
输入：S->a S->b
输出：S->a|b
在这里插入图片描述
输入：S->aA A->b
输出：S->ab
在这里插入图片描述
输入：S->aS S->b
输出：S->a*b
在这里插入图片描述
输入：S->aA A->bB B->dD D->e
输出：abde
在这里插入图片描述

输入：S->a S->aA A->a A->d A->aA A->dD
输出：a|a((a|d)*(a|d))
在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

（编译原理）正规文法转正规式（原代码） 的相关文章

随机推荐

  • 转化Foggy_Cityscapes数据集为voc和yolo格式用作目标检测

    目录 一 数据集下载 xff08 1 xff09 解压后文件夹目录 xff08 2 xff09 gtFine格式如下所示 xff1a 二 转换为VOC数据集格式 xff08 1 xff09 生成xml标签 xff08 2 xff09 将le

  • 如何获取数据库的逻辑文件名、数据库文件的路径

    1 sp helpdb 数据库名 2 获取数据库文件路径 select ltrim rtrim filename from 数据库名 sysfiles where charindex 39 MDF 39 filename gt 0 sele

  • Linux进度条以及makefile相关知识

    一 在Linux环境下实现进度条 xff0c 其原理是 xff1a 用sleep函数或usleep函数控制每隔多长时间输出一次 xff0c 每次输出字符会比上次输出字符多一个 在此代码中 xff0c 用 r而不用 n的原因 xff1a n表

  • hdu - 4642 - Fliping game（博弈）

    题意 xff1a Alice和Bob玩游戏 xff0c 一个N M的矩阵 xff0c 里面是1或0 xff0c 每人每次选择一个1的位置 xff0c 然后将这个位置到右下角的整个矩形元素全部取反 xff08 1变0 xff0c 0变1 xf

  • 图形界面报错“已拒绝X11转移申请”的解决方法

    今天想通过本机给虚拟机起x manager图形界面的时候报出 解决办法 xff1a 原来X11 forwarding依赖 xorg x11 xauth 软件包 xff0c 所以必须先安装 xorg x11 xauth 软件包 yum ins

  • bash: ifconfig: command not found 解决办法

    经常遇到 34 bash xxxx command not found 34 这样的问题 xff0c 用root用户也不行 xff0c 在网上查阅了此问题 xff0c 解决方法如下 xff1a 原文1 http hi baidu com j

  • 用CMfcShellTree和CMFCShellListCtrl实现资源管理器并过滤扩展名

    资源管理器 CMfcShellTree和CMFCShellListCtrl是VS2008 SP1和VS2010内自带的控件 xff0c 用这两个控件实现资源管理器只需几行代码 CMFCShellTreeCtrl m tree CMyShel

  • 解决虚拟机下CentOS系统无法识别usb设备

    其实不是什么 解决 xff0c 虚拟机默认是自动挂载usb设备的 只是要注意插usb设备的时候 xff0c 虚拟机必须要处于当前窗口 然后就会自动弹出已安装好usb设备的提示 xff08 如果系统比较卡 xff0c 需要多等一会 xff09

  • 基于MDK的汇编语言编写及小灯闪烁的汇编程序实现

    基于MDK的STM32汇编语言编写及小灯闪烁的汇编程序实现 一 新建工程二 配置环境1 选择设备2 选择运行环境3 添加源文件 三 测试代码1 源码2 仿真器设置3 编译调试 四 HEX文件解读五 闪烁LED的程序六 总结参考 一 新建工程

  • WIndows10连接虚拟机显示connection confused

    Windows10连接虚拟机显示connection confused 当我们想由win10连接虚拟机终端时 xff0c 使用第三方软件Putty或者win10的cmd都可能出现connection confused问题 xff0c 解决这

  • 交换两个数字（不使用其他变量）

    面试题 交换两个数字 xff08 不使用其他变量 xff09 一 题目要求 xff1a 有两个整数变量a 61 6 b 61 100不使用其他变量 xff0c 交换两个变量的值 二 解法 解法1 xff08 使用其他变量 xff09 xff

  • unity如何使用电脑模拟VR环境

    unity如何通过VRTK模拟VR环境 如何在没有HTC VIVE的前提下使用VR xff1f 由于作者研究室课题是基于虚拟现实的人机交互 xff0c 需要用到VR下的场景 xff0c 但由于实验室设备只有一套 xff0c 而当我们想要随时

  • 笔试算法：青蛙跳台阶

    笔试算法 xff1a 青蛙跳台阶 1 题目表述 假设青蛙正在跳台阶 需要 n 阶你能到达楼顶 每次青蛙可以跳 1 或 2 个台阶 xff0c 但不可以连续跳2个 请问有多少种不同的方法可以到楼顶呢 xff1f 注意 xff1a 给定 n 是

  • 输入一行字符，分别统计出其中英文字母、空格、数字和其他字符的个数

    输入一行字符 xff0c 分别统计出其中英文字母 空格 数字和其他字符的个数 首先需要判断各自所出的范围 xff1a 中英文字母 xff1a a到z A到Z 空格 xff1a 空一个字符 数字 xff1a 1 9 然后则对一串字符进行逐个比

  • 逆波兰式的实现及表达式的值

    逆波兰式的实现 1 概念 逆波兰式也叫后缀表达式 xff0c 这里先简单帮大家理解一下概念性问题 像我们平常使用到的表达式如 a 43 b c

  • C语言栈的用法（创建、入栈、出栈、遍历）

    C语言栈的用法 xff08 创建 入栈 出栈 遍历 xff09 本篇博客主要简单介绍如何使用C语言构建栈 xff0c 元素入栈 xff0c 元素出栈以及遍历所有的栈内元素 1 栈的定义 首先对栈进行定义 xff0c 构建一个简单的结构体 x

  • 我印象中的徐志摩

    我印象中徐志摩 在我上中学的时候 xff0c 徐志摩对于我来说是一个神圣不可侵犯的名字 xff0c 那么一个具有才华和能力 xff0c 从他的作品里感受到他那浪漫的文艺气息和对自由生活的追求 xff0c 无不令我们这些初入青春期的孩子们留下

  • 根据文法规则，判断文法类型

    根据文法规则 xff0c 判断文法类型 1 实验要求 输入 xff1a 文法规则 输出 xff1a 文法类型 2 实验原理 文法规则 xff1a 以四元组的形式展示出来 xff1a 文法G 定义为四元组G 61 Vn Vt P S Vn x

  • 根据文法进行表达式推导

    根据文法进行表达式推导 xff08 编译原理 xff09 1 实验要求 已知文法 xff1a E gt T E 43 T T gt F T F F gt E i 请给出下述表达的推导公式 xff1a i 43 i i i 43 i i 2

  • （编译原理）正规文法转正规式（原代码）

    xff08 编译原理 xff09 正规文法转正规式 一 实验要求 输入 xff1a 正规文法输出 xff1a 正规式 例 xff1a 输入 xff1a S gt aB B gt b 输出 xff1a ab 输入 xff1a S gt aS

热门标签