Hive-技术补充-ANTLR语法编写

一、导读

我们学习一门语言，或外语或编程语言，是不是都是要先学语法，想想这些语言有哪些相同点

        1、中文、英语、日语......是不是都有 主谓宾 的规则

        2、c、java、python、js......是不是都有 数据类型 、循环 等语法或数据结构

虽然人们在过去的几十年里发明了多种编程语言，但基本的语言模式并不多。因为他们在设计时都会情不自禁的与自己脑海中的自然语言关联，并用数学符号表达了出来。因此如果你掌握了一门语言后再去学其他语言就会变的容易。总结下来有四种抽象的计算机语言模式：

        1、序列：即一列元素，例如一个数组初始化时给的一串值

        2、选择：在多种可选方案中做出选择，例如编程语言中的if语句

        3、词法符号依赖：一个词法符号往往成对出现，比如{} () []

        4、嵌套结构：一种自相似的语言结构，例如编程语言中的if嵌套 for嵌套

为了表达以上模式，我们先了解下巴克斯-诺尔范式（Backus Normal Form简称BNF）

二、巴克斯-诺尔范式

是一种用于表示上下文无关文法的语言，它是由约翰·巴科斯（John Backus）和彼得·诺尔（Peter Naur）首先引入的用来描述计算机语言语法的符号集。

几乎所有程序设计语言都是通过上下文无关文法来定义的。巴克斯-诺尔范式是上下文无关语法的一个例子。

而且上下文无关文法足够简单可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生，例如 LR 分析器和 LL 分析器。

三、从编程语言中提取语法

可以形象的理解为就像从一堆字符串中抽取一系列正则表达式来把他们完全表达出来，只是语法比正则表达式更丰富。

讨论语法的整体结构以及如何建立初始的语法框架，是任何编程语言项目的基础步骤。

语法由一个为该语法命名的头部定义和一些列可以相互引用的语言规则组成，例如：

grammar MyG；
rule1 : 《stuff》;
rule2 : 《more stuff》;
......

tuff 和 more stuff 为语言规则

下面我们来表达下常用的四种语言模式

1、序列模式

可以直接使用 类似 'RETR'的常量字符串来表示任意简单字符序列，如关键字、标点符号等
我们使用语法规则来为编程语的特定结构命名，就像我们编程时为多次相同功能命名的函数

+ 字符串表示一个或多个元素的情况

* 字符串表示0个或多个元素的情况

file : (row '\n')* ; //以一个 '\n' 作为终止符的序列
row : field(',',field)* ;  //以一个 ',' 作为分隔符的序列
field:INT ; //假设字段都是整数

file 规则使用带终止符的序列模式来匹配0或多个row\n 序列
row 规则使用带分隔符的序列来匹配一个field 后面跟着0个或多个','field 序列的情形
','隔开了所有field 。rwo规则匹配类似 1、1,2 以及 1,2,3 的序列 

2、选择模式

使用 | 表达编程语言中的选择模式，可以分割多个可选的语法结构，例如：

filed : INT | STRING ;

type: 'float' | 'int' | 'void'

stmt : node_stmt

        | edge_stmt

        | attr_stmt

        | id '=' id

        | subgraph

        ;

3、词法符号依赖模式

举个例子，如果我们在某个语句中看到了 [ ，就必须在同一个语句中找到与它匹配的 ] ，
通常[] 会把其他元素包裹起来，比如数组的初始化声明。
可以这样表示 ：

vector : '[' INT+ ']' ;

4、嵌套模式

如果一条规则的定义中需要用到它自身，我们就需要一条嵌套规则，比如递归规则。下面时一条while循环的嵌套规则

stat : 'while' '(' expr ')' stat //匹配while语句
    | '{' stat* '}'                 //匹配 {} 中若干条语句组成的代码
    ......                         //其他语句
    ;

四、优先级处理

我们先来写一个包含乘法和加法的语法：

expr : expr '*' expr //匹配由 '*' 运算符连接的子表达式
    | expr '+' expr  //匹配由 '+' 运算符连接的子表达式
    | INT
    ;

当处理 1 + 1 和 2*2 时没有问题，但是当处理 1+1*2 时就会由问题，

ANTLR 通过优先选择位置靠前的备选分支来解决歧义问题，这隐式的运行我们指定运算符优先级

尽管如此，一些运算符（例如指数运算符）是从右向左结合的，所以我们需要在这样的运算符上使用assoc选项手工指定结合性，这样，输入的 2^3^4就能够被正确解释为 2^(3^4)

expr : <assoc=right> expr '^' expr //运算符是右结合的
    | INT
    ;

此外还可以使用优先级上升来解决这个问题

五、常见的词法结构

在词法角度上，不同编程语言的外观十分相似。也就是我们只需要描述标识符和整数一次，稍加改动，就可以将它运用于大多数编程语言中。

词法分析器也是使用不同的规则来描述繁多的语言结构。和语法分析器不同的是它是通过输入的字符流来识别特定语言结构

ANTLR运行词法规则和语法规则写在同一个文件中。不过词法分析和语法分析是两个不同的阶段，ANTLR是通过这种方式区分的：词法规则以大写字母开头，语法规则以小写字母开头。

例如 ID 是要给词法规则 expr 是一个语法规则

下面让我们一起来构造些常见词法符号的词法规则：

1、匹配标识符

ID : ('a'..'z'|'A'..'Z')+ ; //匹配1个或多个大小写字母
ID : [a-zA-Z]+ ; //匹配1个或多个大小写字母

有时不同的规则会起到冲突，比如

grammar KeywordTest;
enumDef : 'enum' '{'...'}';
......
FOR : 'for';
ID : [a-zA-Z]+ ; //不会匹配'enum'和'for'

按照语法ID规则也可以匹配到'enum'和'for' ，ANTLR词法分析器解决歧义的方式优先使用靠前的词法规则。

2、匹配数字

INT : '0'..'9'+; //匹配1个或多个数字
INT : [0-9]+;     //匹配1个或多个数字

不过浮点数要复杂的多：

FLOAT : DIGIT+'.' DIGIT* //匹配 1.39 3.1569 等...
    | '.' DIGIT+          //匹配 .1 .3654 等...
    ;
    
fragment
DIGIT : [0-9]; //匹配单个数字

这里我们使用了一条辅助规则 DIGIT，这样就不用重复书写了。将一条规则声明为fragment可以告诉ANTLR该规则不是词法符号，它只会被其他词法规则使用。

3、匹配字符串常量

STRING : '"' .*? '"'; //匹配"..." 间的任意文本

其中 . 匹配任意的单个字符。*表示0或多个字符 ? 是通过正则表达式提供了对贪婪子规则的支持

但是还不够完善，因为字符串中不应该再出现双引号。如果要加双引号必须加上转义符 \
 

STRING : '"' (ESC|.)*? '"';
fragment
ESC : '\\"' | '\\\\' ; //双字符序列 \" 和 \\

4、匹配注释和空白字符

当词法分析器匹配到我们定义的规则后，会把这些词法符号放入词法符号流，输送给语法分析器。

语法分析器检查词法符号流的语法结构，但是如果其中有注释或空白字符时，会十分容易出错，因此我们需要在词法匹配时就将它去除

assign : ID (WS|COMMENT)? '=' (WS|COMMENT)? expr (WS|COMMENT) ? ;

我们再使用 skip 指令通知词法分析为i将它丢弃
LINE_COMMENT : '//' .*? '\r'? '\n' -> skip ; //匹配 "//" 任意字符序列 '\n' 
COMMENT : '/*' .*? '*/' -> skip ; //匹配 "/*" 任意字符序列 '*/' 

注意windows上的换行符是 '\r\n' 而 linux上的换行符是 '\n' (因此注意windows上的文本文件上传到linux后每行会多一个\r符号)

另外词法分析器可以接收多种位于 -> 之后的指令 ，skip 只是其中一种 ，例如 channel 指令代表一个隐藏通道 

下面我们看下 空白字符的处理 

大多数编程语言将空白字符看作词法符号间的分隔符，并将它们忽略 比如 int a = 1 ; 

（python是个例外，它使用空白字符来表达某些语法的目的：换行符代表一行命令的终止，特定数量的缩进指明嵌套的层级）

下列规则告诉 ANTLR 丢弃空白字符

WS : (' '|'\t'|'\r'|'\n')+ -> skip ; //匹配一个或多个空白字符并将它们丢弃

WS : [ \t\r\n]+ -> skip ; //匹配一个或多个空白字符并将它们丢弃

六、词法分析器和语法分析器的界限

词法和语法规则在一份文件中，且词法规则可以包含递归，这使得词法分析器变的和语法分析器一样强大，甚至可以匹配一些语法结构。

划定词法分析器和语法分析器的界限不仅是语言的职责，更是语言编写的应用程序的职责。

词法分析器应该匹配并丢弃任何语法分析器无须知晓的东西。比如注释和空白字符。

由词法分析器来匹配类似标识符、关键字、字符串、数字的常见词法符号。语法分析器的层级更高，所以我们不应当让它处理将数字组合成整数这样的事情，
这会加重它的负担。

将语法分析器无需区分的词法结构归为同一个词法类型符号。

例如：如果我们的程序对待整数和浮点数的方式是一致的，那就可以把它们都归纳为 NUMBER 类型的词法符号。

同样的将可以以相同方式处理的实体归为一类，

例如：如果语法分析器不关心xml的内容，词法分析器就可以将<>中的所有内容归为一个名为 TAG 的词法符号类型

相反，如果语法分析器需要把一种类型的文本拆开处理，那么词法分析器就应该将它的各个组成部分作为独立的词法符号输送个语法分析器

语法分析器和词法分析器是灵活的，受我们支配的，我们可以根据需求的不同来规定他们的功能和界限

比如我们有这样一个需求：

我们在代理服务器上有一份日志文件（ip 请求方法 状态码），日志内容如下
192.168.56.239 "GET /download/foo.html HTTP/1.0" 200
......

当我们大脑看到这些信息后很自认的就可以想出很多统计逻辑，不过我们的需求只是统计行数，

那我们就可以忽略到里面每行的的内容，只关注换行符即可

语法文件部分内容如下：
file : NL+ ;                     //匹配换行符序列的语法分析器
STUFF: ~'\n'+ -> skip ; //除 '\n' 之外的字符全部丢掉
NL : '\n' ;                       //将设定的换行符返回给语法分析器或者其他的调用者

接下来我们增加一个需求：

从日志文件中提取ip地址列表，这意味着我们需要一条匹配ip地址的词法规则，最好还有一些词法规则来匹配一行记录中的其他元素

语法文件部分内容如下：

file : row ;                        //匹配日志文件中全部行的语法规则
row : ip STRING INT NL ;            //匹配日志文件中的一行记录

IP : INT '.' INT '.' INT '.' INT ;  //匹配ip 例如 192.168.56.239
INT : [0-9]+ ;                         //匹配ip地址中的一个字节或者http的状态码
STRING : '"' .*? '"' ;                 //匹配http请求方法
NL : '\n';                            //匹配一行记录的终止符
WS : ' ' -> skip ;                    //忽略空格

我们也可以把IP词法规则转换成ip语法规则，只需要转换成小写即可

file : row ;                        //匹配日志文件中全部行的语法规则
row : ip STRING INT NL ;            //匹配日志文件中的一行记录
ip : INT '.' INT '.' INT '.' INT ;  //匹配ip 例如 192.168.56.239

INT : [0-9]+ ;                         //匹配ip地址中的一个字节或者http的状态码
STRING : '"' .*? '"' ;                 //匹配http请求方法
NL : '\n';                            //匹配一行记录的终止符
WS : ' ' -> skip ;                    //忽略空格