第四章词法分析
课前索引
【课前思考】
◇词法分析程序的功能是什么？
◇ PL/0词法分析程序识别哪几种单词？
◇画出PL/0词法分析程序的流程图。
◇ C语言，PASCAL语言的标识符和数的表示分别有什么规定？
◇编写一个程序（C的，或PASCAL的）识别C++语言的标识符。
【学习目标】
◇明确词法分析在编译过程所处的阶段和作用。
◇掌握词法分析程序的手工实现方法。
◇理解通常的单词分类和构词规则。
◇会使用单词的描述和识别机制。
◇掌握词法分析程序的自动构造原理。
【学习指南】
词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。词法分析也是语法分析的一部分，把词法分析从语法分析中独立出来是为了使编译程序结构清晰，也是为了便于使用自动构造工具，提高编译效率。
本章首先介绍词法分析程序的功能和设计原则，然后引入正规式和其对单词的描述，接着讲述有穷自动机理论，最后给出词法分析程序的自动构造原理。
【难重点】
◇如何设计和实现词法分析程序
◇正规式的定义-如何用作单词的描述工具
◇有穷自动机的定义和分类-如何用作单词的识别系统
◇正规式到有穷自动机的转换算法-词法分析程序的自动构造原理
【知识结构】
词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。
词法分析程序的主要任务：
- 读源程序，产生单词符号
词法分析程序的其他任务：
- 滤掉空格，跳过注释、换行符
- 追踪换行标志，复制出错源程序，
- 宏展开，……
本章要点：
- 告诉你掌握词法分析程序的设计和实现的办法
- 首先需要描述和刻画程序设计语言中的原子单位--单词，其次需要识别单词和执行某些相关的动作。
- 描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。
4.1 词法分析程序
首先讨论词法分析程序与语法分析程序的接口方式
词法分析程序完成的是编译第一阶段的工作。词法分析工作可以是独立的一遍，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件做为语法分析程序的输入而继续编译过程。然而，更一般的情况，是将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词，或说直到下一单词的第一个字符为止。这种设计方案中，词法分析程序和语法分析程序是放在同一遍里，而省掉了中间文件，象第2章介绍的PL/0编译程序那样.也是大多数编译程序采用的方案。
实现词法分析（lexical analysis）的程序
逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析程序和语法分析程序的关系
f4-1-1.swf
词法分析程序的主要功能是从字符流的源程序中识别单词，它要从左至右逐个字符地扫描源程序，因此它还可完成其它一些任务。比如，滤掉源程序中的注释和空白(由空格，制表或回车换行字符引起的空白)；又比如，为了使编译程序能将发现的错误信息与源程序的出错位置联系起来，词法分析程序负责记录新读入的字符行的行号，以便行号与出错信息相联；再有，在支持宏处理功能的源语言中，可以由词法分析程序完成其预处理等等。
接着讨论词法分析程序的输出
词法分析程序的功能是读入源程序，输出单词符号。单词符号是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分成下列5种：
①保留字，也称关键字，如PASCAL语言中的begin,end,if,while和var等。
②标识符，用来表示各种名字，如常量名、变量名和过程名等。
③常数，各种类型的常数，如25，3.1415，TRUE和"ABC"等。
④运算符，如+，*，<=等。
⑤界符，如逗点，分号，括号等。
五种单词符号：
- 保留字，关键字
- 标识符
- 常数（量）
- 运算符
- 界符
你能举出一些例子吗?
词法分析程序所输出的单词符号常常采用以下二元式表示：(单词种别，单词自身的值)。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。比如在PASCAL的语句const i=25, yes=1；中的单词25和1的种别都是常数，常数的值25和1对于代码生成来说，是必不可少的。有时，对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行。比如，对于标识符来说，还需要记载它的类别、层次还有其它属性，如果这些属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下形式(标识符，指向该标识符所在符号表中位置的指针)，如上述语句中的单词i和yes的表示为：
(标识符，指向i的表项的指针)
(标识符，指向yes的表项的指针)
单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5，程序段if i=5 then x∶=y；在经词法分析器扫描后输出的单词符号和它们的表示如下：
- 保留字if(3，'if')
- 标识符i(1，指向i的符号表入口)
- 等号=(4，'=')
- 常数5(2，'5')
- 保留字then(3，'then')
- 标识符x(1，指向x的符号表入口)
- 赋值号∶=(4，'∶=')
- 标识符y(1，指向y的符号表入口)
- 分号；(5，'；')
将词法分析工作从语法分析中分离出来的原因
实际上，词法也是语法的一部分，词法描述完全可以归并到语法描述中去，只不过词法规则更简单些。这在后面的章节中可以看到。为什么将词法分析做为一个独立的阶段？为什么把编译过程的分析工作划分成词法分析和语法分析两个阶段？主要的考虑因素为：
①使整个编译程序的结构更简洁、清晰和条理化。
②编译程序的效率会改进。
③增强编译程序的可移植性。
①使整个编译程序的结构更简洁、清晰和条理化。词法分析比语法分析简单的多，但是由于源程序结构上的一些细节，常使得识别单词的工作甚为曲折和费时。例如，空白和注释的处理；再比如对于FORTRAN和cobol那种受书写格式限制的语言，需在识别单词时进行特殊处理等等。如果统统合在语法分析时一并考虑，显然会使得分析程序的结构复
杂得多。
②编译程序的效率会改进。大部分编译时间是花费在扫描字符以把单词符号分离出来。把词法分析独立出来，采用专门的读字符和分离单词的技术可大大加快编译速度。另外，由于单词的结构可用有效的方法和工具进行描述和识别，进而可建立词法分析程序的自动构造工具。
③增强编译程序的可移植性。在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，比如采用ASC II还是EBCDIC字符编码。另外语言的字符集的特殊性的处理，一些专用符号，如PASCAL中的"↑"的表示等等，都可置于词法分析程序中解决而不影响编译程序其它成分的设计。
4.2 正规表达式与正规集（正规语言）
程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立词法分析技术，进而可以建立词法分析程序的自动构造方法。
为了理解将使用的形式工具，首先表述一些基本术语和概念。
- 符号一个抽象实体,我们不再形式地定义它(就象几何中的"点"一样)。例如字母是符号，数字也是符号。
- 字母表字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。
- 符号串由字母表中的符号组成的任何有穷序列称为符号串，例如00 11 10 是字母表Σ={0，1}上的符号串。
不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。
字母表A={a,b,c}上的一些符号串有：a,b,c,ab,aaca。在符号串中，符号的顺序是很重要的，例如符号串ab就不同于ba,abca和aabc也不同。可以使用字母表示符号串，如x=STR 表示"x是由符号S、T和R，并按此顺序组成的符号串"。
如果某符号串x中有m个符号，则称其长度为m，表示为|x|=m，如001110的长度是6。
允许空符号串，即不包含任何符号的符号串，用ε表示，其长度为0，即|ε|=0。
下面介绍有关符号串的一些运算。
- 符号串的头尾，固有头和固有尾
- 符号串的连接
- 符号串的方幂
- 符号串集合
符号串的头尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。
举个例子:设z=abc,那么z的头是ε,a,ab,abc,除abc外，其它都是固有头；z的尾是ε,c,bc,a bc,z的固有尾是ε,c,bc。
当我们对符号z=xy的头感兴趣而对其余部分不感兴趣时，我们可以采用省略写法：z=x…；
如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…；符号t是符号串z的第一个符号，则表示为z=t…。
符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串. 由于ε的含义，显然有εx=xε=x。
例如设x=ST，y=abu，则它们的连接xy=STabu，看出|x|=2，|y|=3，|xy|=5。
符号串的方幂：设x是符号串，把x自身连接n次得到符号串z，即z=xx…xx，称为符号串x的n次方幂，写作z=x n ，也即把符号串x相继地重复写n次。x0=ε,x1=x,x2=xx,x3=xxx 分别对应于n=0,1,2和3
例子；若x=AB 则:
x0= ε
x1 = AB
x2 = ABAB
x3 = ABABAB
x n = xx n-1 = x n-1 x (n>0)
符号串集合：若集合A中的一切元素都是某字母表Σ上的符号串，则称A为字母表Σ上的符号串集合。两个符号串集合A和B的乘积定义如下：AB={xy|x∈A且y∈B}，即AB 是满足x属于A，y属于B的所有符号串xy所组成的集合。例如，若A={a,b},B={c,d},则集合AB={ac,ad,bc,bd}。因为对任意符号串x有εx=xε=x，所以有{ε}A= A{ε}=A。
指定字母表Σ之后，使用Σ*表示Σ上的一切符号串（包括ε）组成的集合。Σ* 称为Σ的闭包。Σ上的除ε外的所有符号串组成的集合记为Σ+。Σ+ 称为Σ的正闭包。
Σ+=Σ* -{ε}=ΣΣ* =Σ∪Σ2∪Σ3∪……
Σ* ={ε}∪Σ∪Σ2∪……
例：Σ={a,b}
Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}
Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}
我们用以描述单词符号的工具是正规式。
正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的工具。
正规式也称正则表达式，也是表示正规集的数学工具。下面是正规式和它所表示的正规集的递归定义。
定义（正规式和它所表示的正规集）：
设字母表为Σ，辅助字母表Σ`={Φ，ε，|，·，*，(，}。
① ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和{ }；
②任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；
③假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1*也都是正规式,它们所表示的正规集分别为L(e1), L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*。
④仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。
正规式定义中的“|”读为“或”（也有使用“+”代替“|” 的）；“·”读为“连接”；“*”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“(”、“)”、“*”、“·”、“|” 。连接符“·”一般可省略不写。“*”、“·”和“|” 都是左结合的。
令∑={a，b}，∑上的正规式和相应的正规集的例子有：
正规式正规集
a {a}
a|b {a,b}
ab{ab}
(a|b)(a|b){aa,ab,ba,bb}
a*{ε,a,a, ……任意个a的串}
(a|b)*{ε,a,b,aa,ab ……所有由a和b组成的串}
(a|b)*(aa|bb)(a|b)*{∑*上所有含有两个相继的a或两个相继的b组成的串}
若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价，写作e1=e2。
例如：e1= (a|b)，e2 = b|a
又如：e1= b(ab)*，e2 =(ba)* b
再如：e1= (a|b)*，e2 =(a* |b* )*
设r,s,t为正规式，正规式服从的代数规律有：
① r|s=s|r "或"服从交换律
② r|(s|t)=(r|s) | t "或"的可结合律
③ (rs)t=r(st) "连接"的可结合律
④ r(s|t)=rs|rt
(s|t)r=sr|tr 分配律
⑤ εr=r, rε=r ε是"连接"的恒等元素零一律
⑥ r|r=r
r*=ε|r|rr|…"或"的抽取律
程序设计语言的单词都能用正规式来定义。请看下面两个例子：
例4.1
令Σ={l，d}，则Σ上的正规式r=l(l|d)* 定义的正规集为：{l,ll,ld,ldd,……}，其中l代表字母，d代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。
例4.2
Σ={d，·，ε，+，-},则Σ上的正规式d*(·dd*|ε)( ε(+| -ε|)dd*|ε)表示的是无符号数的集合。其中d为0~9的数字。
外文教材中常常遇到的术语
- Token 单词,词标，符号
- lexeme 词素，词位
- pattern 模式，式样
这段话帮你理解外文教材中常常遇到的术语In general，there is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token. The pattern is said to match each string in the set. A lexeme is a sequence of characters in the source program that is matched by the pattern for a token. 例如：
源程序语句Const pi=3.14159，x1=10；中的pi和x1是token “identifier”的lexeme，其pattern为字母开头，后面跟有字母和/或数字的字符序列。
4.3 有穷自动机
有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。
有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。
关于有穷自动机我们将讨论如下题目
- 确定的有穷自动机DFA
- 不确定的有穷自动机NFA
- NFA的确定化
- DFA的最小化
4.3.1 确定的有穷自动机DFA
DFA定义：-一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中
① K是一个有穷集，它的每个元素称为一个状态；
② Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；
③ f是转换函数，是K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；
④ S ∈ K是唯一的一个初态；
⑤ Z K是一个终态集，终态也称可接受状态或结束状态。
举一个DFA 的例子：
DFA M=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：
f（S，a）=U f（V，a）=U
f（S，b）=V f（v，b）=Q
f（U，a）=Q f（Q，a）=Q
f（U，b）=V f（Q，b）=Q
一个DFA可以表示成一个状态图(或称状态转换图)。假定DFA M含有m个状态，n 个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头"=>"或标以"-"，终态结点用双圈表示或标以"+"，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；
DFA 的状态图表示
一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头"=>"标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。
DFA 的矩阵表示
DFA的确定性表现在转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。
为了说明DFA如何作为一种识别机制,我们还要理解下面的定义。
∑*上的符号串t在M上运行
- 一个输入符号串t，（我们将它表示成Tt1的形式，其中T∈∑，t1∈ ∑*）在DFA M上运行的定义为：
- f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K
- 扩充转换函数f，是K×Σ*→K上的映射，且：f（k i，ε）= k i
∑*上的符号串t被M接受
- 若t∈∑*，f(S，t)=P，其中S为M的开始状态，P∈Z，Z为终态集。
- 则称t为DFA M所接受（识别）
DFA M所能接受的符号串的全体记为L(M)
结论：
∑上一个符号串集V∑*是正规的，当且仅当存在一个∑上的确定有穷自动机M，使得V=L(M)
例：证明t=baab被下图的DFA所接受。
f（S，baab）=f（f（S，b），aab）
= f（V，aab）= f（f（V，a），ab）
=f（U，ab）=f（f（U，a），b）
=f（Q，b）=Q
Q属于终态。
得证。
4.3.2不确定的有穷自动机NFA
接下来我们讨论不确定的有穷自动机NFA
定义
不确定的有穷自动机NFA N=(K，∑，f，S，Z)
其中：
K为状态的有穷非空集
∑为有穷输入字母表
f为K*∑*到K的子集（2K）的映射
S K是初始状态集
Z K为终止状态集。
例子：
NFA N=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）
其中
f（S，0）={P}
f（Z，0）={P}
f（P，1）={Z}
f（Z，1）={P}
f（S，1）={S，Z}
状态图表示
同样NFA也有矩阵表示
f4-2-1.swf
类似DFA, 对NFA N=(K，∑，f，S，Z)也有如下定义
∑*上的符号串t在NFA N上运行
一个输入符号串t，（我们将它表示成Tt1的形式，其中T∈∑，t1∈∑*）在NFA N上运行的定义为：
f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K.
∑*上的符号串t被NFA N接受
若t∈∑*，f(S，t)=P，其中S为N的开始状态，P∈Z，Z为终态集。
则称t为NFA N所接受（识别）
∑*上的符号串t被NFA N接受也可以这样理解：对于Σ*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的ε道路，那么空字可为M 所接受。
NFA N所能接受的符号串的全体记为L(N)
结论：
∑上一个符号串集V∑*是正规的，当且仅当存在一个∑上的不确定的有穷自动机N，使得V=L(N)
下图的NFA称作具有ε转移的不确定的有穷自动机
对任何一个具有ε转移的不确定的有穷自动机NFA N，一定存在一个不具有ε转移的不确定的有穷自动机NFA M，使得L(M)=L(N)。
这里给出与上图等价的一个NFA。
4.3.3 不确定的有穷自动机N的确定化
根据定义，显然DFA是NFA的特例。对于每个NFA M，存在一个DFA M′，使得L(M)=L(M′)。
对于任何两个有穷自动机M和M′，如果 L(M)=L(M′)，则称M与M′是等价的。
我们将介绍一种算法，对于给定的NFA M，构造其等价的DFA M′。
请你注意这个结论：DFA是NFA的特例
对每个NFA N一定存在一个DFA M，使得L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。与某一NFA等价的DFA不唯一。
在有穷自动机的理论里，有这样的定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。我们不对定理进行证明，只介绍一种算法（这
种算法称为子集法），将NFA转换成接受同样的语言的DFA。
为什麽对DFA如此亲睐呢？因为它的行为很容易用程序来模拟。
DFA M=（K，Σ，f，S，Z）的行为的模拟程序
K:=S；
c:=getchar;
while c<>eof do
{K:=f(K,c);
c:=getchar;
};
if K is in Z then return (…yes?)
else return (…no?)
从NFA的矩阵表示中可以看出，表项通常是一个状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本想法是该DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。也就是说，在读入输入符号串a1a2…a n之后，该DFA处在这样一个状态，该状态表示这个NFA的状态的一个子集T，T是从NFA的开始状态沿着某个标记为a1a2…a n 的路径可以到达的那些状态。
为介绍算法首先定义对状态集合I的几个有关运算：
1. 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。
回顾在前面章节对转换函数的扩充：如输入字符是空串，则自动机仍停留在原来的状态上，显然，状态集合I的任何状态S都属于ε-closure(I)。
2. 状态集合I的a弧转换，表示为move(I,a)，定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。
我们使用图4.4的NFA N的状态集合来理解上述两个运算。
图 4.4 NFA N
ε-closure(0)=｛0，1，2，4，7｝
即｛0，1，2，4，7｝中的任一状态都是从状态0经任意条ε弧可到达的状态，令｛0，1，2，4，7｝=A，则move(A,a)=｛3，8｝，因为在状态0，1，2，4和7中，只有状态2
和7有a弧射出，分别到达状态3和8。
而ε-closure(｛3，8｝)=｛1，2，3，4，6，7，8｝。
再看一个例子，对下图所示NFA的状态集合I的运算
图4.5
I={1},ε-closure(I)={1,2}；
I={5},ε-closure(I)={5,6,2}；
move({1,2},a)={5,3,4}
ε-closure({5,3,4})={2,3,4,5,6,7,8}；
NFA确定化算法：假设NFA N=(K, ∑,f,K0,K t)按如下办法构造一个DFA M=(S, ∑,d,S0,S t)，使得L(M)=L(N)：
① M的状态集S由K的一些子集组成（k的子集构造算法见下页）。用[S1 S2... S j]表示
S的元素，其中S1, S2,,... S j是K的状态。并且约定，状态S1, S2,,... S j是按某种规则排列的，
即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]；
② M和N的输入字母表是相同的，即是∑；
③转换函数是这样定义的：
d([S1 S2,... S j],a)= [R1R2... R t] 其中{R1,R2,... , R t} = e-closure(move({S1, S2,,... S j},a))
④ S0=e-closure(K0)为M的开始状态；
⑤ S t={[S i S k... S e]，其中[S i S k... S e]∈S且{S i , S k,,... S e}∩K t≠φ}
构造NFA N的状态K的子集的算法：
假定所构造的子集族为C，即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。
①开始，令e-closure(K0)为C中唯一成员，并且它是未被标记的。
② while （C中存在尚未被标记的子集T）do {
标记T；
for 每个输入字母a do
{
U:= e-closure(move(T,a))；
if U不在C中then
将U作为未标记的子集加在C中
}
}
例 4.3 应用左面的算法对图4.4的NFA N构造子集，步骤如下：
①首先计算ε-closure(0)，令T0=ε-closure(0)={0，1，2，4，7}，T0未被标记，它现在
是子集族C的唯一成员。
②标记T0；令T1=ε-closure(move(T0,a))={1，2，3，4，6，7，8}，将T1加入C中，
T1未被标记。
令T2=ε-closure(move (T,b))={1，2，4，5，6，7}，将T2加入C中，它未被标记。
③标记T1；计算ε-closure(move(T1,a))，结果为{1，2，3，4，6，7，8}，即T1，T1
已在C中。
计算ε-closure(move(T1,b))，结果为{1，2，4，5，6，7，9}，令其为T3，T3加至C 中，它未被标记。
④标记T2，计算ε-closure(move(T2,a))，结果为{1，2，3，4，6，7，8}，即T1，T1
已在C中。
计算ε-closure(move(T2,b))，结果为{1，2，4，5，6，7}，即T2，T2已在C中。
⑤标记T3，计算ε-closure(move(T3,a))，结果为{1，2，3，4，6，7，8}，即T1。
计算ε-closure(move(T3,b))，结果为{1，2，4，5，6，7，10}，令其为T4，加入C中，T4未被标记。
⑦标记T4，计算ε-closure(move(T4,a))，结果为{1，2，3，4，6，7，8}，即T1
计算ε-closure(move(T4,b))结果为{1，2，4，5，6，7}，即T2。
至此，算法终止共构造了五个子集：
T0={0，1，2，4，7} T1={1，2，3，4，6，7，8}
T2={1，2，4，5，6，7} T3={1，2，4，5，6，7，9}
T4={1，2，4，5，6，7，10}
那么图4.4的NFA N构造的DFA M为
① S={[T0]，[T1]，[T2]，[T3]，[T4]}
② Σ={a,b}
③ D([T0]，a)=[T1] D([T2]，a)=[T1]
D([T0]，b)=[T2] D([T2]，b)=[T2]
D([T1]，a)=[T1] D([T3]，a)=[T1]
D([T1]，b)=[T3] D([T3]，b)=[T4]
D([T4],a)=[T1]
D([T4]，b)=[T2]
④ S0=[T0]
⑤ S t=[T4]
不妨将[T0]，[T1]，[T2]，[T3]，[T4]重新命名，以利于书写，或用A，B，C，D，E或
用0，1，2，3，4分别表示。若采用后者，该DFA M的状态转换图如图4.6所示。图 4.6
DFA M又例：将下图的
NFA确定化
划分子集及重新命名：
确定化后的自动机：
4.3.4 确定有穷自动机的化简
我们说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两
个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。
所谓有穷自动机的多余状态，是指这样的状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。例如图4.7(a)的有穷自动机M中的状态s4便是多余状态。
在有穷自动机中，两个状态s和t等价的条件是：
①一致性条件状态s和t必须同时为可接受状态或不可接受状态。
②蔓延性条件对于所有输入符号，状态s和状态t必须转换到等价的状态里。
如果有穷自动机的状态s和t不等价，则称这两个状态是可区别的。显然在图4.6的DFA M中，状态0和4是可区别的，因为状态4是可接受态(终态)，而0是不可接受态。又如状态2和3是可区别的，因为状态2读出b后到达2，状态3读出b后到达4，而2和4是不等价的。
图 4.7 消除多余状态
对于给定的有穷自动机，如果它含有多余状态，可以非常简单地将多余状态消除，而得到与它等价的有穷自动机，例如图4.7(a)的状态s4连同状态s4射出的两个弧消掉，得到如图4.7(b)的有穷自动机。而在图4.7(b)中，状态s6和s8也是不能从开始状态经由任何输入串而到达的，也将它们连同由它们射出的弧消除而得到如图4.7(c)的有穷自动机。
确定有穷自动机的化简就是指DFA的最小化，也就是寻求最小状态DFA
简言之，最小状态DFA满足：
没有多余状态（死状态）
没有两个状态是互相等价（不可区别）
下图的DFA中，没有多余状态。考察状态C和D，首先C和D同是终态，其次在读入a后分别到达C和F，而C和F也同是终态，C和F读入a后都到达C，读入b后都到达E，所以C和D等价。
确定有穷自动机的化简方法有很多，我们介绍一个方法，叫做"分割法"：把一个DFA(不含多余状态)的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。通过将此方法施于图4.8的DFA M上来做一介绍。
DFA的最小化
对于一个DFA M =（K,∑,f, k0,,k t)，存在一个最小状态DFA M?=（K?,∑,f?,k0?,k t?)，,使L(M?)=L(M). 算法的核心
把M的状态集K分成不相交的子集。
结论：接受L的最小状态有穷自动机不计同构是唯一的。
DFA的最小化算法
f4-3-2.swf
过程PP：构造∏new
①对∏每一个状态组G进行下述工作：
将G划分为子组。G的两个状态s和t分在同一子组的充要条件是：对所有的输入符号a，状态s和t的a转换都是∏的同一组中的状态。
②形成的所有子组成为∏new的状态组。
图4.8 DFA M和DFA M'
例4.4将图4.8中的DFA M最小化。
首先将M的状态分成两个子集：一个由终态(可接受态)组成，一个由非终态组成，这个初始划分P0为：P0=({1，2，3，4}，{5，6，7})，显然第一个子集中的任何状态都与第二个子集中的任何状态不等价。
现在观察第一个子集{1，2，3，4}，在读入输入符号a后，状态3和4分别转换为第一个子集中所含的状态1和4，而1和2分别转换为第二个子集中所含的状态6和7，这就意味着{1，2}中的状态和{3，4}中的任何状态在读入a后到达了不等价的状态，因此{1，2}中的任何状态与{3，4}中的任何状态都是可区别的，因此得到了新的划分P1如下：P1=({1，2}{3，4}{5，6，7})
下面试图在P1中寻找一个子集和一个输入符号使得这个子集中的状态可区别，P1中的子集{3，4}对应输入符号a将再分割，而得到划分P2=({1，2}，{3}，{4}，{5，6，7})。
P2中的{5，6，7}可由输入符号a或b而分割，得到划分P3=({1，2}，{3}，{4}，{5}，{6，7})。
经过考察，P3不能再划分了。令1代表{1，2}消去2，令6代表{6，7}，消去7，我们便得到了图4.8(b)的DFA M′，它是4.8(a)的DFA M的最小化。
比起原来的有穷自动机，化简了的有穷自动机具有较少的状态，因而在计算机上实现起来将简洁些。
DFA的最小化—例子
4.4词法分析程序的自动构造
对有穷自动机和正规表达式进行了上述讨论之后，我们介绍词法分析程序的自动构造方法，这个方法基于有穷自动机和正规表达式的等价性，即：
对于∑上的一个NFA M，可以构造一个∑上的正规式R，使得L(R)=L(M)。对于∑上的一个正规式R，可以构造一个∑上的NFA M，似的L(M)=L(R)。
下面介绍从Σ上的一个正规式R构造Σ上的一个NFA M，使得L(M)=L(R)的方法。
我们所介绍的方法称为"语法制导"的方法，即按正规式的语法结构指引构造过程，首
先将正规式分解成一系列子表达式，然后使用如下规则为R构造NFA，对R的各种语法结构的构造规则具体描述如下：
①(a)对于正规式，所构造的NFA为：
(b) 对于正规式ε，所构造的NFA为：
(c) 对于正规式a，a∈Σ，所构造的NFA为：
②若s，t为Σ上的正规式，相应的NFA分别为N(s)和N(t),则
(a) 对正规式R=s|t，所构造的NFA(R)如下：
其中x是NFA(R)的初态，y是NFA(R)的终态，x到N(s)和N(t)的初态各有一ε弧，从N(s)和N(t)的终态各有一ε弧到y，现在N(s)和N(t)的初态或终态已不作为N(R)的初态和终态了。
(b) 对正规式R=st，所构造的NFA(R)为：
其中N(s)的初态成了N(R)的初态，N(t)的终态成了N(R)的终态。N(s)的终态与N(t)的
编译原理实验报告实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：13软件四 姓名：丁越 学号： 电子邮箱： 实验地点：秋白楼B720 实验成绩： 日期：2016年3 月18 日
一、实验目的 通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析 程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 （1）主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字 后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中 （编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上 送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical，它根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符 k表示关键字；i表示标识符；c表示常数；p表示分界符；s表示运算符（编程时类号分别为 1，2，3，4，5）。 对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有 该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数 变为二进制形式存入数组中 ci中，并记录其在表中的位置。 lexical过程中嵌有两个小过程：一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；另一个名为error，当出现错误时，调用这个过程， 输出错误编号。 2.实践部分
编译原理实验--词法分析器 实验一词法分析器设计 【实验目的】 1(熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。 2(复习高级语言，进一步加强用高级语言来解决实际问题的能力。 3(通过完成词法分析程序，了解词法分析的过程。 【实验内容】 用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符 串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果(基本字， 运算符，标识符，常数以及界符)输出。 【实验流程图】
【实验步骤】 1(提取pl/0文件中基本字的源代码 while((ch=fgetc(stream))!='.') { int k=-1; char a[SIZE]; int s=0; while(ch>='a' && ch<='z'||ch>='A' && ch<='Z') { if(ch>='A' && ch<='Z') ch+=32; a[++k]=(char)ch; ch=fgetc(stream); } for(int m=0;m<=12&&k!=-1;m++) for(int n=0;n<=k;n++) {
if(a[n]==wsym[m][n]) ++s; else s=0; if(s==(strlen(wsym[m]))) {printf("%s\t",wsym[m]);m=14;n=k+1;} } 2(提取pl/0文件中标识符的源代码 while((ch=fgetc(stream))!='.') { int k=-1; char a[SIZE]=" "; int s=0; while(ch>='a' && ch<='z'||ch>='A' && ch<='Z') { if(ch>='A' && ch<='Z') ch+=32; a[++k]=(char)ch; ch=fgetc(stream); } for(int m=0;m<=12&&k!=-1;m++) for(int n=0;n<=k;n++) { if(a[n]==wsym[m][n]) ++s; else s=0; if(s==(strlen(wsym[m]))) {m=14;n=k+1;} } if(m==13) for(m=0;a[m]!=NULL;m++) printf("%c ",a[m]);
实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表
编译技术 班级网络0802 学号3080610052姓名叶晨舟 指导老师朱玉全2011年 7 月 4 日
一、目的 编译技术是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。 二、任务及要求 基本要求： 1．词法分析器产生下述小语言的单词序列 这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号种别编码助记符内码值 DIM IF DO STOP END 标识符 常数（整）= + * ** ， （ ）1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - - 内部字符串 标准二进形式 - - - - - - 对于这个小语言，有几点重要的限制： 首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。 再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为
编译技术实验报告 实验题目：词法分析 学院：信息学院 专业：计算机科学与技术学号： 姓名：
一、实验目的 (1)理解词法分析的功能； (2)理解词法分析的实现方法； 二、实验内容 PL0的文法如下 …< >?为非终结符。 …::=? 该符号的左部由右部定义，可读作“定义为”。 …|? 表示…或?，为左部可由多个右部定义。 …{ }? 表示花括号内的语法成分可以重复。在不加上下界时可重复0到任意次 数，有上下界时可重复次数的限制。 …[ ]? 表示方括号内的成分为任选项。 …( )? 表示圆括号内的成分优先。 上述符号为“元符号”，文法用上述符号作为文法符号时需要用引号…?括起。 〈程序〉∷=〈分程序〉． 〈分程序〉∷= [〈变量说明部分〉][〈过程说明部分〉]〈语句〉 〈变量说明部分〉∷=V AR〈标识符〉{，〈标识符〉}：INTEGER； 〈无符号整数〉∷=〈数字〉{〈数字〉} 〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉} 〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}； 〈过程首部〉∷=PROCEDURE〈标识符〉； 〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉 〈赋值语句〉∷=〈标识符〉∶=〈表达式〉 〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END 〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉 〈表达式〉∷=〈项〉{〈加法运算符〉〈项〉} 〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')' 〈加法运算符〉∷=+|- 〈乘法运算符〉∷=* 〈关系运算符〉∷=<>|=|<|<=|>|>= 〈条件语句〉∷=IF〈条件〉THEN〈语句〉 〈字母〉∷=a|b|…|X|Y|Z 〈数字〉∷=0|1|2|…|8|9 实现PL0的词法分析
词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。
3.1 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。
词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序，设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 各种单词符号对应的种别码： 表各种单词符号对应的种别码 词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根
据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。
词法分析 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 扫描子程序主要部分流程图 其他
词法分析程序的C语言程序源代码： // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针； // 全局变量buffer与line对应保存源文件字符及其行号，char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意，第"< 编译原理实验报告 实验一 一、实验名称：词法分析器的设计 二、实验目的：1，词法分析器能够识别简单语言的单词符号 2，识别出并输出简单语言的基本字.标示符.无符号整数.运算符.和界符。 三、实验要求：给出一个简单语言单词符号的种别编码词法分析器 四、实验原理： 1、词法分析程序的算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 2、程序流程图 （1 （2）扫描子程序 3 五、实验内容： 1、实验分析 编写程序时，先定义几个全局变量a[]、token[]（均为字符串数组),c,s( char型)，i,j,k（int型），a[]用来存放输入的字符串，token[]另一个则用来帮助识别单词符号，s用来表示正在分析的字符。字符串输入之后，逐个分析输入字符，判断其是否‘#’，若是表示字符串输入分析完毕，结束分析程序，若否则通过int digit(char c)、int letter(char c)判断其是数字，字符还是算术符,分别为用以判断数字或字符的情况，算术符的判断可以在switch语句中进行，还要通过函数int lookup(char token[])来判断标识符和保留字。 2 实验词法分析器源程序： #include 理工大学信息工程与自动化学院学生实验报告 （2012 —2013学年第一学期） 一、实验目的及容 编译技术是理论与实践并重的课程，而其实验课要综合运用所学的多门课程的容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。 调试并完成一个词法分析程序，加深对词法分析原理的理解。 二、实验原理及基本技术路线图（框原理图或程序流程图） 1、待分析的简单语言的词法 （1）关键字： begin if then while do end 所有关键字都是小写。 （2）运算符和界符： := + –* / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义：ID=letter（letter| digit）* NUM=digit digit * （4）空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码 3、词法分析程序的功能 输入：所给文法的源程序字符串。 输出：二元组（syn，token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 二、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC以及VISUAL C++6.0软件。 三、实验法、步骤（或：程序代码或操作过程） （1）程序代码： #include 本代码只供学习参考： 词法分析源代码： #include 信息工程学院实验报告（2010 ~2011 学年度第一学期） 姓名：柳冠天 学号：2081908318 班级：083 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ：= + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 表2.1 各种单词符号对应的种别码 2.3 词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 实验2 词法分析程序的设计 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数0 | (（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*) 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < = ( ) ； 关键字if then else while do 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 五、实验步骤 1、根据正规式，画出状态转换图； 编译原理实验报告 实验一 实验题目：词法分析 指导老师：任姚鹏 专业班级：计算机科学与技术系网络工程方向1002班姓名：xxxx 2013年 4月13日 实验类型__验证性__ 实验室_软件实验室三__ 一、实验项目的目的和任务： 了解和掌握词法分析的方法，编程实现给定源语言程序的词法分析器，并利用该分析器扫描源语言程序的字符串，按照给定的词法规则，识别出单词符号作为输出，发现其中的词法错误。 二、实验内容： 1．设计一个简单的程序设计语言（语言中有若干运算符和分界符；有若干关健字；若干标识符及若干常数） 2．确定编译中使用的表格、词法分析器的输出形式、标识符与关键字的区分方法。 3．把词法分析器设计成一个独立的过程。 三、实验要求: 1.从键盘上输入源程序； 2.处理各单词，计算个单词的值和类型； 3.输出个单词名、单词的值和类型。 四、实验代码 #include 一、实验目的 了解词法分析程序的两种设计方法：1.根据状态转换图直接编程的方式；2.利用DFA 编写通用的词法分析程序。 二、实验内容及要求 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 2．编写DFA模拟程序 算法如下： DFA（S=S0,MOVE[][],F[],ALPHABET[]） /*S为状态，初值为DFA的初态，MOVE[][]为状态转换矩阵，F[] 为终态集，ALPHABET[] 为字母表，其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar（）；//读 i=0； while（nextchar！=NULL）//NULL代表此类单词 { if （nextcha r！∈ALPHABET[]）{ERROR（“非法字符”），return（“非法字符”）；} S=MOVE[S][nextchar] //下一状态 if（S=NULL）return（“不接受”）；//下一状态为空，不能识别，单词错误 wordbuffer[i]=nextchar ；//保存单词符号 i++； nextchar=getchar（）； } Wordbuffer[i]=‘\0’; 编译原理词法分析程序实现实验报告实验一词法分析程序实现 一、实验内容 选取无符号数的算术四则运算中的各类单词为识别对象，要求将其中的各个单词识别出来。输入:由无符号数和+，,，*，/, ( , ) 构成的算术表达式，如 1.5E+2,100。输出:对识别出的每一单词均单行输出其类别码(无符号数的值暂不要求计算)。二、设计部分 因为需要选取无符号数的算术四则运算中的各类单词为识别对象，要求将其中的各个单词识别出来，而其中的关键则为无符号数的识别，它不仅包括了一般情况下的整数和小数，还有以E为底数的指数运算，其中关于词法分析的无符号数的识别过程流程图如下: 输入字符p指向第一个字符 符号识别*p=+||-||*||/ YYNN*p=0~9*p=E*p=0~9||"." N无效符号Y *p=“.”GOTO 2 GOTO 1 GOTO 1: NY无符号数GOTO 1*p=0~9*p='/0' YN P++NNP++*p=E*p='+'||'-' YY P++P++continue YY *p=0~9*p=0~9 NN 无符号数无符号数 P++P++ continuecontinue GOTO 2: GOTO 2 *p=Econtinue Y 无符号数 P++ continue 三、源程序代码部分 #include 编译原理实验 词 法 分 析 程 序 实验一：词法分析程序 1、实验目的 从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号形式的中间程序。 2、实验内容 表C语言子集的单词符号及内码值 单词符号种别编码助记符内码值 while 1 while -- if 2 if -- else 3 else -- switch 4 switch -- case 5 case -- 标识符 6 id id在符号表中的位置 常数7 num num在常数表中的位置 + 8 + -- - 9 - -- * 10 * -- <= 11 relop LE < 11 relop LT == 11 relop LQ = 12 = -- ; 13 ; -- 输入源程序如下 if a==1 a=a+1; else a=a+2; 输出对应的单词符号形式的中间程序 3、实验过程 实验上机程序如下： #include "stdio.h" #include "string.h" int i,j,k; char s ,a[20],token[20]; int letter() { if((s>=97)&&(s<=122))return 1; else return 0; } int Digit() {if((s>=48)&&(s<=57))return 1; else return 0; } void get() { s=a[i]; i=i+1; } void retract() {i=i-1;} int lookup() { if(strcmp(token, "while")==0) return 1; else if(strcmp(token, "if")==0) return 2; else if(strcmp(token,"else")==0) return 3; else if(strcmp(token,"switch")==0) return 4; else if(strcmp(token,"case")==0) return 5; else return 0; } void main() { printf("please input you source program,end('#'):\n"); i=0; do { i=i+1; scanf("%c",&a[i]); }while(a[i]!='#'); i=1; memset(token,0,sizeof(char)*10); j=0; get(); while(s!='#') { if(s==' '||s==10||s==13) get(); else { switch(s) 编译原理 实验报告 实验名称：词法分析及语法分析专业班级： 姓名： 学号： 完成日期： 实验一、sample语言的词法分析 一、实验目的 给出SAMPLE文法规范，要求编写SAMPLE语言的词法分析程序。 二、实验准备 了解sample语言单词的定义，选择任一种编程语言实现词法分析。 三、实验内容 给出SAMPLE语言文法，输出单词（关键字、专用符号以及其它标记）。 1、格式 输入：源程序文件。输出：关键字、专用符号以及其它标记。 2、实现原理 程序中先判断这个句语句中每个单元为关键字、常数、运算符、界符，对与不同的单词符号给出不同编码形式的编码，用以区分之。 3、实验方法 读懂Sample源代码，自己重点独立实现对常量的判别。 四、实验设计 1、设计SAMPLE语言的词法分析器 A、字符集定义 1． <字符集> → <字母>│<数字>│<单界符> 2． <字母> → A│B│…│Z│a│b│…│z 3． <数字> → 0│1│2│…│9 4． <单界符> → +│-│*│/│=│<│>│(│)│[│]│:│. │; │, │' B、单词集定义 5．<单词集> → <保留字>│<双界符>│<标识符>│<常数>│<单界符> 6．<保留字> → and│array│begin│bool│call│case│char│constant│dim│do│else │end│false│for│if│input│integer│not│of│or│output│procedure│program │read│real│repeat│set│stop│then│to│true│until│var│while│write 7．<双界符> → <>│<=│>=│:= │/*│*/│.. 8．<标识符> → <字母>│<标识符> <数字>│<标识符> <字母> 9．<常数> → <整数>│<布尔常数>│<字符常数> 10．<整数> → <数字>│<整数> <数字> 11．<布尔常数> → true│false 12．<字符常数> → ' 除 {'} 外的任意字符串 ' 2、词法分析系统流程设计 南华大学 计算机科学与技术学院实验报告 （2018~2019学年度第二学期） 课程名称编译原理 实验名称词法分析器的设计与 实现 姓名学号 专业班级 地点教师 1.实验目的及要求 实验目的 加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。 实验要求 1.对单词的构词规则有明确的定义； 2.编写的分析程序能够正确识别源程序中的单词符号； 3.识别出的单词以<种别码，值>的形式保存在符号表中，正确设计和维护 符号表； 4.对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误 提示，保证顺利完成整个源程序的词法分析； 2.实验步骤 1.词法分析规则 <标识符>::=<字母>|<标识符><字母>|<标识符><数字> <常数>::=<数字>|<数字序列><数字> <数字序列>::＝<数字序列><数字>|<数字>|<.> <字母>::=a|b|c|……|x|y|z <数字>::=0|1|2|3|4|5|6|7|8|9 <运算符>::=<关系运算符>|<算术运算符>|<逻辑运算符>|<位运算符>|<赋值运算符> <算数运算符>::＝+|-|*|／|...|-- <关系运算符>::＝<|>|!=|>=|<=|== <逻辑运算符>::=&&| || |！ <位运算符>::=&| | |！ <赋值运算符>::==|+=|-=|/=|*= <分界符>::＝,|;|(|)|{|}|：| // |/**/ <保留字>::＝main|if|else|while|do|for|...|void 实验1-4 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法：1.根据状态转换图直接编程的方式；2.利用DFA 编写通用的词法分析程序。 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 2．编写DFA模拟程序 算法如下： DFA（S=S0,MOVE[][],F[],ALPHABET[]） /*S为状态，初值为DFA的初态，MOVE[][]为状态转换矩阵，F[] 为终态集，ALPHABET[] 为字母表，其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar（）；//读 i=0； while（nextchar！=NULL）//NULL代表此类单词 { if （nextcha r！∈ALPHABET[]）{ERROR（“非法字符”），return（“非法字符”）；} S=MOVE[S][nextchar] //下一状态 if（S=NULL）return（“不接受”）；//下一状态为空，不能识别，单词错误 wordbuffer[i]=nextchar ；//保存单词符号 i++； nextchar=getchar（）； } Wordbuffer[i]=‘\0’; If（S∈F）return（wordbuffer）；//接受 Else return（“不接受”）；编译原理实验报告(词法分析器语法分析器)
编译原理实验报告一 简单样本语言的词法分析器
编译原理实验词法分析语法分析
编译原理词法分析和语法分析报告+代码(C语言版)
编译原理实验报告2词法分析程序的设计
编译原理实验(词法分析)
编译原理词法分析器
编译原理词法分析程序实现实验报告
编译原理实验 词法分析&语法分析程序
编译原理词法分析及语法分析
编译原理实验-词法分析器的设计与实现.docx
(完整版)《编译原理》词法分析程序设计方案
相关主题
文本预览