转载

常用语言模式

现在，我们已经有了一个自顶向下的草拟出语法的通用策略，下面我们要专注于一些常用的语言模式。尽管在过去几十年里有大量的语言被发明，但仍然只有较少的基本语言模式需要被处理。这是因为人们趋向于设计遵循自然语言约束的语言，语言也会因为设计者遵循数学上的常用表示法而趋向于相似。甚至在词法级别，语言趋向于重用一些相同的结构，例如标志符、整数、字符串等。这些单词顺序和依赖的约束来源于自然语言，并逐渐演化成为四种抽象的语言模式：

模式：序列

这是像数组初始值设定项中的值那样的一系列元素，也是在计算机语言中最常见的结构。例如，下面是登录到POP服务器时的序列：

USER parrt
PASS secret
RETR 1

这些命令本身也是序列。大部分命令是一个关键词（保留标志符，例如USER和RETR）跟随一个运算元再跟随一个换行符。为了在语法中指定此类序列，我们可以按照顺序简单地列出各个元素。以下是检索命令的序列（其中INT表示整数记号类型）：

retr : 'RETR' INT '\n' ;

我们可以给RETR序列打上retr规则的标签，这样在语法的其它地方，我们就能使用规则名字作为简写来引用RETR序列。对于任意长度的序列像矢量[1 2 3]这样的简单整数列表，虽然它是一个有限序列，但我们不可能通过像INT INT INT ...这样的规则片段来列出所有可能的整数列表。为了编码这样的一个或者多个元素，我们使用“+”子规则运算符。例如，{INT}+表示任意长度的整数序列，或者使用简写INT+也可以。至于可以为空的列表，我们则使用零个或者多个运算符“*”。这种模式的变体有带终结符的序列和带分隔符的序列，CSV文件就很好地示范了这两者。

file : (row '\n')* ;           // 带一个“\n”终结符的序列
row  : field (',' field)* ;    // 带一个“,”分隔符的序列
field: INT ;                   // 假设字段只是整数

规则file使用带终结符模式的列表去匹配零个或者多个row '\n'序列，记号“\n”终结序列的每个元素。规则row使用带分隔符模式的列表去匹配一个field后面有零个或者多个',' field序列，记号“,”分隔各个字段。最后，还有个特殊类型的零个或者一个序列，用“?”指定。可以使用它去表达可选的构造体。

模式：选择

这是一个在多个可供替代的短语之间的选择，比如在编程语言中不同种类的语句。为了在语言中表示选择的这个概念，我们使用“|”作为ANTLR中的“or”运算符去分隔被称为“选项”的语法选择。回到CVS语法，我们可以通过整数或者字符串的选择让规则field变得更灵活。

field: INT | STRING ;

任何时候，如果你发现正在说“语言结构x可以是这个或者那个”，那么你就可以确定应该使用选择模式，在规则x中使用“|”。

模式：记号依赖

记号依赖表示一个记号的存在需要在短语的其它地方有它的对等物的存在，比如匹配的左右括号。前面我们曾经使用INT+去表达在矢量[1 2 3]中的整数非空序列。为指定周围有方括号的矢量，我们需要一种方法去表达记号中的依赖。如果我们在句子中看到一个符号，那么我们必须在句子的其它地方找到它的对等物。为表达这种语法，我们必须使用同时指定对等符号的序列，它们通常包围或分组着其它元素。在这个案例中，我们这样指定矢量：

vector : '[' INT+ ']' ;    // [1], [1 2], [1 2 3], ...

扫视任何有效的代码，你会看到必须成对出现的各种分组符号：(...)，[...]，{...}。但是要牢记，依赖符号并不是必须配对的，类C语言都有的a ? b : c三元运算符就指定了当看到“?”符号时需要在接下来的短语中看到“:”符号。

模式：嵌套短语

嵌套短语有一个自相似的语言结构，它的子短语也遵循相同的结构。表达式是典型的自相似语言结构，由被运算符分隔的嵌套子表达式组成。类似地，while的代码块是嵌套在外部代码块内的一个代码块。我们在语法中使用递归规则表达自相似的语言结构。因此，如果规则的伪代码引用它自身，我们将需要一个递归的自引用规则。让我们来看下代码块的嵌套是如何工作的。while语句是关键词while跟随一个在括号中的条件表达式再跟随一个语句。我们也可以把多条语句包裹在花括号里当作一个单块语句。表达语法如下所示：

stat: 'while' '(' expr ')' stat    // 匹配WHILE语句
    | '{' stat* '}'                // 匹配在括号中的语句块
    ;

这里的stat可以是单条语句或者被花括号括起来的一组语句。规则stat是直接递归的，因为它在两个选项中直接引用它自身。如果我们把第二个选项移到它自己的规则中，规则stat和block将是双向间接递归的。语法如下所示：

stat: 'while' '(' expr ')' stat    // 匹配WHILE语句
    | '{' stat* '}'                // 匹配语句块
    ;
block: '{' stat* '}' ;             // 匹配在括号中的语句块

看下面仅有3类表达式（索引数组引用、括号表达式和整数）的简单语言的语法：

expr: ID '[' expr ']'    // a[1], a[b[1]], a[(2*b[1])]
    | '(' expr ')'       // (1), (a[1]), (((1))), (2*a[1])
    | INT                // 1, 94117
    ;

注意递归是如何自然地发生的。数组索引表达式的索引组件是表达式本身，因此我们只需要在选项中引用expr即可。下图是关于两个例子输入的语法分析树：

分析树中的内部树节点是规则引用，叶子是记号引用。从树根到任何节点的路径表示元素的规则调用栈（或者ANTLR生成的递归下降语法分析器调用栈）。路径代表递归嵌套的子树有多个相同规则的引用。规则节点是其下方子树的标签。根节点是expr，所以整棵树是一个表达式。在1之前的那棵expr子树会把整数当作一个表达式。为实现这些模式，我们只需要由选项、记号引用、规则引用组成的语法规则即可。我们还可以把这些元素组成子规则，子规则是裹在括号内的行内规则。我们也可以将子规则标记为“?”或“*”或“+”循环去识别被包围的语法片段多次。