正则表达式直接转为DFA算法www
更新时间:2024-01-11 07:47:01 阅读量: 教育文库 文档下载
- 正则表达式转dfa例题推荐度:
- 相关推荐
正则表达式直接转DFA
一、 设计原理
1. 正则表达式转换为DFA
算法描述
2. 正则表达式转换为DFA
(1) 建立字母表。输入的正则表达式由于一般不输入“与”操作符,因此
首先给表达式加入 .作为与操作。再利用逆波兰式的堆栈操作,把操作符与字母分开,便得到了字母表。
(2) 详解NULLABLE、FIRSTPOS、LASTPOS和FOLLOWPOS的计算规则 (3) 转载请注明出处:http://www.cnblogs.com/dzodzo/archive/2009/12/15/1624225.html (4) PDF版:http://www.fsderno.com/pdf/complier1.pdf (5) 引入 (6) 正在上编译原理的课程,为了对抗遗忘,写下这篇文章加强自己的记忆,
同时也希望能给大家带来帮助。
(7) 在编译原理中,要把正则表达式转化为DFA,其中有一步就是要计算语法
分析树上各结点的nullable、firstpos、lastpos和followpos。如果不理解其中的原理去背计算规则,这是一件非常痛苦的事情,本文的目的就是希望能说清楚两个问题,为什么要计算,如何计算。
(8) 前置知识:
(9) 句子:给定文法G[Z],若有Z +=> x, 且x∈VT*;则称x是文法G[Z]
的句子。
(10) or结点:标号为并运算符|的内部结点。 (11) cat结点:标号为连接运算符·的内部结点。 (12) star结点:标号为星号运算符*的内部结点。 (13) 位置:每个终结符对应一个位置。如图1。
(14)
(15) 计算NULLABLE(N)
(16) 说完了前置知识,我们先说一下比较容易理解的nullable(n),为什么要
计算nullable(n)呢?那是因为我们要根据结点n的nullable(n)函数的取值而采取不同的方法去计算firstpos和lastpost。说到这里可能有人要骂我了,“你这说了等于没说嘛”。希望大家稍安勿躁,因为问题是环环相扣的,我只是把解答放到后面了呵呵。
(17) nullable(n)表示以n为根结点推导出的句子集合是否包括空串,当推导
出的句子集合包含空串,那么nullable(n)=true;如果不包含空串,那么nullable(n)=false。现在我们针对结点n的五种情况进行分析: (18) 1、当结点n是叶子结点并且取值为空,此时以n为根结点推导出的句子
肯定为空,所以此时nullable(n)为true。如图2所示。
(19)
(20) 2、当结点n是叶子结点并且取值为id,此时以n推导出的句子有非空值
id,所以此时nullable(n)为false。
(21)
(22) 3、当结点n是or结点,此时n结点肯定为内部结点。由于是或运算,
当结点n的左子树(c1)或者右子树(c2)能推导出空串时,结点n也能推导出空串。即nullable(n)=nullable(c1) or nullable(c2)。以下三种情况都会使nullable(n)=true。(c1->ε表示c1能推导出空串ε,下同)
(23)
(24) 4、当结点n是cat结点,此时n结点肯定为内部结点。由于是连接运算,
当结点n的左子树(c1)和右子树(c2)能同时推导出空串,则结点n能推导出空串,即nullable(n)=nullable(c1) and nullable(c2)。以下一种情况nullable(n)=true。
(25)
(26) 5、当结点n是star结点,此时n结点肯定为内部结点,由Kleene闭包
运算的定义可知结点n推导出的句子集合包括空串,因此nullable(n)=true。
(27)
(28) 计算FIRSTPOS(N)
(29) 说完了nullable的计算规则,我们来说下firstpos(n)。为什么要算
firstpos?那是因为我们在为计算followpos做准备:)不要郁闷,继续往下看,你一定会知道终极的原因!firstpos(n)函数定义了以结点n为根的子树中的位置集合。这些位置对应于以结点n为根推导出的某个句子的第一个符号(“某个”代表可能有多个,因此firstpos的计算结果是位置的集合)。我们还是按照nullable的分析方法,以五种结点类型说明firstpos(n)的计算规则。
(30) 1、当结点n为叶子结点并且为空串,因为是空串,所以此时没有第一个符号,即firstpos(n)={?}。
(31)
(32) 2、当结点n为位置i的叶子结点。此时结点n只能推导出位置i的终结符,因此firstpos(n)={i}
(33)
(34) 3、当结点n为or结点(内部结点),此时进行or运算,左子树(c1)推
导出的第一个位置的集合firstpos(c1)包含于firstpos(n),同样右子树(c1)推导出的第一个位置的集合firstpos(c2)包含于firstpos(n)。因此firstpos(n)等于左右子树firstpos的并集。即firstpos(n)=firstpos(c1) U firstpos(c2)。
(35)
(36) 4、当结点n为cat结点(内部结点),此时进行连接运算,若左子树不能
推导出空串,那么结点n推导出的某个句子的第一个符号一定在firstpos(n)中。若左子树能推导出空串,那么第一个符号就有可能出现在右子树推导出的句子中。 (37) 因此:if(nullable(c1))
(38) firstpos(n)=firstpos(c1) U firstpos (c2) //图9 (39) else
(40) firstpos(n)=firstpos(c1) //图10
(41)
(42) 5、当结点n为star结点(内部结点),结点n只有一个棵子树(c1),无
论结点n的能不能推导出空串,firstpos(n)=firstpos(c1)。
Stack *s1,*s2; //s1为保存运算符的堆栈,s2为逆波兰式的输出结果 s1=(Stack *)malloc(sizeof(Stack)); s2=(Stack *)malloc(sizeof(Stack)); InitList(s1); InitList(s2); Push(s1,'#');
if((fp=fopen(\路径的写法 {
printf(\ exit(0); } else {
while((ch=fgetc(fp))!=EOF) {
if(Isalpha(ch)) {
Push(s2,ch); }
//begin :求取逆波兰式 else {
//括号的处理 if(ch=='(') { Push(s1,ch); } else {
if(ch==')') {
temp=GetTop(s1); while(temp!='('){ Push(s2,temp); Pop(s1);
temp=GetTop(s1); }
Pop(s1); } else { temp=GetTop(s1); //putchar(temp);
if(temp=='(') Push(s1,ch); else {
if(PriorCompare(ch,temp))//新的运算符的优先级高于栈顶元素 { Push(s1,ch); }
else {
while(PriorCompare(ch,temp)==0) {
Push(s2,temp); Pop(s1);
temp=GetTop(s1); if(temp=='(') break; }
Push(s1,ch); } } } } } } }
while(StackEmpty(s1)!=1) {
temp=GetTop(s1); Push(s2,temp); Pop(s1);
}//end:求取逆波兰式结束
//begin:下为显示逆波兰表达式,并将其存入到一个数组中的结果 int i = s2->top ; char nbl[i+1];
if(!StackEmpty(s2)) {
printf(\将正则表达式转换为逆波兰表达式后为:\ for(int j=0;j
nbl[j]= s2->data[j]; putchar(nbl[j]); }
nbl[i]='.';
putchar(nbl[i]); printf(\ }
//end:显示逆波兰结束
//begin:采用直接转为DFA的算法 int length= s2->top+1; bool nullable[length];
int position[length];//标识字符位置 int firstpos[length][length]; int lastpos[length][length]; int followpos[length][length]; int pos=1;
for(int i=0;i for(int j=0;j firstpos[i][j]=lastpos[i][j]=followpos[i][j]=0; } } // printf(\ for(int i=0;i if(Isalpha(nbl[i])||nbl[i]=='#') { position[i]=pos; pos++; nullable[i]=false; firstpos[i][0]=position[i]; lastpos[i][0]=position[i]; } else { position[i]=0;//运算符的position设为0 if(nbl[i]=='|') { nullable[i]=(nullable[i-2]||nullable[i-1]); int j=0; while(firstpos[i-1][j]!=0) { firstpos[i][j]=firstpos[i-1][j]; lastpos[i][j]=firstpos[i-1][j]; j++; } int k=0; int m; while(firstpos[i-2][k]!=0) { for(m=0;m if(firstpos[i][m]==firstpos[i-2][k]) break; } if(m==j) { firstpos[i][j]=firstpos[i-2][k]; lastpos[i][j]=firstpos[i-2][k]; j++; } k++; } } else if(nbl[i]=='*') { nullable[i]=true; int j=0; while(firstpos[i-1][j]!=0) { firstpos[i][j]=firstpos[i-1][j]; lastpos[i][j]=firstpos[i-1][j]; j++; } } else //连接符. { nullable[i]=(nullable[i-2]&&nullable[i-1]); if(nullable[i-2]==1) { int j=0; int m; while(firstpos[i-1][j]!=0) { firstpos[i][j]=firstpos[i-1][j]; j++; } int k=0; while(firstpos[i-2][k]!=0) { for(m=0;m if(firstpos[i][m]==firstpos[i-2][k]) break; } if(m==j) { firstpos[i][j]=firstpos[i-2][k]; j++; } k++; } } else { int j=0; while(firstpos[i-2][j]!=0) { firstpos[i][j]=firstpos[i-2][j]; j++; } } if(nullable[i-1]) { int j=0; while(firstpos[i-1][j]!=0) { lastpos[i][j]=firstpos[i-1][j]; j++; } int k=0; int m; while(firstpos[i-2][k]!=0) { for(m=0;m if(lastpos[i][m]==firstpos[i-2][k]) break; } if(m==j) { lastpos[i][j]=firstpos[i-2][k]; j++; } k++; } } else { int j=0; while(firstpos[i-1][j]!=0) { lastpos[i][j]=firstpos[i-1][j]; j++; } } } } } for(int i=0;i int j=0; while(firstpos[i][j]!=0) { printf(\ j++; } printf(\ } printf(\ for(int i=0;i int j=0; while(lastpos[i][j]!=0) { printf(\ j++; } printf(\ } for(int i=0;i if(nbl[i]=='.') { int m=0; while(lastpos[i-2][m]!=0) { int k; for(k=0;k if(followpos[lastpos[i-2][m]][k]==0) break; } int n=0; while(firstpos[i-1][n]!=0) { followpos[lastpos[i-2][m]][k]=firstpos[i-1][n]; n++; k++; } m++; } } if(nbl[i]=='*') { int m=0; while(lastpos[i][m]!=0) { int n; for(n=0;n if(followpos[lastpos[i][m]][n]==0) break; } int k=0; while(firstpos[i][k]!=0) { followpos[lastpos[i][m]][n]=firstpos[i][k]; k++; n++; } m++; } } } printf(\ for(int i=0;i if(position[i]!=0) { int k=0; printf(\ while(followpos[position[i]][k]!=0) { printf(\ k++; } printf(\ } } //end:直接转为DFA的算法 getch(); return 0; }
正在阅读:
正则表达式直接转为DFA算法www01-11
病例分析复习题06-02
iphone 5s点位图(1)09-03
江大16秋《课程与教学论》第三次离线作业11-05
《企业所得税网上申报系统操作手册(适用于纳税人申报)》08-30
上海市长宁、嘉定区2017届高三上学期期末质量调研(一模)数学试题01-01
组成原理考前辅导复习题10-21
小学数学(人教版)四年级下册期末测试卷07-23
人教版七年级英语下册第4单元测试题附答案05-03
商品学结课论文11-02
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 正则
- 表达式
- 转为
- 算法
- 直接
- DFA
- www
- 计算机导论期中检测试题答案
- 2019高考化学(人教经典版)大一轮复习检测:第5章 物质结构 元素周期律5-1a Word版含解析
- 混凝土购销合同简易版
- 2018届高考数学二轮复习第一部分专题六解析几何1.6.2圆锥曲线的定义性质直线与圆锥曲线限时规范训练理
- 步步高必修一物理第三章学案4汇总
- HJ毕业论文格式
- 小学三年级科学期末考试试卷
- 直线射线线段教学反思
- 我国保险企业会计核算问题研究
- 骨干教师跟岗学习总结
- 工程材料与热加工
- 2013年师大一中小升初外地生考试语文试卷
- 论建筑电气安装工程中存在的问题及防治措施
- 《百合花》教案
- 拓展注册会计师行业新业务服务经济发展方式转变有奖征文启事
- 风电场交接班实施细则
- 历年自主招生面试题优选
- (新人教版)七年级上册生物:单细胞生物教学设计
- 2012年新版PEP小学三年级英语上册unit4教案
- 战略发展中心工作思路及工作计划