- 1、本文档共50页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
第3章词法分析;3.1单词的描述
3.2单词的识别
3.3词法分析阶段的错误处理
3.4词法分析器生成工具Lex
;3.1单词的描述;假设r和s都是RE,表示的语言分别是L(r)和L(s),则
r|s是一个RE,L(r|s)=L(r)∪L(s)
rs是一个RE,L(rs)=L(r)L(s)
r*是一个RE,L(r*)=(L(r))*
(r)是一个RE,L((r))=L(r);令∑={a,b},则
L(a|b)=L(a)∪L(b)={a}∪{b}={a,b}
L((a|b)(a|b))=L(a|b)L(a|b)={a,b}{a,b}={aa,ab,ba,bb}
L(a*)=(L(a))*={a}*={ε,a,aa,aaa,...}
L((a|b)*)=(L(a|b))*={a,b}*={ε,a,b,aa,ab,ba,bb,aaa,...}
L(a|a*b)={a,b,ab,aab,aaab,...}
;十进制整数的RE
(1|...|9)(0|...|9)*|0
八进制整数的RE
0(1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*
十六进制整数的RE
0x(1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*
;可以用RE定义的语言叫做正则语言(regularlanguage)或正则集合(regularset)
;RE的代数定律;对任何正则文法G,存在定义同一语言的正则表达式r
对任何正则表达式r,存在生成同一语言的正则文法G;正则定义是具有如下形式的定义序列:
d1→r1
d2→r2
…
dn→rn
其中:
每个di都是一个新符号,它们都不在字母表Σ中,而且各不相同
每个ri是字母表Σ∪{d1,d2,…,di-1}上的正则表达式;C语言中标识符的正则定义
digit→0|1|2|…|9
letter_→A|B|…|Z|a|b|…|z|_
id→letter_(letter_|digit)*
;(整型或浮点型)无符号数的正则定义
digit→0|1|2|…|9
digits→digitdigit*
optionalFraction→.digits|ε
optionalExponent→(E(+|-|ε)digits)|ε
number→digitsoptionalFractionoptionalExponent;3.1单词的描述
3.2单词的识别
3.3词法分析阶段的错误处理
3.4词法分析器生成工具Lex
;3.2单词的识别;有穷自动机(FiniteAutomata,FA)由两位神经物理学家MeCuloch和Pitts于1948年首先提出,是对一类处理系统建立的数学模型
这类系统具有一系列离散的输入输出信息和有穷数目的内部状态(状态:概括了对过去输入信息处理的状况)
系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后,系统的内部状态也将发生改变;电梯控制装置
输入:顾客的乘梯需求(所要到达的层号)
状态:电梯所处的层数+运动方向
电梯控制装置并不需要记住先前全部的服务要求,只需要知道电梯当前所处的状态以及还没有满足的所有服务请求
;
输入带(inputtape):用来存放输入符号串
读头(head):从左向右逐个读取输入符号,不能修改(只读)、
不能往返移动
有穷控制器(finitecontrol):具有有穷个状态数,根据当前的
状态和当前输入符号控制转入下一状态;转换图(TransitionGraph)
结点:FA的状态
初始状态(开始状态):只有一个,由start箭头指向
终止状态(接收状态):可以有多个,用双圈表示
带标记的有向边:如果对于输入a,存在一个从状态p到状态q的的转换,就在p、q之间画一条有向边,并标记上a;给定输入串x,如果存在一个对应于串x的从初始状态到某个终止状态的转换序列,则称串x被该FA接收
由一个FA接收的所有串构成的集合称为是该FA定义(或接收)的语言,记为L(M);当输入串的多个前缀与一个或多个模式匹配时,总是选择最长的前缀进行匹配
在到达某个终态之后,只要输入带上还有符号,DFA就继续前进,以便寻找尽可能长的匹配;确定的FA(Deterministicfiniteautomata,DFA)
非确定的FA(N
您可能关注的文档
- 美容药物学补充阅读-自由基学习资料.pptx
- 美容药物学第00章 绪论-2015学习资料.pptx
- 美容药物学第01章 皮肤保养基础-2015学习资料.pptx
- 美容药物学第03章 保湿-2015学习资料.pptx
- 美容药物学第04章 防晒-2015学习资料.pptx
- 美容药物学第6章 祛痘-2015学习资料.pptx
- IBM AIX & Linux 课件 chap2-程序包原理及linux package.ppt
- IBM AIX & Linux 课件 chap3-设备管理与驱动.ppt
- IBM AIX & Linux 课件 chap4-存储管理与文件系统.ppt
- IBM AIX & Linux 课件 chap5-安全管理及开发基础技术.ppt
最近下载
- IEC_62366-1AMD1-2020 医疗设备 - 第 1 部分:可用性工程在医疗设备中的应用.pdf VIP
- 妇幼卫生信息管理培训.pptx VIP
- 毗邻建筑物及地下管线保护方案.doc VIP
- 江苏灵山耿湾禅意小镇旅游度假村规划设计方案文本.pptx
- 行政法历年司考真题(案例分析) .pdf VIP
- NB∕T 42030-2014 -生物质循环流化床锅炉技术条件.pdf
- 软件系统项目验收报告.docx VIP
- DGJ32J 203-2016 建筑工地扬尘防治标准.docx
- 无线电反制技术及其在无人机探测与反制领域的应用.pdf VIP
- 《人文英语4》形考任务(1-8)试题答案解析.pdf VIP
文档评论(0)