动手实现第二个文法定义

为什么是第二个呢？因为第一个我们已经在计算器那边实现了。

ANTLR的g4文法规则补充

在上一节中，我们学到了文法定义的概念，以及ANTLR文法定义的规则。我们补充一下：

• 词法规则的匹配结果是终结符；语法规则的匹配结果是非终结符。
• 词法规则、词法片段规则（fragment开头）首字母要大写；语法规则首字母要小写。
  • 词法规则使用到的式子只能是字符或者词法片段，以及字符串，不能是其他词法规则；词法片段仅用于词法规则中，不会被当作终结符；
  • 词法片段规则使用到的式子只能是词法片段规则，以及字符串；
  • 语法规则使用到的式子可以是语法规则和词法规则，以及字符串；
• []表示括号内部的字符选其一，[0-9]表示从0到9的字符选其一；+代表1个或者多个；*代表0个或者多个；?代表0个或1个
• 形如rule : 'rule'| 'grammar' ;称为一个完整规则。其中|隔开多个候选式，这些候选式共用一个规则名。
• 在候选式内可以用括号()和|如：expr: expr ('*'|'/') expr | '1';表示候选式可以匹配expr '*' expr或者expr '/' expr。

更多ANTLR的规则请参考《ANTLR4权威指南》。

回顾计算器的文法定义文件

grammar Expr;
prog:   (expr NEWLINE)* ;
expr:   expr ('*'|'/') expr
    |   expr ('+'|'-') expr
    |   INT
    |   '(' expr ')'
    ;
NEWLINE : [\r\n]+ ;
INT     : [0-9]+ ;

我们可以看到在Expr.g4文件中：

• 小写字母开头的规则有prog和expr，这是语法规则。
  • prog: (expr NEWLINE)* ;表示prog是由无数个表达式后连着换行组成的。也就是说，在我们定义的语言内，可以由无数个表达式，中间由换行隔开。
  • expr则是表达式的定义了，定义了四则运算，并从上到下设置了优先级顺序（括号表达式和INT除外，因为匹配算法让它们没有二义性）。
• 大写字母开头的规则有NEWLINE和INT，这是词法规则。
  • NEWLINE : [\r\n]+ ;表示匹配一个或者多个换行符号
  • INT : [0-9]+ ;表示匹配一个或者多个0到9的数字

prog没有被任何规则引用，因此它是语法树入口。

现在，由于表达式expr太弱了，我们无法区分候选式，以及候选式内部的运算符，我们给它们命个名：

grammar Expr;
prog:   (expr NEWLINE)* ;
expr:   expr op=('*'|'/') expr  #mulDivExpr
    |   expr op=('+'|'-') expr  #addSubExpr
    |   INT                     #intExpr
    |   '(' expr ')'            #parenExpr
    ;
NEWLINE : [\r\n]+ ;
INT     : [0-9]+ ;

这样，就可以在程序中用op作为片段规则名索引到操作符，用mulDivExpr作为候选式规则名标注了候选式节点了。值得一提的是，候选式规则名不可以与其他规则名重复。

此外，在标注上，可以用left+=expr用left列表来接收expr。具体例子看Llang的一节。

从JSON文法定义说起

现在，你可能对设计一种文法还是毫无头绪。

还记得我们学习过的JSON这样的描述性文本语言吗？它如此简单的规则，是不是很容易就被说明了呢？

首先，我们要有自顶向下、分类的思维：

• 一个JSON只有一个值。
• 这个值可以是对象、列表、字面量
• 对象是由{ }与其中的多个key-value对组成的。
  • key只能是字符串，value就是上述定义的值。
• 列表是由[ ]与其中的值组成的。

可以看到，我们的思维路径是，自顶向下地拆解JSON的语言定义，我们可以初步尝试给我们定义的概念设置规则名，例如：json；value、object、list、literal；pair；key。

接下来，我们将规则名写入g4文件中，并建立初步的规则：

json: value;
value: object | list | literal;
object: '{' pair (',' pair )*  '}'
	| '{' '}'
	;
list: '[' value (',' value)* ']'
	| '[' ']'
	;
pair: key ':' value;
key: ...

我们可以看到，我们用pair (',' pair )*方式来定义连续的，只由逗号分隔的一串文本；而用候选式匹配空的内容。这是一个套路。

然后我们发现，定义到key之后似乎往下不了。这时候需要拆解词法规则了。一般来说，词法规则比较固定，可以参照一些正则表达式的写法，或者参照一些其他语言的写法。

NUMBER
    : '-'? INT ('.' [0-9]+)? EXP?
    ;

fragment INT
    : '0'
    | [1-9] [0-9]*        // integer part forbis leading 0s (e.g. `01`)
    ;

fragment EXP
    : [Ee] [+\-]? [0-9]+    // exponent number permits leading 0s (e.g. `1e01`)
    ;

我们分析一下数字的写法，可以发现，还是按照数字的规则给数字分片段，每个片段再额外定义规则。

最后，我们不要忘记省略定义过程中出现的空白符号，用词法规则WS: [ \t\n\r]+ -> skip可以忽略掉一系列空白符。

为什么在语言文件中WS词法规则没被引用，却可以忽略掉空白符呢？这是因为词法分析是编译器处理的优先步骤，输入文本的所有符号都会先进行词法分析。这时候如果词法规则没有被语法规则引用或者匹配到语法规则中的字符串，则相当于被忽略掉了。

让我们看看完整的JSON文法规则是怎么定义的：

/** Taken from "The Definitive ANTLR 4 Reference" by Terence Parr */

// Derived from https://json.org

// $antlr-format alignTrailingComments true, columnLimit 150, minEmptyLines 1, maxEmptyLinesToKeep 1, reflowComments false, useTab false
// $antlr-format allowShortRulesOnASingleLine false, allowShortBlocksOnASingleLine true, alignSemicolons hanging, alignColons hanging

grammar JSON;

json
    : value EOF
    ;

obj
    : '{' pair (',' pair)* '}'
    | '{' '}'
    ;

pair
    : STRING ':' value
    ;

arr
    : '[' value (',' value)* ']'
    | '[' ']'
    ;

value
    : STRING
    | NUMBER
    | obj
    | arr
    | 'true'
    | 'false'
    | 'null'
    ;

STRING
    : '"' (ESC | SAFECODEPOINT)* '"'
    ;

fragment ESC
    : '\\' (["\\/bfnrt] | UNICODE)
    ;

fragment UNICODE
    : 'u' HEX HEX HEX HEX
    ;

fragment HEX
    : [0-9a-fA-F]
    ;

fragment SAFECODEPOINT
    : ~ ["\\\u0000-\u001F]
    ;

NUMBER
    : '-'? INT ('.' [0-9]+)? EXP?
    ;

fragment INT
    // integer part forbis leading 0s (e.g. `01`)
    : '0'
    | [1-9] [0-9]*
    ;

// no leading zeros

fragment EXP
    // exponent number permits leading 0s (e.g. `1e01`)
    : [Ee] [+\-]? [0-9]+
    ;

// \- since - means "range" inside [...]

WS
    : [ \t\n\r]+ -> skip
    ;

这里EOF代表文件末尾或者字符流末尾的意思，这是为了严格规定输入文本只能匹配本文法。

从Llang定义起

Llang是小豆8593设计，XiLaiTL实现的一款列表语言。XiLaiTL/Llang: List Language (github.com)

从文法定义上来看，Llang的特点是，语法规则非常简单，而表达式则非常多用。

我们可以看到，首先我们定义了程序入口规则application，由于一个文件就是一个列表，因此定义listContent作为文件内容。列表内容则由列表表达式listExpression与值表达式valueExpression分开。他们的区别是运算的时机。

单纯从寥寥几个定义，我们就把Llang说得七七八八了。

grammar llang_simple;

application: (','? listContent)*;

listExpression
    : left+=identifier ('\'' left+=identifier)* ':' right=valueExpression                                              # defineExpression
    | left+=valueExpression ('\'' left+=valueExpression)*  '>'+                                                        # popExpression
    | left+=valueExpression ('\'' left+=valueExpression)* '<' right+=valueExpression ('\'' right+=valueExpression)*    # pushExpression
    | left+=valueExpression ('\'' left+=valueExpression)*  '->' right+=valueExpression ('\'' right+=valueExpression)*  # selectExpression
    | left+=valueExpression ('\'' left+=valueExpression)*                                                              # runExpression
    | ('~'|'del') right+=valueExpression ('\'' right+=valueExpression)*                                                # deleteExpression
    | left+=valueExpression ('\'' left+=valueExpression)*  '=' right=valueExpression                                   # assignmentExpression
    | left+=valueExpression ('\'' left+=valueExpression)*  '++'                                                        # selfPlusExpression
    | '(' listExpression ')'                                                                                           # parenExpression
    ;

valueExpression
    : identifier                                 # singleName
    | '[' (listContent (','? listContent)*)? ']' # anonymousList
    | valueExpression '[' NumericLiteral ']'     # getChild
    | '&' valueExpression                        # connectToNew
    ;

listContent
    : listExpression ';'   #listContentList
    | valueExpression      #listContentValue
    ;

NumericLiteral
    : '-'? DecimalIntegerLiteral
    ;
fragment DecimalIntegerLiteral
    : '0'
    | [1-9] [0-9]*
    ;
identifier
    : Identifier
    | NumericLiteral
    | Colon
    | SelectArrow
    | Push
    | Pop
    | GlobalList
    | SelfPlus
    | Assign
    | DeleteWord
    | Delete
    | '#' Identifier
    ;
Identifier: IdentifierPart+;
fragment IdentifierPart: [a-z_A-Z];

OpenBracket:                    '[';
CloseBracket:                   ']';
OpenParen:                      '(';
CloseParen:                     ')';
Colon:                          ':';
SemiColon:                      ';';
SelectArrow:                   '->';
Push:                           '<';
Pop:                            '>';
GlobalList:                     '@';
Comma:                          ',';
SelfPlus:                      '++';
Assign:                         '=';
DeleteWord:                   'del';
Delete:                         '~';
Connect:                        '&';
Seperator:                     '\'';
FilePrefix:                     '#';

WS: [ \t\n\r] + -> skip;

从SysY语言定义起

SysY语言是C语言的一个子集，通常用做编译原理的实验与比赛。

C语言由定义内容、语句和表达式三部分组成。以此我们可以区分这三者。

观察SysY.g4，我们可以看到，表达式的优先级次序，可以通过语法定义，而非候选式的优先级表达出来。例如：

/*乘除模表达式*/
mulExp: left=unaryExp (op+=('*' | '/' | '%') right+=unaryExp )* ;
/*加减表达式*/
addExp: left=mulExp (op+=('+' | '-') right+=mulExp)* ;
/*关系表达式*/
relExp: left=addExp (op+=('<' | '>' | '<=' | '>=') right+=addExp)*;
/*相等性表达式*/
eqExp: left=relExp (op+=('==' | '!=') right+=relExp)*;

通过这样包围方式的引用，也可以完成不同于Llang的优先级次序定义，请读者分析讨论。

grammar SysY;

/*编译单元*/
compUnit: ( decl | funcDef)* EOF;
/*声明*/
decl: constDecl | varDecl;
/*常量声明*/
constDecl: 'const' bType constDef ( ',' constDef )* ';';
/*基本类型*/
bType: 'int' | 'float';
/*常数定义*/
constDef
    : Identifier  '=' constInitVal                        #constDefSingle
    | Identifier ( '[' constExp ']' )+ '=' constInitVal   #constDefArray
    ;
/*常量初值*/
constInitVal
    : constExp                                            #constInitValSingle
    | '{'( constInitVal ( ',' constInitVal )* )? '}'      #constInitValArray
    ;
/*变量声明*/
varDecl: bType varDef ( ',' varDef )* ';';
/*变量定义*/
varDef
    : Identifier                                          #varDefSingle
    | Identifier ( '[' constExp ']' )+                    #varDefArray
    | Identifier '=' initVal                              #varDefSingleInitVal
    | Identifier ( '[' constExp ']' )+ '=' initVal        #varDefArrayInitVal
    ;
/*变量初值*/
initVal
    : exp                                                 #initValSingle
    | '{' ( initVal ( ',' initVal )* )? '}'               #initValArray
    ;
/*函数定义*/
funcDef: funcType Identifier '(' funcFParams? ')' block;
/*函数类型*/
funcType: 'void' | 'int' | 'float';
/*函数形参表*/
funcFParams: funcFParam ( ',' funcFParam )*;
/*函数形参*/
funcFParam
    : bType Identifier                                    #funcFParamSingle
    | bType Identifier '['  ']' ( '[' exp ']' )*          #funcFParamArray
    ;

/*语句块*/ 
block: '{' ( blockItem )* '}';
/*语句块项*/
blockItem: decl | stmt;
/*语句*/
stmt
    : lVal '=' exp ';'                                    #stmtAssign
    | exp? ';'                                            #stmtExp
    | block                                               #stmtBlock
    | 'if' '(' cond ')' stmt ( 'else' stmt )?             #stmtCond
    | 'while' '(' cond ')' stmt                           #stmtWhile
    | 'break' ';'                                         #stmtBreak
    | 'continue' ';'                                      #stmtContinue
    | 'return' exp? ';'                                   #stmtReturn
    ;
/*表达式*/
exp: addExp; /*注：sysY 表达式是 int float型表达式*/
/*条件表达式*/ 
cond: lOrExp;
/*左值表达式*/
lVal: Identifier                                          #lValSingle
    | Identifier ('[' exp ']')+                           #lValArray
    ;
/*基本表达式*/
primaryExp
    : '(' exp ')'                                         #primaryExpParen
    | lVal                                                #primaryExpLVal
    | number                                              #primaryExpNumber
    ;
/*数值*/
number
    : intConst
    | floatConst
    ;
/*一元表达式*/
unaryExp
    : primaryExp                                          #unaryExpPrimaryExp
    | Identifier '(' funcRParams? ')'                     #unaryExpFuncR
    | unaryOp unaryExp                                    #unaryExpUnary
    ;
/*单目运算符*/
unaryOp: '+' | '-' | '!'; /*注 '!' 仅出现在条件表达式中*/

/*函数实参表*/
funcRParams: funcRParam (',' funcRParam)*;
funcRParam: exp | StringLiteral ;


/*乘除模表达式*/
mulExp: left=unaryExp (op+=('*' | '/' | '%') right+=unaryExp )* ;
/*加减表达式*/
addExp: left=mulExp (op+=('+' | '-') right+=mulExp)* ;
/*关系表达式*/
relExp: left=addExp (op+=('<' | '>' | '<=' | '>=') right+=addExp)*;
/*相等性表达式*/
eqExp: left=relExp (op+=('==' | '!=') right+=relExp)*;
/*逻辑与表达式*/
lAndExp: left=eqExp (op+='&&' right+=eqExp)* ;
/*逻辑或表达式*/
lOrExp: left=lAndExp (op+='||' right+=lAndExp)*;
/*常量表达式*/
constExp: addExp ; /*注： 使用的 Ident 必须是常量*/

/*标识符*/ 
Identifier: IdentifierNondigit (IdentifierNondigit|Digit)*;
fragment IdentifierNondigit: [A-Z_a-z];
fragment Digit:[0-9];

/*整型常量*/ 
intConst: DecimalConstant                                 #intDecConst
    | OctalConstant                                       #intOctConst
    | HexadecimalConstant                                 #intHexConst
    ;
DecimalConstant: NonzeroDigit | NonzeroDigit Digit+;
OctalConstant: '0'| '0' OctalDigit+;
HexadecimalConstant: HexadecimalPrefix HexadecimalDigit+;
fragment HexadecimalPrefix: '0x' | '0X';
fragment NonzeroDigit: [1-9];
fragment OctalDigit: [0-7];
fragment HexadecimalDigit: [0-9a-fA-F];


/*浮点型数*/
floatConst: FloatingConstant;
FloatingConstant
    : DecimalFloatingConstant
    | HexadecimalFloatingConstant;
fragment DecimalFloatingConstant
    : FractionalConstant ExponentPart?
    | DigitSequence ExponentPart
    ;
fragment HexadecimalFloatingConstant
    : HexadecimalPrefix HexadecimalFractionalConstant BinaryExponentPart
    | HexadecimalPrefix HexadecimalDigitSequence BinaryExponentPart
    ;
fragment FractionalConstant
    : DigitSequence? '.' DigitSequence
    | DigitSequence '.'
    ;
fragment ExponentPart
    : 'e' Sign? DigitSequence
    | 'E' Sign? DigitSequence
    ;
fragment Sign : '+' | '-';
fragment DigitSequence : Digit+;
fragment HexadecimalFractionalConstant
    : HexadecimalDigitSequence? '.' HexadecimalDigitSequence
    | HexadecimalDigitSequence '.'
    ;
fragment BinaryExponentPart
    : 'p' Sign? DigitSequence
    | 'P' Sign? DigitSequence
    ;
fragment HexadecimalDigitSequence: HexadecimalDigit+;

/*用于特殊输入的字符串*/
StringLiteral: '"' SChar*  '"';
fragment SChar
    : ~["\\\r\n]
    | EscapeSequence
    ;
fragment EscapeSequence: '\\' ["\\];

Whitespace: [ \t]+ -> skip;

Newline: ('\r' '\n'?|'\n') -> skip;

/*注释*/
BlockComment: '/*' .*? '*/'-> skip;

LineComment: '//' ~[\r\n]* -> skip;

更多g4文件参考

在antlr的仓库中，我们可以看到大多数语言的语法定义：

antlr/grammars-v4: Grammars written for ANTLR v4; expectation that the grammars are free of actions. (github.com)

另外，大多数语言的语法定义都是BNF范式形式的。

• C语言标准：open-std.org/jtc1/sc22/wg14/www/docs/n3054.pdf
• Python语言指南： The Python Language Reference — Python 3.12.2 documentation
• Java语法标准：The Java® Language Specification (oracle.com)
• kotlin语言定义：Introduction - Kotlin language specification
• kotlin语法：Grammar (kotlinlang.org)