从零开始写一个Jison解析器(4/10)：Jison解析器生成器语法格式详解
从零开始写一个Jison解析器(4/10)：Jison解析器生成器语法格式详解
-
从零开始写一个
Jison解析器(4/10)：Jison解析器生成器语法格式详解
按行解析的解析器
前面已经成功运行了按行解析的解析器，本文以此为例详细讲解Jison解析器生成器的语法格式。
%lex
%%
[^\n\r]+ { return 'LINE'; }
[\n\r]+ { return 'EOL'; }
<<EOF>> { return 'EOF'; }
/lex
%%
p
: ll EOF
{ console.log($1); }
;
ll
: ll l
{ $$ = $1 + $2; }
| l
{ $$ = $1; }
;
l
: LINE EOL
{ $$ = $1 + $2; }
;
Jison 解析器生成器的语法结构
Jison是广泛应用的解析器生成器Bison的JavaScript移植，除了Bison中的静态类型的语义和专用于C语言的概念外，Jison和Bison中的概念基本相同。
虽然Jison的名称是Bison的首字母 B 改为JavaScript的 J，然而并不是简单移植，而是同时包含了Bison以及配合使用的Flex的功能。
使用Flex和Bison解析时处理过程包含两部分：标记解释 tokenizing 和句法分析 parsing，标记解释 tokenizing 使用Flex，这个过程也称为词法分析 lexical analysis，而Bison负责句法分析 parsing，这个过程也称为语义分析 semantic analyse。
描述句法分析 parsing 的方式被称为形式文法 formal grammar，遵循形式文法 formal grammar 的语言被称为形式语言 formal language，形式文法 formal grammar 按照乔姆斯基谱系共分为四种：
- 无限制文法
unrestricted grammar - 上下文相关文法
context-sensitive grammar - 上下文无关文法
context-free grammar - 正则文法
regular grammar
Jison的句法分析 parsing 与Bison同样采用上下文无关文法 context-free grammar。
Jison的语法文件既可以把词法分析 lexical analysis 和语义分析 semantic analyse 分成两个文件，也可以在一个文件中同时包含这两部分。使用一个文件时，使用 %lex 和 /lex 标记区分词法分析 lexical analysis 部分和语义分析 semantic analyse 部分， %lex 和 /lex 标记中的 lex 即为 lexical 的缩写。
参照前面的语法内容，从 %lex 开始到 /lex 是词法分析 lexical analysis，/lex 到结束是句法分析 parsing。
Jison 语法中的词法分析 lexical analysis 部分
词法分析 lexical analysis 中使用 %% 分成两部分，%% 之前是词法分析 lexical analysis 的定义 definitions 部分，%% 之后是词法分析 lexical analysis 的规则 rules 部分，本例中仅包含规则 rules 部分，定义 definitions 部分没有内容。规则 rules 部分包含一系列如下形式的规则 rules
pattern action
其中 pattern 为该规则 rules 匹配的模式，action 为匹配模式时执行的动作。pattern 基于正则表达式，并增加部分扩展功能。本例中词法分析 lexical analysis 的前两条规则 rules 中的模式 [^\n\r]+ 和 [\n\r]+ 即为正则表达式。
[^\n\r]+ { return 'LINE'; }
[\n\r]+ { return 'EOL'; }
本例中词法分析 lexical analysis 的第三条规则 rules 中的 <<EOF>> 即为匹配文件末尾的模式。
<<EOF>> { return 'EOF'; }
本例中三条规则 rules 中的动作 action 都是直接返回标记 token 的名称，分别为 LINE、EOL、EOF。Jison中词法分析 lexical analysis 的动作 action 使用JavaScript语法。
Jison 语法中的语义分析 semantic analyse 部分
语义分析 semantic analyse 中也使用 %% 分成两部分，%% 之前是语义分析 semantic analyse 的声明 declarations 部分，%% 之后是语义分析 semantic analyse 的语法规则 grammar rules 部分，本例中仅包含语法规则 grammar rules 部分，声明 declarations 部分没有内容。
语义分析 semantic analyse 中语法规则 grammar rules 比词法分析 lexical analysis 中的规则 rules 复杂些，基础的形式为
result : components...
;
其中 components 为语法规则 grammar rules 的组成部分，result 为匹配语法规则 grammar rules 的结果。本例中第三条语法规则 grammar rules 即为这种形式。
l
: LINE EOL
;
其中 LINE EOL 表示该语法规则 grammar rules 需要匹配两个组成部分 LINE 和 EOL，当匹配时可以得到结果 l，或者说 LINE 和 EOL 组合成 l。
LINE 和 EOL 中间的空格用于分割 LINE 和 EOL，并不参与匹配，因此可以按需增加空格。
语法规则 grammar rules 中也可以设置匹配时执行的动作 action，动作 action 放在组成部分 component 之后，本例中第三条语法规则 grammar rules 的动作 action 为 { $$ = $1 + $2; }。
l
: LINE EOL
{ $$ = $1 + $2; }
;
Jison中语法规则 grammar rules 的动作 action 使用JavaScript语法。本例中 $1 变量的值为匹配 LINE 的值，也就是词法分析 lexical analysis 中返回 LINE 的规则中模式 pattern 定义的 [^\n\r]+ 匹配的字符串。本例中 $2 变量的值为匹配 EOL 的值，也就是词法分析 lexical analysis 中返回 EOL 的规则中模式 pattern 定义的 [\n\r]+ 匹配的字符串。赋值给变量 $$ 就是 LINE 和 EOL 组合成 l 的值，本例中 $1 和 $2 字符串简单连接，在实际中可以按需处理，后面的文章中有更复杂的例子。
包含多项规则 rule 的语法规则 grammar rules
语法规则 grammar rules 也可以是匹配多种情况得到相同的结果，多个规则之间使用管道符号 | 连接，形式为
result : rule1-components...
| rule2-components...
...
;
本例中第二条语法规则 grammar rules 即为这种形式。
ll
: ll l
| l
;
其中第一项规则 ll l 表示该语法规则 grammar rules 需要匹配两个部分 ll 和 l，第二项规则 l 表示该语法规则 grammar rules 需要匹配一个部分 l。其中 l 由前面讲解的第三条语法规则 grammar rules 定义，从这条语法规则 grammar rules 可以看出，组成部分不仅可以是词法分析 lexical analysis 中的标记 token，也可以是语法规则 grammar rules 中定义的规则。
递归规则 recursive rule
组成部分是语法规则 grammar rules 中定义的规则时，不仅可以是其他语法规则 grammar rules 的结果，例如第二项规则 l，还可以是自身，例如第一项规则就是 ll 和 ·l，这种规则中包含自身的语法规则 grammar rules 有一个专门的名称————递归规则 recursive rule。
本例中的递归规则 recursive rule 是最简单的形式，最开始匹配第二项规则 l，结果为 ll，然后 ll 和紧接着的 l 匹配第一项规则 ll l，结果仍是 ll，此时的 ll 相当于两个 l，以此类推。
当语法规则 grammar rules 中包含多个规则时，每项规则都可以设置动作 action，动作 action 紧接着对应的规则，本例中两项规则分别设置了动作 { $$ = $1 + $2; } 和 { $$ = $1; }。
ll
: ll l
{ $$ = $1 + $2; }
| l
{ $$ = $1; }
;
这两项动作 action 的语法和前面相同，由于是递归规则 recursive rule，动作 action 也相应的递归执行，例如最开始匹配第二项规则 l，执行动作 { $$ = $1; }，然后 ll 和紧接着的 l 匹配第一项规则 ll l，执行动作 { $$ = $1 + $2; }，其中的 $1 即为最开始匹配第二项规则 l 的值，相当于前后两次匹配的 l 对应的字符串连接，以此类推。本例中的两个动作的结果就是按照匹配的顺序组合字符串。
动作 action 中的代码可以自由编写，例如把第一项规则的动作 { $$ = $1 + $2; } 修改为 { $$ = $2 + $1; } 即为按照逆序连接字符串，后面的文章还有更复杂的例子。
由于递归规则 recursive rule 的结果又可以匹配自身，因此在使用递归规则 recursive rule 时，为了避免匹配时出现歧义，最好将递归规则 recursive rule 的结果组合成不匹配递归规则 recursive rule 后再使用，例如本例中的第一条语法规则 grammar rules 中将 ll 和 EOF 组合成 p， ll 和 EOF 的组合不匹配 ll，这样使用 p 就可以避免直接使用 ll 导致的歧义。
p
: ll EOF
;
由于 p 是语法规则 grammar rules 中的最后组合，本例中直接在 p 的动作中输出。
p
: ll EOF
{ console.log($1); }
;
动作 action 的语法为 javascript，此处尽管匹配了 EOF，但是在动作 action 没有使用 $2，也没有赋值给 $$。动作 action 中的程序可以自由编写，后面的文章中讲解更复杂的例子时会详细讲解设计要点。
Jison 语法结构小结
综合以上内容，Jison文件的结构为
/* 词法分析 lexical analysis 开始 */
%lex
/* 词法分析 lexical analysis 中的定义 definition */
%%
/* 词法分析 lexical analysis 中的规则 rule */
/* 每一项规则 rule 包含模式 pattern 和动作 action */
pattern1 action1
pattern2 action2
pattern3 action3
/* 词法分析 lexical analysis 结束，语义分析 semantic analyse 开始 */
/lex
/* 语义分析 semantic analyse 中的声明 declarations */
%%
/* 语义分析 semantic analyse 中的语法规则 grammar rules */
/* 每一项语法规则 grammar rule 可以定义一个或者多个规则，每个规则为若干组成部分，每个规则可以定义相应的动作 action */
result1 : rule11-components...
| rule12-components...
...
;
result2 : rule21-components...
| rule22-components...
...
;
result3 : rule31-components...
| rule32-components...
...
;