10 时隔多日，终于捡起了龙书第四章。
然后在习题 4.4.5 栽了跟头。没想明白，打算写一个单步调试，但写都没写出来。
最后抄了答案，豁然开朗。一次 S -> aSa | aa 可以先尝试前者，再尝试后者，但是一旦尝试前者正常返回，就会永远错过调用后者的可能了。
听起来很类似 Tuna 讲座上 Haskell Parsec 的一个特性：S -> ab | ac，如果 ab 解析失败，被吞掉的 a 永远不会归还。这里的解法是提取左公因子。这个不是回溯，但相当类似。
原题也绝对可以通过改写等价表达式让解析结果正常起来。比如显然原式与 S -> aa | aaS 等价，这玩意能出问题就怪了（懒得写）。
然后在习题 4.4.5 栽了跟头。没想明白，打算写一个单步调试，但写都没写出来。
最后抄了答案，豁然开朗。一次 S -> aSa | aa 可以先尝试前者，再尝试后者，但是一旦尝试前者正常返回，就会永远错过调用后者的可能了。
听起来很类似 Tuna 讲座上 Haskell Parsec 的一个特性：S -> ab | ac，如果 ab 解析失败，被吞掉的 a 永远不会归还。这里的解法是提取左公因子。这个不是回溯，但相当类似。
原题也绝对可以通过改写等价表达式让解析结果正常起来。比如显然原式与 S -> aa | aaS 等价，这玩意能出问题就怪了（懒得写）。