工具¶

编译器前端工具:

词法分析: Lex（或其 GNU 版本，Flex）
语法分析: Yacc（或 GNU 的版本，Bison）、Antlr、JavaCC
Antlr

1. 有限自动机是比较简单的一种自动机，对应于正则文法，也叫做 3 型文法
    又叫做线性文法（Linear Grammar）。
    它的特点是产生式的右边部分最多只有一个非终结符，
    比如 X->aYb，其中 a 和 b 是终结符
2. 比它强大的是下推自动机，对应于上下文无关文法，也叫做 2 型文法
    区别: 上下文无关文法允许递归调用，而正则文法不允许
    上下文相关的情况: 不是语法分析阶段负责的，而是放在语义分析阶段来处理的
3. 比它更强大的是线性有界自动机，对应于上下文相关文法，也叫 1 型文法
4. 图灵机的范围比它们都大，它对应 0 型文法。你任何能用产生式写出来的文法规则，都属于 0 型文法

LLVM 的文档里有一个小的教程，做了一个完整的前端: https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html
脚本语言playscript: https://github.com/xiaomiwujiecao/playscript-java
教程相关源码: https://github.com/RichardGong/PlayWithCompiler
Anluin’s Learning Algorithm

语法分析的原理
递归下降算法（Recursive Descent Parsing）
上下文无关文法（Context-free Grammar，CFG

语法和文法有什么区别:

1. 文法，英文叫做Grammar，是形式语言（Formal Language）的一个术语
    正则文法(Regular Grammar)、上下文无关文法(Context-free Grammar)等，用来描述词法和语法
2. 语法，英文是Syntax，主要是描述词是怎么组成句子的
    一个语言的语法规则，通常指的是这个Syntax

递归下降:

采用递归下降算法，总是采用深度优先的策略，先解析最左子节点，然后解析最左子节点的最左子节点。
等着这棵子树完全构建完毕了，再构建第二棵子树。

会导致两个问题，一个是“回溯”，一个是不能处理左递归文法。