當前位置:編程學習大全網 - 編程軟體 - first集follow集求解算法及構造預測分析表

first集follow集求解算法及構造預測分析表

要理解壹個概念,第壹步先要知道人們為什麽要發明這個概念:

目的1:first set 和follow set 的作用都是為了計算predict set(predict set 在有些書中叫做LL table)。

目的2:predict set 是預測分析(predict parsing)的核心。我在 shift reduce,預測分析,遞歸下降分析(這是解析方法)和LL(K) LR(K) SLR以LALR的關系? - 彭飛的回答 這個回答中提到:LL通過預測驅動,而LR通過預測來解決沖突

這個LL parser 對應的grammar 是:

可以看到有三個產生式可以產生stat 這個非終結符(這裏的stat 是開始符號)。換句話說LL parser 在自頂向下分析的過程中:1)predict:先確定要生成的非終結符,即語法樹節點類型,2)match:再根據已經確定的非終結符去匹配(展開)到下壹層。

在這個例子中,我們從stat 開始,要確定stat 展開到下壹步三個選項中的哪壹個(也就是說這裏需要壹個語句,但具體是哪種語句呢?),這時就要用if 來根據每個產生式的predict set 來判斷這裏到底需要哪種stat。可以從代碼中看出returnstat的predict set 是{‘return’},assign的是{id},ifstat 的是{‘if’}。而且這三個產生式的predict set 沒有任何交集,if 語句只需要比對下壹個輸入符號就可以確定需要產生的非終結符,這就叫做LL(1)

第二步,當理解了這個概念的意圖之後就要學習它在任意例子上的應用了。因為現實中的編程語言不可能像上面的例子壹樣簡單,我們需要壹套形式化的算法來計算first set,follow set,然後進壹步計算predict set

這裏我直接放壹個我們上課時用的handout,簡單明了:

  • 上一篇:Python是解釋型語言嗎
  • 下一篇:服務器管理屬於哪種註冊商標?
  • copyright 2024編程學習大全網