词法分析

• 手写 - 有限自动机
• 工具 - Lex，基于正则表达式

语法分析

• 执行脚本语言的过程，就是遍历AST（抽象语法树）的过程
• 知道AST的作用以后，那么，怎么构造AST？
  • 自顶向下：递归下降
  • 自底向上：搭积木，先构造小单元，在组装更大单元
  • 现成的工具：Yacc Antlr JavaCC…

语义分析

• 消除语义模糊，生成一些属性信息，让计算机能够依据这些信息生成目标代码
• 语义分析的某些成果，会作为属性标注在AST上
  • 比如在age这个标识符节点和45这个字节量节点上都会标识int类型
• 树上还可以标记很多属性，有些属性在之前节点已经标注，比如行号

断词

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 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 : 文本值

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  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，只要再扩展这个有限自动机，增加里面的状态和迁移路线，就可以逐步实现一个完整的词法分析器。

正则表达式

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

  1 2 3 4

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

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