使用antlr4构造我的语法树

  • 2020 年 1 月 13 日
  • 笔记

一、编译原理

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

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

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

1.1、词法(Lexer)

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

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

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

词法规则 antlr语法表示规则,查看以下example:

INTERGER: DIGIT+            |'0'[Xx] HEX_DIGIT+            ;
  • 一个分号";"表示结束
  • 一个标识符必须是全大写:
  • 一个冒号表示开始
  • 一个"|"表示可选

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

词法

意义

A

匹配A

A B

匹配A紧接着匹配B

(A|B)

匹配A或者B

‘text’

匹配text字符串

A?

A出现0次或者1次

A+

A出现1次或者多次

A*

A出现0次或者多次

[A-Z0-9]

在范围内的字符或数字

‘a’..'z'

类似于[a-z],另一种表达

-[A-Z]

不匹配[A-Z]的字符

.

任意字符

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: { rn}->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模式

四、有什么用

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

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