当前位置：文档之家 › 第2章词法分析

第2章词法分析

  • 格式：ppt
  • 大小：705.50 KB
  • 文档页数：96

下载文档原格式

  / 96

合集下载

编译原理(2)词法_2(NFA、DFA的确定化和化简)

编译原理(2)词法_2(NFA、DFA的确定化和化简)
西北农林科技大学本科教程
第 3 讲
主讲教师：赵建邦
本讲目标

第二章《词法分析》2.3-2.5节

2.3 2.4 2.5
正规表达式与有限自动机简介 正规表达式到优先自动机的构造 词法分析器的自动生成

重点掌握

有限自动机理论 有限自动机的构造、确定化和化简
第二章 词法分析
2.1 2.2
• DFA是一个五元组，Md＝ (S, ∑, f, s0 , Z) ，其中： (1) S是一个有限状态集合，它的每个元素称为一个状态 (2) ∑是一个有穷字母表，它的每个元素称为一个输入字符 (3) f是一个从S×∑至S的单值映射，也叫状态转移函数 (4) s0∈S 是唯一的初态 (5) Z S 是一个终态集
J中的每一个状态经过任意条 ε通路得到ε_CLOSURE(J) =
4
Ia= {5,6,2,3,8,4,7}
2.4

正规表达式到有限自动机的构造
2.4.2：NFA的确定化（子集法）
(1) 构造一张转换表，第一列记为状态子集I，对于不同的符号
(a∈Σ)，在表中单设一列Ia ； (2) 表的首行首列置为ε_CLOSURE(s0)，其中s0为初始状态； (3) 根据首行首列的I，为每个a求其Ia 并记入对应的Ia 列中， 如果此Ia 不同于第一列中已存在的所有状态子集I，则将其
si
r1 r2 r1 *
sj sj
si
si
sj
si
2.4
正规表达式到有限自动机的构造
例2.6 对给定正规表达式 b*(d|ad)(b|ab)+ 构造其NFA M [解答] 先用R+=RR*改造正规表达式 b*(d|ad)(b|ab)+ = b*(d|ad)(b|ab)(b|ab)* 按照正规式从左到右构造NFA： b X ε 1 ε 2 a 3

第二章 翻译技巧：词法翻译法

第二章 翻译技巧：词法翻译法

一、词的选择和意义引申考研翻译的过程和核心解题策略一、理解应以原文，拆分语法结构二、改变原文顺序，组合汉语译文词义选择和词义引申词义的选择和词义引申是考研翻译中最常用的翻译技巧。

1.在1994年72)题a leader of the new school contends 中，school 是“学派”的意思，而不是“学校”的意思；2.在1996年74）题elegant system 中，elegent是“完美，完善”的意思，而不是“优雅”的意思；3.在2001年75）题And home appliances will become so smart that ...中，smart 是“智能化”的意思，而不是“聪明”的意思；4.在2003年75）题like the concept of set in mathematics 中，set 是“集，集合”，而不是“一套，放置”等意思；5.在2004年62）题we are obliged to them 中，obliged是“感谢，感激”，而不是“被迫”的意思。

词义的选择例1.I’ll see her home tonight.今晚我送她回家。

例2. India is the home of elephants.印度是大象的生长地。

例3.He’s at home with the classics.他精通古典文学。

例4.New homes are for sale.新房出售。

例5.She’s at home where she is.她在哪儿都自由自在。

例6.Maternity homr costs in America have gone up sharply.美国妇产医院收费已经急剧上涨。

例7.Much is produced here for home market.这里为国内市场生产了许多产品。

例8.He looks on London as his home.他把伦敦看成是他的故乡。

《编译原理》期中及期末习题

《编译原理》期中及期末习题

第一章高级语言与编译程序概述典型例题:单项选择题1.1.1．将编译程序分成若干个“遍”是为了___。

a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率1.1.2．构造编译程序应掌握____。

（陕西省2000年自考题）a.源程序b.目标语言c.编译方法d.以上三项都是1.1.3．变量应当＿。

a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值1.1.4．编译程序绝大多数时间花在____上。

（陕西省1998年自考题）a.出错处理b.词法分析c.目标代码生成d.管理表格1.1.5．____不可能是目标代码。

( 陕西省1997年自考题)a.汇编指令代码b.可重定位指令代码c.绝对指令代码d.中间代码1.1.6．数组A[1…20,1…10]的首地址偏移量为0，按列存储，每个元素占一个字节，存储器按字节编址，则A[i,ｊ］的偏移地址为____。

a.(i-1)X10+（j-1）b.(i-1)X20+(j-1)c. (i-1)＋(j-1)X10d.(i-1)+(j-1)X201.1.7.使用____可以定义一个程序的意义。

a.语义规则b.词法规则c.产生规则d.左结合规则1.1.8．表达式X:=5中，变量x____。

a.只有左值b.只有右值c.既有左值又有右值d.没有左值也没有右值1.1.9．词法分析器的输入是__。

a.单词符号b.源程序c.语法单位d.目标程序1.1.10．中间代码生成时所遵循的是＿。

a.语法规则b.词法规则c.语义规则d.等价变换规则1.1.11．编译程序是对__。

a.汇编程序的翻译b.高级语言程序的解释执行c.机器语言的执行d.高级语言的翻译1.1.12．词法分析应遵循＿。

（陕西省2000年自考题）a.语义规则b.语法规则c.构词规则d.等价变换规则多项选择题：1.2.1 编译程序各阶段的工作都涉及到___。

清华大学编译原理第二版课后习答案

清华大学编译原理第二版课后习答案

Lw.《编译原理》课后习题答案第一章第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

盛威网（）专业的计算机学习网站1《编译原理》课后习题答案第一章目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

编译技术复习题答案

编译技术复习题答案

第一章：编译系统概述一．单项选择题1．编译程序前三个阶段完成的工作是〔C〕。

A．词法分析, 语法分析和代码优化B．代码生成, 代码优化和词法分析C．词法分析, 语法分析, 语义分析和中间代码生成D．词法分析, 语法分析和代码优化2．编译程序绝大多数时间花在〔D〕上。

A．出错处理 B．词法分析 C．目标代码生成D．表格管理3．编译程序是对〔C〕。

A．汇编程序的翻译 B．高级语言程序的说明执行C．高级语言的翻译 D．机器语言的执行4．在运用高级语言编程时，首先可通过编译程序发觉源程序的全部〔A〕错误。

A．语法 B．语义 C．语用 D．运行二．填空题1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。

2．通常把编译过程分为分析前端及后端两大阶段。

词法, 语法和语义分析是对源程序的(分析)，中间代码生成, 代码优化及目标代码的生成那么是对源程序的(综合)。

3．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。

4．对以下错误信息，请指出可能是编译的哪个阶段〔词法分析, 语法分析, 语义分析,代码生成〕报告的。

〔1〕 else 没有匹配的if 〔语法分析〕〔2〕数组下标越界〔语义分析〕〔3〕运用的函数没有定义〔语法分析〕〔4〕在数中出现非数字字符〔词法分析〕5．假如编译程序生成的目标程序是机器代码程序，那么源程序的执行分为两大阶段：〔编译阶段〕和〔运行阶段〕。

假如编译程序生成的目标程序是汇编语言程序，那么源程序的执行方式分成三个阶段：〔编译阶段〕〔汇编阶段〕和〔运行阶段〕。

6．编译程序在其工作过程运用最多的数据构造是〔表〕，它记录着源程序中各种信息，以便查询或修改，在这些〔表〕中，尤以〔符号表〕最重要，它的生存期最长，运用也最频繁。

三．简述题：1．编译程序的工作分为那几个阶段答：词法分析, 语法分析和语义分析是对源程序进展的分析(称为编译程序的前端)，而中间代码生成, 代码优化和代码生成三个阶段合称为对源程序进展综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。

编译原理第三版课后习题答案

编译原理第三版课后习题答案

编译原理第三版课后习题答案编译原理是计算机科学中的一门重要课程，它研究的是如何将高级程序语言转换为机器语言的过程。

而《编译原理》第三版是目前被广泛采用的教材之一。

在学习过程中，课后习题是巩固知识、提高能力的重要环节。

本文将为读者提供《编译原理》第三版课后习题的答案，希望能够帮助读者更好地理解和掌握这门课程。

第一章：引论习题1.1：编译器和解释器有什么区别？答案：编译器将整个源程序转换为目标代码，然后一次性执行目标代码；而解释器则逐行解释源程序，并即时执行。

习题1.2：编译器的主要任务是什么？答案：编译器的主要任务是将高级程序语言转换为目标代码，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等过程。

第二章：词法分析习题2.1：什么是词法分析？答案：词法分析是将源程序中的字符序列划分为有意义的词素（token）序列的过程。

习题2.2：请给出识别下列词素的正则表达式：（1）整数：[0-9]+（2）浮点数：[0-9]+\.[0-9]+（3）标识符：[a-zA-Z_][a-zA-Z_0-9]*第三章：语法分析习题3.1：什么是语法分析？答案：语法分析是将词法分析得到的词素序列转换为语法树的过程。

习题3.2：请给出下列文法的FIRST集和FOLLOW集：S -> aAbA -> cA | ε答案：FIRST(S) = {a}FIRST(A) = {c, ε}FOLLOW(S) = {$}FOLLOW(A) = {b}第四章：语义分析习题4.1：什么是语义分析？答案：语义分析是对源程序进行静态和动态语义检查的过程。

习题4.2：请给出下列文法的语义动作：S -> if E then S1 else S2答案：1. 计算E的值2. 如果E的值为真，则执行S1；否则执行S2。

第五章：中间代码生成习题5.1：什么是中间代码？答案：中间代码是一种介于源代码和目标代码之间的表示形式，它将源代码转换为一种更容易进行优化和转换的形式。

第2章 词法分析-sxw

2.3.1 正规表达式与正规集
正规表达式是典型的词法规则描述工具.
正规式也称正则表达式. 正规表达式(regular expression)是说明单词的模 式(pattern)的一种重要的表示法(记号),是定义正 规集的数学工具.我们用以描述单词符号.下面是 正规式和它所表示的正规集的递归定义.
第2章 词法分析
程序语言中使用的标识符是一个以字母开头的字 母数字串,如果字母用letter表示,数字用digit表示, 则标识符可表示为 letter (letter∣digit)* 其中,letter与 (letter∣digit)*的并置表示两者的连 接;括号中的"∣"表示letter或digit两者选一;"*" 表示零次或多次引用由"*"标记的表达式; (letter∣digit)*是letter∣digit的零次或多次并置,即表 示 一 长 度 为 0 , 1 , 2 , … 的 字 母 数 字 串 ; letter (letter∣digit)*表示以字母开头的字母数字串,也即标 识符集.letter (letter∣digit)*就是表示标识符的正规式, 而标识符集就是这个正规式所表示的正规集.
第2章 词法分析
retract ( ); c=reserve ( ); if (c==0) { buildlist ( );
/*扫描指针回退一个字符*/
/*将标识符登录到符号表中*/
return (id,指向id的符号表入口指针); } else return (保留字码,null); break;
第2章 词法分析
x i y
j
k
图2–2 不同输入字符的状态转换
第2章 词法分析

第二章 词法分析


8
单词种别表示单词的种类， (1) 单词种别表示单词的种类，是语法分 析所需要的信息。 析所需要的信息。 一个语言的单词符号如何划分种类、 一个语言的单词符号如何划分种类、分为 几类、如何编码都属于技术性问题， 几类、如何编码都属于技术性问题，主要取 决于处理上的方便。 决于处理上的方便。 通常让每种单词对应一个整数码， 通常让每种单词对应一个整数码，这样可 最大限度地把各个单词区别开来。 最大限度地把各个单词区别开来。
6
(4) 运 算 符 ： 如 “ +” 、 “ − ” 、 “ * ” 、 /”、 >”、 <”等 “/”、“>”、“<”等。 (5) 界符：在语言中是作为语法上的分界符 界符： 号使用的， 号使用的 ， 如“ ， ”、 “ ；” 、 “（ ” 、 “ ） ” 等。 一个程序语言的保留字、 一个程序语言的保留字、运算符和界符 的个数是确定的， 的个数是确定的，而标识符或常数的使用则 不限定个数。 不限定个数。
24
终态一般对应一个return( 语句。 终态一般对应一个return( )语句。 return意味着从词法分析器返回到调用段 return意味着从词法分析器返回到调用段 一般指返回到语法分析器。 ，一般指返回到语法分析器。
图2–4 含有分支或回路的状态示意 (a) 含分支的状态 ；(b) 含回路的状态 含分支的状态i； 含回路的状态i
(3,’if’) (1,指向 的符号表入口) 指向i (1,指向i的符号表入口) (4,’=’) (2,’5’) (3,’then’) (1,指向 的符号表入口) 指向x (1,指向x的符号表入口) (4,’:=’) (1,指向 的符号表入口) 指向y (1,指向y的符号表入口) (5,’;’)

编译原理教程(第二版)胡元义课后答案第二章


第二章 词法分析 对图2-21的DFA进行最小化。首先将状态分为非终态 集和终态集两部分：{0,1,2,5}和{3,4,6,7}。由终态集 可知，对于状态3、6、7，无论输入字符是a还是b的下一 状态均为终态集，而状态4在输入字符b的下一状态落入 非终态集，故将其化为分 {0,1,2,5}, {4}, {3,6,7} 对于非终态集，在输入字符a、b后按其下一状态落 入的状态集不同而最终划分为
重新命名
图2-9 习题2.5的状态转换矩阵
第二章 词法分析
a 0 a 1 b 2
b b 3
a a 4
图2-10 习题2.5的最简DFA
第二章 词法分析 2.6 有语言L={w|w∈(0,1)+，并且w中至少有两个
1，又在任何两个1之间有偶数个0}，试构造接受该语
言的确定有限状态自动机(DFA)。
M′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图
2-3所示。
第二章 词法分析 表2-2 状态转换矩阵
f 状态 0 1 2 字符
a 2 — 2
b 1 2 2
第二章 词法分析 将图2-3所示的DFA M′最小化。首先，将M′的状 态分成终态组{1,2}与非终态组{0}。其次，考察{1,2}，
0 0 0 1 1 0 2 0 3 1 4 0 5 1 0 0 6
图2-13 习题2.6的最简DFA
第二章 词法分析 2.7 已知正规式((a|b)*|aa)*b和正规式(a|b)*b。
(1) 试用有限自动机的等价性证明这两个正规式
是等价的；
(2) 给出相应的正规文法。 【解答】 图2-14所示。 (1) 正规式((a|b)*|aa)*b对应的NFA如

编译原理

编译原理第一章：1．编译程序是现代计算机系统的基本组成部分之一2．一个计算机系统中通常配置多个高级语言的编译程序3．在一个计算机系统中可为某些高级语言配置多个不同性能的编译程序4．编译程序是一种语言翻译程序，其功能是把一种语言编写的程序翻译成另一种语言的等价程序5．被编译的程序称为源程序，编译后的等价程序称为目标程序6．编译程序的任务就是将源语言程序翻译成等价的目标语言程序7．通常将编译过程分为六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

8．词法分析的主要任务是从左至右扫描字符序列，并按照此法规则识别出一个个的单词9．单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。

10．计算机语言中，单词的种类通常有保留字、标识符、数、算符、界符等11．语法分析的主要任务是：按照语言的语法规则，把词法分析所得的单词序列分解成各类语法成分。

12．词法分析和语法分析都是对源程序进行结构分析，但二者是有区别的。

13．语义分析的主要功能是审查源程序有无语义错误，伪代码生成阶段收集类型信息。

14．中间代码生成阶段的主要任务是，把源程序转换成一种中间代码15．中间代码是一种结构简单、含义明确的记号系统16．中间代码可以设计成多种形式，其设计原则有两点：一是容易生成，二是容易转换成目标代码17．代码优化的主要任务是对中间代码进行改造，使生成的目标代码更为高效18．目标代码生成阶段的任务是把中间代码转换成特定机器上的绝对指令代码或者可重定位的指令代码或者汇编指令代码19．在编译过程的每个阶段中都含有出错处理和表格管理的工作20．编译程序的结构可以按功能分为八个模块，即词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序，此外还有与上述每个阶段都有关系的出错处理程序和表格管理程序。

21．按照编译程序的工作主要是与源语言有关还是与目标机有关，编译过程也可前端和后端22．前端的工作主要依赖于源语言而与目标机无关，包括词法分析、语法分析、语义分析、中间代码生成以及每个阶段中的出错处理和表格管理工作，还包括代码优化阶段的部分工作23．后端的工作主要与目标机有关而与源语言无关，主要是代码生成及相关的出错处理和表格管理工作24．编译过程中，对源程序或者中间语言程序从头至尾扫描一次并完成相应工作的过程称为“一遍”或者“一趟”25．解释程序是另一种语言处理程序，其工作特点是边分析边执行，不生成目标代码。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2.3 正规表达式与有限自动机简介
2.3.1 正规表达式与正规集
状态转换图对构造词法分析器非常 有效，为便于词法分析器的自动生成， 需将状态转换图的概念形式化。正规表 达式就是一种形式化表示法，它可以表 示单词符号的结构，从而精确定义单词 符号集。正规表达式简称正规式，它表 示的集合称为正规集。
下面以标识符为例来说明正规式与正规集: 标识符是以字母开头的字母数字串。
第2章 词法分析
2.1 词法分析器设计方法 2.2 一个简单的词法分析器示例 2.3 正规表达式与有限自动机简介 2.4 正规表达式到有限自动机的构造 2.5 词法分析器的自动生成
词法分析的任务: 从左至右逐个字符 地对源程序进行扫描, 产生一个个单词符 号, 把字符串形式的源程序改造成为单词 符号串形式的中间程序。
…
case 'z':
while (letter ( )‖digit ( )) { concatenation ( ); /*将当前读入
的字符送入token数组*/
getchar ( );
}
retract ( ); /*扫描指针回退一个字符*/ c=reserve ( ); if (c==0) {
buildlist ( ); /*将标识符登录到符号表*/ return (id, id在符号表中的入口指针); } else return (保留字码, null) ; break;
(5)letter( )和digit( ): 判断character中的字 符是否为字母和数字的布尔函数,若是 则返回true, 否则返回false。
(6)reserve( ): 按token数组中的字符串查 保留字表, 若是保留字则返回其编码, 否则返回0。
(7) retract( ): 扫描指针回退一个字符, 同 时将character置为空白。
③ (R)*是Σ上的正规式， 它表示的正规集为(L(R))*；{闭包}
(4)仅由有限次使用(1)~(3)得到的表示式是 Σ上的正规式, 它表示的集合是Σ上的 正规集。
说明： 1>Σ上的一个字指的是由Σ中字符构成的
一个有穷序列; 不包含任何字符的序列称为空字ε。 Σ*表示Σ上所有字的全体, 包括空字ε。 例如, 若Σ={a, b} 则Σ*={ε, a, b, aa, ab, ba, bb, aaa, …}
＝ 11 ＝ 12
其它
返回(relop, EQ)
；
13* 返回(＝, -)
14
其它 15 *
返回(; , -) 非法字符错
注意: (1)状态2识别出一个单词符号后需先
查保留字表,若匹配则为保留字,否则为标 识符。若为标识符,还需查符号表,看表中 是否有此标识符。若符号表中无此标识符, 则先将它登录到符号表中,再返回它在符号 表中入口地址作为内码值;若表中有此标识 符,则直接返回其入口地址作为内码值。
(2)状态4识别出一个常数后需先将它 转换成二进制常数再登录到常数表,然后返 回它在常数表中的入口指针作为内码值。
2.2.3 状态转换图的实现 状态转换图易于用程序实现,最简单
的办法是让每个状态对应一小段程序。对 图2–5,首先引进一组变量和过程：
(1)character: 字符变量,存放最新读入 的源程序字符。
(8)buildlist( ): 将标识符登录到符号表或 将常数登录到常数表。
(9)error( ): 进行出错处理。
C语言子集对应的的词法分析器如下: token= ' '; /*对token数组初始化*/ s=getchar( ); getbe( ); /*滤除空格*/
switch (s)
{ case 'a':
(2) 单词自身的值 单词自身的值是编译其它阶段需要的信息。
对于单词符号,若一个种别只含一个单词,则 其种别编码就代表它自身的值。若一个种别含
多个单词,则除种别编码外, 还应给出单词自身 的值,以便把同一种类的单词区别开来。
注意：标识符自身的值是标识符自身的字
符串,常数自身的值是常数本身的二进制数值。 此外,也可用指向某类表格中一特定项目的
词
字符串形式 字符
法 分
的源程序
析
器
单词 取下一单词 语
法
符
分
号
析
表
器
2.1 词法分析器设计方法
2.1.1 单词符号的分类与输出形式 1. 单词符号分类 单词符号是程序语言的基本语法单位。 程序语言的单词符号通常分为五种： (1)保留字：如if、while (2)标识符：标记常量、变量、函数等的名字 (3)常数：如实型0.618、布尔型TRUE (4)运算符：如+、-、*、/、>、< (5)界符：分界符，如, 、 ; 、( 、) 注意：保留字、运算符和界符的个数确定，
2>Ф表示不含任何元素的空集{}。 注意ε、{}和{ε}的区别： ε表示不包含任何字符的序列,它是正
规集中的一个元素；{}表示不含任何字 的集合, 它是一个空的正规集；{ε}表示 由空字组成的集合。
3>使用括号可改变运算符的运算次序。 若规定*优先于·, ·优先于|, 则在不混淆情况下,可省去括号。
它们表示的正规集分别为{ε}和Ф。 (2) 对任一a∈Σ, a是Σ上的正规式，
它表示的正规集为{a}。 (3)若R和S是Σ上的正规式, 它们表示的
正规集为L(R)和L(S), 则 ① R|S是Σ上的正规式，
它表示的正规集为L(R)∪L(S)；
② R·S是Σ上的正规式， 它表示的正规集为L(R)L(S); {连接积}
— — — LE LT EQ — —
2.2.2 C语言子集对应的状态转换图的设计
首先对输入串做预处理。 即剔除多余的空格、注释等。
其次把保留字作为一类特殊标识符处理。 即对保留字不专设对应的状态转换图， 当状态转换图识别出一个标识符时就
去查表，确定它是否为一个保留字。 C语言子集对应的状态转换图如下：
标识符和常数的个数不确定。
2. 单词符号的输出形式
( 单词种别, 单词自身的值 ) (1) 单词种别: 单词种别表示单词的种类。
一个语言的单词符号如何分类、分为几类、 如何编码主要取决于处理上的方便。通常，每种 单词对应一个整数码。
保留字：可全体视为一种，也可一字一种； 标识符：统归为一种； 常数：统归为一种,或按整、实、布尔等再分； 运算符和界符：一符一种，或统归为一种。
指针来区分同类中的不同单词。例如,对于标识 符,可用它在符号表的入口指针作为自身的值; 常数可用它在常数表的入口指针作为自身的值。
2.1.2 状态转换图
词法分析中,可用状态
转换图识别单词。状态 转换图中,结点代表状态；
j x
结点之间由有向边连接， 有向边上可标记字符。
i
如图,状态i下,若输入
y
字符为x,则读入x并转到
词法分析程序也叫词法分析器或扫描 器。其功能是输入源程序,输出单词符号。
词法分析可采用如下两种处理结构： (1)把词法分析程序作为主程序。将词法
分析作为独立的一遍来完成。
字符串形式 字符 的源程序
词
符号表
法
分 析
单词
单词符号
器
串程序
(2) 把词法分析程序作为语法分析程序调 用的子程序。进行语法分析时,每当需 要一个单词时便调用词法分析程序。
case '+': return ('+'，null); break; case‘-': return (‘-'，null); break; case '*': return ('*'，null); break; case '<':
getchar ( ); if (character== '=') return(relop,LE); else { retract ( );
k
状态j;若输入字符为y,则
读入y并转到状态k。
状态转换图中状态的数目是有限的， 其中必有一个初态和若干个终态，终态 结点用双圈表示。识别标识符的状态转 换图如下：
字母或数字
字母 0
其它
*
1
2
(a)
识别无符号整数的状态转换图如下：
数字
数字 0
其它
*
1
2
(b)
识别无符号数的状态转换图如下：
E
数字
4>Σ*的正规式R和S的连接可形式化为 RS={ | ∈R & ∈S}
例如, R={a, b}，S={1, 2}，
RS={a1, a2, b1, b2} 5> R自身的n次连接记为 Rn=RR …R
6>R0={ε}, R*=R0∪R1∪R2∪R3∪…, R*为R的闭包 R+=RR*, 称R+是R的正闭包。 闭包R*中的每个字都是由R中的字经
return (relop,LT); } break;
case '=': getchar ( ); if (character=='=') return(relop,EQ); else { retract ( ); return ('=', _ ); } break;
case ';': return (';', -); break; default: error ( ); }
字母 j
i 数字 k
图2-4 不含回路的分支状态
状态i 对应的switch语句如下：
s=getchar ( );
switch (s)
{ case 'a':