在像 Haskell 的 Parsec 这样的解析器组合库中编写解析器时,通常有两种选择:
- 编写词法分析器将
String
输入拆分为标记,然后对[Token]
执行解析 - 直接在
String
上编写解析器组合器
第一种方法通常是有意义的,因为许多解析输入可以被理解为由空格分隔的标记。
在其他地方,我看到有人建议不要对标记进行分词(或称为扫描或词法分析),并引用简单性作为主要原因。
在进行或不进行词法分析之间有哪些一般权衡?
在像 Haskell 的 Parsec 这样的解析器组合库中编写解析器时,通常有两种选择:
String
输入拆分为标记,然后对 [Token]
执行解析String
上编写解析器组合器第一种方法通常是有意义的,因为许多解析输入可以被理解为由空格分隔的标记。
在其他地方,我看到有人建议不要对标记进行分词(或称为扫描或词法分析),并引用简单性作为主要原因。
在进行或不进行词法分析之间有哪些一般权衡?
现在你不能再对String
使用普通解析器, 例如为了用库函数 parseFloat :: Parsec String s Float
(它在输入流上操作于一个String类型的参数) 解析数字, 你必须像这样 takeNextToken :: TokenParser String
,然后在其上执行parseFloat
解析器,并检查解析结果(通常是Either ErrorMessage a
)。这样写起来很混乱且限制了组合性。
你需要调整所有的错误信息。如果你的标记解析器在第20个标记处失败了,在输入字符串中的位置在哪里?你必须手动将错误位置映射回输入字符串,这很繁琐(在Parsec中这意味着需要调整所有的SourcePos
值)。
错误报告一般更差。当你在错误的输入上运行string "hello" *> space *> float
,比如"hello4"
,它会精确告诉你在hello
后面缺少空格,而一个词法分析器只会声明发现了一个“无效标记”。
许多人们期望的作为原子单位并由词法分析器分隔的东西实际上对于词法分析器来说太困难了。以字符串字面量为例——突然之间"hello world"
不再是两个标记"hello
和world"
,而是一个标记(当然,如果引号没有被转义,比如\"
)——虽然这对于解析器来说很自然,但对于词法分析器来说意味着复杂的规则和特殊情况。
你不能像以前那样方便地在标记上重用解析器。如果你定义了如何从String
中解析出双精度,导出它,那么其他人可以使用它;他们不能先运行你的(专门的)标记解析器。
你会被束缚住。当你正在开发要解析的语言时,使用词法分析器可能会让你做出早期决策,修复你后来可能想要更改的东西。例如,想象一下你定义了一个包含一些Float
标记的语言。某个时刻,你想引入负数字面量(-3.4
和- 3.4
)——这可能不可能由于词法分析器将空格解释为标记分隔符。使用仅解析器的方法,你可以保持更灵活,更容易对语言进行更改。这并不奇怪,因为解析器是一个更复杂的工具,本质上编码了规则。
* 从计算理论上,我们知道所有的正则语言也是上下文无关语言;词法分析器通常是正则的,而解析器则是上下文无关甚至上下文有关的(像Parsec这样的单子解析器可以表达上下文相关性)。
/^"([^\\"]|\\")*"/
是一个真正的正则表达式(在形式上——我想),甚至处理转义字符。不过,这个观点也是正确的。 - Matt Fenwick