在使用像Parsec这样的解析器组合库时,我应该使用词法分析器吗？

Question

在像Haskell的Parsec这样的解析器组合库中编写解析器时,通常有2个选择:

• 编写词法分析器将String输入拆分为标记,然后执行解析[Token]
• 直接编写解析器组合器 String

第一种方法通常似乎有意义,因为许多解析输入可以理解为由空格分隔的标记.

在其他地方,我看到人们建议不要进行标记化(或扫描或激发,有人称之为),简单性被引用作为主要原因.

lexing和不做之间的一般权衡是什么？

Answer 1

最重要的区别是lexing将翻译您的输入域.

一个很好的结果是

• 你不必再考虑空白了.在直接(非lexing)解析器中,你必须space在允许空格的所有地方撒上解析器,这很容易被遗忘,如果空格必须分开你的所有标记,它会使你的代码混乱.

• 您可以逐个考虑您的输入,这对人类来说很容易.

但是,如果你执行词法,你得到的问题是

• 您不能再使用常见的解析器String- 例如,使用库函数parseFloat :: Parsec String s Float(在String输入流上操作)解析数字时,您必须执行类似的操作takeNextToken :: TokenParser String并在其上execute执行parseFloat解析器,检查解析结果(通常Either ErrorMessage a).编写和限制可组合性是很麻烦的.

• 您已调整所有错误消息.如果令牌上的解析器在第20个令牌处失败,那么输入字符串中的那个是什么？您必须手动将错误位置映射回输入字符串,这很繁琐(在Parsec中这意味着调整所有SourcePos值).

• 错误报告通常更糟糕.string "hello" *> space *> float在错误的输入上运行"hello4"就会告诉你准确地说在预期之后会有空格丢失hello,而词法分析者只会声称找到了"invalid token".

• 很多人认为是原子单位并被词法分析器分开的东西实际上对于词法分析者而言确实"太难"了.举个例子字符串字面-突然"hello world"没有两个标记"hello和world"了(但只,当然,如果引号不转义,像\") -虽然这是很自然的解析器,这意味着复杂的规则和特殊情况下的词法分析器.

• 你不能在令牌上重复使用解析器.如果你定义如何解析a中的double String,导出它,世界其他地方可以使用它; 他们不能先运行你的(专用)标记器.

• 你被困在了.当您开发要解析的语言时,使用词法分析器可能会导致您做出早期决策,修复您之后可能想要更改的内容.例如,假设您定义了包含某个Float标记的语言.在某些时候,你想引入负面文字(-3.4和- 3.4) - 这可能是不可能的,因为词法分析器将空格解释为标记分隔符.使用仅解析器方法,您可以更灵活,更轻松地更改语言.这并不奇怪,因为解析器是一种更复杂的工具,它本身就是对规则进行编码.

总而言之,我建议在大多数情况下编写无lexer解析器.

最后,词法分析器只是一个"愚蠢的"*解析器 - 如果你需要一个解析器,将它们组合成一个.

_{*从计算理论来看,我们知道所有常规语言都是无语境的语言 ; 词法分析器通常是常规的,解析器无上下文甚至是上下文敏感(像Parsec这样的monadic解析器可以表达上下文敏感性).}