编译器构建 - 为什么有些令牌需要带有回溯的最终状态？

Question

所以我正在为考试学习编译器构造，但似乎有些地方我无法理解。

让我们假设以下一组终端：

T = {:, *, =, (, ), <, >, {, }, [a..z], [0..9]}

以及接受的标记集（l指向一个字母，d指向一个数字）：

A = { l(l|d)* , (d)+ , { (anything)* } , : , := , < , <= , <> , > , >= , ( , (* , * , *) } 

这是状态转换图：

现在我明白状态号 20 需要回溯因为：

• 可能会出现 (，但后面可能会出现 *。
• 可能会出现 :，但后面可能会出现 =。
• 可能会出现 <，但后面可能会出现 = 或 >。
• 可能会出现 >，但后面可能会出现 =。

但是状态 3 、 5 和 11 呢？ , 为什么我们需要回溯他们？.

Answer 1

这里好像是"backtracking"表示你已经阅读了一个角色，但是你还没有消费它。所以对于状态 3，我们已经消耗了一个 l，也许还有一些 l 和 d，然后我们得到了一些两者都不是的字符；该字符终止 l(l|d)* 规则，但仍需要处理。

对比状态 7，我们读取 } 字符来终止规则，我们已经用完了 }，所以我们不需要 "backtrack."

这个解释和状态3、5、20是一致的，但是我不明白为什么11需要回溯。