实现一个简单的词法分析器
词法分析
词法分析的工作是将一个长长的字符串识别出一个个的单词，这一个个单词就是 Token。而且词法分析的工作是一边读取一边识别字符串的，不是把字符串都读到内存再识别
词法单元:
-
单词的内部表示是词法单元 token
-
编程语言中最小的语法单元
-
词法单元的表示
目标程序语句:
- age >= 45
解析age >= 45
过程图:
图1.png
标识符、比较操作符和数字字面量这三种 Token 的词法规则:
- 标识符：第一个字符必须是字母，后面的字符可以是字母或数字
-
比较操作符：> 和 >=（其他比较操作符暂时忽略）
-
数字字面量：全部由数字构成（像带小数点的浮点数，暂时不管它）
有限自动机:
图2.png
- 初始状态：刚开始启动词法分析的时候，程序所处的状态
- 标识符状态：在初始状态时，当第一个字符是字母的时候，迁移到状态 2。当后续字符是字母和数字时，保留在状态 2。如果不是，就离开状态 2，写下该 Token，回到初始状态
- 大于操作符（GT）：在初始状态时，当第一个字符是 > 时，进入这个状态。它是比较操作符的一种情况
- 大于等于操作符（GE）：如果状态 3 的下一个字符是 =，就进入状态 4，变成 >=。它也是比较操作符的一种情况
- 数字字面量：在初始状态时，下一个字符是数字，进入这个状态。如果后续仍是数字，就保持在状态 5
圆圈有单线的也有双线的。双线的意思是这个状态已经是一个合法的 Token 了，单线的意思是这个状态还是临时状态。
标识符和关键字规则的冲突
解析“int age = 40”这个语句，以这个语句为例研究一下词法分析中会遇到的问题：多个规则之间的冲突。
问题：
- int 这个关键字，与标识符很相似，都是以字母开头，后面跟着其他字母
换句话说，int 这个字符串，既符合标识符的规则，又符合 int 这个关键字的规则，这两个规则发生了重叠。这样就起冲突了，我们扫描字符串的时候，到底该用哪个规则呢？
当然int 这个关键字的规则，比标识符的规则优先级高。普通的标识符是不允许跟这些关键字重名的。
关键字是语言设计中作为语法要素的词汇，例如表示数据类型的 int、char，表示程序结构的 while、if，表述特殊数据取值的 null、NAN 等。
在词法分析器中，如何把关键字和保留字跟标识符区分开
修改自动机为下面的形式:
当第一个字符是 i 的时候，我们让它进入一个特殊的状态。接下来，如果它遇到 n 和 t，就进入状态 4。但这还没有结束，如果后续的字符还有其他的字母和数字，它又变成了普通的标识符。比如，我们可以声明一个 intA（int 和 A 是连着的）这样的变量，而不会跟 int 关键字冲突。
代码实现
以 int x = 45为分析目标
定义Token:
自定义的Token:
public interface Token {
// 获取类型
TokenType getTokenType();
// 获取文本值
String getText();
}
TokenType:Token类型
是标识符，比较操作符还是数字字面量？
public enum TokenType {
// 先定义了少量的类型 主要了解 整个过程 有需要可以后续再添加
Assignment,// =
Identifier, //标识符
IntLiteral, //整型字面量
StringLiteral, //字符串字面量
GE, // >=
Int
}
在主类中定义一个私有类:SimpleToken
图示:
private final class SimpleToken implements Token {
private TokenType tokenType = null;
private String text = null;
@Override
public TokenType getTokenType() {
return tokenType;
}
@Override
public String getText() {
return text;
}
}
使用枚举类来表示有限状态机的各种状态
private enum DfaState {
Initial,
If, Id_if1, Id_if2, Else, Id_else1, Id_else2, Id_else3, Id_else4, Int, Id_int1, Id_int2, Id_int3, Id, GT, GE,
Assignment,
Plus, Minus, Star, Slash,
SemiColon,
LeftParen,
RightParen,
IntLiteral
}
现在考虑数据的处理:
图示:
图5.png
// 开始解析 进入初始化状态
// 解析完一个Token 也进入初始化状态
private DfaState initToken(char ch) {
if (tokenText.length() > 0) {
current_token.text = tokenText.toString();
tokens.add(current_token);
tokenText = new StringBuilder();
current_token = new SimpleToken();
}
//初始状态
DfaState dfaState = DfaState.Initial;
if (isAlpha(ch)) { //第一个字符是字母
// 出现了字符 'i'
if (ch == 'i') {
dfaState = DfaState.Id_int1;
} else {
dfaState = DfaState.Id; //进入Id状态
}
current_token.tokenType = TokenType.Identifier;
tokenText.append(ch);
} else if (isDigit(ch)) { //第一个字符是数字
dfaState = DfaState.IntLiteral;
current_token.tokenType = TokenType.IntLiteral;
tokenText.append(ch);
} else if (ch == '=') {
dfaState = DfaState.Assignment;
current_token.tokenType = TokenType.Assignment;
tokenText.append(ch);
} else {
dfaState = DfaState.Initial;
}
return dfaState;
}
public SimpleTokens lexicalanalyz(String resource) throws IOException {
tokens = new ArrayList<>();
CharArrayReader reader = new CharArrayReader(resource.toCharArray());
tokenText = new StringBuilder();
current_token = new SimpleToken();
int int_for_char = 0;
char char_for_int = 0;
DfaState dfaState = DfaState.Initial;
while ( (int_for_char = reader.read()) != -1 ) {
char_for_int = (char) int_for_char;
switch (dfaState) {
case Initial:
dfaState = initToken(char_for_int);
break;
case Id:
if (isDigit(char_for_int) || isAlpha(char_for_int)) {
tokenText.append(char_for_int);
} else {
dfaState = initToken(char_for_int);
}
break;
case GT:
if (char_for_int == '=') {
current_token.tokenType = TokenType.GE;
dfaState = DfaState.GE;
tokenText.append(char_for_int);
} else {
dfaState = initToken(char_for_int);
}
break;
case GE:
case Assignment:
case IntLiteral:
if (isDigit(char_for_int)) {
tokenText.append(char_for_int);
} else {
dfaState = initToken(char_for_int);
}
break;
case Id_int1:
if (char_for_int == 'n') {
dfaState = DfaState.Id_int2;
tokenText.append(char_for_int);
} else if (isDigit(char_for_int) || isAlpha(char_for_int)) {
dfaState = DfaState.Id;
tokenText.append(char_for_int);
} else {
dfaState = initToken(char_for_int);
}
break;
case Id_int2:
if (char_for_int == 't') {
dfaState = DfaState.Id_int3;
tokenText.append(char_for_int);
}
else if (isDigit(char_for_int) || isAlpha(char_for_int)){
dfaState = DfaState.Id; //切换回id状态
tokenText.append(char_for_int);
}
else {
dfaState = initToken(char_for_int);
}
break;
case Id_int3:
if (isBlank(char_for_int)) {
current_token.tokenType = TokenType.Int;
dfaState = initToken(char_for_int);
}
else{
dfaState = DfaState.Id; //切换回Id状态
tokenText.append(char_for_int);
}
break;
default:
}
}
if (tokenText.length() > 0) {
initToken(char_for_int);
}
return new SimpleTokens(tokens);
}
网友评论