`
tempsitegoogle
  • 浏览: 862238 次
文章分类
社区版块
存档分类
最新评论

【编译原理】正则表达式

 
阅读更多

08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://blog.csdn.net/xiaowei_cqu/article/details/7747205


《编译原理》第三章习题

我们的教材是那本经典的“龙书”:《Compiler: Principles, Techniques, and Tools》

灰常灰常喜欢小监老师的课,就是做作业的记忆太痛苦了。。。

3.3.2 试描述下列正则表达式定义的语言


1) a(a|b)*a
以a开头且以a结尾,中间由零个或多个a或b的实例构成的串
2) ((ε|a)b*)*
零个或多个a或b的实例构成的串
3)(a|b)*a(a|b)(a|b)
三个或多个a或b的实例构成的串,且倒数第三个实例一定为a。
4)a*ba*ba*ba*
零个或多个a的实例,三个b的实例构成的串。
!!5)(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*
零个或偶数个a的实例,相同个数的b的实例构成的串

3.3.5


3) Comments, consisting of a string surround by /* and */, without an intervening*/, unless it is inside double-quotes (")
(\/\*) (.*^(\/\*)) (“(.*)”|ε) (.*^(\/\*)) (\*\/)

3.4.1 给出识别练习3.3.2中各个正则表达式所描述的语言的状态转换图


1) a(a|b)*a

2) ((ε|a)b*)*

3)(a|b)*a(a|b)(a|b)

4)a*ba*ba*ba*

!!5)(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*


3.6.2 为练习3.3.5中的每一个语言设计一个DFA或NFA


Comments, consisting of a string surround by /* and */, without an intervening*/, unless it is inside double-quotes (")
设计NFA如下:

(感觉这个有些问题,不知道^可不可以用作转移条件。。。。)

3.6.5 给出如下练习中的NFA的转换表


1)练习3.6.3

2)练习3.6.4

3)图 2-6


3.7.1 将下列图中的NFA转换为DFA


1)图3-26

2)图3-29


3)图3-30



3.7.3 用算法3.23和3.20将正则表达式转换为DFA


1) (a|b)*
由算法3.23得到NFA:

由算法3.20得到DFA:

2) (a*|b*)*
由算法3.23得到NFA:

由算法3.20得到DFA:

3) ((ε|a)b*)*
由算法3.23得到NFA:

由算法3.20得到DFA:

此处可以看到 1) 2) 3)表示的语义是等价的,NFA可以有多种表示形式,但DFA是唯一的
4)(a|b)*abb(a|b)*
由算法3.23得到NFA:

由算法3.20得到DFA:


转载请注明出处:http://blog.csdn.net/xiaowei_cqu/article/details/7764967



分享到:
评论

相关推荐

    编译原理正则表达式转NFA转DFA DFA最小化 Cpp代码

    编译原理课的大作业 包含三个小实验 在一个cpp文件里 正则表达式转换为nfa nfa转换为dfa dfa最小化 个人原创代码

    编译原理正则表达式的相关应用

    大学课程中编译原理课程的正则表达式章节中关于正则表达式的理解和应用,使用Java GUI进行编写,主要包括了各种主要的正则匹配和正则使用

    编译原理正则表达式匹配网址

    Java 程序设计: 为 UnLinker.java 文件中的 UnLinker 类实现成员函数 String clean(String text)。 函数 clean 的功能是:屏蔽字符串参数 text 中的网页链接信息,并返回屏蔽后的结果; 如果无需屏蔽,则返回原来的...

    正则表达式转NFA

    课程设计 正规式构造nfa.这是编译原理的一个实验, 是把一个正则表达式转化为不确定有穷自动机NFA的算法程序,朋兴趣的朋友可以下载来看看哦。

    正则表达式 到 NFA

    这是编译原理的一个实验, 是把一个正则表达式转化为不确定有穷自动机NFA的算法程序,朋兴趣的朋友可以下载来看看哦. 一个正则表达式就是由普通字符(例如字符 a 到 z)以及特殊字符(称为元字符)组成的文字模式...

    构造正则表达式的简化DFA算法

    构造正则表达式的简化DFA算法论文 介绍了构造等价于给定正则表达式的简化确定有限自动机(DFA) 的算 法. 方法是首先构造与正则表达式等价的非确定有限自动机(NFA) , 这里省略了构 造带E动作的有限自动机的操作, 然后...

    正则表达式转为NFA

    正则表达式转为NFA 请参看 http://blog.csdn.net/lileyear/上的文章 \"blex ----我的flex\

    正则表达式到NFA

    编译原理的一个实验,正则表达式到NFA

    编译原理程序小集(正则表达式 NFA DFA MFA 词法分析 语义分析)

    上编译原理课的时候做的几个小程序,包含一个简单的词法分析程序、正则表达式-NFA-DFA-MFA转换程序、表达式求值语义分析程序,其中正则表达式-NFA-DFA-MFA重点写的,花了不少心思,写得不是特别满意,今后会重新上传...

    精通正则表达式~~~

    正则表达式的应用原理... 241 应用之前的优化措施... 242 通过传动装置进行优化... 246 优化正则表达式本身... 247 提高表达式速度的诀窍... 252 常识性优化... 254 将文字文本独立出来... 255 将锚点独立...

    编译原理中正规式转化为nfa

    编译原理中的正规式到nfa的转换 超详细的课程设计

    编译原理--正则表达式文档

    正则表达式 原文地址 http://www.cppblog.com/vczh/archive/2008/05/22/50763.html

    正则表达式最小化DFA

    正则表达式转NFA->NFA转DFA->最小化DFA->测试字符串是否匹配

    正则表达式编译原理

    正则表达式编译原理

    C++ 正则文法定义-正则表达式-NFA-DFA-最小化DFA-字符串匹配DFA

    内容主要包括:自定义正则文法(在ProgramManager类中自定义),根据正则文法和输入的正则表达式构建NFA,NFA自动构建DFA,DFA最小化,DFA匹配字符串。其中含有大量的中文注释,并提供了测试方法。本人还是学生,...

    DFA.rar_正则表达式 DFA_正则表达式dfa

    编译原理课程设计之正则表达式与自动机之间的变换

    正则表达式和DFA

    学校的课程设计,非常完整,里面包含源程序和实验报告,详细的程序流程图。 实验要求:正则表达式--NFA--DFA--最小DFA

    基本正则表达式实现regex-v1.0

    学习编译原理,做一个简单的正则表达式。 ---------------------------------------- 实现了基本的正则表达式功能,支持基本的运算符:|、连接、*、+、?。 暂不支持转义字符,不过通过修改Scanner可以轻松解决。 ...

    VC++从正则表达式到有穷自动机实例

    想研究透彻正则表达式,必须知道有穷自动机的原理,这个源码可以给你一个很好的示例参考。编译后程序会生成一个可执行文件,运行这个文件出来一个DOS窗口,然后按提示输入正则表达式。

Global site tag (gtag.js) - Google Analytics