使用antlr4构造我的语法树

一、编译原理

编译器的前端和后端。前端指的是编译器对程序代码的分析和理解。前端阶段只与语言的语法有关，而和目标机器无关。后端则是生成目标机器的目标代码有关。第一节说说编译器的前端技术。

一、编译器的前端和后端技术

编译器将一般会将词法和语法解析器分开实现。

1.1、词法（Lexer）

英语一般用空格和标点将单词隔开，但是在计算机，仅仅用空格和标点分割是不够的。比如“a!=5“。

词法规则玩玩是用类似于正则语法的表达式生成“有限状态机”算法，并根据这些算法切割出token。

词法规则负责从输入读取，并解析成一个个token符号。为了方便，antlr一般将这些token编号用数字表示。

词法规则 antlr语法表示规则，查看以下example：

INTERGER: DIGIT+
          |'0'[Xx] HEX_DIGIT+
          ;

• 一个分号";"表示结束
• 一个标识符必须是全大写：
• 一个冒号表示开始
• 一个"|"表示可选

可用的选项还有，类似于正则文法。

1.2.1显式词法

以大写字母开头。或者是有名的词法规则。

比如说PROJECT: "antlr4_code_gen"

1.2.2 匿名隐式词法

他的位置在于parser之后，但是在显式词法之前。一般都是以“T__数字”表示。比如说这个匿名的词法代表着一个冒号的token。

二、显式和隐式词法

1.2.3 fragment:分片表示

INTERGER: DIGIT+
          | '0' [Xx] HEX_DIGIT+
          ;
fragment DIGIT: [0-9];
fragment HEX_DIGIT: [0-9A-Fa-f];

1.2.4 词法的优先级

匹配遵循以下的优先级准则：

• 匹配输入的最多字符串的那个词法
• 如果是特殊字符比如“{”，“”:”，那么使用隐式语法匹配
• 如果匹配多个词法，则选按先后顺序找最先匹配到的那个

1.2.5 词法的命令

词法命令用于操作解析到的token，比如常用到的skip:放弃解析到的token

WHITESPACE: { \r\n}->skip

其他的还有channel(n)，type(n)，mode(n), pushMode(n)，popMode(n)

1.1.4 词法的执行动作

比如说以下的两个例子：

ID: [A-Z]+ {log{"matched rule"}}
ID: {A-Z}+ {isIdValid()}

1.2、语法（Rule）

词法分析是识别一个个token，而语法分析是识别出程序的语法树状结构。这棵树也叫做AST(Abstrace Syntax Tree)抽象语法树。参考这个网址给出的演示，https://resources.jointjs.com/demos/javascript-ast，如下的表达式将被解析出一颗AST树。

三、程序代码

四、代码对应的AST树

1.3、语义分析

语义分析的目的是消除语义中模棱两可的“二义性”。比如一个变量同时定义在花括号外部和内部，那么到底该用哪一个。

二、antlr使用

2.1Antlr是什么

antlr是java实现的编译工程，历经20多年发展，目前是4.7版本。虽然是java实现的编译工具，但是antlr支持生成cpp、java、python、c#等的解析运行库，可以当做多种语言的解析工具用。

2.2安装antlr

2.2.1 安装依赖java环境

在安装好的java环境，需要把官网下载的包antlr-4.7.2-complete.jar放在某个文件路径下，并把这个路径加到CLASS_PATH。

CLASSPATH=.:/usr/local/lib/antlr-4.7.2-complete.jar

2.3使用antlr

设置antlr4的快捷命令：

antlr4='java -jar /usr/local/lib/antlr-4.7.2-complete.jar'

根据语法文件生成相对应语言版本的解析工具代码。

Bbcode.g4的规则如下：

五、Bbcode.g4文件

生成命令：

 antlr4 -Dlanguage=Cpp -visitor ./Bbcode.g4 -o antlr4-bbcode

• -Dlangguage是生成Cpp，如果不指定，默认是java
• -visitor额外生成vistor模式访问的工具代码，没有指定默认是listener模式。
• *g4代表着你的g4文法文件
• -o输出代码文件到哪个文件夹下

输出的代码目录结构如下：

图六、antlr生成目录结构

图7、解析出的规则

图八、token词法文件

三、使用antlr-runtime构建自己的代码工程

3.1 antlr结构

提取出相对应语言版本的antlr-runtime目录到自己的工程。这里以cpp举例。https://github.com/antlr/antlr4/tree/master/runtime/Cpp。把git工程拉到本地。然后

cp Cpp /data/mariolu/antlr4-runtime -rf

在build目录执行编译，这里注意cmake设置宏把自己的antlr的jar路径替换上去

mkdir build && mkdir run && cd build
cmake      .. -DANTLR_JAR_LOCATION=/usr/local/lib/antlr-4.7.2-complete.jar -DWITH_DEMO=True
make

设置安装路径，注意吧DESTDIR设置成自己的路径

DESTDIR=/runtime/Cpp/run      make install

然后可以在/runtime/Cpp/run找到lib包和include包，这两个包都可以拷贝到自己的工程下，

图九、拷贝runtime库和头文件到自己的工程路径下

3.2 antlr的访问模式

listener模式是antlr解析AST树的各个节点，并调用相应的hook函数，而visitor需要实现遍历访问，如果没有主动visit，则不会进行处理。监听者模式有点类似于XML的解析语法，在这颗AST语法树（类似于DOM树）,当解析到node，则调用listener的hook函数接口。

两者的区别是啥：

图十、使用Listener模式和Visitor模式访问

3.2.1 使用listener模式

图十一、listener模式

3.2.2 使用visitor模式

图十二、visitor模式

四、有什么用

可以模拟解析，了解学习某种编程语言特性。

也可以自定义自己的语法规则，拿来自动化生成代码。