当前位置：文档之家 › 编译原理-第3章-词法分析

编译原理-第3章-词法分析

  • 格式：pptx
  • 大小：597.59 KB
  • 文档页数：76

下载文档原格式

  / 76

合集下载

编译原理词法分析与语法分析的核心算法

编译原理词法分析与语法分析的核心算法

编译原理词法分析与语法分析的核心算法编译原理是计算机科学与技术领域中的一门重要课程。

在编程中，我们常常需要将高级语言编写的程序翻译成机器语言，使计算机能够理解并执行我们编写的程序。

而编译原理中的词法分析和语法分析是编译器的两个核心算法。

一、词法分析词法分析是编译器的第一个阶段，它负责将输入的字符序列（源代码）划分为一个个的有意义的词素（Token），并生成相应的词法单元（Lexeme）。

词法分析的核心算法主要包括以下两个步骤：1. 正则表达式到有限自动机的转换：正则表达式是一种描述字符串匹配模式的表达式，它可以用来描述词法分析中各种词素的规则。

而有限自动机则是一种用来识别或匹配正则表达式所描述的模式的计算模型。

将正则表达式转换为有限自动机是词法分析的关键步骤之一。

2. 词法分析器的生成：在将正则表达式转换为有限自动机后，我们可以使用生成器工具（如Lex、Flex等）来生成词法分析器。

词法分析器可以按照预定的规则扫描源代码，并将识别出的词素转换成相应的词法单元，供后续的语法分析使用。

二、语法分析语法分析是编译器的第二个阶段，它负责分析和处理词法分析阶段生成的词法单元序列，并根据预定的语法规则确定语法正确的序列。

语法分析的核心算法主要包括以下两个步骤：1. 上下文无关文法的定义：上下文无关文法（Context-Free Grammar，简称CFG）是一种用于描述形式语言的文法。

它由一组产生式和终结符号组成，可以用于描述语法分析中的语法规则。

在语法分析中，我们需要根据具体编程语言的语法规则，编写相应的上下文无关文法。

2. 语法分析器的生成：通过使用生成器工具（如Yacc、Bison等），我们可以根据上下文无关文法生成语法分析器。

语法分析器可以根据预先定义的文法规则，对词法单元序列进行分析，并构建出语法树（Parse Tree）供后续的语义分析和代码生成使用。

综上所述，词法分析与语法分析是编译原理中的两个重要阶段，也是实现编译器的核心算法。

北航编译原理课件 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.S是一个有穷集，它的每个元素称为一个状态；
2.Σ是一个有穷字母表，它的每个元素称为一个输入 符号，所以也称Σ为输入符号表；
3.δ是在S×Σ→S上的单值映射，即，如δ (s，a)=s’， (s∈S，s’∈S)就意味着，当前状态为s，输入符为 a时，将转换为下一个状态s’，我们把s’称作s的一 个后继状态；
编译原理 在 入 准初带备整•••始的读输读有个时开入始入头穷模，始，状带：控型读位状态：可制由头置态存以器如状的所三处，处放在：果态符识部于表于输输控读正号别分输示初入入制头好组组符带状移是成成号上态动终的：向发到结字后生最状能移变后态被头每有动化一，该转向读穷个则有移后入控符输限到移一 制号入自下动个器后带动一一符控面上机个个号制，状位，状态置读态，
编译原理
词法分析 读字符
结束 Y
结束
N Y 空字
N 字母 N 数字
Y 组合标识符 Y 组合整数
查保留字Βιβλιοθήκη N 纯单分符Y 输出单分符
N
>,<,!,= Y 读字符
=
N
N
/ Y 读字符
*
N
Y
错误处理
输出保留字
Y 保留字
N 输出标识符
组合整数
读字符
Y 输出双分符
输出单分符 N 输出单分符/
注释处理
读字符
03-第3章-语法分析-编译原理-中国科技大学(共13讲)

03-第3章-语法分析-编译原理-中国科技大学(共13讲)

VT : VN : S: P : 终结符集合 非终结符集合 开始符号，非终结符中的一个 产生式集合， 产生式形式 : A expr (expr) expr id op
• 例 ( {id, +, , , (, )}, {expr, op}, expr, P )
expr expr op expr expr expr op +
3.2 语言和文法
• 无二义的文法 stmt matched _stmt | unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt
3.2 语言和文法
expr expr + term | term term term factor | factor factor id | (expr)
expr term
term expr factor id term factor id expr + term * factor id id + id id 分析树
3.2 语言和文法
3.2.3 验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合 • 按串长进行归纳：配对括号串可由S推出
–归纳基础： S – 归纳假设：长度小于2n的都可以从S推导出来 – 归纳步骤：考虑长度为2n(n 1)的w = (x) y S (S)S * (x) S * (x) y
编译原理和技术
中国科学技术大学 计算机科学与技术学院 陈意云
词法分析-编译原理-03-(二)

词法分析-编译原理-03-(二)


5. 5.1 5.2 5.3 5.4 5.5 5.6 5.7 6 6.1 6.2
isalpha(ch) : ch→buf; 下一字符→ch WHILE isalpha(ch) OR isdigit(ch) DO ch→buf; 下一字符→ch 回送 ch; key = isKeyword(buf) IF key >= 0 THEN 返回 key Lookup( buf ) → attr 返回 IDN ':' : 下一字符→ch; IF ch等于'=' THEN 返回 ASG 出错处理
第三章 词法分析 3.1 词法分析的任务
输入源程序，输出单词符号
把构成源程序的字符串转换成语义
上关联的单词符号的序列
单词符号
token
按照最小的语义单位设计， 通常表示为二元组
（单词种别，属性值）
1) 单词符号的表示
单词种别
通常按照语法分析的需要设置． 常用： 各关键字，标识符，常数，各
例3-3 状态图的实现算法
1. 2. 3.1 3. 4. 4.1 4.2 4.3 4.4 4.5 读入当前字符 ch //跳过空格 WHILE ch 是空格 DO 下一字符 → ch CASE ch OF isdigit(ch) : ch→buf; 下一字符→ch WHILE isdigit(ch) DO ch→buf; 下一字符→ch 回送 ch 将缓冲区的数字字符串变成数字→attr 返回 NUM
7 8 9 10 11 12 13 14 15 16 17 18
'+' : 返回 ADD '-' : 返回 SUB '*' : 返回 MUL '/' : 返回 DIV '=' : 返回 EQ '>' : 返回 GT '<' : 返回 LT '(' : 返回 LP ')' : 返回 RP ';' : 返回 SEMI 其它 : 出错处理 END OF CASE
编译原理中的词法分析与语法分析原理解析

编译原理中的词法分析与语法分析原理解析

编译原理中的词法分析与语法分析原理解析编译原理是计算机科学中的重要课程，它研究的是如何将源程序翻译成目标程序的过程。

而词法分析和语法分析则是编译过程中的两个重要阶段，它们负责将源程序转换成抽象语法树，为接下来的语义分析和代码生成阶段做准备。

本文将从词法分析和语法分析的原理、方法和实现技术角度进行详细解析，以期对读者有所帮助。

一、词法分析的原理1.词法分析的定义词法分析（Lexical Analysis）是编译过程中的第一个阶段，它负责将源程序中的字符流转换成标记流的过程。

源程序中的字符流是没有结构的，而编程语言是有一定结构的，因此需要通过词法分析将源程序中的字符流转换成有意义的标记流，以便之后的语法分析和语义分析的进行。

在词法分析的过程中，会将源程序中的字符划分成一系列的标记（Token），每个标记都包含了一定的语义信息，比如关键字、标识符、常量等等。

2.词法分析的原理词法分析的原理主要是通过有限状态自动机（Finite State Automaton，FSA）来实现的。

有限状态自动机是一个数学模型，它描述了一个自动机可以处于的所有可能的状态以及状态之间的转移关系。

在词法分析过程中，会将源程序中的字符逐个读取，并根据当前的状态和字符的输入来确定下一个状态。

最终，当字符读取完毕时，自动机会处于某一状态，这个状态就代表了当前的标记。

3.词法分析的实现技术词法分析的实现技术主要有两种，一种是手工实现，另一种是使用词法分析器生成工具。

手工实现词法分析器的过程通常需要编写一系列的正则表达式来描述不同类型的标记，并通过有限状态自动机来实现这些正则表达式的匹配过程。

这个过程需要大量的人力和时间，而且容易出错。

而使用词法分析器生成工具则可以自动生成词法分析器的代码，开发者只需要定义好源程序中的各种标记，然后通过这些工具自动生成对应的词法分析器。

常见的词法分析器生成工具有Lex和Flex等。

二、语法分析的原理1.语法分析的定义语法分析（Syntax Analysis）是编译过程中的第二个阶段，它负责将词法分析得到的标记流转换成抽象语法树的过程。

编译原理词法分析和语法分析

编译原理词法分析和语法分析

if(ch=='=')
{ syn=21;
token[m++]=ch;
}
else
{ syn=31;
p--;
}
break;
case '=':token[m++]=ch;
ch=prog[p++];
if(ch=='=')
{ syn=25;
token[m++]=ch;
}
else
{ syn=18;
p--;
}
break;
break;
case -1:printf("you have input a wrong string\n");
getch();
exit(0);
default: printf("( %-10s%5d )\n",token,syn);
break;
}
}while(syn!=0);
getch();
}
scaner()
printf("success!\n");
}
else { if(kk!=1) printf("the string haven't got a 'end'!\n");
kk=1;
}
}
else { printf("haven't got a 'begin'!\n");
kk=1;
}
return;
}
yucu()
if(syn==18)
{ scaner();/*读下一个单词符号*/
编译原理-词法分析

编译原理-词法分析

编译原理-词法分析
词法分析是编译原理中的重要阶段，负责将源代码分解为词法单元，为后续 的语法分析准备输入。
词法分析的定义和作用
词法分析是编译器的第一阶段，其主要目的是将源代码转换为有意义的词法 单元，如标识符、关键字、操作符等，以便后续的语法分析和语义分析使用。
词法分析的流程
1
扫描
将源代码分割为符号序列。
2
识别
将符号序列映射到相应的词法单元。

归类
将词法单元分为不同的类别，如标识符、关键字、操作符等。
常见的词法分析技术
正则表达式
用于描述词法单元的模式。
有限自动机
用于识别符号序列并生成词法 单元。
词法分析器生成器
自动生成词法分析器的工具。
词法分析的应用场景
词法分析广泛应用于编译器、解释器和语言处理工具等领域，确保源代码的正确解析和语义分析。
词法分析的挑战和解决方案
错误处理
如何处理错误输入和不合法的词法 单元。
性能优化
如何提高词法分析的速度和效率。
跨平台兼容
如何处理不同编程语言和操作系统 的词法规则。
结论和总结
词法分析是编译原理中不可或缺的一部分，对于编译器的正确性和性能有着 重要影响。了解词法分析的流程和技术，可帮助开发者构建更高效的编译器 和语言处理工具。
编译原理 第3章 词法分析与有穷自动机(第5-8讲)

编译原理 第3章 词法分析与有穷自动机(第5-8讲)


它所对应的状态表如图：
状态 0 1 2 3 a 1 3 1 3 后继 状态 b 2 2 3 3
输入字符 接受 否 否 否 是
式的转化
22
第3章 词法分析与有穷自动机
■DFA所识别的语言
给定DFA M，对于字符c1,c2,…,cn,当以下条件成立时， 称M接受由c1,c2,…,cn组成的字符串c1c2…cn： 存在状态序列s0,s1,s2,…,sn,使得s1=f(S,c1), s2=f(s1,c2),…,sn=f(sn-1,cn)，且sn∈Z。 由DFA M接受的语言L(M)是所有M接受的字符串组成的集 合。
25
第3章 词法分析与有穷自动机
判断下图是DFA还是NFA的状态转换图，并 写出其他2种表示形式
26
第3章 词法分析与有穷自动机
■由正规表达式R构造NFA
1.基本正规表达式 (a)对于正规式φ,所构造NFA: (b)对于正规式ε,所构造NFA: (c)对于正规式a,a∈Σ,则 NFA:
x ε y
练习：若S=a|bb，则L((a|bb)*)=？
5
第3章 词法分析与有穷自动机
■正规式中运算的优先级
括号优先，* 次之，•（连接）再次之，| 最后 例：a|bc* ≌ a|(b(c*)) ab|c*d ≌ (ab)|((c*)d)
■ 正规式与正规集举例
L(a|bc*)=L(a)∪L(bc*) 思考：L(ab|c*d)=？ =L(a)∪L(b)L(c*) =L(a)∪L(b)(L(c))* ={a}∪{b}{ε,c,cc,ccc……} ={a,b,bc,bcc,bccc,……}
17
第3章 词法分析与有穷自动机
■有穷自动机的状态转移图表示方法
编译原理第三章(4-2)

编译原理第三章(4-2)

北京交通大学 于双元 15
无符号数一般形式：dm dm-1 · · · d1 d0 ·d-1 d-2 · · ·d-nE+ dd · · · d E d 0 d . 3 d 1 d d E 4 d 5 d d 6
.
d
2
+∣d
. d d
d
d
F
北京交通大学 于双元 16
无符号数一般形式：dm dm-1 · · · d1 d0 ·d-1 d-2 · · ·d-nE+ dd · · · d E d 0 d . 3 d 1 d d E 4 d 5 d d 6
A B
②开始符号S作为初始状态 设一符号F不属于V作为终止状态
S
F B F F
③形如A→aB的规则
④形如A→a的规则 特别:A → ε
A A
a a
A 未曾在A的射出弧中 出现过的终结符号
北京交通大学 于双元
也可以消除ε产生式后再画状态图。
4
例:G[Z]: Z→0U∣1V U →1Z∣1 V →0Z∣0
1 初态
0 Z 1
U
1 0
F
0
V
②此过程是一种推导过程. （最右（左）推导）
相当于: Z=>0U =>01Z =>011V =>0110Z =>01100U =>011001
能否编程序实现？
有什么问题？
北京交通大学 于双元
8
3 、左线性文法的状态图
左线性文法的规则呈: A→Ba或A→a A,B∈Vn ，a∈Vt （1）状态图 ①G[S]的每一个非终结符号代表一结点(状态) A B
北京交通大学 于双元
23
3、设有如下状态转换图，试给出对应的正则文法 （左线性和右线性）。

编译原理作业集-第三章-修订版

编译原理作业集-第三章-修订版第三章词法分析本章要点１．词法分析器设计，２．正规表达式与有限⾃动机，３．词法分析器⾃动⽣成。

本章⽬标：１．理解对词法分析器的任务，掌握词法分析器的设计；２．掌握正规表达式与有限⾃动机；３．掌握词法分析器的⾃动产⽣。

本章重点：1．词法分析器的作⽤和接⼝，⽤⾼级语⾔编写词法分析器等内容，它们与词法分析器的实现有关。

应重点掌握词法分析器的任务与设计，状态转换图等内容。

2．掌握下⾯涉及的⼀些概念，它们之间转换的技巧、⽅法或算法。

（1）⾮形式描述的语⾔?正规式（2）正规式→ NFA（⾮确定的有限⾃动机）（3）NFA → DFA（确定的有限⾃动机）（4）DFA →最简DFA本章难点（1）⾮形式描述的语⾔?正规式（2）正规式→ NFA（⾮确定的有限⾃动机）（3）NFA → DFA（确定的有限⾃动机）（4）DFA →最简DFA作业题⼀、单项选择题（按照组卷⽅案，⾄少15道）1. 程序语⾔下⾯的单词符号中，⼀般不需要超前搜索a. 关键字b. 标识符c. 常数d. 算符和界符2. 在状态转换图的实现中，⼀般对应⼀个循环语句a. 不含回路的分叉结点b. 含回路的状态结点c. 终态结点d. 都不是3. ⽤了表⽰字母，d表⽰数字， ={l，d}，则定义标识符的正则表达式可以是：。

(a)ld*(b)ll*(c)l(l | d)*(d)ll* | d*4. 正规表达式(ε|a|b)2表⽰的集合是(a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb}(c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba}5. 有限状态⾃动机可⽤五元组（V T，Q，δ，q0，Q f）来描述，设有⼀有限状态⾃动机M的定义如下：V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为：δ（q0，0）=q1δ（q1，0）=q2δ（q2，1）=q2δ（q2，0）=q2M所对应的状态转换图为。

编译原理

S中有些p与a对应，有些不对应。
13
3.9直接从正则式到DFA

构造算法
实例 例3.37
得到的DFA状态比通过NFA得到的DFA状态少！
14
3.10 DFA最简化（3.9.6-3.9.7）

DFA最简化原理
最简DFA唯一性：每一个正则式可以由一个状态数最少
的DFA识别，且这个DFA唯一。 可行性：DFA存在不可区别状态，可以合并。 化简条件：确保DFA是全函数
8
3.9直接从正则式到DFA

构造原理
转换表：聚焦重要状态之间的转移 开始状态：可能出现在给定正则表达式描述的语言中任
何一个串第一个符号位置的所有重要状态。 接受状态：和结尾#相关的位置
9
3.9直接从正则式到DFA

构造算法
定义四个函数：nullable、firstpos、lastpos、
C b a B a b
开始
A
a
b
a
D
19
例 题 1

叙述下面的正则式描述的语言，并画出接受该语言 的最简DFA的状态转换图 (1|01)* 0*
描述的语言：所有不含子串001的0和1的串
1 0
1
.
start 1 刚读过的不是0 0 2 连续读过一个0 0 3 连续读过 不少于两个0
20
例 题 2
编译原理
第三章 词法分析
1
计算机科学与技术学院
3.8词法分析器生成工具的设计

词法分析器模型 图3.49
词法分析器工作方式
DFA模拟器 图3.27
NFA模拟器 图3.27
DFA转换表
NFA转换表

计算机编译原理


本课程的目的
构造编译器基本知识
编译的阶段和相关的活动 相关数据结构和算法
计算机科学中相关的基础理论
形式语言与自动机
进一步加深对软件开发的认识
第一章 概述
【课前思考】 ◇ 什么是编译程序？ ◇ 编译过程和编译程序的结构？ 【学习目标】 介绍语言翻译的基本概念
程序和语言 翻译和解释
介绍翻译的步骤和相关的活动 介绍编译器的开发方法
输入字符串（即源程序） 输出单词符号（最基本的语法单位） 。
词法分析举例
一个C源程序片段：
int a; a=a+2; 词法分析后返回(如右 图)：
单词类型 保留字 标识符 界符 标识符 算符(赋值) 标识符 算符(加) 整数 界符 单词值 int a ; a = a + 2 ；
(2) 语法分析（Syntax analysis）
程序的执行方式
高级语言程序通常采用两种方式执行：解释方 式和翻译方式 解释方式：逐个语句地分析和执行，如Basic， Prolog
优点：易于查错 缺点：效率低，运行速度慢
翻译方式：对整个程序进行分析，翻译成等价 机器语言程序后执行，如Pascal，Fortran，C
优点：只需分析和翻译一次， 缺点：在运行中发现的错误必须在源程序中查找
编译程序的功能
从功能上看，一个 编译程序就是一个 语言翻译程序。 源语言通常是一个 高级语言，如 FORTRAN，C 或 Pascal。 目标语言通常是一 个低级语言,如汇编 或机器语言。
出错和警告信息
编译程序
源语言程序
目标语言程序
T形图
常用T形图来表示编译程序涉及的三个语言： S I 其中： S:源语言(程序)，Source language(program) O:目标语言(程序), target/object language(program) I:实现语言, implementation language O

编译原理-第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章词法分析

一、正规式与正规集的递归定义
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*上的正规集

编译原理第3章课后习题答案


Dtran[I,b] =ε-closure(move(I,b))= ε-closure（{5, 16}）=G DFA D 的转换表 Dtran NFA 状态 {0,1,2,4,7} {1,2,3,4,6,7,8} {1,2,4,5,6,7} {1,2,4,5,6,7,9} {1,2,4,5,6,7,10,11,12,13,15} {1,2,3,4,6,7,8,12,13,14,15,17,18} {1,2,4,5,6,7, 12,13,15,16,17,18} {1,2,4,5,6,7, 9,12,13,15,16,17,18} {1,2,4,5,6,7, 10,11,12,13,15,16,17,18} 可得 DFA 的如下状态转换图： DFA 状态 A B C D E F G H I a B B B B F F F F F b C D C E G H G I G
3.3.1 给出 3.2.2 中正则表达式所描述的语言的状态转换图。
(1)a( a|b )*a 的状态转换图如下：
（2）
ε
ε a
b
（3）
a
start 0
a a a
1 2
4
b a b
5
b b
3
6
7
（4）a*ba*ba*ba*
a b
a b
a b
a
3．6.3 使用算法 3.25 和 3.20 将下列正则表达式转换成 DFA： (1)
注：consonant 为除五元音外的小写字母，记号 ctnvowels 对应的定义即为题目要求的正则
定义。
(2) 所有由按字典顺序递增序排列的小写字组成的串。 a*b*……z* （3)注释，即/*和*/之间的串，且串中没有不在双引号（ “）中的*/。 head——>/* tail ——>*/ * * incomment->(~(*/)|“. ”) comment->head incomment tail （9）所有由 a 和 b 组成且不含有子串 abb 的串。 * * A->b (a︱ab)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
9
2014-7-6
3.1.3 源程序的输入缓冲与预处理(续)

输入缓冲区
正拼单词
单词开始指针
扫描指针
工作区 (token)
2014-7-6
10
3.1.3 源程序的输入缓冲与预处理(续)

双缓冲区问题__超前扫描导致的效率问题
: : :E: :=: :M: * C : * : * : 2 : eof : : : :
15
2014-7-6
3.2.2 正则表达式(续)—RE
定义3.1 设∑是一个字母表，则∑上的正则表达式及其所表示 的正则语言可递归地定义如下： ⑴ 是∑上的一个正则表达式，它表示空集； ⑵ ε是∑上的一个正则表达式，它表示语言{ε}； ⑶ 对于a(a∈∑)，a是∑上的一个正则表达式，它表示的正则 语言是{a}； ⑷ 假设r和s都是∑上的正则表达式，它们表示的语言分别为 L(r)和L(s)，则： ① (r)也是∑上的正则表达式，它表示的语言为L(r)； ② (r|s)也是∑上的正则表达式，它表示的语言为L(r)∪L(s)； ③ (r•s)也是∑上的正则表达式，它表示的语言为L(r)L(s)； ④ (r*)也是∑上的正则表达式，它表示的语言为(L(r))*； ⑸ 只有经有限次使用上述规则构造的表达式才是∑上的正则 表达式。
2014-7-6 22
根据正则文法构造等价的正则表达式
⑤ 如果有A=β1、A=β2、…、A=βh，则用 A=β1|β2|…|βh代替之。 如果最后得到的关于S的方程式为如下形式， S=α1|α2|…|αh 则将方程式右边所有其中仍然含有语法变量 的αi(1≤i≤n)删除，得到的结果就是与G等价 的正则表达式；如果任意的αi(1≤i≤n)均含有 语法变量，则就是与G等价的正则表达式。
forward := forward +1
end else if forward在缓冲区第二部分末尾 then begin 重装缓冲区第一部分; 将forward移到缓冲区第一部分开始 end
else forward:= forward +1;
end
else /* eof 在表示输入结束 */

大小问题 128Byte*2|1024Byte*2|4096Byte*2
2ห้องสมุดไป่ตู้14-7-6 21
根据正则文法构造等价的正则表达式
③ 如果有A=(r1|r2|…|rn)B，B=(t1|t2|…|tm)C，则用 A=(r1|r2|…|rn) (t1|t2|…|tm)C替换之，其中B≠A； 如果有A=(r1|r2|…|rn)B，B=(t1|t2|…|tm)，则用 A=(r1|r2|…|rn) (t1|t2|…|tm)替换之，其中B≠A； ④ 对A=(t1|t2|…|tm)*A且A=(r1|r2|…|rn)B，其中B≠A，则 用A=(t1|t2|…|tm)* (r1|r2|…|rn)B替换之； 对A=(t1|t2|…|tm)*A且A=r1|r2|…|rn则用A=(t1|t2|…|tm)* (r1|r2|…|rn)替换之；
例3.6 将如下文法G转换成相应的正则表达式
24
将正则表达式转换成等价的正则文法


问题：给定∑上的一个正则表达式r，根据r构 造正则文法G，使得L(G)=L(r) 定义3.3 设字母表为∑，{A、B、…、C}为语 法变量集合，对于∑上的任意正则表达式r， 形如Ar的式子称为正则定义式；如果r是∑ 中的字母和用正则定义式定义的变量组成的 正则表达式，则形如Ar的式子称为正则定 义式。
2014-7-6
跟实现有关
8
3.1.3 源程序的输入缓冲与预处理

超前搜索和回退

双字符运算符（**, /*,:=,…） DO 90 k=1,10 DO 90 k=1.10 假定源程序存储在磁盘上，这样每读一个字符就 需要访问一次磁盘，效率显然是很低的。

缓冲区


空白字符的剔除

剔除源程序中的无用符号、空格、换行、注释等
2014-7-6 12
3.1.5 词法分析器的位置
符 号 表 源程序 词法分析器 语法分析器 语义分析与 代码生成 目标程序
目标代码整理 图3.4 以语法分析器为中心

以语法分析器为中心的优点：

简化编译器的设计。 提高编译器的效率。 增强编译器的可移植性。
13
2014-7-6
3.2 单词的描述
14
2014-7-6
3.2.2 正则表达式

例3.2：标识符的另一种表示

letter(letter|digit)* | 表示"或" * 表示Kleene闭包 + 表示正闭包 ？表示“0或1个” Letter和(letter|digit)*的并列表示两者的连接



正则式r表示正则集,相应的正则集记为 L(r)
与and等；关系运算符=、<>、、、和等
5. 分界符: ，、；、（、）...
2014-7-6 4
二、单词的内部形式 表示单词的种类，可用整
数编码或记忆符表示 不同的单词不同的值
种别
属性值
几种常用的单词内部形式：
1、按单词种类分类
2、保留字和分界符采用一符一类
3、标识符和常数的单词值又为指示字
根据正则文法构造等价的正则表达式

具体步骤
(1) 根据正则文法G构造正则表达式联立方程组。 假设正则文法G是右线性的，其每个产生式的右部 只含有一个终结符，则有如下方程式构造规则：
① 对形如A a1|a2|…|am的产生式，构造方程式A= a1|a2|…|am。其中可以有形如Aε的产生式； ② 对形如Aa1A|a2A|…|amA的产生式，构造方程式 A=(a1|a2|…|am)*A； ③ 对形如Aa1B|a2B|…|amB的产生式，构造方程式 A=(a1|a2|…|am)B，其中B≠A。
2014-7-6
20
根据正则文法构造等价的正则表达式
(2)解联立方程组，求等价的正则表达式r 用代入消元法逐个消去方程组中除开始符号S 外的其他变量，最后即可得到关于开始符 号S的解。代入消元规则如下： ① 如果有A=r1B|r2B|…|rnB，则用 A=(r1|r2|…|rn)B替换之，其中B≠A； ② 如果有A=t1A|t2A|…|tmA，则用 A=(t1|t2|…|tm)*A替换之；
3
2014-7-6
3.1.1 单词的分类与表示 & 3.1.2 词法分析器的输出
一、单词的种类
1. 关键字:也称基本字，begin、end、for、do... 2. 标识符:由用户定义，表示各种名字 3. 常数:整常数、实常数、布尔常数、字符串常数等 4. 运算符:算术运算符+、-、*、/等；逻辑运算符not、or


为正则文法的每个产生式构造一个正则表达式方 程式，这些方程式中的变量是文法G中的语法变 量，各变量的系数是正则表达式，简称为方程式。 从而得到一个联立方程组。 用代入消元法消去联立方程组中除开始符号外的 其他变量，最后得到关于开始符号S的解：S = r， r即为所求的正则表达式。
19
2014-7-6
2014-7-6
类别编码 1 2 3 4 5 6 7 8 9 …… 20 21 22 23 ……
单词值 内部字符串 整数值 数值 0 或 1 内部字符串 …… -
7
例3.1 语句if count>7 then result := 3.14 的单词符号序列
(IF，0) (ID，指向count 的符号表入口) (GT，0) (INT，7) (THEN，0) (ID，指向result的符号表入口) (ASSIGN，0) (REAL，3.14) (SEMIC，0)
（指针值）
2014-7-6 5
1、按单词种类分类
单词名称
标识符 无符号常数(整)
类别编码
1 2
单词值
内部字符串
整数值 数值
无符号浮点数
布尔常数 字符串常数 保留字 分界符
2014-7-6
3
4 5
0 或 1
内部字符串 保留字或内部编码 分界符或内部编码
6
6
7
2、保留字和分界符采用一符一类
单词名称 标识符 无符号常数(整) 无符号浮点数 布尔常数 字符串常数 BEGIN END FOR DO ……… : + * , (
2014-7-6 17
3.2.3 正则表达式与正则文法的等价性

正则表达式与正则文法等价

对任意一个正则表达式，存在一个定义同 一语言的正则文法 对任意一个正则文法，存在一个定义同一 语言的正则表达式

2014-7-6
18
根据正则文法构造等价的正则表达式


问题：给定正则文法G，构造一个正则表达 式r，使得L(r) =L(G) 基本思路
2014-7-6 23
根据正则文法构造等价的正则表达式

2014-7-6
S aS|aB B bB|bC|aB|bS C cC|c 1.列方程组 * S=a S S =aB B=(a|b)*B B=bC B=bS C=c*C C=c 2.代入法解方程组 * C=c c B=bc*c|bc B=(a|b)*(bc*c|bc) * B=(a|b) bS S=a*aB * * * * * S=a a(a|b) bS|a a(a|b) (bc c|bc) * * * * * * S=(a a(a|b) b) a a(a|b) (bc c|bc) + * * + * + 如果用正闭包表示，则为(a (a|b) b) a (a|b) (bc |bc)
第3章 词法分析