编译原理-词法分析
词法分析
对源程序进行扫描产生单词符号，将源程序改造为单词符号串的中间程序，即输入源程序、输出单词符号。词法分析器(Lexical Analyzer)包括扫描器(Scanner)与执行词法分析的程序
单词符号是一个程序语言的基本语法符号。称作 token(记号) ，是具有独立意义的最小语法单位。将字符组合成记号与在一个英语句子中将字母构成单词并确定单词的含义很相像，此时的任务很像拼写。
程序语言的单词符号一般分为：
- 关键字：保留字
- 标识符：变量名、过程名等
- 常数：数字、字符串、布尔型等
- 运算符：±/*等
- 界符：逗号，分号，/、/ 等
单词符号常常表示成二元式：（单词种别，单词符号的属性值）。单词种别是语法分析需要的信息，通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上方便。
- 标识符一般统归为一种。
- 常数则按类型分种。
- 关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。
- 运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。
- 界符一般用一符一种的分法。
种别通常定义为枚举类型的逻辑项。
typedef enum {
IF,ELSE,PLUS,NUM,ID,……
} TokenType;
单词符号的属性值是指单词符号的特性或特征，可以是标识符在符号表的入口地址、数值的二进制值等。
如果是一符一种的分法（如关键字，运算符等），词法分析器只给出其种别编码，不给出其属性值。
如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码，还应给出属性值，以便把同一种类的单词区别开来。标识符属性值是自身的符号串；也可是在符号表的入口地址。常数自身值是常数的二进制数值。
扫描器必须计算每一个记号的若干属性，所以将所有的属性收集到一个单独构造的数据类型中是很有用的，这种数据类型称作记号记录(token record)。
typedef struct {
TokenType tokenval;
char* stringval;
int numval;
} TokenRecord;
或作为一个联合
typedef struct {
TokenType tokenval;
unon { char* stringval;
int numval;
} attribute;
} TokenRecord;
简而言之，扫描源程序，按照（单词种别，单词符号的属性值）这样的二元形式输出单词符号串
【例】试给出程序段 if (a>1) b = 100;输出的单词符号串。
假定基本字、运算符和界符都是一符一种，标识符自身的值是字符串，常数是二进制值。
(2,) 基本字 if
(29,) 左括号 (
(10,‘a’) 标识符 a
(23,) 大于号 >
(11,‘1’的二进制) 常数 1
(30，) 右括号 )
(10,‘b’) 标识符 b
(17,) 赋值号 =
(11,‘100’的二进制) 常数 100
(26,) 分号 ;
另一种表示可以为：
【例】考虑下述 C++ 代码段：while ( i >= j ) i--;
假定基本字、运算符和界符都是一符一种，标识符自身的值是符号表的入口地址，常数是二进制值。
经词法分析器处理后，转换为如下的单词符号序列：
( while ,- )
( ( ,- )
( id ,指向i的符号表表项的指针 )
( >= ,- )
( id ,指向j的符号表表项的指针 )
( ) ,- )
( id ,指向i的符号表表项的指针 )
( -- ,- )
( ； ,- )
词法分析作为一个独立的阶段（一遍），把源程序的字符序列翻译成单词符号序列存放于文件中，待语法分析程序工作时再从文件输入这些单词符号进行分析。结构更简单、清晰和条理化。有利于集中考虑词法分析一些细节问题。
词法分析作为一个子程序，每当语法分析器需要一个单词符号时就调用这个词法分析子程序。每一次调用，词法分析器就从输入字符串中识别出一个单词符号。
通常，构造词法分析程序有两种方法：
- 手工方式：根据识别语言单词的状态转换图，使用某种高级语言。例如：用 C 语言直接编写词法分析程序
- 自动方式：利用词法分析程序的自动生成工具 LEX 自动生成词法分析程序。
词法分析手动设计
1.输入缓冲区、预处理
词法分析器工作的第一步是输入源程序文本到输入缓冲区。
预处理工作：是将输入的源程序中的多余的空白符、跳格符、回车符、换行符等编辑性字符以及注释部分剔除掉，并将结果存入扫描缓冲区，方便单词符号的识别。
2.扫描缓冲区
- 为了保证单词符号不被扫描缓冲区边界打断，扫描缓冲区一般设计为如下一分为二的区域；
- 每次输入更新其一半空间的内容，使得词法分析器在最坏情况下识别单词符号的长度是扫描缓冲区长度的一半。因此也称配对缓冲区。
- 两个指示器
- 起点指示器：新单词的首字符；
- 搜索指示器：用于向前搜索以寻找单词的终点；
- 如果搜索指示器从单词起点出发搜索到半区的边缘，但未到单词的终点，则调用预处理程序，把后续的字符串装进另半区
单词符号的识别：超前搜索：源程序中的单词符号构成没有特殊的结尾，单词符号与单词符号之间在不引起可读性理解错误时也可以不必有空格作间隔，因此有时当单词符号的所有字符都已处理后，特别是当有单词符号是另一个单词符号的前缀子串时，词法分析器不能确定当前单词识别是否已结束，需要再超前搜索若干个字符后才能确定，返回识别出的单词，如果这时有多读进的字符，则需要回退处理。
例如 C 语言中的单词符号“>”、“>=”的识别就需要超前搜索。
不使用超前搜索的几种情况
- 规定所有基本字都是保留字；用户不能用它们作自己的标识符；基本字作为特殊的标识符来处理，使用保留字表；
- 如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔
状态转换图：状态转换图可用于识别（或接受）一定的字符串。大多数程序语言的单词符号都可以用转换图予以识别。
状态转换图是一张有限方向图，结点代表状态，用圆圈表示，状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类，一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态
状态转换图可用于识别(或接受)一定的字符串，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于 α，则称α被该状态转换图所识别(接受)
【示例】
设计时假定：
- 基本字：所有基本字都是保留字，用户不得使用它们作为自己定义的标识符；
- 基本字作为一类特殊的标识符来处理，不再专设对应的转换图。但需要把关键字预先安排在一个表格，此表叫关键字表。当识别出一个标识符时，就去查关键字表，以确定它是否为一关键字。
- 若关键字、标识符和常数之间没有确定的运算符或界限府作间隔，则必须至少用一个空白符作间隔。
状态转换图实现时可以让每个状态结点对应一小段程序。
分支节点：
循环状态节点
终态节点
下面使用伪码来简单实现词法分析器
全局变量与过程
ch 字符变量，存放最新读入的源程序字符
strToken 字符数组，存放构成单词符号的字符串
GetChar 子程序过程，把下一个字符读入到 ch 中
GetBC 子程序过程，跳过空白符，直至 ch 中读入一非空白符
Concat 子程序，把ch中的字符连接到 strToken
IsLetter和 IsDisgital 布尔函数，判断ch中字符是否为字母和数字
Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送0
Retract 子程序，把搜索指针回调一个字符位置
InsertId 整型函数，将strToken中的标识符插入符号表，返回符号表指针
InsertConst 整型函数，将strToken中的常数插入常数表，返回常数表指针
int code, value;
strToken := “ ”; /*置strToken为空串*/
GetChar();GetBC();
if (IsLetter())
begin
while (IsLetter() or IsDigit())
begin
Concat(); GetChar();
end
Retract();
code := Reserve();
if (code = 0)
begin
value := InsertId(strToken);
return ($ID, value);
end
else
return (code, -);
end
else if (IsDigit())
begin
while (IsDigit())
begin
Concat( ); GetChar( );
end
Retract();
value := InsertConst(strToken);
return($INT, value);
end
else if (ch =‘=’) return ($ASSIGN, -);
else if (ch =‘+’) return ($PLUS, -);
else if (ch =‘*’)
begin
GetChar();
if (ch =‘*’) return ($POWER, -);
Retract(); return ($STAR, -);
end
else if (ch =‘,’) return ($COMMA, -);
else if (ch =‘(’) return ($LPAR, -);
else if (ch =‘)’) return ($RPAR, -);
else ProcError( ); /* 错误处理*/
curState = 初态
GetChar();
while( stateTrans[curState][ch]有定义){
//存在后继状态，读入、拼接
Concat();
//转换入下一状态，读入下一字符
curState= stateTrans[curState][ch];
if curState是终态 then 返回strToken中的单词
GetChar( );
}
正则式
正则式：定义语言单词符号的一种方式（或者叫正规式）
【例】定义标识符的正则式
字母(字母 | 数字)*
正则式和正则集的递归定义：
- ε 和 Φ 都是 ∑ 上的正则式，它们所表示的正则集分别为 {ε} 和 Φ；
- 任何 a∈∑, a 是 ∑ 上的一个正则式，它所表示的正则集为 {a}；
- 假定 e1 和 e2 都是 ∑ 上的正则式，它们所表示的正则集分别记为 L(e1)和 L(e2)，则：
e1|e2 是正则式，表示的正则集为 L(e1)∪L(e2)（并集）
e1e2 是正则式，表示的正则集为 L(e1)L(e2) （连接集）
(e1)* 是正则式，表示的正规集为 (L(e1))*（闭包）
优先级为闭包、连接积、或。
正则集可以用正则式表示，正则式是表示正则集一种方法，一个字符串集合是正则集当且仅当它能用正则式表示
正则式表示字符串的格式，正则式 r 完全由它所匹配的串集来定义。这个集合为由正则式生成的语言(language generated by the regular expression)，写作 L®，每个正则式可以看作是一个匹配模式。
【例】设∑={a,b,c},则aa*bb*cc* 是∑上的一个正则式
aa*bb*cc* 是∑上的一个正则式，它所表示的正则集是
L = {abc,aabc,abbc,abcc,aaabc,…}
= {a^m b^n c^l | m,n,l ≥1}
【例】设程序语言字母表是键盘字符集合，则程序语言单词符号可用如下正则式定义
关键字 if | else | while | do
标识符 l (l | d)*
所整常数 dd*
关系运算符 < | <= | > | >= | <>
其中 l 代表 a~z 中任一英文字母
其中 d 代表 0~9 中任一数字
正则式等价
若两个正则式所表示的正则集相同，则认为二者等价。两个等价的正则式 R1 和 R2 记为 R1=R2。
【例】
(a|b)* = (a*|b*)*
b(ab)* = (ba)* b
正则式扩展
正则式 r 的一个或多个重复，写作 r+
. 表示与任意字符匹配。
用方括号和一个连字符表示字符的范围，如[0-9]，[a-z]，[a-zA-Z]。这种表示法还可以用作表示单个的解，如a|b|c 可写成[abc]
不在给定集合中的任意字符用 ”~”，如正规式 ~a 表示字母表中非 a 字符
可选的子表达式r？表示由 r 匹配的串是可选的（0个或1个）。如natural = [0-9]+，signedNatural = (+|-)? Natural
正则文法与正则式
正则文法与正则式都是描述正规集的工具。
对任意一个正则文法，存在定义同一语言的正则式；反之，对每个正则式存在一个生成同一语言的正则文法。
正则文法到正则式的转换
将正则文法中的每个非终结符表示成关于它的正则式方程，获得一个联立方程组。依照求解规则：
若 x = αx |β(或x = αx+β)，则解为x = α*β
若 x = xα | β(或x = xα+β)，则解为x = βα*
以及正规式的分配率、交换率和结合率求关于文法开始符号的正规式方程组的解。
这个解是关于文法开始符号 S 的一个正则式。上述两个规则较为重要，将递归的x消为α的闭包
【例1】
首先给出相应的正规式方程组（+代替|）
Z = 0A ………(1)
A = 0A+0B ………(2)
B = 1A+$\epsilon $ ………(3)
将(3)代入(2)式中的 B 得
A = 0A+01A+0 ………(4)
对(4)利用分配率 A = (0+01)A+0 ………(5)
对(5)使用规则得 A = (0+01)*0 ………(6)
将(6)代入(1)得 Z = 0(0+01)*0
即正规文法G[Z]所生成语言的正规式是 0(0|01)*0
【例2】
设有正规文法Ｇ：
A→aB|bB
B→aC|a|b
C→aB
试给出该文法生成语言的正规式
同上述步骤
首先给出相应的正规式方程组（+代替|）
A = aB+bB ………(1)
B = aC+a+b ………(2)
C = aB ………(3)
将(3)代入(2)式中得
B = aaB+a+b ………(4)
对(4)使用规则得 B = (aa)*(a+b) ………(5)
将(5)代入(1)得 A = (a+b)(aa)*(a+b)
即正规文法G[Z]所生成语言的正规式是 (a|b)(aa)*(a|b)
【例3】
设有正规文法Ｇ：
Z→U0|V1
U→Z1|1
V→Z0|0 试给出该文法生成语言的正规式
首先给出相应的正规式方程组（+代替|）
Z = U0+V1 ………(1)
U = Z1+1 ………(2)
V = Z0+0 ………(3)
将(2)(3)代入(1)式得
Z = Z10+10+Z01+01 ………(4)
Z = Z(10+01)+10+01 ………(4)
对(4)使用规则得Z = (10+01)(10+01)*
即正规文法G[Z]所生成语言的正规式是 (10|01)(10|01)*
【例4】
已知描述“标识符”单词符号的正规文法
<标识符> →l | <标识符>l | <标识符>d
首先给出相应的正规式方程组（+代替|）
S = l+Sl+Sd
S = l+S(l+d)
使用规则得
S = l(l+d)*
该文法的正规式是
l(l|d)*
正规式到正规文法的转换
字母表∑上的正规式到正规文法 G＝(,,P,S)的转换方法如下：
- 令 VT = ∑
- 对任意正规式 R 选择一个非终结符 Z，生成规则 Z→R，并令 S＝Z；
- 若 a 和 b 都是正规式，对形如 A→ab 的规则转换成 A→aB 和 B→b两规则，其中 B 是新增的非终结符；
- 在已转换的文法中，将形如 A→a*b 的规则进一步转换成 A →aA | b；
- 不断利用规则(3)和(4)进行转换，直到每条规则最多含有一个终结符为止。
【例1】
将R = (a|b)(aa)*(a|b) 转换成相应的正规文法
令 A 是文法开始符号，根据规则(2)变换为
A → (a|b)(aa)*(a|b)
根据规则(3)变换为
A → (a|b)B
B → (aa)*(a|b)
根据规则(4)变换为（逆推，将*转变为|）
A → aB|bB
B → aaB|a|b（aaB中有两个a，要简化到只有一个终结符为止）
根据规则(3)变换为
A → aB|bB
B → aC|a|b
C → aB
【例2】
将描述标识符的正规式R=l(l|d)*转换成相应的正规文法
令 S 是文法开始符号，根据规则(2)变换为
S→l(l|d)*
根据规则(3)变换为
S→lA
A→(l|d)*
根据规则(4)变换为
S→lA
A→(l|d)A |ε
进一步变换为
S→lA
A→lA|dA|ε（消除ε）
进一步变换为
S→l|lA
A→l|d|lA|dA
有穷自动机
有穷自动机是具有离散输入与输出系统的一种抽象数学模型。有穷自动机有“确定的”和“非确定的”两类。确定的有穷自动机 和 非确定的有穷自动机都能准确地识别正规集。
确定有穷自动机(DFA)
一个确定有穷自动机 DFA M 是一个五元式：M=( Q, ∑, f, S, Z) 其中：
Q：有限状态集，它的每个元素称为一个状态。
∑：有穷字母表，它的每个元素称为一个输入字符。
F：状态转换函数，是从 Q×∑ 至 Q 的单值映射。f(qi, a) = qj (qi,qj ∈ Q，a ∈ ∑)表示：当现行状态为 qi、输入字符为 a 时，自动机将转换到下一状态 qj 。称 qj 为 qi 的一个后继。
S∈Q：是唯一的初态。
Z $\subset $ Q：终态集（可空）。
【例】设DFA M=({q0,q1,q2},{a,b},f,q0,{q2})
其中：
f(q0,a)= q1
f(q1,b)= q1
f(q0,b)= q2
f(q2,a)= q2
f(q1,a)= q1
f(q2,b)= q1
状态转换矩阵、状态转换图
一个 DFA 可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示 f(s, a) 的值。这个矩阵称为状态转换距阵，或称转换表。
一个 DFA 也可以用一张（确定的）状态转换图表示，假定 DFA M 含有 m 个状态 n 个输入字符，这个状态转换图则有 m 个结点，每个结点最多有 n 条箭弧射出和别的状态相连，同一结点射出的每条箭弧用 ∑ 中的一个不同的输入字符作标记，整张图含有唯一一个初态结点和若干个（可以是0个）终态结点。
DFA M 识别的符号串：对于 ∑* 中的任何字 β，若存在一条从初态到某一终态结点的通路，且这条通路上的所有弧的标记符连接成的字等于 β ，则称β 可为 DFA M 所识别。若 M 的初态结同时又是终态结，则ε可为 M 所识别。
DFA M 所能识别的符号串的全体为其接受的语言，记为L(M)。
结论：V $ \subset $ ∑* 是正规的当且仅当存在 ∑ 上的自动机 M，使得 V=L（M）
模拟 DFA 的算法
输入：输入以文件结束符 eof 结尾的串 x；一个 DFA D，其开始状态为 s0，接受状态集合为 F。
输出：如果 D 接受 x，则回答 “yes”，否则回答“No”。
方法：把下列算法应用于输入字符串x。函数 move(s,c) 给出在状态 s 上遇到输入字符 c 时应该转换到的下一个状态。函数 getch() 返回输入串 x 的下一个字符。
s=s0;
while ((c=getch())!=eof) {
s=move(s,c);
if (s is in F) return “yes”;
}
非确定有限自动机(NFA)
一个非确定有限自动机 M 是一个五元式：M=(Q,∑,S,Z,F)，其中：
Q：有限状态集
∑：有穷字母表
F：状态转换函数，是一个从 Q×∑* 至 S 的子集 S’ 的映射（多值映射）。即
f： Q×∑* →2Q 幂集
S $\subset $ Q：非空初态集
Z $\subset $ Q：终态集（可空）
一个 NFA 也可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示 f(s, a) 的值（状态集）。一个 NFA 也可以用一张状态转换图表示。
NFA 和DFA的区别
NFA可以有多个初态；
弧上的标记可以是∑*中的一个字(甚至可以是一个正规式)，而不一定是单个字符；
同一个字可能出现在同状态射出的多条弧上；
DFA是NFA的特例。
NFA M 识别的符号串，对于 ∑* 中的任何字 β，若存在一条从初态到某一终态结点的通路，且这条通路上的所有弧的标记符连接成的字（忽略ε弧）等于 β，则称β 可为 NFA M 所识别。若 M 的某些状态既是初态又是终态则空字 ε 被 M 所接受。
NFA M 所能识别的符号串的全体为其接受的语言，记为L(M)，如上例中NFA M’ 所识别的语言为L(M’) = b*(b|ab)(bb)*
由 NFA 的定义可知，同一个符号串 β 可由多条路来识别，DFA 是 NFA的特例，利用有穷自动机构造词法分析程序的方法是：
- 从语言单词的描述中构造出 NFA；
- 将 NFA 转化为 DFA；
- 化简为状态最少化的 DFA；
- 对 DFA 的每一个状态构造一个程序段将其转化为识别单词的词法分析程序。
NFA 确定化为 DFA 的方法
NFA 的确定化是指对任给的 NFA，都能相应地构造一DFA，使它们接受相同的语言。
对于一个 NFA，由于状态转换函数 f 是一个多值函数，因此总存在一些状态 q，对于它们有
f(q,a)={q1, q2,…,qn}
它是 NFA 状态集合的一个子集，为了将 NFA 转换为 DFA，把状态集合{q1, q2,…,qn}看做一个状态 A，也就是说，从 NFA 构造 DFA 的基本思想是 DFA 的每一个状态代表 NFA 状态集合的某个子集，这个 DFA 使用它的状态去记录在 NFA 读入输入符号之后可能到达的所有状态的集合，称此构造方法为子集法。
状态集合 I 的 ε-闭包
设 I 是 NFA N 的一个状态子集，ε-CLOSURE(I)定义如下：
若 s ∈ I，则 s ∈ ε-CLOSURE(I)
若 s ∈ I，那么从 s 出发经过任意条 ε 弧而能到达的任何状态 s’，都属于 ε-CLOSURE(I)
ε-CLOSURE(I)是一个从给定结点集合出发在转换图上搜索可达结点集合的过程。
将 I 中所有的状态压入栈 stack 中；
将 ε-CLOSURE(I)初始化为 I；
while 栈stack不空 do
begin
将栈顶元素 t 弹出栈；
for 每个这样的状态u:从t到u有一条标记为ε的边 do
if u 不在 ε-CLOSURE(I) 中 do
begin
将 u 添加到 ε-CLOSURE(I)；
将 u 压入栈 stack 中
end
end
从 NFA N=(Q,∑,F,S,Z)构造等价的DFA M=(Q’,∑,F’,S’,Z’)的方法
首先将从初态 S 出发经过任意条 ε 弧所能到达的状态所组成的集合作为 M 的初态 S’，然后从 S’ 出发，经过对输入符号 a∈∑ 的状态转移所能到达的状态(包括读输入符号之前或之后所有可能的 ε 转移所能到达的状态)所组成的集合作为 M 的新状态，如此重复，直到不再有新的状态出现为止。
置 DFA M 中的状态集合 Q’和 Z’为 ∅ 集。
给出 M 的初态 S’＝ ε-CLOSURE(S)，并把 S’ 置为未标记状态后加入到 Q’中。
初始时，ε-CLOSURE(S)是Q’中唯一的状态且未被标记；
while Q’中存在一个未标记的状态 T do
begin
标记 T；
for 每个输入符号 a do
begin
U = ε-CLOSURE( f(T,a) );
if U 没有在 Q’中 then
将 U 作为一个未标记的状态添加到 Q’中；
f’(T,a) = U;
end
end
【例】NFA确定化
有穷自动机与文法的相互转化
右线性正规文法到有穷自动机的转换方法
左线性正规文法到有穷自动机的转换方法
有穷自动机到正规文法的转换方法
有穷自动机与正则表达式的相互转化
由正则表达式构造NFA
输入：字母表上的正规式 R
输出：识别语言 L® 的 NFA N
整个分裂过程中，所有新结点均采用不同的名字，保留 X，Y 为全图唯一初态结点和终态结点。
有穷自动机到正规式的转换
逆推过程，增加新初态 X，与所有原初态用ε相连，增加新终态 Y，与所有原终态用ε相连，从而构成一个新的NFA M’，它只有一个初态 X 和一个终态 Y。在X 与 Y 之间进行弧合并。
实际设计
词法分析的任务就是扫描源文件，按照（单词符号（token），单词符号属性值）这样的二元形式输出单词符号串
词法分析中要使用正则表达式来扫描整个文件以判别单词符号的种类，单词符号按照种类进行划分，例如
TOKEN: {
<VOID : "void">
| <CHAR : "char">
| <SHORT : "short">
| <INT : "int">
| <LONG : "long">
| <STRUCT : "struct">
| <UNION : "union">
| <ENUM : "enum">
| <STATIC : "static">
| <EXTERN : "extern">
| <CONST : "const">
| <SIGNED : "signed">
| <UNSIGNED : "unsigned">
| <IF : "if">
| <ELSE : "else">
| <SWITCH : "switch">
| <CASE : "case">
| <DEFAULT_ : "default">
| <WHILE : "while">
| <DO : "do">
| <FOR : "for">
| <RETURN : "return">
| <BREAK : "break">
| <CONTINUE : "continue">
| <GOTO : "goto">
| <TYPEDEF : "typedef">
| <IMPORT : "import">
| <SIZEOF : "sizeof">
}
上述Token描述了关键字规则
TOKEN: {
<IDENTIFIER: ["a"-"z", "A"-"Z", "_"](["a"-"z", "A"-"Z", "_", "0"-"9"])*>
}
上述Token描述了标识符规则
正则表达式会使用最长前缀匹配规则，如遇到了voidFunction 会匹配voidFunction（标识符）而不是void （保留字）Function。
同理，描述数值规则可使用（匹配10,16,8进制数值）
TOKEN: {
<INTEGER: ["1"-"9"] (["0"-"9"])* ("U")? ("L")?
| "0" ["x", "X"] (["0"-"9", "a"-"f", "A"-"F"])+ ("U")? ("L")?
| "0" (["0"-"7"])* ("U")? ("L")?
>
}
对于空白符或者注释来说要跳过，因此不使用TOKEN来描述，使用SPECIAL_TOKEN来描述空白符
SPECIAL_TOKEN: { <SPACES: ([" ", "\t", "\n", "\r", "\f"])+> }
[" “, “\t”, “\n”, “\r”, “\f”] 表示 " “（空格）、”\t”（制表符）、"\n"（换行符）、"\r"（回车）、"\f"（换页符）之中的任意一个，后面加上“+”表示上述 5 种字符之一1 个或多个排列而成的字符串。
描述行注释
SPECIAL_TOKEN: {
<LINE_COMMENT: "//" (~["\n", "\r"])* ("\n" | "\r\n" | "\r")?>
}
上述代码所描述的模式是以“//”开始，接着是换行符以外的字符，并以换行符结尾的字符串。简单来说，这里描述的是从“//”开始到换行符为止的字符串。文件的最后可能没有换行符，因此换行符是可以省略的。
描述块注释
首先要注意的是下列模式是无法正确地扫描块注释的。
SKIP { <"/*" (~[])* "*/"> }
按照最长匹配原则，可能会把代码也当做注释匹配进去，如
/* 本应只有这一行是注释…… */
int
main(int argc, char **argv)
{
printf("Hello, World!\n");
return 0;
}/* 以状态 0 结束 */
如果这样写，那么直到注释的终结符为止都和模式“(~[])*”匹配，
为了解决这个问题，需要进行如下修改，也就是进行状态转移
MORE: { <"/*"> : IN_BLOCK_COMMENT }
<IN_BLOCK_COMMENT> MORE: { <~[]> }
<IN_BLOCK_COMMENT> SKIP: { <"*/"> : DEFAULT }
上述例子中的 IN_BLOCK_COMMENT 是扫描的状态（state）。通过使用状态，可以实现只扫描代码的一部分。
让我们来讲解一下状态的使用方法。首先再看一下上述例子中的第 1 行。
SKIP: { <"/*"> : IN_BLOCK_COMMENT }
这样在规则定义中写下 { 模式：状态名 } 的话，就表示匹配模式后会迁移（transit）到对应的状态。上述例子中会迁移到名为 IN_BLOCK_COMMENT 的状态。
扫描器在迁移到某个状态后只会运行该状态专用的词法分析规则。也就是说，在上述例子中，除了IN_BLOCK_COMMENT 状态专用的规则之外，其他的规则将变得无效。要定义某状态下专用的规则，可以如下这样在 TOKEN 等命令前加上 < 状态名 >。
< 状态名 > TOKEN: {~}
< 状态名 > SKIP: {~}
< 状态名 > SPECIAL_TOKEN: {~}
DEFAULT 状态（DEFAULT state）表示扫描器在开始词法分析时的状态。没有特别指定状态的词法分析规则都会被视作 DEFAULT 状态。也就是说，至今为止所定义的保留字的扫描规则、标识符的规则以及行注释的规则实际上都属于 DEFAULT 状态。<"*/">:DEFAULT 的意思是匹配模式 “*/” 的话就回到最初的状态。
MORE命令将表示为“仅匹配该规则的话扫描还没有结束”，也就是说，进入该状态的匹配必须表示为/*…*/这样的形式，否则就会报错
扫描字符串字面量
MORE: { <"\""> : IN_STRING } // 规则 1
<IN_STRING> MORE: {
<(~["\"", "\\", "\n", "\r"])+> // 规则 2
| <"\\" (["0"-"7"]){3}> // 规则 3
| <"\\" ~[]> // 规则 4
}
<IN_STRING> TOKEN: { <STRING: "\""> : DEFAULT } // 规则 5
首先，借助状态迁移可以用多个规则来描述 token。扫描到规则 1 的起始符“"”后迁移到IN_STRING 状态，只有规则 2、3、4 在该状态下是有效的。其次，除了最后的规则 5 之外，规则 1 ～ 4 都使用 MORE 命令将用多个规则扫描一个 token。也就是以“ ”包裹的任意字符
试验
基于自动机的词法分析器
使用正则表达式进行词法分析，针对的语言的语法如下所示。
输入：所给源程序字符串。输出：二元组(syn,token或sum) 构成的序列，syn 为单词种别码，token为存放的单词自身字符串，sum为整形常量。
语言的词法为：
1、关键字
main
if then else
while do
repeat until
for from to step
switch of case default
return
integer real char bool
and or not mod
read write
所有关键字都是小写。
2、专用符号
运算符包括：=、+、-、*、/、<、<=、>、>=、!=
分隔符包括：,、;、:,{、}、[、]、(、)
3、其它标记ID和NUM
通过以下正规式定义其它标记：
ID→letter(letter | digit)*
NUM→digit digit*
letter→a | … | z | A | … | Z
digit→0|…|9
4、空格由空白、制表符和换行符组成
空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。
单词符号种别码在教科书中未设定，因此此处指定为按上述单词符号的顺序从1开始按照顺序递增。
词法分析记号描述Token
/**
* 词法分析-单词符号表示
* 抽象类，单词种别的父类，维护符号与种别码的映射
*/
public abstract class Token {
//表示文件末尾的结束符
public static final Token EOF = new Token(-1) {
};
//表示每一行的结束符，也就是换行符\n
public static final String EOL = "\\n";
/**
* 定义匹配不同单词种别的正则表达式
* 因为末尾有一个| 所有要按顺序写
*/
public static final String KEYWORD_REGEX = "main|if|then|else|while|do|repeat|until|for|" +
"from|to|step|switch|of|case|default|return|integer|real|char|bool|and|or|not|mod|read|write|";//匹配关键字
public static final String OPERATOR_REGEX = "=|\\+|\\-|\\*|\\/|<|<=|>|>=|!=|";//匹配运算符
public static final String SEPARATOR_REGEX = "[,;:{}\\[\\]\\(\\)]|";//匹配分隔符
public static final String ID_REGEX = "[a-zA-Z][a-zA-Z0-9]*|";//匹配标识符
public static final String NUM_REGEX = "[0-9]+";//常量值标识符
/**
* 定义单词符号与种别码的映射
* 所有的信息按顺序存放在文件中，读取文件并加载到该静态类中
*/
public static Map<String, Integer> tokenTypeMap;
//映射的配置文件的位置
public static String mapConfigPath = new File("").getAbsolutePath() + "/tokenTypeMap.config";
static {
tokenTypeMap = new LinkedHashMap<>();
try {
Scanner in = new Scanner(new BufferedInputStream(new FileInputStream(mapConfigPath)));
int ite = 1;
String res = in.hasNext() ? in.next() : null;
while (res != null) {
if (!(res.equals("") || res.charAt(0) == ' ' || res.charAt(0) == '#')) {
tokenTypeMap.put(res, ite++);
}
res = in.hasNext() ? in.next() : null;
}
} catch (Exception e) {
e.printStackTrace();
}
}
private int lineNumber;//该单词符号所在的行号
public Token(int line) {
this.lineNumber = line;
}
}
上述读取的配置文件为关键字，运算符等固定的符号的配置文件，将其读入内存并按照顺序编码
tokenTypeMap.config
#关键字
main
if then else
while do
repeat until
for from to step
switch of case default
return
integer real char bool
and or not mod
read write
#运算符
= + - * / < <= > >= !=
#分隔符
, ; : { } [ ] ( )
#标识符与常数值
ID NUM
词法分析输出结果TokenRecord
/**
* 词法分析的输出结果
* (单词符号码，单词符号属性值）
*/
public class TokenRecord extends Token {
public TokenRecord(int line) {
super(line);
}
private int flagCode;//标识码
private String stringValue;//字符值
private String numValue;//数值
public int getFlagCode() {
return flagCode;
}
public String getNumValue() {
return numValue;
}
public String getStringValue() {
return stringValue;
}
public void setFlagCode(int flagCode) {
this.flagCode = flagCode;
}
public void setNumValue(String numValue) {
this.numValue = numValue;
}
public void setStringValue(String stringValue) {
this.stringValue = stringValue;
}
}
词法分析编译异常CompileException
/**
* 词法分析时出现的编译错误
* 抛出异常
*/
public class CompileException extends Exception {
public int errorLine;//出现错误的行号
public String errorReason;//出现错误的原因
public CompileException(int errorLine, String errorReason) {
this.errorLine = errorLine;
this.errorReason = errorReason;
}
@Override
public String toString() {
return "第" + errorLine + "行：" + errorReason;
}
}
预处理器Processor
/**
* 预处理器，删除程序中的空行、空格与注释
*/
public class Preprocessor {
/**
* 读取指定程序文件，进行预处理
*
* @param file
* @return
*/
public static LinkedHashMap<Integer, String> preprocess(File file) throws CompileException {
LinkedHashMap<Integer, String> res = new LinkedHashMap<>();
boolean blockStatus = false;//是否处于块注释中
int lineNumber = 1;
try {
Scanner scanner = new Scanner(new FileReader(file));
String lineInfo = scanner.hasNextLine() ? scanner.nextLine() : null;
//对每一行进行处理
while (lineInfo != null) {
StringBuilder lineProcessValue = new StringBuilder();
for (int i = 0; i < lineInfo.length(); i++) {
//处于块注释中
if (blockStatus) {
if (i + 1 < lineInfo.length() && lineInfo.charAt(i) == '*' && lineInfo.charAt(i + 1) == '/') {
i++;
blockStatus = false;
}
continue;
}
if (lineInfo.charAt(i) == ' ' || lineInfo.charAt(i) == '\n') continue;//空格或者换行符省略
if (i + 1 < lineInfo.length() && lineInfo.charAt(i) == '/' && lineInfo.charAt(i + 1) == '/')
break;//遇到行注释，本行退出
if (i + 1 < lineInfo.length() && lineInfo.charAt(i) == '/' && lineInfo.charAt(i + 1) == '*') {//遇到块注释，进行标识
i++;
blockStatus = true;
continue;
}
lineProcessValue.append(lineInfo.charAt(i));
}
lineInfo = scanner.hasNextLine() ? scanner.nextLine() : null;
if (!lineProcessValue.toString().equals("")) res.put(lineNumber, lineProcessValue.toString());
lineNumber++;
}
} catch (Exception e) {
e.printStackTrace();
}
//块注释出错，抛出异常
//TODO 因为没有定义字符串字面量"..."与字符字面量'.'，虽然可以检验是否存在连续的//，但是如果//放在字符串字面量里检验规则就变了，这里就不检验
if (blockStatus) throw new CompileException(lineNumber, "检查注释");
return res;
}
}
词法分析器Lexer
/**
* 词法分析器，读取指定文件，返回单词符号二元组
*/
public class Lexer {
//正则式
public static final String regex = Token.KEYWORD_REGEX + Token.OPERATOR_REGEX +
Token.SEPARATOR_REGEX + Token.ID_REGEX + Token.NUM_REGEX;
/**
* 进行词法分析
*
* @param file 源文件
* @return （种别码，单词符号或值）二元组
*/
public List<TokenRecord> lex(File file) {
List<TokenRecord> tuple = new ArrayList<>();
try {
//先进行预处理
LinkedHashMap<Integer, String> map = Preprocessor.preprocess(file);
//正则匹配每行的数据
Pattern pattern = Pattern.compile(regex);
for (int lineNumber : map.keySet()) {
String string = map.get(lineNumber);
Matcher matcher = pattern.matcher(string);
while (matcher.find()) {
TokenRecord tokenRecord = new TokenRecord(lineNumber);
String match = matcher.group();
if (Token.tokenTypeMap.containsKey(match)) {
System.out.println("(" + match + ",-)");
tokenRecord.setFlagCode(Token.tokenTypeMap.get(match));
tokenRecord.setStringValue("-");
} else if ('0' <= match.charAt(0) && match.charAt(0) <= '9') {
System.out.println("(NUM," + match + ")");
tokenRecord.setFlagCode(Token.tokenTypeMap.get("NUM"));
tokenRecord.setStringValue(match);
} else {
System.out.println("(ID," + match + ")");
tokenRecord.setFlagCode(Token.tokenTypeMap.get("ID"));
tokenRecord.setStringValue(match);
}
tuple.add(tokenRecord);
}
}
} catch (CompileException e) {//编译异常
e.printStackTrace();
return null;
}
return tuple;
}
}
测试
/**
* 词法分析器测试
*/
public class LexerTest {
public static void main(String[] args) {
try {
File file = new File(new File("").getAbsoluteFile() + "/test.txt");
Lexer lexer = new Lexer();
for (TokenRecord tokenRecord : lexer.lex(file)) {
System.out.println("(" + tokenRecord.getFlagCode() + "," + tokenRecord.getStringValue() + ")");
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
测试文件为test.txt
integer main(){
integer i=0;//行注释
while(i<100)i++;/*块注释
*/
return i;
}
NFA确定化为DFA
设计确定有穷自动机DFA和非确定有穷自动机NFA描述的对象模型，实现DFA和NFA的基本操作（输入和输出）。设计一个将NFA确定化成DFA的方法。
测试文件结构为：
1)状态个数stateNum，约定状态编号0..(stateNum-1)；
2)字符个数 symbolNum，约定符号编号 1..symbolNum，编号为0的符号为 ；
3)以下若干行是状态转换，一行一个转换，以-1结束；
转换的格式：状态，符号（可以是0），若干个状态，以-1结束；
4)开始状态集合，-1结束；
5)终止状态集合，-1结束；
【例】
11
2
0 0 1 7 -1
1 0 2 4 -1
2 1 3 -1
3 0 6 -1
4 2 5 -1
5 0 6 -1
6 0 1 7 -1
7 1 8 -1
8 2 9 -1
9 2 10 -1
-1
0 -1
10 -1
输出：确定的DFA，描述为：
状态个数：5
字符表个数：2
状态转换：
(0,1)->1
(0,2)->2
(1,1)->1
(1,2)->3
(2,1)->1
(2,2)->2
(3,1)->1
(3,2)->4
(4,1)->1
(4,2)->2
开始状态：0
结束状态集[4]
DFA描述
/**
* @author LSL
*/
public class DFA {
private List<Integer> statusList;//状态集
private List<Integer> symbolList;//字符集
private List<Function> functionList;//状态转换集
private int begin;//初态
private List<Integer> endList;//终态集
public DFA(){
statusList=new ArrayList<>();
symbolList=new ArrayList<>();
functionList=new ArrayList<>();
begin=0;
endList=new ArrayList<>();
}
/**
* 状态保存，此处不使用int[][]
*/
static class Function{
private int state;//状态
private int symbol;//符号
private int convertState;//转换后状态
public Function(int state,int symbol,int convertState){
this.state=state;
this.symbol=symbol;
this.convertState=convertState;
}
@Override
public boolean equals(Object object){
if(!(object instanceof Function))return false;
return state==((Function) object).state && symbol==((Function) object).symbol;
}
public int getConvertState() {
return convertState;
}
}
@Override
public String toString(){
StringBuilder res=new StringBuilder("状态个数："+statusList.size()+"\n"+
"字符表个数："+(symbolList.size()-1)+"\n"+//字符表包含0，此处应减一
"状态转换：\n");
//排序
functionList.sort((Function f1,Function f2)->{
if(f1.state==f2.state)return f1.symbol-f2.symbol;
else return f1.state-f2.state;
});
//输出函数
for (Function function:functionList){
res.append("(").append(function.state).append(",").append(function.symbol).
append(")->").append(function.getConvertState()).append("\n");
}
res.append("开始状态：").append(begin).append("\n");
res.append("结束状态集").append(endList.toString()).append("\n");
return res.toString();
}
//getter与setter...此处省略
public void addConvertState(int state, int symbol, int convertState){
Function function=new Function(state,symbol,convertState);
functionList.add(function);
}
}
NFA描述
/**
* @author LSL
*/
public class NFA {
private List<Integer> statusList=new ArrayList<>();//状态集
private List<Integer> symbolList=new ArrayList<>();//字符集
private List<FunctionExtension> functionList=new ArrayList<>();//状态转换集
private List<Integer> beginList=new ArrayList<>();//初态集
private List<Integer> endList=new ArrayList<>();//终态集
/**
* 读取文件构造NFA
* @param file
*/
public NFA(File file){
try {
Scanner scanner=new Scanner(new FileReader(file));
int stateNum=scanner.nextInt();
int symbolNum=scanner.nextInt();
Set<Integer> statusSet=new HashSet<>();//状态集合
Set<Integer> symbolSet=new HashSet<>();//符号集合
String line=scanner.nextLine();
while (line.equals(""))line=scanner.nextLine();//避免多余的空行
while (!line.equals("-1")){
String[] num=line.split(" ");
statusSet.add(Integer.parseInt(num[0]));//状态集
symbolSet.add(Integer.parseInt(num[1]));//符号集
FunctionExtension extension=new FunctionExtension(Integer.parseInt(num[0]),Integer.parseInt(num[1]));//转换
for(int j=2;j<num.length-1;j++){
statusSet.add(Integer.parseInt(num[j]));
extension.convertStateList.add(Integer.parseInt(num[j]));
}
functionList.add(extension);
line=scanner.nextLine();
}
statusList.addAll(statusSet);
symbolList.addAll(symbolSet);
//读取开始状态集
line=scanner.nextLine();
while (line.equals(""))line=scanner.nextLine();//避免多余的空行
String[] num=line.split(" ");
for(int i=0;i<num.length-1;i++)beginList.add(Integer.parseInt(num[0]));//开始状态集
//读取结束状态集
line=scanner.nextLine();
while (line.equals(""))line=scanner.nextLine();//避免多余的空行
num=line.split(" ");
for(int i=0;i<num.length-1;i++)endList.add(Integer.parseInt(num[0]));//开始状态集
//TODO 由状态数和符号数可校验读取是否正确
}catch (Exception e){
e.printStackTrace();
}
}
/**
* 状态保存，此处不使用int[][]
*/
static class FunctionExtension{
private int state;//状态
private int symbol;//符号
private List<Integer> convertStateList=new ArrayList<>();//转换后状态
public FunctionExtension(int state,int symbol){
this.state=state;
this.symbol=symbol;
}
}
/**
* 将该NFA转换为DFA
* @return 转换后的DFA
*/
public DFA convertToDFA(){
DFA res=new DFA();
Map<List<Integer>,Integer> convertMap=new LinkedHashMap<>();//未标记的转换映射列表
Map<List<Integer>,Boolean> convertMapFlag=new LinkedHashMap<>();//映射是否被标记
int stateId=0;//状态标识(索引）
List<Integer> init=Closure(beginList);
convertMap.put(init,stateId++);//DFA索引映射NFA状态集
convertMapFlag.put(init,false);
while (true){
List<Integer> T=null;
//寻找是否存在未标记状态
for(List<Integer> flag:convertMapFlag.keySet()){
if(!convertMapFlag.get(flag)){
T=flag;//找到未标记状态
break;
}
}
if(T==null)break;
convertMapFlag.put(T,true);//重置为标记状态
//对每个符号进行一次操作
for(int symbol:symbolList){
/**
* 此处，因为0代表epsilon，不应该对epsilon进行Closure操作
*/
if(symbol==0)continue;
//获取f(T,symbol)=f(status1,symbol) U f(status2,symbol) U ......
Set<Integer> tmp=new HashSet<>();//Set去重
for(int status:T){
tmp.addAll(getFunctionConvert(status,symbol));
}
List<Integer> U=Closure(new ArrayList<>(tmp));//获取Closure(f(T,symbol))
//判断U集合是否已经在已标记状态集合映射中，此处比对List<Integer>
boolean find=false;
List<Integer> UCopy = null;
for(List<Integer> flagList:new ArrayList<>(convertMap.keySet())){
if(sortListEquals(U,flagList)){
find=true;
UCopy=flagList;//等价于U
break;
}
}
//如果U不在映射集合中则加入
if(!find){
convertMap.put(U,stateId++);
convertMapFlag.put(U,false);//未标记
}
//设置DFA的转换f'(T,symbol)=U
if(!find)res.addConvertState(convertMap.get(T),symbol,convertMap.get(U));
else res.addConvertState(convertMap.get(T),symbol,convertMap.get(UCopy));
}
}
//初始化dfa的状态集，符号表，初始状态，终态集
for(List<Integer> list:convertMap.keySet()){//状态集
res.getStatusList().add(convertMap.get(list));
}
res.getSymbolList().addAll(symbolList);//符号表
res.setBegin(0);//初始态一定为0
res.getEndList().add(stateId-1);//终态集
return res;
}
/**
* 从给定状态集合出发，寻找可达节点
* @param stateList 初始状态集合
* @return 从该集合中的节点出发的所有可达节点集合
*/
private List<Integer> Closure(List<Integer> stateList){
//将closure(state)初始化为状态集合
List<Integer> res=stateList;
//将所有状态压入栈中
Stack<Integer> stack=new Stack<>();
stack.addAll(stateList);
while (!stack.empty()){
int node=stack.pop();//出栈
//搜寻函数转换列表，发现结果集
for (FunctionExtension extension:functionList){
if(extension.state==node&&extension.symbol==0){//0代表epsilon
for(int endState:extension.convertStateList){//可达终态集
if(!res.contains(endState)){
res.add(endState);
stack.push(endState);
}
}
}
}
}
res.sort(Comparator.comparingInt(num->num));//返回的结果排序
return res;
}
/**
* 给定状态与符号，返回转换后的状态集
* @param state
* @param symbol
* @return
*/
public List<Integer> getFunctionConvert(int state,int symbol){
for(FunctionExtension extension:functionList){
if(extension.state==state && extension.symbol==symbol)return extension.convertStateList;
}
return new ArrayList<>();
}
/**
* 判断两个列表是否元素完全相同，列表已排序
* @param a
* @param b
* @return
*/
public boolean sortListEquals(List<Integer> a,List<Integer> b){
if(a.size()!=b.size())return false;
for(int i=0;i<a.size();i++){
if(!a.get(i).equals(b.get(i)))return false;
}
return true;
}
@Override
public String toString(){
StringBuilder res=new StringBuilder(statusList.toString()+symbolList.toString()+beginList.toString()+endList.toString());
for(FunctionExtension extension:functionList){
res.append("\n").append(extension.state).append(" ").append(extension.symbol).append(" ").append(extension.convertStateList);
}
return res.toString();
}
}
测试
public class NfaToDfaTest {
public static void main(String[] args){
File file = new File(new File("").getAbsoluteFile() + "/test.txt");
NFA nfa=new NFA(file);
System.out.println(nfa.convertToDFA().toString());
}
}
上一篇： BFS