C#词法分析器之转换DFA详解
什么是词法分析?
词法分析(Lexical Analysis)是编译器中的一个步骤,也称为扫描器(Scanner)。词法分析的主要任务是将程序中的代码转换成一个个Token(标记)。Token是指单词或符号等,是编译器中的最小单位。
词法分析器的输入是源代码,识别出其中的每个Token,每个Token包括 Token种类 和 Token值 两个部分。如:
int a = 1;
其中的Token可以分别识别为:
<keyword, int> <identifier, a> <assign, => <int_constant, 1> <semicolon, ;>
什么是DFA?
DFA(Deterministic Finite Automaton)即确定有限状态自动机,它是一种计算模型的抽象概念,可以识别输入的字符串是否符合所定义的规则。
DFA可以表示为一个五元组:
(D, Σ, δ, s, F)
其中:
- D:有限状态集合
- Σ:输入字符集合
- δ:转移函数,即从一个状态根据输入字符转移到下一个状态
- s:起始状态
- F:终止状态集合
根据输入字符,每次可以从一个状态转移到另一个状态,直至输入结束并到达终止状态,判断输入的字符串是否符合规则。
DFA在词法分析中的应用
DFA可以用于词法分析器中,识别出源代码中的各个Token。可以构建多个DFA来检查源代码中的关键字、标识符、数字、运算符、分隔符等Token,从而实现对源代码的Token解析。
以下是一个构建数字识别DFA的示例:
- 首先,定义该DFA的五元组:
D = {S0, S1, S2, S3}
Σ = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.', 'e'}
s = S0
F = {S1, S2, S3}
其中,D是状态的集合,Σ是输入符号的集合,s是初始状态,F是接受状态的集合。
- 然后,定义状态和状态之间的转移函数:
δ(S0, '0') = S1
δ(S0, '1'-'9') = S2
δ(S1, '0'-'9') = S3
δ(S2, '0'-'9') = S2
δ(S2, '.') = S3
δ(S2, 'e') = S2
δ(S3, '0'-'9') = S3
δ(S3, 'e') = S2
- 最后,根据该DFA,识别输入的字符串是否为数字。例如,对于输入
"3.14"
,从状态S0开始,按照输入字符依次转移:
S0 -> S2 (input: 3)
S2 -> S3 (input: .)
S3 -> S2 (input: 1)
S2 -> S3 (input: 4)
最终到达S3状态,字符串 "3.14" 被识别为数字。
如何构建词法分析器
构建词法分析器,通常做法是:
- 定义输入字符集合
- 定义各种Token类型及其匹配的正则表达式
- 构建DFA
- 实现DFA的转移函数
- 从起始状态开始,按照输入字符进行状态转移,直至到达终止状态,识别出Token,并返回Token的类型及值
参考 https://www.cnblogs.com/bjwu/p/9674199.html
示例1:识别关键字
假设我们要实现一个只能识别 if
和 else
关键字的词法分析器,具体步骤如下:
- 定义输入字符集合:即所有的小写字母、数字、下划线
- 定义关键字类型为
keyword
- 定义
if
和else
的正则表达式:(if)|(else)
- 构建DFA:
- 定义五元组:
- D = {S0, S1, S2, S3, S4}
- Σ = {a-z, 0-9, _}
- s = S0
- F = {S3, S4}
- 定义状态之间的转移函数:
- δ(S0, 'i') = S1
- δ(S1, 'f') = S2
- δ(S2, Σ) = S3(即到达终止状态 S3,识别出
if
) - δ(S0, 'e') = S1
- δ(S1, 'l') = S2
- δ(S2, 's') = S4
- δ(S4, 'e') = S3(即到达终止状态 S3,识别出
else
) - 其他状态转移情况均指向 S0
- 实现DFA的转移函数:如下示例代码
public Token GetNextToken()
{
int state = 0;
string lexeme = "";
char c;
while ((c = _sourceCode[_currentIndex++]) != '\0')
{
lexeme += c;
switch (state)
{
case 0:
if (c == 'i') state = 1;
else if (c == 'e') state = 4;
else return null;
break;
case 1:
if (c == 'f') state = 2;
else if (c == 'l') state = 3;
else return null;
break;
case 2: // reach the end state
if (c < 'a' || c > 'z' ) return new Token(TokenType.Keyword, "if");
else return null;
case 3:
if (c == 's') state = 4;
else return null;
break;
case 4: // reach the end state
if (c < 'a' || c > 'z' ) return new Token(TokenType.Keyword, "else");
else return null;
break;
}
}
return null;
}
示例2:识别数字
假设我们要实现一个只能识别整数和浮点数的词法分析器,具体步骤如下:
- 定义输入字符集合:即所有数字字符
- 定义数字类型为
numeric
- 定义正则表达式:
- 以数字开头的整数:
[1-9][0-9]*
- 以 0 开头的整数:
0
- 浮点数:
[0-9]+(\.[0-9]+)?(e[+\-]?[0-9]+)?
- 构建DFA:
- 定义五元组:
- D = {S0, S1, S2, S3, S4, S5, S6, S7}
- Σ = {0-9}
- s = S0
- F = {S2, S3, S6}
- 定义状态之间的转移函数:
- δ(S0, '0') = S1
- δ(S0, '1'-'9') = S2
- δ(S1, Σ) = S5 (0 只能作为一位整数输入)
- δ(S2, Σ) = S2
- δ(S2, '.') = S3
- δ(S2, 'e') = S6
- δ(S5, Σ) = S5
- δ(S3, Σ) = S4
- δ(S4, Σ) = S4
- δ(S4, 'e') = S6
- δ(S6, '+'|'-'|Σ) = S7
- δ(S7, Σ) = S7
- 解释:
- 初始状态(S0)读入 '0',进入状态 S1
- 初始状态(S0)读入 '1'~'9', 进入状态 S2
- 进入状态 S1,只能接受空输入,转移到状态 S5
- 进入状态 S2,接受数字字符,作为整数部分,继续保持状态 S2
- 进入状态 S2,第一次读入 '.',进入状态 S3,开始读取小数部分
- 进入状态 S3,继续接受数字字符,进入状态 S4
- 进入状态 S4,继续接受数字字符,维持状态 S4
- 进入状态 S4,遇到字符 'e' 进入状态 S6,开始读取指数部分
- 进入状态 S5,只能接受空输入,输出整数结果
- 进入状态 S6,读入符号或数字,进入状态 S7 进行判断
- 进入状态 S7,需要接收数字字符输入,进行指数部分的匹配和判断
- 实现DFA的转移函数:如下示例代码
public Token GetNextToken()
{
int state = 0;
string lexeme = "";
char c;
while ((c = _sourceCode[_currentIndex]) != '\0')
{
lexeme += c;
_currentIndex++;
switch (state)
{
case 0:
if (c == '0') state = 1;
else if (c >= '1' && c <= '9') state = 2;
else return null;
break;
case 1:
if (c >= '0' && c <= '9') return null;
else return new Token(TokenType.Number, lexeme);
case 2:
if (c >= '0' && c <= '9') state = 2;
else if (c == '.') state = 3;
else if (c == 'e') state = 6;
else return new Token(TokenType.Number, lexeme);
break;
case 3:
if (c >= '0' && c <= '9') state = 4;
else return null;
break;
case 4:
if (c >= '0' && c <= '9') state = 4;
else if (c == 'e') state = 6;
else return new Token(TokenType.Number, lexeme);
break;
case 5:
return new Token(TokenType.Number, lexeme);
case 6:
if (c == '+' || c == '-') state = 7;
else if (c >= '0' && c <= '9') state = 8;
else return null;
break;
case 7:
if (c >= '0' && c <= '9') state = 8;
else return null;
break;
case 8:
if (c >= '0' && c <= '9') state = 8;
else return new Token(TokenType.Number, lexeme);
break;
}
}
return null;
}
以上是构建C#词法分析器中转换DFA的详细攻略,希望能对大家有所帮助。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C#词法分析器之转换DFA详解 - Python技术站