当在像 Haskell 的 Parsec 这样的解析器组合器库中编写解析器时,您通常有 2 个选择:
- 编写一个词法分析器来分割你的
String
输入token,然后进行解析[Token]
- 直接编写解析器组合器
String
第一种方法通常似乎是有意义的,因为许多解析输入可以理解为由空格分隔的标记。
在其他地方,我看到人们建议不要标记化(或scanning or lexing,有些人这么称呼它),简单性被认为是主要原因。
进行词法分析和不进行词法分析之间的一般权衡是什么?
最重要的区别是 lexing 将翻译您的输入域.
A nice结果是
但是,如果您执行词法分析,您会得到problems that
您不能使用通用解析器String
不再 - 例如用于使用库函数解析数字parseFloat :: Parsec String s Float
(在字符串输入流上运行),你必须做类似的事情takeNextToken :: TokenParser String
and execute
the parseFloat
解析器,检查解析结果(通常Either ErrorMessage a
)。这写起来很混乱并且限制了可组合性。
您已调整所有错误消息。如果您的标记解析器在第 20 个标记处失败,那么该标记位于输入字符串的哪个位置?您必须手动将错误位置映射回输入字符串,这很乏味(在秒差距中,这意味着调整所有SourcePos
值)。
错误报告通常更糟糕。跑步string "hello" *> space *> float
输入错误,例如"hello4"
会准确地告诉您,在hello
,而词法分析器只会声称找到了"invalid token"
.
很多事情都是人们所期望的原子单位和被词法分析器分开实际上对于词法分析器来说“太难”识别。以字符串文字为例 - 突然"hello world"
不是两个令牌"hello
and world"
不再(但是only,当然,如果引号没有转义,比如\"
) - 虽然这对于解析器来说是非常自然的,但对于词法分析器来说这意味着复杂的规则和特殊情况。
您也不能在标记上重复使用解析器。如果您定义如何解析双精度型String
,出口它,世界其他地方都可以使用它;他们无法首先运行您的(专用)标记器。
你被它困住了。当您开发要解析的语言时,使用词法分析器可能会导致您做出早期决定,修复您之后可能想要更改的内容。例如,假设您定义了一种语言,其中包含一些Float
令牌。在某些时候,您想引入负数文字(-3.4
and - 3.4
) - 这可能是不可能的,因为词法分析器将空格解释为标记分隔符。使用仅解析器的方法,您可以保持更加灵活,从而更轻松地更改语言。这并不奇怪,因为解析器是一种更复杂的工具,它本质上编码rules.
总而言之,我建议在大多数情况下编写无词法分析器的解析器。
最后,词法分析器只是一个“简化的”*解析器 - 如果您无论如何都需要一个解析器,请将它们组合成一个。
* From computing theory, we know that all regular languages are also context-free languages http://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy; lexers are usually regular, parsers context-free or even context-sensitve (monadic parsers like Parsec can express context-sensitiveness).
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)