將FIRST和FOLLOW集合編碼爲遞歸下降解析器

這是我詢問How to encode FIRST & FOLLOW sets inside a compiler的上一個問題的後續步驟，但這一個更多地是關於我的程序的設計。將FIRST和FOLLOW集合編碼爲遞歸下降解析器

我正在通過編寫遞歸下降解析器來實現我的編譯器的語法分析階段。我需要能夠利用FIRST和FOLLOW集合，以便更有效地處理源程序語法中的錯誤。我已經爲我的所有非終端計算了FIRST和FOLLOW，但在決定將它們邏輯放置在我的程序中的位置以及最佳數據結構是什麼時，無法做到這一點。

注：所有的代碼是僞代碼

選項1）使用的地圖，並通過他們的名字所有非終端映射到包含它們的前兩分集和FOLLOW集：

class ParseConstants 
    Map firstAndFollowMap = #create a map ..... 
    firstAndFollowMap.put("<program>", FIRST_SET, FOLLOW_SET) 
end

這似乎是一個可行的選擇，但我的解析器裏面我會那麼需要幾分醜陋這樣的代碼來獲取第一和FOLLOW，並傳遞給誤差函數：

#processes the <program> non-terminal 
def program 
    List list = firstAndFollowMap.get("<program>") 
    Set FIRST = list.get(0) 
    Set FOLLOW = list.get(1) 

    error(current_symbol, FOLLOW) 
end

選項2）c eate一類每一個非終端和具有第一和FOLLOW屬性：

class Program 
    FIRST = ..... 
    FOLLOW = .... 
end

這會導致代碼看起來更好一點：

#processes the <program> non-terminal 
def program 
    error(current_symbol, Program.FOLLOW) 
end

這是我想了兩個選項，我我很想聽聽任何其他關於如何編碼這兩組的方法的建議，以及對我發佈的兩種方式的任何批評和補充都會有所幫助。感謝

我還張貼了這個問題在這裏：http://www.coderanch.com/t/570697/java/java/Encode-FIRST-FOLLOW-sets-recursive

來源

2012-03-18 Hunter McMillen

你並不真正需要的FIRST和FOLLOW集。您需要計算這些以獲取分析表。如果LL（k）（表示在堆棧中看到non-terminal，在輸入中看到token，其中action要應用並且應用哪個rule），或者如果（C | LA |）表示{<non-terminal, token> -> <action, rule>}， LR（K）（這意味着給state堆棧和輸入token，這action拿，去哪個state。

後你得到這個表，你不需要第一，並遵循了。

如果您正在編寫語義分析器，則必須假定解析器正在工作rrectly。短語級錯誤處理（意味着處理解析錯誤）與語義分析完全正交。

這意味着，如果出現語法分析錯誤，語句級錯誤處理程序（PLEH）將嘗試修復錯誤。如果無法解析，則停止。如果可以的話，語義分析器不應該知道是否有錯誤被修正，或者根本沒有任何錯誤！

例如，您可以看看my compiler library。

關於短語級錯誤處理，您再次不需要FIRST和FOLLOW。現在我們來談談LL（k）（僅僅是因爲關於LR（k）我還沒有想過）。你建立語法表後，你有很多條目，就像我說的是這樣的：

<non-terminal, token> -> <action, rule>

現在，當你分析，你採取什麼是在棧上，如果它是一個終端，那麼你必須與之相匹配與輸入。如果不匹配，短語級別的錯誤處理程序踢：

角色之一：處理缺少終端 - 簡單地生成您在詞法分析器需要並且有解析器重試類型的假冒終端。你也可以做其他的事情（例如，如果你有想要的令牌，從詞法分析器中刪除一個令牌）（例如，在輸入中檢查）

如果從堆棧中得到的是非終端（T），你必須看看你的詞法分析器，得到lookahead並看看你的桌子。如果條目<T, lookahead>存在，那麼你很好。按照操作並從堆棧中彈出/彈出。但是，如果不存在這樣的條目，那麼短語級別的錯誤處理程序就會啓動：

角色二：處理意外的終端 - 您可以做很多事情來通過它。你做什麼取決於什麼T和lookahead是你的語法和你的專業知識。你可以做的事情

的例子是：

失敗！你無能爲力
忽略這個終端。這意味着您將lookahead推入堆棧（再次推入T後）並繼續解析器。解析器將首先匹配lookahead，將其丟棄並繼續。例如：如果您有像這樣的表達式：*1+2/0.5，您可以通過這種方式刪除意外的*。
將lookahead更改爲可接受的內容，請將T推回並重試。例如，像這樣的表達式：5id = 10;可能是非法的，因爲您不接受以數字開頭的id。例如，您可以用_5id替換它以繼續

來源

2012-03-18 19:20:01 Shahbaz

感謝您提供的所有信息，這非常有幫助。 – 2012-03-18 19:38:46

沒問題。實際上，我現在正在爲我的編譯器開發更多功能，因此它已經成爲我的頭等大事了 – Shahbaz 2012-03-18 21:19:59

將FIRST和FOLLOW集合編碼爲遞歸下降解析器

回答

相關問題