词法分析

• 手写 - 有限自动机
• 工具 - 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中有详细的规则说明

• 很多国外厂商的软件，普遍都具备二次编程能力，拥有自己的语言和生态。

联系

• 作为程序员，在实际工作中经常会碰到需要编译技术的场景
  • Hibernate & HQL的解析
  • Spring & 注解的支持和字节码动态生成
  • 模板引擎 & 条件分支、循环
  • 解析用户输入
  • 防止代码注入
  • 提供像React那样的DSL
  • 提供像TypeScript那样的把一门语言翻成另一门
  • 像CMake和Maven那样通过配置文件来灵活工作
  • 运维工程师分析日志文件
• 提升程序员的竞争力
  • 理解底层机制，深入思考问题
  • 培养深层次解决问题的能力，而不仅从表面解决问题
• 维度
  • 前端语法
  • 代码优化
  • 硬件结合

克服畏难心理

• 通过具体案例理解抽象原理
• 切实体会某个技术在哪个环节中发挥什么作用
• 在工作中真正运用到编译技术
  • Antlr工具的使用：做编译器前端
  • LLVM工具的使用：做编译器后端

课程规划

1. 编译器前端，即词法、语法、语义三大分析
   • 了解原理
   • 实现一门脚本语言
   • 使用工具提升编译工作的效率
   • 在应用场景中检验学习成果
2. 编译器后端，如何生成目标代码和对代码进行优化
   • 纯手工生成汇编代码
   • 引入中间代码
   • 使用后端工具LLVM
   • 生成可执行文件能支持及时编译
   • 多层优化
3. 发展趋势
   • 人工智能
   • 云编程