文章目录
  1. 1. 语法分析策略
    1. 1.1. 如何从文法得到解析器
      1. 1.1.1. 递归下降法语法解析器
      2. 1.1.2. 解析器组合子
      3. 1.1.3. 解析器生成器
  2. 2. 输出生成策略
    1. 2.1. 嵌入式语法翻译
    2. 2.2. 树的构建和遍历
    3. 2.3. 内嵌解释器
  3. 3. 取舍
  4. 4. 解析中的概念
    1. 4.1. 单独的词法分析
    2. 4.2. 文法和语言
    3. 4.3. 正则文法、上下文无关文法和上下文相关文法
    4. 4.4. 自顶向下解析和自底向上解析
  5. 5. 混入另一种语言
  6. 6. XML DSL

内部DSL最终还是会受限于宿主语言的语法结构,外部DSL则提供了更大的语法自由度—我们可以使用自己喜欢的任何语法。

相比于内部DSL,实现外部DSL的不同之处在于解析过程,我们要解析纯文本输入,这些输入不受任何现有语言的约束。

语法分析策略

在解析外部DSL时,要将一串文本分解成某种结构,通过这种结构来理解文本的含义。这个“结构化”的过程称为语法分析(syntactic analysis)。如下面的代码:

event doorClosed D1CL
event drawerOpened D2OP
command unlockPanel PNUL
command lockPanel PNLK

语法分析要做的就是识别出event doorClosed D1CL这一行是一个事件的定义,并将其与命令定义区分开。

哪怕从未涉足过任何严肃的语法分析,我们应该也试过最简单的解决方法—分隔符指导翻译,其基本思路是,首先找出能把输入分解成语句的分隔符(通常是换行符),根据这些分隔符把输入语句拆分成语句,然后逐个语句进行处理,找出其中的含义。

但是分隔符指导翻译不适用于处理层次结构的输入上下文。比如:

events
    doorClosed D1CL
    drawerOpened D2OP
end

commands
    。。。。

更适合的方法是“语法指导翻译”。首先为输入语言定义一个形式化的文法,就像这样:

list: eventList commandList;
eventList: 'events' eventDec* 'end';   //*表示后继元素可以出现多次
eventDec: identifier identifier;
commandList: 'commands' commandDec* 'end';
commandDec: identifier identifier;

文法用于定义程序设计语言的合法语法。绝大多数文法都是以某种形式的“BNF”编写,其中每行代表一条规则:首先是规则名称,然后是满足该规则的合法元素。

如何从文法得到解析器

递归下降法语法解析器

经典、易于理解的解析方法:用函数内部的控制流来展现文法规则。每条文法规则会转换为解析器中的一个函数,每个BNF运算符到控制流的转换过程都有清晰的模式可循。

该方法的问题在于:文法会隐藏于控制流之下,因此代码可读性就大大降低。

解析器组合子

更时尚方式:将每条规则转换成一个对象,再把对象组合成一个与文法对应的结构。我们仍需要递归下降法语法解析器的元素,但这些元素会包装成组合子对象,只要将它们组合起来就行了。这样,我们甚至不需要理解递归下降法语法解析器算法的细节,也可以实现一个文法。

解析器生成器

可以把BNF当做DSL来操作:用这种DSL来编写文法,解析器生成器负责生成解析器。

解析器生成器(如ANTLR)是最精密的途径:这些工具都非常成熟,并且能以极高的效率处理负责的语言。以BNF作为DSL,会让语言更容易理解和维护,因为其语法已经清晰地定义出来,并且能够自动地绑定到解析器上。不过这些工具需要一定的学习成本。

输出生成策略

大部分时候,当解析输入时,解析过程的输出结果应该是一个“语义模型”,随后我们就可以直接解释它或者将其作为代码生成的输入。

输出语义模型的方式有三种:

嵌入式语法翻译

直接把方法调用放进解析器,从而在解析过程中生成语义模型。

采用这种方法可以在解析的同时逐步构建语义模型。只要得到了足够的输入,能识别出语义模型的一个组成部分,就立即创建这个部分。在真正创建语义模型中的对象之前,经常会需要一些中间解析数据–这是可能需要把信息存入“符号表”。

树的构建和遍历

需要两步—树的构建:首先输入文本,构建出一棵包含文本结构的语法树,同时用符号表处理语法树各个部分之间的交叉引用;然后,执行第二阶段,遍历语法树,生成语义模型。

使用树的构建的一个好处:把整个解析任务分解成两个更简单的任务。类比XML处理,嵌入式语法翻译类似于SAX,树的构建类似于DOM。

内嵌解释器

在解析过程中执行解释,并直接输出最终结果。参考计算器。

内嵌解释器并不生成语义模型。很少用到。

取舍

内嵌解释器很少使用;树构建时,语法树内存开销较大,同时,当复杂度较小时,构建和遍历语法树显得过于麻烦,但是,翻译的复杂度越大,树的构建就越适合。

解析中的概念

单独的词法分析

语法指导翻译通常分为两个阶段:词法分析(也叫做扫描或标记解释)和语法分析(也叫做解释迷惑人的称谓)。词法分析阶段将输入文本转化为一串标记(token),这是一种数据类型,包含两个主要属性: 类型和内容。 例如,在状态机语言中,

state idle

就会转化为两个标记:

[content: "state", type: state-keyword]
[content: "idle", type: identifier]

语法分析器随后会根据文法规则把这串标记组织成一棵语法树。

但是先做词法分析同时会产生很多影响:首先我们要谨慎使用文本,如:

state initial state

表示一个initial state的状态,但是第二个state默认情况下会被词法分析器识别为state关键字而不是一个标识符(使用可变分词方式解决)。

其次,先做词法分析意味着空白字符通常会去掉,解析器根本不会看见它们,这就使得处理有语法意义的空白字符变得困难。

之所以像这样把词法分析器分离出来,是因为这使得词法分析器和语法分析器变得简单,而且还能提升性能,尤其是在资源有限的硬件上。

文法和语言

一种文法形式化地定义一种语言的语法,但是多种文法能够识别同一语言的的情况也很常见。比如,对于下面输入文本:

events
    doorClosed D1CL
    drawerOpened D2OP
end

可以写出如下文法:

eventBlock: Event-keyword eventDec* End-keyword;  
eventDec: Identifier identifier;    

当然,也可以写成如下文法:

eventBlock: Event-keyword eventList End-keyword; 
eventListeventDec*; 
eventDec: Identifier identifier;

有多种原因会让我们得到不同的文法。首先,不同的解析器生成器使用不同的文法,这些文法的语法和语义都不同;即便是同一个解析器生成器,当采用不同的方式构建文法规则时,也会得到不同的文法。和其他任何代码一样,我们也重构文法,使其更易理解。

正则文法、上下文无关文法和上下文相关文法

编程社区用乔姆斯基谱系对文法分类,而我们主要关注三类文法:正则文法、上下文无关文法和上下文相关文法。它们共同构成一个层级谱系:所有正则文法都是上下文无关的,所有上下文无关文法都是上下文相关的。(具体解释这里不做说明)

正则文法对我们很重要,因为它可以用一个有限状态机来处理—这点很重要,因为正则表达式就是有限状态机,所以正则语言可以用正则表达式来解析。

就计算机语言,正则文法有一个大问题:不能处理嵌套元素(不能“计数”)。显然,这对于计算机语言,不是一个好消息,起码任何通用语言都应该能够进行数学计算,而且这也会影响到有块结构的程序,如:

for(int i in numbers) {
    if(isInteresting(i)) {
        doSomething(i);
    }
}

这段程序需要嵌套快,因此不是正则的。

要处理这种嵌套块,就得网上走一步:上下文无关文法。上下文无关文法可以使用下推机(push-down machine)—带有栈的有限状态机来实现。大部分编程语言的解析器都使用上下文无关文法,大部分解析器生成器也使用它,“递归下降法语法分析器”和“解析器组合子”都会生成下推机。于是,大部分现代编程语言都是用上下文无关文法来解析的。

但是上下文无关文法不能处理我们想要的所有语法规则,其一个常见异常情况是这样一条规则:变量务必先声明后使用。问题在于,当使用变量时,变量声明常出现在当前所在程序分支所在层次结构之外。尽管上下文无关文法可以保存层级结构上下文,但也没有足够的上下文来处理这种情况–因此还需要“符号表”。

在上一级是上下文相关文法。它可以处理嵌套元素。

这些语言的分类可以告诉我们为什么会有一个独立的词法分析阶段,词法分析通常是用正则表达式来完成,语法分析则会使用下推机。因此词法分析器的用途有限,但速度一般可以更快。

正则文法和上下文无关文法食物名最可能使用的两种文法,不过还有一种新的文法也值得关注—解析表达式文法(Parsing Expression Grammar, PEG)。PEG是一种新的文法格式,可以处理大部分上下文无关 的情景和一些上下文相关的情景。

自顶向下解析和自底向上解析

编写解析器的方法有多种,一个最大的区别是:解析器是自顶向下还是自底向上。这不仅会影响解析器工作的方式,而且会影响解析器所能处理的文法类型。

自顶向下解析器首先处理文法中最高级别的规则,根据它确定如何尝试及匹配。自顶向下解析器将规则视为某种目标,用于指导自己接下来需要查找的元素。

自底向上解析器完成的操作与上面恰好相反。读入关键字,查看当前输入是否匹配某个规则,如果匹配不成功,解析器就把已经读入的内容暂时放到一旁(或叫做移进(shifting)),并读入写一个标记(一个标识符),这样直到匹配,然后将上面的标识符规约成一个块。所以也称为“移进-规约解析”

很多时候,自顶向下解析器也称为LL解析器,自底向上称为LR解析器:第一个字母表示“从哪个方向开始扫描输入”,第二个字母则表示“如何识别规则”(L是从左向右,R是从右向左)。

递归下降算法是一个自顶向下的解析算法,自顶向下的一大缺点是:无法处理左递归。例如:

expr: expr '+' expr;

类似这样的规则会导致解析器在尝试匹配expr时陷入无穷递归。

混入另一种语言

面对一种外部DSL,一个最大的风险是:它可能不经意间演变成一种通用语言。

DSL中可以外加代码。外加代码是指嵌入DSL中的一小段通用语言代码。DSL解析器不会解析这段代码,它只是作为一段代码放入“语义模型”,留待后续处理。如:

scoot handles floor_wax in MA RI CT when (/^Baker/.test(lead.name))

除了通用语言代码,也可以混入另一种DSL。

使用外加代码的一个问题是:需要用不同的方式对外加代码进行标记划分,因此需要某种“可变分词方式”。最简单的可变分词方式方法是,用某种清晰的分隔符将嵌入代码引用起来,使其能够识别为单个标记,从而以单一字符串的形式经过解析。如上面的例子,是使用了一对大括号,但是这样同时增加了一些噪音。

XML DSL

很多常见的XML配置文件实际上就是DSL,但不是所有的配置文件都是DSL。比如“属性列表”和DSL是不同的,那只是一份简单的“键-值对”列表,可能再加上分类。

XML不是编程语言,是一种没有语义的语法结构。XML是DSL的承载语法,但是它又引入了太多语法噪音—太多的尖括号、引号和斜线,每个嵌套元素都必须有开始标签和结束标签。

自定义的外部DSL也带来了一个烦恼:它们处理引用、字符转义之类事情的方式总是难以统一。但在这方面,XML提供了一个统一可靠的方案。

XML在错误处理和诊断方面很出色。

XML的另一个优势:只要将XML文档与一份结构定义比较,不需要执行其中的内容就可以知道其格式是否正确。

文章目录
  1. 1. 语法分析策略
    1. 1.1. 如何从文法得到解析器
      1. 1.1.1. 递归下降法语法解析器
      2. 1.1.2. 解析器组合子
      3. 1.1.3. 解析器生成器
  2. 2. 输出生成策略
    1. 2.1. 嵌入式语法翻译
    2. 2.2. 树的构建和遍历
    3. 2.3. 内嵌解释器
  3. 3. 取舍
  4. 4. 解析中的概念
    1. 4.1. 单独的词法分析
    2. 4.2. 文法和语言
    3. 4.3. 正则文法、上下文无关文法和上下文相关文法
    4. 4.4. 自顶向下解析和自底向上解析
  5. 5. 混入另一种语言
  6. 6. XML DSL