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

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")])。解析器是否会产生额外的字符串输出或替换/修改它(例如Parser $ \s -> [((), 'a':s)])？我怀疑上下文敏感的语法可能就是这种情况，但想出一个合理的例子却有困难。

对于现实世界的问题，为什么这么做是有道理的呢？

参考文献

• Haskell中的一元分析

Answer 1

以下是将令牌插入到输入流中很方便的几种情况。(另一个问题是如何将其实际集成到解析管道中。)

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

这并不是一个详尽的清单，但至少可以说明问题。并不是所有这些情况都一定涉及上下文敏感性(理论上，ASI可以使用上下文无关的语法来处理，尽管我无意尝试)，并且并不是所有上下文敏感的实例都必然需要令牌注入(类型和变量名称之间的C中的歧义只需要选择正确的令牌)。