2.2 词法分析器的设计
下面将词法分析器作为一个独立的子程序来考虑其设计。本节主要探讨实现词法分析器的关键技术和词法分析器的手工实现。
2.2.1 输入及其处理
词法分析器的结构如图2-3所示。
词法分析器首先将源程序文本输入一个缓冲区中，该缓冲区称为输入缓冲区，单词符号的识别可以直接在输入缓冲区中进行。但在通常情况下为了单词识别的方便性，需要对输入的源程序字符串做一个预处理。对于许多程序语言来说，空格、制表符、换行符等编辑性字符只有出现在符号常量中时才有意义；注释几乎可以出现在程序中的任何地方。但编辑性字符和注释的存在大多只是为了改善程序的易读性和易理解性，不影响程序本身的语法结构和实际意义。通常在词法分析阶段可以通过预处理将它们删除。因此可以设计一个预处理子程序来完成上述工作，每当词法分析器调用该预处理子程序时，其便处理一串固定长度的源程序字符串，并将处理结果放在词法分析器指定的缓冲区中，称为扫描缓冲区。接下来单词符号的识别就可以直接在该扫描缓冲区中进行，而不必考虑其他的杂务。
词法分析器对扫描缓冲区进行扫描时通常使用两个指针，即开始指针和搜索指针。其中，开始指针指向当前正在识别的单词的起始位置，搜索指针用于向前搜索以寻找该单词的终点位置，两个指针之间的符号串就是当前已经识别出来的那部分单词。刚开始，两个指针都指向下一个要识别的单词符号的开始位置，然后，搜索指针向前扫描，直到发现一个单词符号为止，一旦发现一个单词，搜索指针指向该单词的右部，在处理完这个单词以后，两个指针同时指向下一个要识别的单词符号的起始位置。
为了尽可能避免在单词符号识别过程中，单词符号超过缓冲区边界，通常将扫描缓冲区划分为长度相等的两个区，两区进行互补使用，假设两区的长度都为N。如果搜索指针搜索到半区的边缘但尚未找到单词的终点，那么就调用预处理程序，将后续的N个输入字符输入另一半区。
2.2.2 单词符号的描述：正规文法和正规式
为了便于后面讨论的展开，首先定义一些相关概念。
定义2.1（字母表、字母和字） 字母表是一个非空有穷集合，记作∑。字母表∑中的元素称为该字母表的一个字母，也称为字母表上的字符（或符号）。字母表∑中符号组成的有穷序列称为∑上的字符串，也称为∑上的字或者句子，不包含任何字符的序列称为空字，记作ε。
∑+表示∑上的所有非空字组成的集合，∑*表示∑上的所有字组成的集合。
例2.2 {0，1}就是一个字母表，0110、ε是该字母表上的字。
对于一种高级程序设计语言而言，它的字母表就是该语言的有效字符集。
定义2.2（语言和句子） 设∑是一个字母表，∑*的任意子集L称为字母表∑上的一个语言。对于?x∈L，x称为L的一个句子。
例2.3 下面集合均为字母表{0，1}上的语言
{0, 1}
{00, 11}
{0, 1, 00, 11}
{0, 1, 00, 11, 01, 10}
{00, 11}*
{01, 10}*
定义2.3（语言的乘积） 设∑1、∑2是字母表，L1?∑1*，L2?∑2*，语言L1与L2的乘积是字母表∑1?∪?∑2上的一个语言，该语言定义为：
L1L2={xy | x∈L1，y∈L2}
定义2.4（语言的幂、正闭包和克林闭包） 设∑是一个字母表，?L?∑*，L的n次幂是一个语言，该语言定义为：
1）当n = 0时，Ln = {ε}；
2）当n≥1时，Ln = Ln-1L。
L的正闭包L+是一个语言，该语言定义为：
L+=L?∪?L2?∪?L3?∪?L4?∪?…
L的克林闭包L*也是一个语言，该语言定义为：
L*= L0?∪?L?∪?L2?∪?L3?∪?L4?∪?…
设∑是一个字母表，基于上述定义，∑+可表示为：
∑+=∑?∪?∑2?∪?∑3?∪?∑4?∪?…
∑*可表示为：
∑*=∑0?∪?∑+ =∑0?∪?∑1?∪?∑2?∪?∑3?∪?…
例2.4 设{0，1}是一个字母表，则
{0，1}3 ={000，001，010，011，100，101，110，111}
{0，1}+ = {0，1，00，01，10，11，000，001，010，011，100，…}
{0，1}* = {ε，0，1，00，01，10，11，000，001，010，011，100，…}1. 正规文法
文法是用来描述语言语法结构的形式规则，而单词符号是程序设计语言的基本语法单位，如果把每类单词都看作一种语言，那么多数程序设计语言的单词符号构词规则都可以用正规文法来描述。
定义2.5（正规文法） 正规文法G定义为一个四元组（VT，VN，P，S），其中
1）VT为终结符组成的非空有限集。
2）VN为非终结符组成的非空有限集，VN和VT不含公共的元素，即VN?∩?VT = ?。
3）P为产生式组成的集合，每个产生式形如A→αB 或 A→α，其中，α∈VT*，A，B∈VN。
4）S称为文法的开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。
正规文法所描述的是VT上的正规集。若正规文法G的产生式集P中每个产生式都限定为具有如下形式：
A→a或A→aB，a∈VT?∪?{ε}，A，B∈VN
则称G为右线性文法。显然，右线性文法是特殊的正规文法，而任何由正规文法产生的语言都能被右线性文法产生，因此右线性文法类和正规文法类是等价的。任何由右线性文法产生的语言又都能被如下形式的文法G = （VT，VN，P，S）产生，其中VT、VN、S和右线性文法中的定义相同，P中的产生式仅为A→a和A→Ba两种形式，其中a∈VT?∪?{ε}，A、B∈VN，该文法称为左线性文法。反之任何由左线性文法产生的语言都能被右线性文法产生。因此有时也把右线性文法和左线性文法称为正规文法。
为了书写简单起见，通常将具有相关左部的产生式，如
P→α1
P→α2
…
P→αn
缩写为 P→α1 |α2 | … | αn，其中，“|”读成“或”，每个αi称为P的一个候选式。表示一个文法时，通常只给出开始符号和产生式。
下面给出C语言的标识符、无符号整数和无符号数的正规文法。
例2.5 C语言标识符的正规文法。C语言的标识符集是由以字母或下划线开始的字母、数字和下划线组成的串的集合，生成该集合的正规文法为G(id)：
id→A rid | B rid | … | Z rid | a rid | b rid | … | z rid | _ rid
rid→ε | A rid | B rid | … | Z rid | a rid | b rid | … | z rid | _ rid
0 rid | 1 rid | 2 rid | … | 9 rid
其中，id和rid为文法的非终结符，每个产生式的左部都只有一个非终结符，右部是由一个终结符和一个非终结符或者ε组成，显然这是一个正规文法，并且是右线性文法。
通常，在书写上述正规文法时，会用letter表示字母（即letter→A | … | Z | a | …| z），用digit表示数字（即digit→0 | 1 | … | 9），这样C语言标识符的正规文法可以表示为如下形式G(id)：
id→letter rid |_ rid
rid→ε | letter rid | _ rid | digit rid（2.1）
在今后如无特殊说明，在书写正规文法时，我们都用letter表示字母，用digit表示
数字。
例2.6 Pascal语言无符号整数的正规文法。无符号整数整数的正规文法为G(digits)：
digits→digit rint
rint→ε | digit rint
例2.7 Pascal语言无符号数的正规文法。无符号数是形如1946、11.28、63E8、1.99E-6这样的符号串，生成无符号串的正规文法G(num)如下：
num→digit num1
num1→digit num1 | . num2 | E num4 | ε
num2→digit num3
num3→digit num3 | E num4 | ε
num4→+ digits | - digits |digit num5
digits→digit num5
num5→digit num5 | ε（2.2）
其中：num1表示无符号数的第一个数字之后的部分，num2表示小数点以后的部分，num3表示小数点后第一个数字以后的部分，num4表示E之后的部分，digits表示数字组成的非空串，num5表示数字组成的串，包括空串。
2. 正规式
除了可以利用正规文法来表示单词符号外，还可以利用正规式来表示单词符号。正规式又称为正则表达式，其也是描述正规集的工具。下面是正规式和正规集的递归定义。
定义2.6（正规式和正规集） 对于给定的字母表∑，正规式和正规集的递归定义如下：
1）ε和?都是∑上的正规式，它们所表示的正规集为{ε}和?。
2）任何a∈∑，a是∑上的正规式，它所表示的正规集为{a}。
3）假定r1和r2都是∑上的正规式，它们所表示的正规集为L(r1)和L(r2)，则
① (r1|r2)为正规式，它所表示的正规集为L(r1)?∪?L(r2)。
② (r1.r2)为正规式，它所表示的正规集为L(r1)L(r2)。
③ (r1)*为正规式，它所表示的正规集为(L(r1))*。
仅由有限次使用上述三个步骤而定义的表达式才是∑上的正规式，仅由这些正规式表示的子集才是∑上的正规集。
正规式间的运算符“|”表示或，“·”表示连接（通常可省略），“*”表示闭包，使用括号可以改变运算的次序。如果规定“*”优先于“·”，“·”优先于“|”，则在不出现混淆的情况下括号也可以省去。
例2.8 C语言标识符的正规式。C语言标识符的正规式为(letter|_)(letter|_|digit)*，其所表示的正规集即为所有以字母或下划线开头的字母、数字和下划线组成的串的集合。
例2.9 Pascal语言无符号整数的正规式。无符号整数的正规式为digit(digit)*。其所表示的正规集为：
L(digit(digit)*)= L(digit)L(digit)*= L(digit)(L(digit))*={0～9数字组成的字符串}
例2.10 Pascal语言无符号数的正规式。无符号数的正规式为digit digit*(.digit digit*|ε)(E(+ | - | ε)digit digit* | ε)，其所表示的正规集为形如1946、11.28、63E8、1.99E-6的符号串组成的集合。
定义2.7（正规式的等价性） 若两个正规式r1和r2所表示的正规集相同，则称这两个正规式等价，记作r1 = r2。
例2.11 证明 b(ab)* = (ba)*b。
证明：因为L(b(ab)*) = L(b)L((ab)*) = L(b)(L(ab))* = L(b)(L(a)L(b))*
= {b}{ab}* = {b}{ε, ab, abab, ababab, …} = {b, bab, babab, bababab, …}
L( (ba)*b) = L((ba)*)L(b) = (L(ba))*L(b)= (L(b)L(a))*L(b)
= {ba}*{b}= {ε, ba, baba, bababa, …}{b}={b, bab, babab, bababab, …}
所以L(b(ab)*)=L((ba)*b)，从而b(ab)*=(ba)*b。
设r1、r2和r3为正规式，则下面代数定律成立：
1）r1|r2 = r2|r1 或运算满足交换律
2）r1 |(r2|r3) = (r1|r2)|r3 或运算满足结合律
3）r1(r2r3) = (r1r2)r3 连接运算满足结合律
4）r1(r2|r3) = r1r2|r1r3, (r2|r3)r1 = r2r1|r3 r1 连接运算对或运算满足分配律
5）εr = r, rε= r ε是连接运算的单位元（或称幺元）
在正规式中，由于某些结构频繁出现，为了方便起见，可以用缩写形式来表示它们。
1）一个或者多个：“+”是一元操作符，表示一个或者多个。比如，a+表示由一个或多个a构成的所有串的集合。
假设r为一个正规式，则有如下代数恒等式：
r* = r+ | ε，r+ = r*r = rr*
2）零个或一个：“?”是一元操作符，表示零个或一个。比如，r?=r | ε。
使用“+”和“?”，可以将无符号数正规式重写为“digit+(.digit+)?(E(+|-)?digit+)?”。
3）字符类：缩写的字符类[a-z]表示正规式a | b | … | z。
使用字符类可将无符号整数用正规式“[0-9][0-9]*”描述。
3.正规定义式
为了表示方便，可以对正规式进行命名，并用这些名字来引用相应的正规式。
定义2.8（正规定义式） 令∑是基本符号的字母表，那么正规定义式是如下形式的序列
d1→r1
d2→r2
…
dn→rn
其中，各个di的名字都不同，每个ri都是∑?∪?{d1，d2，…，di-1}上的正规式。
例2.12 C语言标识符集合的正规定义式：
letter_→A | B | … | Z | a | b | … | z | _
digit→0 | 1 | … | 9
id→letter_( letter_ | digit )*
例2.13 Pascal语言无符号数集的正规定义式：
digit→0 | 1 | … | 9
digits→digit digit*
optional_fraction→.digits | ε
optional_exponent→( E ( + | - | ε ) digits ) | ε
number→digits optional_fraction optional_exponent
4.正规文法和正规式的等价性
正规文法与正规式等价，也即对任意一个正规文法，存在一个定义同一语言的正规式，反之，对任意一个正规式存在一个定义同一语言的正规文法。有些语言可以很容易用正规文法来定义，而有些语言则可以很容易地用正规式来定义，下面介绍两者之间的等价性转化。
算法2.1 将正规文法转化为等价的正规式
输入：正规文法(VT，VN，P，S )
输出：与(VT，VN，P，S )等价的正规式r
步骤：
1.给定一个正规文法(VT，VN，P，S )，利用以下转换规则对文法的产生式进行转换。
① 若A→xB∈P，并且B→y∈P，则将两个产生式转化为A = xy。
② 若A→xA∈P，并且A→y∈P，则将两个产生式转化为A = x*y。
③ 若A→x∈P，并且A→y∈P，则将两个产生式转化为A = x | y。
2.不断应用规则①～③，直至只剩下一个开始符号定义的正规定义式，并且正规定义式的右部不含非终结符，此时所得到的正规定义式的右部即为所求的等价正规式。
例2.14 将描述C语言标识符的正规文法（2.1）转换成与之等价的正规式。
解：利用算法2.1中规则③和连接运算关于或运算满足分配律将
rid→letter rid | _ rid | digit rid
转化为
rid→(letter | _ | digit) rid
从而有
rid→(letter| _ | digit) rid | ε
由算法2.1中规则②可得
rid→(letter | _ | digit)*
同理，利用算法2.1中规则③和连接运算关于或运算满足分配律将
id→letter rid |_ rid
转化为
id→(letter |_) rid
由算法2.1中规则①将
id→(letter |_) rid，rid→(letter | _ | digit)*
转化为
id→(letter|_)(letter|_|digit)*
则(letter|_)(letter|_|digit)*即为所求正规式。算法2.2 将∑上的正规式r转化为等价的正规文法（VT，VN，P，S）
输入：∑上的正规式r
输出：与r等价的正规文法（VT，VN，P，S）
步骤：
1.令VT = ∑，对任何正规式r，选择一个非终结符，比如S，生成S→r，并将S作为文法的开始符号。
2.按照如下规则对S→r以及分解过程中所产生的各个正规定义式进行分解。
① 若x、y是正规式，对形如A→xy的产生式，重写为A→xB，B→y，其中B为新的非终结符。
② 若x、y是正规式，对于形为A→x*y重写为A→xA，A→y?。
③ 若x、y是正规式，对于形为A→x | y重写为A→x，A→y。
3.不断应用分解规则①～③对各个正规定义式进行分解，直到每个正规定义式右端只含一个语法变量（即符合正规文法产生式的形式）为止。
例2.15 将描述C语言标识符的正规式(letter | _)(letter |_ | digit)*转换成相应的正规文法。
解：根据算法2.2，引入id作为要转化的正规文法的开始符号，并生成
id→(letter | _)(letter | _ | digit)*
利用算法2.2中的规则①和规则②，引入非终结符rid，将上述正规式分解为
id→(letter | _) rid
rid→(letter | _ | digit) rid | ε
执行连接运算对“|”运算的分配律可得
id→letter rid | _ rid
rid→letter rid |_ rid |digit rid | ε
综上可得，产生C语言标识符的正规文法为({letter, _, digit}, {id, rid}, P, id)，其中P是由如下产生式组成的集合
id→letter rid | _ rid
rid→letter rid | _ rid | digit rid | ε
2.2.3 单词符号的识别：超前搜索
由于程序设计语言中的某些单词符号可能存在公共前缀，因此，词法分析器在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。
1. 基本字识别
像Fortran语言对关键字不加保护，关键字和用户自定义的标识符或标号之间可以没有特殊的界符做间隔。为了识别关键字，就需要进行超前搜索。
例如：
1）DO99K = 1，10
2）DO99K = 1.10
前者是循环语句，相当于C语言的“for (K=1；K<=10；K++)”，其循环体为从当前语句开始到标号为99的语句结束。后者是赋值语句，相当于C语言的“DO99K=1.10”。语句1和语句2的区别在于等号之后的第一个界符：前者为逗号，后者不是逗号。为了从语句1中识别出关键字DO，必须超前扫描多个字符，直到能够确定词性为止。对于语句1和语句2，不能当发现字母D和O时就立即将其识别为关键字DO，而是应该超前扫描，跳过所有的字母和数字，看是否有等号。如果有等号，则开始的DO就有可能是关键字，继续往前搜索，若下一个界符是逗号，可将DO识别为关键字。否则，DO构不成关键字，即它只是用户自定义的标识符的前两个字符。
2. 标识符识别
多数语言将标识符定义为以字母开头的字母和数字串，而且在程序中标识符后跟界符或算符，因此标识符的识别大多没有困难。
3.常数识别
按照值的类型不同，常数可以划分为算术常数、逻辑常数和字符串常数。其中，算术常数是指数值型常数，通常包括整数、实数和复数。逻辑常数只有真和假两种取值。字符串常数是程序设计语言中的有效字符组成的任意字符串，为了与标识符相区别，有时候用引号把字符串常数括起来。例如，“string”就是一个由6个字母组成的字符串常数。
多数语言的算术常数可以直接识别，但有些语言的算术常数也要超前搜索。比如，像Fortran程序段中6.EQ.M，只有超前扫描到Q时才能断定6是一个整常数，这是因为实数6.E3与6.EQ.M的前三个字符完全一样，其中6.EQ.M表示“6=M”是否成立的关系表达式，而6.E3是表示常数6.0×103。
逻辑常数和用引号括起来的字符串常数通常都很容易识别，但是对于某些单词的识别需要理解词头的含义，比如，Fortran语言的文字常量nHa1a2…an，当词法分析器读到后面紧跟H的无符号型整常数时，首先需将这个常数的值翻译出来，然后把H后面的n个（n为该整常数的值）字符取出来，作为字符串常数输出。
4.算符和界符的识别
对于由多个字符组成的算符或界符，如++、:=、.EQ.、--、>=，词法分析器需要将它们识别为一个单词符号，而这些单词与其他单词拥有相同的前缀。比如“+”是“++”和“+”的公共前缀。因此也需要利用超前搜索技术来进行识别。
2.2.4 状态转换图及其实现
构造词法分析器首先需要将描述单词符号的正规文法或者正规式转化为状态转换图，然后再依据状态转换图进行词法分析器的构造。所谓的状态转换图是一个有限方向图，结点代表状态，用圆圈表示；状态之间用箭弧连接，箭弧上的标记（字符）代表射出结点状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态（用双圈表示）。
1.由正规文法构造状态转换图
这里以右线性文法为例，说明如何构造状态转换图。具体见算法2.3。
算法2.3 构造右线性文法的状态转换图
输入：右线性文法G = （VT，VN，P，S）
输出：文法G的状态转换图
步骤：
1.状态集合的构成。
对文法G的每一个非终结符号设置一个对应的状态，文法的开始符号对应的状态称为初态，增加一个新的状态，称为终态。
2.状态之间边的形成。
对于右线性文法G中所包含三种形式的产生式，即A→aB，A→a，A→ε，执行如下操作：
① 对于形如A→aB的产生式，画一条从状态A到状态B标记为a的边。
② 对于形如A→a的产生式，画一条从状态A到终态标记为a的边。
③ 对于形如A→ε的产生式，画一条从状态A到终态标记为ε的边。
例2.16 依据算法2.3，对于产生C语言标识符的正规文法（2.1），将非终结符id和rid分别用标号为0和1的状态来表示，引入状态2表示终态。对于文法（2.1）中的产生式
id→letter rid |_ rid
从状态0到状态1画一条标记为letter | _的有向边。
对于产生式
rid→letter rid |_ rid |digit rid
从状态1到状态1画一条标记为letter | _ | digit的有向边。
对于产生式
rid→ε
从状态1到状态2画一条标记为ε的有向边。从而可以得到正规文法（2.1）的状态转换图，如图2-4所示。
例2.17 依据算法2.3，对于产生无符号数的正规文法（2.2），将非终结符num、num1、num2、num3、num4、digits、num5分别用标号为0～6的状态来表示，引入状态7表示终态。
对于产生式
num → digit num1
从状态0到状态1画一条标记为digit的有向边。
对于产生式
num1 → digit num1 | . num2 | E num4 | ε
分别从状态1到状态1画一条标记为digit的有向边，从状态1到状态2画一条标记为“.”的有向边，状态1到状态4画一条标记为E的有向边，状态1到状态7画一条标记为ε的有向边。对于剩余的产生式做类似处理，可以得到正规文法（2.2）的状态转换图，如图2-5所示。
图2-5 正规文法（2.2）的状态转换图
在词法分析过程中，通常为了表示一些例外情况，允许在状态转换图的某些边上标记other，若离开状态s的某条边上标记为other，则other表示离开s的其他边标记的字符以外的任意符号。这样C语言标识符和无符号数的状态转换图又可以分别表示为图2-6和图2-7。
其中，终态结点上的标记“*”表示多读了一个与当前单词符号无关的字符，由于这个无关字符是下一个单词的开始符号，所以必须把它退还给输入串。
图2-7 无符号数的状态转换图
2.由正规式构造状态转换图
根据正规式的意义和状态转换图中状态及其变换的意义，下面是正规式到状态转换图的基本转化规则。其中a、r、s都是∑上的正规式，并且a∈∑。
1）?对应的状态转换图如图2-8a所示。
2）ε对应的状态转换图如图2-8b所示。
3）a对应的状态转换图如图2-8c所示。
4）r | s对应的状态转换图如图2-8d所示。
5）rs对应的状态转换图如图2-8e所示。
6）r*对应的状态转换图如图2-8f所示。
7）r+对应的状态转换图如图2-8g所示。
8）rs*对应的状态转换图如图2-8h所示。
图2-8 典型的正规式所对应的状态转换图
算法2.4 构造正规式的状态转换图
输入：正规式r
输出：正规式r的状态转换图
步骤：
1.设置一个开始状态和一个终止状态，从开始状态到终止状态引一条有向边，边上标记为待转换正规式r。
2.检查图中边的标记，如果相应的标记不是单个字符、?、ε或用“|”连接的字符，则根据基本规则1～8进行替换，直到图中不再存在不满足要求的边。按照习惯，如果一条边上标记的是?，这个边就不用画出来。
例2.18 请给出描述C语言标识符的正规式(letter|_)(letter|_|digit)*相应的状态转换图。
解：依据算法2.4，按照如下过程构造状态转换图。
1）先构造开始状态0和终止状态2，并在两状态之间添加一条标记为(letter|_)(letter|_
|digit)*的边，如图2-9a所示。
2）依据规则h，引入一个新的状态1，将标记为(letter|_)(letter|_|digit)*的边拆分为标记为letter|_和letter|_|digit的边，其中标记为letter|_|digit的边是一个圈，并在状态1和状态2之间加一条标记为ε的边，如图2-9b所示，该图即为所求状态图。
3.利用状态转换图识别单词
一个状态转换图可以用来识别或者接收某个字符串。具体过程如下：
1）从初始状态出发。
2）读入一个字符。
3）按当前字符转入下一状态。
4）重复步骤2～3直到无法继续转移为止。
在遇到读入的字符是单词的界符时，若当前状态是终止状态，说明读入的字符组成了一个单词；否则，说明输入字符串不符合词法规则。
例2.19 识别C语言标识符的状态转换图如图2-6所示，其中0为初态，2为终态。这个转换图识别标识符的过程是：从初态0出发，读入一个输入字符，如果输入字符是字母或者下划线，则转移到状态1；在状态1下读入一个输入字符，如果输入字符是字母、下划线或者数字，则仍然转移到状态1，直到读入非字母、下划线或者数字的字符，然后转移到终态2（终态2上的星号（*）表示此时还要把超前读出的字符退回，即搜索指针回调一个字符位置）。这意味着已经识别出来一个标识符，宣布识别成功。
将从状态转换图的初始状态出发到达终态的所有可能路径上的标记依次连接成的字符串所组成的集合就是该状态转换图能够识别的所有单词，此集合也就是该状态转换图所识别的语言。
大多数程序语言的单词符号都可以用状态转换图予以识别。这里以一个C语言子集作为例子，来说明如何编写词法分析程序。主要步骤是：首先给出描述该子集中各种单词符号的词法规则，其次构造其状态转换图，然后根据状态转换图编写词法分析器。
表2-1列出了这个C语言子集的所有单词符号以及它们的种别编码和内码值。由于直接使用整数编码不利于记忆，故该例中用一些称为助忆符的特殊符号来表示种别编码，每个助忆符均以$开始。
该语言子集所包含的单词符号有：
1）标识符：以字母、下划线开头的字母、数字和下划线组成的符号串。
2）关键字：标识符的子集，包括while、for、if、else、switch、case。
3）无符号整数：由0～9数字组成的字符串。
4）关系运算符：<、<=、= =。
5）算术运算符：+、*、-。
6）赋值号如“=”。
7）界符如“；”。
下面为产生所涉及单词符号的文法的产生式：
1）标识符文法：
id→letter rid |_ rid
rid→letter rid |_ rid |digit rid | ε
2）无符号整数文法：
digits→digit rdigit
rdigit→digit rdigit |ε
3）关系运算符和算术运算符的文法：
op→* | + | - | < | <equal | =equal
equal→=
4）赋值号文法：
assign_op→=
5）界符文法：
single→；
所得到的状态转换图如图2-10所示。
在状态2时，所识别出的标识符应先与表2-1的前六项逐一比较，若匹配，则该标识符是一个保留字，否则就是标识符。如果是标识符，应先查符号表，看表中是否有此标识符。若表中无此标识符，则将它登录到符号表中，然后返回其在符号表中的入口指针（地址）作为该标识符的内码值；若表中有此标识符，则返回其在符号表中的入口指针。在状态4时，应将识别的常数转换成二进制常数并将其登录到常数表，然后返回其在常数表中的入口指针作为该常数的内码值。
4.状态转换图的实现
状态转换图非常易于实现，最简单的方法是为每个状态编写一段程序。下面首先引进一组变量和过程：
1）ch 字符变量：存放最新读入的源程序字符。
2）strToken字符数组：存放构成单词符号的字符串。
3）GetChar()子程序过程：把下一个字符读入ch中。
4）GetBC()子程序过程：每次调用时，检查ch的字符是否为空白符，若是空白符，则反复调用GetChar()，直至ch中读入一非空白符。
5）Concat()子程序过程：把ch中的字符连接到strToken。
6）IsLetter()、IsDigital()和IsUnderline布尔函数：判断ch中字符是否为字母、数字或下划线。
7）Reserve()整型函数：对于strToken中的字符串查找表的前六项（即判断它是否为保留字），若它是保留字则给出它的编码，否则返回0。
8）Retract()子程序：把搜索指针回调一个字符位置。
9）InsertId整型函数：将strToken中的标识符插入符号表，返回符号表指针。
10）InsertConst整型函数：将strToken中的常数插入常数表，返回常数表指针。
11）Error( )：出现非法字符则显示出错信息。
对于不含回路的分支状态来说，可以用一个switch( )语句或一组if-else语句实现。例如，图2-11的状态i所对应的switch语句如下：
ch=GetChar( );
switch (ch)
{ case 'a':
case 'b':
…
case 'z':
…实现状态j功能的语句…;
case '0':
case '1':
…
case '9':
…实现状态k功能的语句…;
case '\':
…实现状态l功能的语句…;
}
对于含回路的状态来说，可以让它对应一个while语句。例如，图2-12的状态i所对应的while语句如下：
ch=GetChar( );
while (IsLetter(ch) || IsDigit( ch))
GetChar ();
…实现状态j功能的语句…;
终态一般对应一个return( )语句；return意味着从词法分析器返回到调用段，一般指返回到语法分析器。
相对于图2-10的词法分析器构造如下：
int code,;
char ch;
char * strToken;
strToken= " "; /*对strToken数组初始化*/
ch=GetChar();
GetBC(); /*滤除空格*/
if (IsLetter(ch) || IsUnderline(ch))
{ while (IsLetter(ch) || IsDigit(ch) || IsUnderline(ch))
{
Concat(); /*将当前读入的字符送入strToken数组*/
GetChar();
}
Retract(); /*扫描指针回退一个字符*/
code=Reserve();
if (code = = 0)
{
return (7,InsertId(strToken));
}
else
return (code,-);
}
else if (IsDigit(ch))
{
while (IsDigit())
{
Concat( );
GetChar( );
}
Retract();
return(8,InsertConst(strToken));
}
else
switch(ch)
{
case '*': return(9,-); break;
case '+': return(10,-); break;
case '-': return(11,-); break;
case '=': ch=getchar();
if (ch= ='=')
return(15,-);
else
{ Retract();
return(12,-);
}
break;
case'<': ch=getchar();
if (ch= ='=')
return(14,-);
else
{ Retract();
return(13,-);
}
break;
case'<': return(16,-); break;
default: Error ( ); break;
}