Haskell Parsing自定义解析器星号计数运行逻辑不理解，求详细讲解

前置说明 #

这段代码基于Parsec风格的解析组合子实现，先解释用到的核心运算符和函数语义：

• char c：解析输入的第一个字符，等于c则成功并消耗该字符，否则解析失败
• many1 p：连续执行解析器p至少1次，返回所有解析结果组成的列表，消耗所有匹配的字符
• >>=：Monad绑定操作，按顺序执行前后两个解析器，将前一个解析器的输出传给后一个解析器作为参数
• +++：备选解析组合子，按顺序尝试执行左侧解析器，成功就返回其结果；失败则回溯到进入该分支前的输入状态，执行右侧解析器
• return v：不消耗任何输入，直接将值v作为解析结果返回，永远执行成功
• parse p input：运行解析器p解析输入字符串，返回(解析结果, 剩余未解析字符串)

myParser 逻辑拆解 #

myParser通过+++定义了四个按顺序尝试的分支，所有分支最终返回的都是已解析部分的星号总数量：

1. 星号计数分支

many1 star >>= \vs -> myParser >>= \x -> return (x+length vs)

先匹配至少一个连续星号，拿到星号列表vs，递归调用myParser解析剩余输入得到后续星号计数x，返回两者的和，相当于把当前匹配到的星号数量累加到后续结果中。

2. 方括号匹配分支

openBr >> myParser >>= \c -> closeBr >> myParser >>= \d -> return (c+d)

先匹配左方括号[，递归调用myParser解析括号内的内容得到括号内星号计数c，再匹配右方括号]，再递归调用myParser解析括号后的内容得到后续计数d，返回两者的和，相当于把括号内和括号后的星号数累加。

3. 圆括号匹配分支
   和方括号分支逻辑完全一致，只是匹配的是()对。

4. 兜底分支
   return 0：所有前面的分支都匹配失败时触发，不消耗任何输入，直接返回计数0。

测试用例运行逻辑解释 #

1. 括号完全匹配的测试用例

输入*(***[*(**)]*)*中所有括号完全配对，所有括号分支都能走完完整的匹配流程，不会提前触发兜底分支：

• 逐段匹配所有星号和括号对，所有9个星号都会被计数分支统计到
• 所有输入字符都被消耗，剩余输入为空，所以输出(9, "")

2. 括号不匹配的测试用例

输入*(***[*(**]*)*中，左方括号[内部的左圆括号(没有对应的右圆括号，匹配到]时会触发失败回溯，流程如下：

1. 顶层解析首先匹配到第一个*，进入星号计数分支，剩余输入为(***[*(**]*)*
2. 递归解析剩余输入时尝试匹配圆括号分支：先匹配到左圆括号(，继续递归解析内部的***[*(**]*)*
3. 解析到[时进入方括号分支，匹配到左方括号[，继续递归解析内部的*(**]*)*
4. 解析到(时进入圆括号分支，匹配到左圆括号(，递归解析内部的**]*)*，匹配到2个*之后剩余输入为]*)*
5. 此时需要匹配右圆括号)，但当前第一个字符是]，匹配失败，当前圆括号分支整体失败，回溯到进入该分支前的输入状态(**]*)*，触发兜底分支返回0
6. 回到方括号分支的后续步骤，需要匹配右方括号]，但当前第一个字符是*，匹配失败，方括号分支整体失败，回溯到[*(**]*)*，触发兜底分支返回0
7. 回到最外层圆括号分支的后续步骤，需要匹配右圆括号)，但当前第一个字符是[，匹配失败，圆括号分支整体失败，回溯到(***[*(**]*)*，触发兜底分支返回0
8. 回到最顶层的星号计数分支，后续递归返回0，所以总计数为1+0=1，剩余输入没有被消耗，就是(***[*(**]*)*，和测试输出一致。

内容的提问来源于stack exchange，提问作者sunny