当前位置：文档之家 › 第3章 词法分析(1)

第3章 词法分析(1)

  • 格式：ppt
  • 大小：296.00 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

词法分析及词法分析程序

词法分析及词法分析程序
语义加工过程：
– w,p,n初值为0，e初值为1；
– 处理整数部分时，对于每个di ,令w=w10+di ; – 处理小数部分时，对于每个di ,令w=w10+di ;及n++;
– 处理指数时，E后若有‘-’号，令e=-1；计算指数值 p=p10+d;
– 在出口处，令ICON=w或FCON=w10^(e(p-n)).
(2)设当前处在Ai状态,所扫描的字符为ai+1,在结点Ai所 射出的诸矢线中,寻找标记为ai+1的矢线(若不存在,则 表明w有语法错误),读入ai+1,并进入状态Ai+1;
(3)重复(2),直到w中所有字符被读完且恰好进入终态F 时,宣告整个识别结束,w可被接受.
28
例:G[Z]:
状态转换图:
Z→0U∣1V
{return ( ICON= w ); {n++; w=w*10+d;}
{return (FCON =w*pow(10,e*p-n) ) ;} {n++;w=w*10+d;} error {p=p*10+d;}
e=-1; error {p=p*10+d;} error {p=p*10+d;} {return (FCON=w*pow(10,e*p-n) );
(1)对于G中形如Aa 的产生式，引矢线RA，且标记
为a；
(2)对于G中形如ABa 的产生式，引矢线 BA，且标
记为a。
34
由左线性文法构造状态转换图
已给文法G=({S,U},{0,1},{SS1 |U1, UU0 | 0},S)
R0
0
1
U1 S

《编译原理》第3章

《编译原理》第3章

NFA到相应的DFA的构造的基本思路是： DFA的每 一个状态对应NFA的一组状态. DFA使用它的状 态去记录在NFA读入一个输入符号后可能达到的 所有状态.
NFA M所能接受的符号串的全体记为L(M)
结论：
上一个符号串集V是正规的，当且仅当存 在一个上的不确定的有穷自动机M，使得 V=L(M)。
DFA是NFA的特例.对每个NFA N一定存在一个DFA Ｍ，使得 L(M)=L(N)。对每个NFA N存在着与之 等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA.这 种算法称为子集法. 与某一NFA等价的DFA不唯一.
0
1
S P
Z
{P} {}
{P}
{S,Z} {Z}
{P}
• δ为S * 到S的子集(2 S)的一种映射
• 从NFA的矩阵表示中可以看出，表项通常是一状态的集合， 而在DFA的矩阵表示中，表项是一个状态
∑*上的符号串t被NFA M接受:
• 对于Σ*中的任何一个串t，若存在一条从某一初态 结点到某一终态结点的道路，且这条道路上所有 弧的标记字依序连接成的串(不理采那些标记为ε 的弧)等于t，则称t可为NFA M所识别(读出或接 受)。 • 若M的某些结点既是初态结点又是终态结点；或 者存在一条从某个初态结点到某个终态结点的道 路,其上所有弧的标记均为ε，那么空字ε可为M所 接受。
其中： δ(S，0)={P}
δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z} • 状态图表示
1 1 S 0 0,1 Z
P
1
• 矩阵表示
状态 输入
δ(S，0)={P} δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z}

北航编译原理课件 03.词法分析

北航编译原理课件 03.词法分析

3. 词法分析程序算法
北京航空航天大学计算机学院
17
1.单词及内部表示 单词及内部表示: 单词及内部表示
单词名称
BEGIN END FOR DO IF THEN ELSE 标识符 常数(整 常数 整) : + * , ( ) :=
保留字和分界符采用一符一类
记忆符
BEGINSY ENDSY FORSY DOSY IFSY THENSY ELSESY IDSY INTSY COLONSY PLUSSY STARSY COMSY LPARSY RPARSY ASSIGNSY
字母、数字
标识符 无符号整数
单字符分界符
S S S
字母
标 数字
非字母数字
出口
数字
数
非数字
出口
+ * ， 单界 （ ） ：
其他字符 非=
出口
双字符分界符
北京航空航天大学计算机学院
S
冒号
=
双界
其他字符
出口 15
查保留字表 读字符
字母、数字
S
字母
标 数字
非字母数字
标识符
非数字
数字
数
无符号整数 单字符分界符
如：b{ab} = {ba}b {a|b} = {{a} {b}} = (a*b*)*
北京航空航天大学计算机学院 23
例：设 ∑ = { a,b },下面是定义在∑上的正则表达式和正则集合 正则表达式 ba* a(a|b)* (a|b)*(aa|bb)(a|b)* 正则集合
北京航空航天大学计算机学院
北京航空航天大学计算机学院 20
‘*’ : ‘,’ : ‘(’ : ‘)’ : ‘:’ :

编译原理词法分析及词法分析程序

编译原理词法分析及词法分析程序
∴M能识别出L(G)中的全部句子。
状态图=>右线性文法
文法G[0] 0->a1
d 0
S->aA A->dA A->b
a c
1 2
b
d
3
1->d1 1->b
0->c
0->c2 2->d
S->c
S->cB，2有出弧 B->d
左线性文法=>状态转换图
设G=(VN,VT,P,S)是一左线性文法,令|VN|=K， 1) 则所要构造的状态转换图共有K+1个状态. 2) VN中的每个符号分别表示K个状态 2.1) G的开始符S为终止状态 3) 起始状态,用R(VN)标记
识别符号串与归约
S





从初态R到下一状态A对应Ba，即终结 符a归约成非终结符B; U 从状态B转换到状态A对应ABa,即将 Ba归约为A; 状态A转换到状态S(终态)对应S Aa,即 U 将Aa归约为开始符S. 归约成功,恰好进入终态,即状态转换图识 U 别了(或接受)该符号串. 识别00011的例子的归约过程
f是转换函数，是在K×Σ →K上的映像，即：如果f（ki，a）=kj， （ki，kj∈K）意味着，当前状态为ki，输入字符为a时，将转换 为下一个状态kj，我们把kj称作ki的一个后继状态；
1.确定的有限自动机
通常把这五要素组成的五元式M=(K,∑,f, S0,Z)称为确定的 有限自动机(DFA)，它是相应的状态转化图的一种形式描 述，或者说，是状态转换矩阵的另一种表示。 在状态转换的每一步，据DFA当前所处状态及扫视的输入 字符，能唯一确定下一状态。

例：文法G=({S,U},{0,1},{SS1 |U1,

第1讲-确定的有限自动机

第1讲-确定的有限自动机

对于Σ*中的任何字符串α，若DFA M中存在一条从 初态结点到某一终态结点的路，且这条路上所有弧的标
记连接成的字符串等于α，则称α可以被DFA M所接受 (识别)。
若M的初态结点同时又是终态结点，则空串ε可被 M所接受（识别）。
若α∈Σ*，f(S, α)=P，其中S为DFA M的初始状 态，P∈Z，Z为终态集，则称字符串α可以被DFA M 所接受(识别) 。
DFA M= ({S,U,V,Q}, {a,b}, f,S,{Q})
事实上，状态转换图是有限自动机的一种表示形式，假定DFA M 含有m个状态，n个输入字符，那么这个状态转换图含有m个状态 （结点），每个结点最多有n个弧射出，整个图含有唯一一个初态 结点(冠以“⇒” )和若干个终态结点(用双圈表示)，若有f(ki,a)=kj (ki∈K,kj∈K,a∈Σ),则从状态结点ki到状态结点kj画标记为a的弧。
(4) S0∈S，是唯一的初始状态；
(5) F ⊆ S，是终止状态集合。
编 译 技术
chapter3 词法分析——有限自动机
例：为下图所示的状态图构造确定的有限自动机。
f(S,a)=U f(S,b)=V f(V,a)=U f(V,b)=Q f(U,a)=Q f(U,b)=V f(Q,a)=Q f(Q,b)=Q
编 译 技术
chapter3 词法分析——有限自动机
一个DFA还可以用一个矩阵(状态矩阵）表示： 矩阵的行表示状态，列表示输入字符，矩阵元素表示 相应状态行和输入字符列下的新状态。
例：上例的DFA的矩阵表示如下：
字符
状态
a
S
U
U
Q
V
U
Q
Q
b
V0 V0 Q0 Q1

计算语言学讲义(03)词法分析(一)

计算语言学讲义(03)词法分析(一)
计算语言学讲义(04)词法分析I
6
序列标注问题
• 输入：一个符号序列 • 输出：给每一个输入符号赋予一个标记 • 常见具体问题：
– 音字转换：拼音序列 – 词性标注：词语序列 – 词义排歧：词语序列 汉字序列 词性序列 词义标记序列
计算语言学讲义(04)词法分析I
7
序列结构化
• 输入：一个符号序列 • 输出：一个结构，刻划符号之间的关系 • 常见具体问题：
• 输入：一段文本 • 输出：单词串 • 算法：（略）
计算语言学讲义(04)词法分析I
21
Stemming
屈折型语言的词语变化形式： • 屈折变化：即由于单词在句子中所起的语法作用的不同而 发生的词的形态变化，而单词的词性基本不变的现象，如 （ take, took, takes）。识别这种变化是词法分析的最 基本的任务。 • 派生变化：即一个单词从另外一个不同类单词或词干衍生 过来，如morphological morphology，英语中派生变化 主要通过加前缀或后缀的形式构成；在其他语言中，如德 语和俄语中，同时还伴有音的变化。 • 复合变化：两个或更多个单词以一定的方式组合成一个新 的单词。这种变化形式比较灵活，如well-formed, 6year-old等等。 Stemming的目的：将上述变化还原
– 成分句法分析：词语序列 短语结构树 – 依存句法分析：词语序列 依存树 – 语义分析：词语序列 语义网络
计算语言学讲义(04)词法分析I
8
问题与方法
• 计算语言学常用方法：
– 规则方法
• 形式语法理论 • 形式逻辑 • ……
– 统计方法
• • • • n元语法模型 隐马尔科夫模型 最大熵模型 ……
计算语言学讲义(04)词法分析I

程序设计语言编译原理(第三版)第3章

程序设计语言编译原理(第三版)第3章

程序设计语言编译原理(第三版)第3章第3章词法分析任务：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串。

§3.1§3.2§3.3§3.4对于词法分析器的要求词法分析器的设计正规表达式与有限自动机词法分析器的自动产生(LE某)—略1§3.1对于词法分析器的要求一.功能和输出形式二.接口设计§3.1对于词法分析器的要求一.功能和输出形式1.功能：输入源程序，输出单词符号2.单词符号的分类(1)关键字:由程序语言定义的具有固定意义的标识符，也称为保留字或基本字。

例如：Pacal语言中begin(2)标识符：用来表示各种名字。

endifwhile等。

如变量名、数组名、过程名等。

(3)常数：整型、实型、布尔型、文字型等例：100(5)界符：,;3.14159()true等ample(4)运算符：+、-、某、/3§3.1对于词法分析器的要求3.输出的单词符号形式二元式：(单词种别，单词符号的属性值)通常用“整数编码”“单词符号的特征或特性”单词符号的编码：标识符：一般统归为一种常数：常按整型、实型、布尔型等分类关键字：全体视为一种/一字一种运算符：一符一种界符：一符一种4§3.1对于词法分析器的要求例：考虑下述C++代码段：while(i>=j)i--;经词法分析器处理后，它将被转换为如下的单词符号序列：<while,-><(,-><id,指向i的符号表项的指针><>=,-><id,指向j的符号表项的指针><),-><id,指向i的符号表项的指针><--,-><;,->§3.1对于词法分析器的要求二.接口设计1.词法分析器作为独立的一遍词法分析字符流(源程序)单词序列(输出在一个中间文件上)2.词法分析器作为一个独立的子程序，但并不一定作为独立的一遍语法分析器单词(至少一个)调用(取下一个单词)词法分析器优点：使整个编译程序的结构更简洁、清晰和条理化.6§3.2词法分析器的设计一.输入和预处理二.单词符号的识别三.状态转换图及其实现§3.2词法分析器的设计一.输入、预处理1.预处理：剔掉空白符、跳格符、回车符、换行符、注解部分等.原因：编辑性字符除了出现在文字常数中之外，在别处的任何出现都无意义.#注解部分不是程序的必要组成部分，它的作用仅在于改善程序的易读性和易理解性.8§3.2词法分析器的设计2.预处理子程序：每当词法分析器调用时，就处理出一串确定长度(如120个字符)的输入字符，并将其装进词法分析器所确定的扫描缓冲区中。

ch3 词法分析

ch3 词法分析

19
例子
数字 数字 其他 * 1 2 3
识别整常数的状态转换图 字母或数字 字母 其他 *
1
2
3
识别标识符的状态转换图
20
词法分析程序的构造


程序设计语言各类单词的词法都能用相应的正规文法 来描述，由正规文法可以构造出相应的状态图，进而 识别一个单词。 状态转换图非常容易用程序来实现， 最简单的办法是让每一个状态结对应一小段程序 一个词法分析程序可以通过一下步骤得到： 1.根据语言的词法规则写出描述单词的正规文法； 2.将正规文法转换成相应的状态图； 3.将状态图转换成算法的流程图，进而实现词法分析 程序。
31
else if (ch =„*‟) begin GetChar(); if (ch =„*‟) return ($POWER, -); Retract(); return ($STAR, -); end else if (ch =„;‟) return ($SEMICOLON, -); else if (ch =„(‟) return ($LPAR, -); else if (ch =„)‟) return ($RPAR, -); else ProcError( ); /* 错误处理*/
正规文法又成为右线性文法。 左线性文法：产生式为 A→Ba或 A→a
15
由正规文法构造状态图
1.对于右线性文法，状态图的构造步骤如下：



步骤1：增加节点Z为终态（假定文法的字母表中 不包括符号Z）； 步骤2：将每一个非终结符号设置为一个对应的状 态； 步骤3：对于形如A→a的每一个规则，引一条从状 态A到Z的弧，弧上标记为a；而对于形如A→aB的 每个规则，引一条从状态A到B的弧，标记为a（其 中B∈VN ，a∈VT ）。

词法分析

词法分析
三、词法分析程序的安排
第三章 词法分析
常常把词法分析程序作为独立的一遍或作 为被语法分析程序所调用的子程序。
1、作为独立的一遍：
语法分析前进行词法分析，把单词符号 串形成中间文件存贮。
2019/11/21
中南大学软件学院 陈志刚
6
3.1 词法分析概述
第三章 词法分析
三、词法分析程序的安排
2019/11/21
中南大学软件学院 陈志刚
27
六、转换系统
第三章 词法分析
定义：转换系统是具有下列三个特征的状态转换 图，即 1) 开始状态S和终止状态Z 唯一; 2) 无弧进入S，也无弧自Z射出；
3)可能存在标记为空串（ε）的弧。
转换系统与状态转换图的区别： ε弧
ε S1
Z1 ε
S
A
Z
2019/11/21
中南大学软件学院 陈志刚
14
3.1 词法分析概述
五、词法分析程序的输出形式
解：输出的单词串为：
第三章 词法分析
2019/11/21
中南大学软件学院 陈志刚
15
第三章 词法分析
3.2 词法分析程序的设计
一、状态转换图
状态转换图是一张有限方向图。用结点代表状态， 状态之间用箭弧连接，箭弧上的标记（字符）代表 在射出结状态下可能出现的输入字符或字符类。
1 非字母或数字 2
例2：
0
1
U
数字
3
非数字
4
=
5
0 0
V
1
2019/11/21
01
+
6
Z
例3：
*
7
非*
8

编译原理 第3章

编译原理 第3章
编译原理 6
3.1.3 识别标识符的若干约定和策略
定义标识符的语法规则为 <标识符>→<字母>∣<标识符><字母>∣<标识符><数字> 从语法上来说,标识符的长度似乎可以任意。 然而,考虑实现技术,许多语言都对标识符的最大允许长度作 了限制。
编译原理
7
设计扫描器时,按如下原则行事: 1. 如果一个标识符中的字符个数超过最大允许长度,则把尾部 多出的字符截去; 2. 对于字符个数不超过最大允许长度的标识符,则按“尽可能 长”的策略来识别标识符。
图3.5 状态图
首先，在开始状态R下扫描的第一个符号是0，转到状态 V，表示0是句柄，归约到V。接下来，在状态V扫描1， 转到状态S，此时句柄为V1，归约成S。再往下扫描1，由 状态S转到状态U，表示句柄为S1归约为U。最后，扫描0， 转到状态S，此时句柄为U0，归约为S，
编译原理 27
图3.6（a）列出分析的每一步。形成图3.6（b）所示的语法 树。 自底向上的分析。
读入a1，沿矢线方向到下一状态，在此状态时扫 描a2，……， 直至W中全部字符读完且进入终态F，则W已被接受。
编译原理 19
例：下面的状态图对于串baabba的识别 S→aA|bB，A→bB|aD|a，B→aA|bD|b，D→aD|bD|a|b
a
A a a
a

S b
b
B
a
D b a,b b Z
编译原理
16
E d
d 0
d
d
d 5 d 6
1
.
d
2
E
4
±
. 图3.4文法G<无符号数>的状态图

词法分析(一)

词法分析(一)
第3章 词法分析(一)
2012-12-5
莆田学院许振和
1
本章要求

主要内容：词法分析的任务，手工 实现词法分析程序，正规式与有穷 自动机，词法分析程序的自动生成 重点掌握：词法分析器的功能和接 口，用状态转换图设计和实现词法 分析程序，正规文法、正规式和有 穷状态自动机的概念及相互转换

2012-12-5
2012-12-5 莆田学院许振和
12
5. 词法错误处理
词法分析器根据各类单词的构词规则分离、 识别单词符号，所以它只对源程序进行非常局部 的检查，仅能发现非法的单词符号。 词法分析器也可以采用下列可能的错误恢 复动作：
（1）删除一个多余的字符； （2）插人一个遗漏的字符； （3）用一个正确的符号代替一个不正确的符号； （4）交换两个相邻的字符。
2012-12-5
莆田学院许振和
23
某简单语言的词法 分析程序的实现 状态转换图的实 现：使用一个 switch case 语 句：每条分支对 应一个case语句 段
2012-12-5
莆田学院许振和
24
词法分析器的自动生成

正规式 正规文法 有穷自动机
见第3章 词法分析(二)
2012-12-5 莆田学院许振和
/ 处理注释和除 号hand_com() 除 号 Y Y
其它特殊符号 识别界符 recog_del()
在界符表中? isdelimete(s) N 出错处理 error()
Y
插入token表
2012-12-5
ins_token(s,token) 莆田学院许振和
19

识别单词前作如下假定：

关键字就是保留字

第三章 词语分析释义法

第三章 词语分析释义法
第三章 词语分析释义法
2011.9.27
词语分析释义法
• 词语分析释义法 根据造词法、构词法、义素构成法、 理据及构形法进行词义说明的方法。 • 词语分析释义法的必要性 词语分析释义法是中高级学习阶段学 生有效识记词汇的必备途径，也符合汉语 词汇的特点。 • 词语分析释义法的前提 词语的理据性、可分析性、规律性。
义素分析释义法的作用
一、说明词义聚合关系：
可以显示同义关系： 边疆：+[国土]+[靠近国界]+[范围大] 边境：+[国土]+[靠近国界]－[范围大] 可以显示反义关系： 朋友：+[人]+[友好] 敌人：+[人]－[友好] 浑浊：+[水]+[杂质] 清澈：+[水]－[杂质] 可以显示类义关系： 教授：+[高等学校职称]+[最高级别] 副教授：+[高等学校职称]－[最高级别]+[次高级别] 讲师：+[高等学校职称]－[最高级别]－[次高级别]+[次低级别] 助教：+[高等学校职称]－[最高级别]－[次高级别]－[次低级别]+[最低级别
作业
• 重叠词、叠音词二者及重叠构形、叠音构词、 重叠构词三者的区别？
半音译半意译： 席梦思 乌托邦 霓虹灯 马克思主义 绿 卡 新西兰 音译+语素： 摩托车 呼拉圈 艾滋病 迷你裙 吉普车 沙丁鱼 卡片 啤酒 音译兼意译： 可口可乐 奔驰 休克 维他命 香波 字母词： OK WTO UFO WIN98 VCD EMAIL FAX MBA SOS AA制 BP机 KTV包房 IC卡 X光
第二节 构词分析释义法
（三）音译外来词 克隆 咖啡 咖啡 沙发 布丁 拷贝 沙龙 吉他 白兰地 迪斯科 海洛因 华尔兹 荷尔蒙 比基尼 马拉松 高尔夫 三明治

Chapt3_词法分析

Chapt3_词法分析

由于部分单分界符与双分界符或注释的首字符相同， 如>、<、=、*和/，所以这些单分界符要在双分界符或 注释中处理。
TEST语言的各条词法规则的状态图
a,b,…,Z,0,1,…,9
S
a,b,…,Z
identifier
0,1,…,9
S S
0,1,…,9
number
+、-、…、；
singleword =
V→Z0|0
画出该文法对应的状态图。
S
0
1
U
1 0
V
1 0
Z
3.3 正则文法及状态图
例3-1 设有正则文法G[Z]： Z→U0|V1 U→Z1|1 利用正则文法来分析符号 串。 例如：分析符号串1001是不 是文法G[Z]的合法句子？ 用文法的产生式来推导：
: if、else、for、while、
注释符：用/*….*/括起
TEST语言的词法规则
<identifier>∷= <letter> | < identifier > <letter> | <identifier><digit> <number>∷= <digit> | <number> <digit> <letter>∷= a | b | … | z | A | B | … | Z <digit>∷= 1 | 2 | … | 9 | 0 <singleword>∷= + | - | * | / | = |（|）|{|}|：|，|；|＜|＞|! <doubleword>∷=＞= |＜= |!= |= = <commend_first>∷= /* <commend_last>∷= */

第3章词法分析

第3章词法分析

例：语言L[G]={abn|n>=1},其正规文 语言L[G]={ab |n>=1},其正规文 法为G[A]： 法为G[A]： A→aB A→aB B→bB| B→bB| b 画出状态转换图
例：部分单词的状态图
Letter,digit
s
letter digit
其它 （IDN，入口） ，入口） digit 其它 （NUM，值） ， （ASG，_） ， ） =
3.2 状态转换图
•识别标识符的流程图 识别标识符的流程图 开始
出口 N N 数字 Y
字母 N 出口
Y
取字符
字母 Y
结点：状态用○表示；终态用◎表示 结点：状态用○表示；终态用◎ 有向弧 弧标记 初态 开始 1 letter 2 ── 箭头 ── 输入字符 Letter,d号的表示
• 常用单词种别 常用单词种别——分类 分类
–各关键字（保留字、基本字） 各关键字（保留字、基本字） 各关键字 –各种运算符 各种运算符 –各种分界符 各种分界符——各用一个种别码标识（特定符号类） 各用一个种别码标识（ 各种分界符 各用一个种别码标识 特定符号类） –其它标识符 其它标识符——用一个种别码标示（非特定符号类） 用一个种别码标示（ 其它标识符 用一个种别码标示 非特定符号类） –常数 常数——用一个种别码标示（非特定符号类） 用一个种别码标示（ 常数 用一个种别码标示 非特定符号类）
• 例：文法 文法G[Z]： ： • Z→ Z→Za| Aa| Bb • A→ A→Ba | a • B→ B→Ab| b • 画出状态转换图
2、从右线性正规文法出发，构造状态图 从右线性正规文法出发， 以每个非终结符为状态结点， 1. 以每个非终结符为状态结点 ， 开始符号 对应初态S 对应初态S ； 2.增设一个终态 Z； 3. 对于规则 A→aB ， 画从状态 A 到 B 的 A→aB， 弧，标为 a； A→a， 4. 对于规则 A→a ， 画从状态 A 到终态 Z 的弧， 的弧，标为 a。

编译原理-第3章 词法分析--习题答案

编译原理-第3章 词法分析--习题答案

第3章词法分析习题答案1．判断下面的陈述是否正确。

（1）有穷自动机接受的语言是正规语言。

(√)（2）若r1和r2是Σ上的正规式，则r1|r2也是Σ上的正规式。

(√)（3）设M是一个NFA，并且L(M)={x,y,z}，则M的状态数至少为4个。

(× )（4）设Σ={a,b}，则Σ上所有以b为首的符号串构成的正规集的正规式为b*(a|b)*。

(× )（5）对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。

(√)（6）对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。

(√) （7）一个DFA，可以通过多条路识别一个符号串。

(× )（8）一个NFA，可以通过多条路识别一个符号串。

(√)（9）如果一个有穷自动机可以接受空符号串，则它的状态图一定含有 边。

(× )（10）DFA具有翻译单词的能力。

(× )2.指与出正规式匹配的串.（1)(ab|b)*c 与后面的那些串匹配？ababbc abab c babc aaabc（2）ab*c*(a|b)c 与后面的那些串匹配？ acac acbbc abbcac abc acc（3）(a|b)a*(ba)* 与后面的那些串匹配? ba bba aa baa ababa答案（1) ababbc c babc（2) acac abbcac abc（3) ba bba aa baa ababa3. 为下边所描述的串写正规式，字母表是{0, 1}.（1)以01 结尾的所有串（2)只包含一个0的所有串（3) 包含偶数个1但不含0的所有串（4)包含偶数个1且含任意数目0的所有串（5)包含01子串的所有串（6)不包含01子串的所有串答案注意 正规式不唯一（1)(0|1)*01（2)1*01*（3)(11)*（4)(0*10*10*)*（5)(0|1)*01(0|1)*（6)1*0*4.请描述下面正规式定义的串. 字母表{x, y}.（1) x(x|y)*x（2)x*(yx)*x*（3) (x|y)*(xx|yy) (x|y)*答案（1)必须以 x 开头和x结尾的串（2)每个 y 至少有一个 x 跟在后边的串 （3)所有含两个相继的x或两个相继的y的串5．处于/* 和 */之间的串构成注解，注解中间没有*/。

第3章编译原理答案(主编张晶)

第3章编译原理答案(主编张晶)

others *
1/
2*
3* 4/ others
5
others others
all
6 all
others *
1/
2*
3* 4/ others
5
状态1：注释开始状态。 状态2：进入注释体前的中间状态。 状态3：表明目前正在注释体中的状态。 状态4：离开注释前的中间状态。 状态5：注释结束状态，即接受状态。
（1）分析和识别单词及属性， 包括识别语言的关键字、标识符、常数、运算符等；
（2）跳过各种分隔符，如空格，回车，制表符等； （3）删除注释； （4）进行词法检查，报告所发现的错误； （5）建立符号表。
main( )/*ADD*/ {int x=10,y=20,sum; sum=x+y; }
词法分析
正则表达式也是描述单词的重要工具。
【例2】设Σ={a,b}
正规式 ba* a(a|b)* (a|b)*abb (a|b)*(aa|bb) (a|b)* (aa|ab|ba|bb) * (a|b)(a|b)(a|b) *
正规集 所有以b为首后跟任意多个a的符号串 所有以a为首的符号串 所有以abb为尾的a，b符号串 所有含有两个相继的a或相继的b的符号串 空串和任何长度为偶数的符号串 任何长度大于等于2的符号串
转换
正规文法
main、(、)、{、int、 x、=、10、,、y、=、 20、,、sum、;、sum、 =、x、+、y、;、}
词法分析程序的设计与实现？
词法规则
状态图
词法分析程序
为识别单词而专门设计的有向图， 是设计词法分析程序的一种好途径。
（1）根据词法规则写出正规文法； （2）将正规文法转换成状态图； （3）将状态图转换成流程图。

编译原理第二版第3章词法分析

编译原理第二版第3章词法分析
一、正规式与正规集的递归定义
1. ε和φ都是∑上的正规式，它所表示的正规集分
别为｛ε｝和Ф； 2. 任何ａ∈∑，ａ是∑上的正规式，它所表示的正 规集为｛ａ｝； 3. 假定ｅ1和ｅ2都是∑上的正规式，他们所表示的 正规集分别为Ｌ(ｅ1)和Ｌ(ｅ2)，那么，以下也 都是正规式和他们所表示的正规集；
一、正规式与正规集的递归定义
3.2 单词符号及输出单词的形式
单词自身值
对常数，基本字，运算符，界符就是他们本 身的值 对标识符，将标识符的名字登记在符号表中， ‚自身值‛是指向该标识符所在符号表中位 置的指针。
假定基本字、运算符和界符都是一符一种 例：if(a>1) b=100; 词法分析后输出的单词序列是: (2, ) if (29, ) ( (10,‘a’) a (23, ) > (11,‘1’) 1 (30, ) ) (10,’b’) b (17, ) = (11,‘100’) 100 (26, ) ;
4. 仅由有限次使用上述三步定义的表达式才是∑上的 正规式，仅由这些正规式所表示的字集才是∑上 的正规集。
重点回顾
四、将正规文法转换成正规式 求非终结符的正规式 将正规文法中的每个非终结符表示成关 于它的一个正规式方程，获得一个联立 方程组 用代入法解正规式方程组 最后只剩下一个开始符号定义的正规式, 其中不含非终结符
3.3 语言单词符号的两种定义方式
作用: 描述单词的构成规则,基于这类描 述工具建立词法分析技术,进而实现词法 分析程序的自动构造。 工具有: 正规文法 正规式(Regular Expression)
多数程序设计语言的单词符号都能用正 规文法或正规式来定义。
3.3.1 正规文法
多数程序设计语言单词的语法都能用正 规文法(3型文法)描述 正规文法回顾 文法的任一产生式α →β 的形式都为 A→aB或A→a，其中A ，B∈VN ，a∈VT A→Ba或A→a，其中A ，B∈VN ，a∈ VT 正规文法描述的是VT*上的正规集

03第3章 词法分析1

03第3章 词法分析1
正则表达式的部分操作符满足结合律、交换律和分配律: 即 (ab)c=a(bc) (a|b)|c=a(b|c) a|b=b|a a(b|c)=ab|ac 注意：连接不满足交换律，即ab≠ba
3.5.2 正则文法与正则表达式的等价性
正则文法与正则表达式有等价性，即可以将正则文法转换成正则 表达式。 例如，用正则文法表示标识符的文法规则如下： ＜标识符＞∷= a|b|…|z |＜标识符＞a|＜标识符＞b|…|＜标识符＞z |＜标识符＞0|＜标识符＞1|…|＜标识符＞9 而采用正则表达式则为： ＜标识符＞= (a|b|c|…|z){a|b|…|z|0|1|…|9} 或简写成 ＜标识符＞=字母{字母|数字} 由此可见，正则表达式在描述语言时比正则文法更为简洁 由此可见，正则表达式在描述语言时比正则文法更为简洁。
3.5.1 正则表达式定义
3.5.1 正则表达式定义
在正则表达式的运算符中，重复优先级高于连接，而连接高于 选择，因此，(p) | ((p) . (q))可写成p | pq , 但表达式(p|q).r中的括 号则不能去掉。 例3.5，设字母表∑={a,b}，则a,b, Φ和ε都是∑上的正则表达式， 所描述的语言为{a}、{b}、{}、{ε}，求表达式{a}{b}、{a|b} {aa|ab|ba|bb} 和{aa|ab|ba|bb}定义的语言。 解：根据正则表达式的形式定义，可得如下结果： 表达式{a}{b}定义的语言为：{ambn|m≥0,n≥0}， 表达式{a|b}定义的语言为：{x|x ∈{a,b}*}，即字母a或b组成的 任意长度字符串。 而表达式{aa|ab|ba|bb}表示的语言由字母a或b组成的所有偶长 度字符串。
3.5.2 正则文法与正则表达式的等价性
例3.7，有正则文法如下，将其换成 等价的正则表达式。 S → aS S →aB B →bC C →aC C →a 解： 先用元符号“{”和“}”将文法改 写成如下： S={a}aB B =bC C = {a}a 然后按解方程组的方法可得： C={a}a B= b{a}a S={a}ab{a}a 最终转成正则表达式 S={a}ab{a}a 可以验证，它表示的语言与原来 的正则文法描述的语言相同。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(b) (r)(s) 是一个正则表达式，表示语言L(r) L(s) (c) (r)* 是一个正则表达式，表示语言 (L(r))* (d) (r) 是一个正则表达式，表示语言 L(r)
所有的运算符都是左结合的。.
23
正则式 定义的语言 {} a {a } (r) | ( s) L(r)∪L(s) (r)(s) L(r) L(s) (r)* (L(r))* (r) L(r) ((a) (b)*)| (c)可以写成ab*| c
5
3.1.1 词法分析与句法分析分开的原因
简化编译器的设计，让句法分析器简单化。 提高编译效率：使用适合词法分析的专门技术。 增强编译器的可移植性：输入设备相关的特殊性可 以被限制在词法分析器中。
6
3.1.2 词法单元、模式、词素
词法单元(token)：一个词法单元名和一个可选的 属性值组成。用<token name, token value>表示。 它是源语言文法的终结符。
26
正则表达式的代数性质
(rs)* ≠ r*s* 定义
为了让正则表达式的表示简洁，可以对正则式命名。 d1 r1 d2 r2 ... dn rn 各个di的名字都不同, di 每个ri都是∪{d1, d2, …, di-1 }上的正则式
备注
a r和s是正则式 r和s是正则式 r是正则式 r是正则式
都是左结合的。优先级从高到低：*，连接，|
24
letter_ {a,b,..z,A,B,…Z,0,1,…9, _ }
letter_ (letter_ | digit )*
正则表达式的例子( = {a, b})
正则表达式 正则集合（regular set ) a|b {a, b} ( a | b) ( a | b ) {aa, ab, ba, bb} aa | ab | ba | bb {aa, ab, ba, bb} a* 由0个或多个a构成的所有字符串集合 ( a | b) * 由a和b构成的所有字符串集合 …… a | a*b 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 偶数个０和偶数个１组成的01字符串
#define ID 600
11
3.1.4 词法错误
词法分析器对源程序采取非常局部的观点 难以发现下面的错误 fi (a == f (x) ) … 在实数是a.b格式下，可以发现下面的错误 123. 此时，使用“恐慌模式”的错误恢复 错误修补
12
3.2 词素的描述
正则表达式是模式的重要表示方法。
7
例子
C语言语句： printf(“total=%d”, score); <id, printf> #define ID_TOKEN 300 <(, > #define IF_TOKEN 400 #define FOR_TOKEN 500 <literal, “total=%d”> …… struct Token { <,, > int TokenName; <id, score> union { int IntValue; <), > double DblValue; <;, > IdItem * ptr;
14
字符串例子及术语
串banana
前缀Prefix : 从s的尾部删除0个或多个符号后得到的串，
例如：, b, ba, ban, bana, banan, banana
后缀Suffix : , a, na, ana, nana, anana, banana 子串(Substring) : , b, a, n,…, ba, an, na, …, ban, ana, nan,…, bana, anan,nana, banan, anana, banana 子序列(Subsequence): bnan, nn 真前缀Proper prefix： b, ba, ban, bana, banan, 真后缀Proper suffix： a, na, ana, nana, anana
…… } Attribute;
};
8
词法单元的例子
词法单元名 const for relation id num literal 词素例举 const for <,<=,=,… sum, count, D5 3.1, 10, 2.8E12 “hello” 模式的非形式描述 const for < 或 <= 或 = 或 … 由字母或下划线开头的字母数字串 任何数值常数 双引号之间的任意字符 串，但双引号本身除外
21
3.2.3 正则表达式
例如，C语言的标识符集可以定义为： letter_ (letter_ | digit )* 其中 letter_ { a,b,…z, A,B,…,Z, _ } 正则式(Regular Expression)可以用来表示简单的语 言，叫做正则集（regular set）。
28
正则定义的例子1
C语言的标识符集合 letter_ A | B | … | Z | a | b | … | z | _ digit 0 | 1 | … | 9 id letter_ ( letter_ | digit)*
i 0 i
L的0个或多个连接, {} L LLLLL … i += L L’ = L L的正闭包( positive i 1 closure) L的一个或多个连接, L LL LLL …
19
语言的运算
例如：L={a,b}, M={cc,dd} 和： L∪M = {s | s L 或 s M } 例如： L∪M ={ a, b, cc, dd } 连接： LM = {st | s L 且 t M} 例如： LM = { acc, add, bcc, bdd } 指数： L0 ={ }，Li = Li -1L 例如： L1=L, L2=LL={aa,ab,ba,bb} L3={aaa, aab, aba, abb, baa, bab, bba, bbb} 闭包： L = L0 ∪ L1 ∪ L2 ∪… Kleene闭包 正闭包： L+ = L1 ∪ L2 ∪…
15
语言(Language)
可枚举
语言(Language)：某个给定字母表上一个任意可数 的字符串集合。 Special Languages: and {}
16
语言的例子
字符集 {0,1} 语言 {1,10,100,1000,100000…} {0,1,00,11,000,111,…} {a,b,c} {abc,aabbcc,aaabbbccc,…} {A, … ,Z} {TEE,FORE,BALL,…} {FOR,WHILE,GOTO,…} {A,…,Z,a,…,z,0,…9, { 所有合法的C语言程序} +,-,…,<,>,…} { 所有语法正确的英语句子}
9
词法单元的例子
下列结构作为词法单元token：关键字、操作符、 标识符、常量、字符串、标点符号 每个关键字对应一个词法单元（token） 表示多个运算符的词法单元tokens 一个表示所有标识符的词法单元 一个或多个表示常量的词法单元，比如数字和 字符串 每一个标点符号有一个词法单元，比如左右括 号、逗号和分号。
模式(pattern)：源语言中特定记号的构成规则， 可以用正则表达式示。(例如：变量名的命名规则） 词素（lexeme)：是源程序中的一个字符序列，它 和某个词法单元的模式匹配，并被词法分析器识别 为该词法单元的一个实例。
Lexeme ['lɛksim]
if ( count > 5 ) sum += count ;
第三章 词法分析
1
本章内容
词法分析器：将源程序的字符流翻译成记号流，以 及用户接口等任务 构造词法分析器 手工 自动生成 重点 正则表达式 有限状态自动机 自动生成工具：Lex/Flex
2
3.1 词法分析器的作用
记号 源程序 词法分析器 语法分析器
取下一个记号 符号表
25
正则表达式的代数性质
AXIOM r|s=s|r r | ( s | t ) = ( r | s) | t ( r s) t = r ( s t ) r(s|t)=rs|rt (s|t)r=sr|tr r=r r=r r* = ( r | )* r** = r* DESCRIPTION | 是可交换的 | 是可结合的 “连接”是可结合的 “连接”是可分配的 是“连接”的单位元 * 和 之间的关系 * 的幂等性
17
串的运算
xy 例如：x=ab y==cd, xy=abcd s = s = s 乘积（指数） 定义s0为，si为si-1s（i > 0） s1=s, s2=ss, s3=sss,… 例如，s=ab, s1=ab, s2=abab, s3=ababab 连接
18
Kleene ，星号，德语称 Kleensche Hülle
13
3.2.1 串和语言
字母表：有限符号的集合. 例： = {0,1}，{a,b},{a,b,„,z,A,B,„,Z} 字符串：符号的有穷序列，例：0110, 字符串s的长度：出现在s中符号的个数，记作|s| 空串：长度为０的符号串，用表示 语言：给定字母表上的任意一个字符串集合 {,0,00,000,…}, {, a,b,aa,ab,ba,bb,…}, {}, 句子：属于语言的字符串。 本书中句子、字符串基本表达同一个意思。
22
定义字母表上的正则表达式的规则
1. 是一个正则表达式，L()= { }
2. 如果a是上的一个符号,那么a是一个正则表达式，并且L(a)= {a} 3. 假设 r和s都是正则表达式，分别表示语言 L(r) and L(s)，那么