解析器何时附加其输入字符串？

Question

给定一个解析器

newtype Parser a = Parser { parse :: String -> [(a,String)] }

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = Parser $ \s -> concat [ parse (f a) s' | (a, s') <- parse p s ]

return :: a -> Parser a
return a = Parser (\s -> [(a,s)])

item :: Parser Char
item = Parser $ \s -> case cs of
                         ""     -> []
                         (c:cs) -> [(c,cs)]

我们可以看到 item 消耗了给它的部分输入字符串 ("abc" -> [('a', "bc")])。是否存在解析器会产生额外的字符串输出或 replace/modify 的情况（例如 Parser $ \s -> [((), 'a':s)]）？我怀疑上下文相关语法可能就是这种情况，但很难想出一个合理的例子。

对于现实世界的问题这样做有意义吗？

参考资料

Monadic Parsing in Haskell

Answer 1

这里有几个可以方便地将令牌注入输入流的情况。（这实际上是如何集成到解析管道中的是另一个问题。）

宏扩展，采用C/C++预处理阶段的风格。这可以说不是宏观扩张的最佳模式；与 C++ 模板解析一样，卫生宏更有可能使用树转换进行扩展。但是面向令牌的预处理器不会很快消失。由于它与语言语法没有紧密结合，最简单的实现是用其扩展中的标记替换宏（和参数，如果适用）。
Ecmascript 样式的自动分号插入 (ASI)。语言语法要求在某些精确定义的情况下将分号插入到令牌流中，这很难（至少）合并到 CFG 中。由于 ASI 仅在输入流中的下一个标记无法移动（并完成其他条件）时才有可能，因此它当然可以集成到解析器循环中。
类似地，缩进感知块语法（例如 Haskell 和 Python）当然可以通过用注入的 INDENT 标记或一些替换前导空格来实现注入的 DEDENT 数量。由于此替换依赖于解析上下文（例如，它不是在括号内完成的），因此在解析器内部注入可能是一种合理的方法。

这不是一个详尽的列表，但它可能至少是指示性的。并非所有这些情况都必然涉及上下文敏感（我相信 ASI 在理论上可以使用上下文无关语法来处理，尽管我无意尝试）并且并非所有上下文敏感的实例都必然需要令牌注入（歧义在 C 中类型和变量名称之间只需要选择正确的标记）。

解析器何时附加其输入字符串？

When would a parser append its input string?

grammar

parsing

haskell

参考资料