面向Java开发人员的Scala指南 - 构建计算器，第2部分 - 编程入门网

以往，创建解析器有两种方法：

手工构建一个解析器。

通过工具生成解析器。

我们可以试着手工构建这个解析器，方法是手动地从输入流中取出一个字符，检查该字符，然后根据该字符以及在它之前的其他字符（有时还要根据在它之后的字符）采取某种行动。对于较小型的语言，手工构建解析器可能更快速、更容易，但是当语言变得更庞大时，这就成了一个困难的问题。

除了手工编写解析器外，另一种方法是用工具生成解析器。以前有 2 个工具可以实现这个目的，它们被亲切地称作lex（因为它生成一个 “词法解析器”）和 yacc（“Yet Another Compiler Compiler”）。对编写解析器感兴趣的程序员没有手工编写解析器，而是编写一个不同的源文件，以此作为 “lex” 的输入，后者生成解析器的前端。然后，生成的代码会与一个 “grammar” 文件 —— 它定义语言的基本语法规则（哪些标记中是关键字，哪里可以出现代码块，等等）—— 组合在一起，并且输入到 yacc 生成解析器代码。

由于这是 Computer Science 101 教科书，所以我不会详细讨论有限状态自动机（finite state automata）、LALR 或 LR 解析器，如果需要深入了解请查找与这个主题相关的书籍或文章。

同时，我们来探索 Scala 构建解析器的第 3 个选项：解析器组合子（parser combinators），它完全是从 Scala 的函数性方面构建的。解析器组合子使我们可以将语言的各种片段 “组合” 成部件，这些部件可以提供不需要代码生成，而且看上去像是一种语言规范的解决方案。

解析器组合子

了解 Becker-Naur Form（BNF）有助于理解解析器组合子的要点。BNF 是一种指定语言的外观的方法。例如，我们的计算器语言可以用清单 3 中的 BNF 语法进行描述：

清单 3. 对语言进行描述

input　　::= ws expr ws eoi; expr　　::= ws powterm [{ws ''^'' ws powterm}]; powterm　　::= ws factor [{ws (''*''|''/'') ws factor}]; factor　　::= ws term [{ws (''+''|''-'') ws term}]; term　　::= ''('' ws expr ws '')'' | ''-'' ws expr | number; number　　::= {dgt} [''.'' {dgt}] [(''e''|''E'') [''-''] {dgt}]; dgt　　::= ''0''|''1''|''2''|''3''|''4''|''5''|''6''|''7''|''8''|''9''; ws ::= [{'' ''|''\t''|''\n''|''\r''}];

语句左边的每个元素是可能的输入的集合的名称。右边的元素也称为 term，它们是一系列表达式或文字字符，按照可选或必选的方式进行组合。（同样，BNF 语法在 Aho/Lam/Sethi/Ullman 等书籍中有更详细的描述，请参阅 参考资料）。

用 BNF 形式来表达语言的强大之处在于，BNF 和 Scala 解析器组合子不相上下；清单 4 显示使用 BNF 简化形式后的清单 3：

清单 4. 简化、再简化

expr　 ::= term {''+'' term | ''-'' term} term　 ::= factor {''*'' factor | ''/'' factor} factor ::= floatingPointNumber | ''('' expr '')''

面向Java开发人员的Scala指南 - 构建计算器，第2部分(4)

其中花括号（{}）表明内容可能重复（0 次或多次），竖线（|）表明也/或的关系。因此，在读清单 4 时，一个 factor 可能是一个 floatingPointNumber（其定义在此没有给出），或者一个左括号加上一个 expr 再加上一个右括号。

在这里，将它转换成一个 Scala 解析器非常简单，如清单 5 所示：

清单 5. 从 BNF 到 parsec

package com.tedneward.calcdsl { 　 object Calc 　 { 　　 // ... 　　 import scala.util.parsing.combinator._ 　　 object ArithParser extends JavaTokenParsers 　　 { 　　　 def expr: Parser[Any] = term ~ rep("+"~term

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!