【编译原理】正则表达式

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

《编译原理》第三章习题

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

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

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

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*

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

本文链接：https://blog.csdn.net/iteye_18800/article/details/82374000

智能推荐

正则表达式

在编写处理字符串的程序或网页时，经常有查找符合某些复杂规则的字符串的需要。正则表达式就是用于描述这些规则的工具。换句话说，正则表达式就是记录文本规则的代码。常用元字符 . 匹配除换行符以外的任意字符 \w 匹配字母或数字或下划线 \s 匹配任意的空白符 \d 匹配数字 \b 匹配单词的开始或结束 ^ 匹配字符串的开始 $ 匹配字符串的结束常用限定符 * 重复零次或更多次 + 重复一次或更多次 ...

正则表达式

正则表达式是用于描述一组字符串特征的模式，用来匹配特定的字符串。通过特殊字符+普通字符来进行模式描述，从而达到文本匹配的目的的工具。应用场景验证：表单提交时，进行用户名密码验证。查找：从大量信息中快速提取指定内容。替换：将指定格式的文本，进行正则匹配查找，找到之后进行特定替换基本要素字符类数字限定符位置限定符 grep是Linux下按行匹配文本的工具 -E：使用扩展正则匹配 --c...

正则表达式

什么是正则表达式？用来检测某个字符串是否符合一定规则的语句。是以对象的形式存在的。声明正则的方法：原子：元字符：原子表：量词：边界匹配： /^.../, /...$/ 贪婪与非贪婪： ...

正则表达式

shell编程之正则表达式部分正则表达式简介正则表达式是用于描述字符排列和匹配模式的一种语法规则。它主要用于字符串的模式分割、匹配、查找以及替换操作。正则表达式与通配符这里归纳一下：正则表达式：主要用来匹配文件内容，如greo 包含匹配通配符：主要用来匹配文件名，如find 完全匹配基础正则表达式字符截取命令 cut [选项] 文件名选项： -f 列号:提取相应的列号，列号以...

正则表达式

列一下正则表达式中常用字符的用法，表格转自菜鸟教程基本元字符：符号.在[]字符集中，其不再代表除换行符之外的任何一个字符，而是纯粹的点符号。符号^在[]字符集中，代表否定前缀，而不是定位字符开始的位置。字符集：捕获组和先行后行断言：非打印字符和预定类：下表从最高到最低说明了各种正则表达式运算符的优先级顺序：捕获组捕获组就是把正则表达式中子表达式匹配的内容，保存到内存中以数字编号或...

【编译原理】正则表达式

《编译原理》第三章习题

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

3.3.5

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

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

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

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

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

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

智能推荐

猜你喜欢