《編譯器設計》第二章第5節的疑惑？

01-11

《編譯器設計》第二章第5節說的為了避免過度回滾而使用的最長適配詞法分析器的偽代碼到底好在哪？誰看過嗎，看了一晚上還是沒看懂Failed數組和全局計數器InputPos到底有什麼作用或者說好處在哪？
下圖分別是使用Failed數組優化後和沒使用Failed數組、全局計數器InputPos的情況。InitializeScanner必須在NextWord之前調用。
目的：為了進行避免過渡回滾。

例：對於正則表達式ab|(ab)*c，前面這個式子的*號應該是克林星號。
它要讀取完abababab然後回滾才能識別最長前綴ab，然後第二次讀取ababab又得回滾才能識別ab，然後第三次讀取abab又得回滾才能識別ab，最後一次讀取ab不用回滾。使用優化後的讀取器就能避免這種問題(也就是使用Failed數組和全局計數器InputPos)。
任何建議回答都好，謝謝。

==================分割線======================================
首先謝謝知乎網友李元奇耐心詳細的回復，下面是對知乎網友李元奇的回復的疑問，貼出來不是對原答案的否定，只是因為我還存在較多疑問，希望被大家看到，可以幫我解答一下。評論如下：
=============================================================

謝謝這麼詳細耐心的回答。下面的困惑點都是建立在上一個困惑點成立或者不成立的情況下，困惑如下：
1.在分割線下面的第五段出現的」一共讀取了4+3+2+1次「，請問這個讀取是指每次讀取一對ab嗎？所以第一次讀取4次，第二次讀取3次，第三次讀取2次，第四次讀取一次。
2.書中說InitializeScanner必須在NextWord之前調用，那麼每次做的標記不都會被InitializeScanner衝掉嗎？除非對於某個輸入字元串，只是第一次識別的時候調用，後面的識別過程就不再是這樣調用了。
3.假設疑問2不成立，確實是像後面"除非"所說。那麼根據後面的那個while循環，標記的應該是Failed數組state和InputPos分別為(Se,8),(S3,8),(S4,7),(S3,6),(S4,5),(S3,4),因為s2是屬於Sa，所以會退出循環，也就是不會繼續標記，這個時候就進行了後面的return TokenType[state]，讀取結束，按照1所說的那種計算，這次讀取了4次。然後進行第二次讀取，那麼InputPos等於3（因為沒有進行InitializeScanner，所以保存的是上一次的值）state等於s0，進入第一個while循環，InputPos+1，不會觸發if Failed（因為這時候Failed[s0][4]，是false，壓根沒有被第二個while更新，因為時候Failed數組的第一維度和第二維度的搭配不再和第一次遍歷讀取一樣了），然後就是push和得到下一個state，再次循環重複，後面的沒有受到第一次標記Failed數組的任何好處，這也就是我最大的困惑。

我也是去年聖誕節才開始學編譯原理的， @藍色當時給我推薦的這本書，看了前端部分又把龍書的前端看了遍。

說的有錯請指出。。

本質上這個改進，是為了在第一次讀取輸入序列的時候儘可能多的存儲識別信息，這樣即使失敗了，後面也能用上這些記錄的信息，少走些彎路。

=======剩下的是苦逼的機械勞動===題主拿筆跟我畫========

然後我們來人力模擬一下。首先，搞清楚這個dfa想要讀啥東西，比如現在它有兩個識別模式，第一個是接受一個「ab」，第二個是n個「ab」後面接一個「c」。我們直到他要幹啥了就可以開始人力模擬了。

如果你給他一個「abababababc」，是一個標準的一堆「ab」後面接一個「c」，所以DFA很高興地從頭讀到尾，並且告訴你，根據第二種識別模式，成功識別了一個單詞。一切正常。

但是如果你給他一個「abababab」，沒有「c」結尾，所以第一次，DFA讀取了第一對「ab」後，發現後面還有「ab」，於是就放棄第一種識別模式，準備按照第二種模式，繼續讀取「ab」直到遇到「c」為止。結果他讀完了整個序列發現沒有「c」，第二種識別模式也失敗了，才發現原來還是要按第一種模式，只讀取一對「ab」，即第一對出現的「ab」。所以他就開始roll back，一直退到開頭只剩下一個「ab」為止，並告訴你，成功識別了一對「ab」。

至此，字元串序列「abababab」，已經成功讀取了前面兩個字母，彙報了結果，剩餘字元串是「ababab」。然後它就繼續按照剛才那種方式，讀完了全部「ababab」，發現失敗，再退到開頭，返回第一對「ab」。然後繼續。

所以一共4對「ab」，一共讀取了4 + 3 + 2 + 1次。這就是書里寫的「Some regular expressions can produce quadratic calls to roll back in the scanner shown in Figure 2.14.」

但事實上，第一次讀取完整個字元串的時候，我們應當多記錄些數據，讓DFA不要每次做無用功，而是根據已有的數據，更高效的判斷輸入序列。

所以做了如下改進：第一，有輸入序列的一個迭代器InputPos，記錄輸入序列的位置；第二，有一個bit-array Failed，記錄失敗的情況；第三，開始前要做一些準備活動，包括置InputPos歸零，並且Failed全部置為false。

根據改進的DFA，再來輸入一次「abababab」。第一次讀取，依然是讀取全部序列，因為現在Failed沒有記錄，所以不會觸發偽代碼中那個「if Failed[] break;」，同時我們還把每次輸入序列的位置和對應狀態做了記錄。讀取完畢後，雖然按計劃第二種識別模式失敗，但是在roll back的過程中，我們把Failed的數據填上了。退到開頭，重新讀取第一對「ab」，發現Failed有標記，退出循環，直接報告匹配的這對「ab」。然後繼續，讀完第二對「ab」，又發現標記，直接退出並報告匹配結果。這樣，只用了4+1+1+1+1的次數就完成了對這個序列的識別。

我也沒搞明白這段代碼的好處在哪裡。似乎Failed[][]的好處只有在詞法分析器對同一個字元串再一次進行分析的時候才能發揮出作用。對同一個字元串分析兩遍？搞毛啊？