02-词法分析

断词

1. 写出正则表达式
2. 画出有限自动机
3. 代码

# initToken(ch)
DFA_state new_state = DFA_state.INIT
if isAlpha(ch):
	new_state = DFA_state.ID
	token.type = TokenType.Identifier
	token_text.append(ch)
elif isDigit(ch):
	new_state = DFA_state.IntLiteral
	token.type = TokenType.IntLiteral
	token_text.append(ch)
elif ch == '>':
	new_state = DFA_state.GT
	token.type = TokenType.GT
	token_text.append(ch)

• Token有两个属性

  • type : 类型（枚举类型的值）
  • text : 文本值

  case Initial:
  	state = initToken(ch);
  case ID:
  	if isAlpha(ch) or isDigit(ch):
  		token_text.append(ch)
  	else:
  		state = initToken(ch) # 退出ID状态，保存Token
  	break
  case IntLiteral:
  	if isDigit(ch) :
  		token_text.append(ch)
  	else :
  		state = initToken(ch)
  	break
  case GT:
  	if ch == '=':
  		token.type = TokenType.GE
  		state = DFA_state.GE
  		tokenText.append(ch)
  	else:
  		state = initToken(ch)
  	break
  case GE:
  	state = initToken(ch)
  	break

• 词法分析的核心，就是依据构造好的DFA，在不同的状态迁移，从而解析出Token，只要再扩展这个有限自动机，增加里面的状态和迁移路线，就可以逐步实现一个完整的词法分析器。

正则表达式

• 为了更加形式化地描述词法规则。
• 优化

  ID: [a-zA-Z_]([a-zA-Z_]|[0-9])*
  IntLiteral: [0-9]+
  GT: '>'
  GE: '>='

• 不同工具的RE写法会略有不同，参考具体文档
  • 比如Java的正则表达式工具在java.util.regex包中，在Javadoc中有详细的规则说明