摘要：編譯原理與實踐集合理解求非終結符的集合，就是求所有可能打頭出現(xiàn)的終結符的集合。注意此時遇到特殊情況，由于非終結符的集中包含空字符，意味著即使非終結符為空也是合法的。存在定理，當且僅當包含時，非終結符為可空的。

求非終結符A的First集合，就是求A所有可能打頭出現(xiàn)的終結符的集合。

假設有個文法 ( A=XXX, ... ) ，它定義了什么是Javascript中的合法變量名 ( 必須以字母或$, _開頭 ) ，那么 First(A) = { number, $, _ } 。

下面通過解例題來描述一種更適合人腦的First集合求法，類似填字游戲。

簡單整型表達式文法

exp -> exp addop term | term
addop -> + | -
term -> term mulop factor | factor
mulop -> *
factor -> ( exp ) | number

PS: +, -, *, (, ), number 為終結符

步驟一，完整展開文法并編號

(1) exp -> exp addop term
(2) exp -> term

(3) addop -> +
(4) addop -> -

(5) term -> term mulop factor
(6) term -> factor

(7) mulop -> *

(8) factor -> ( exp )
(9) factor -> number

步驟二，寫出所有需要求的First集合 ( First集合群 )

First(exp) = {}
First(addop) = {}
First(term) = {}
First(mulop) = {}
First(factor) = {}

這些First集合都是空集，接下來就是不斷往里填入終結符。可參考對First集合的理解和特定文法快速腦補進行，也可參考下面的技巧，慢慢來。

步驟三，從上到下遍歷已編號的產生式并逐條處理

處理編號為(1)式子，exp -> exp addop term。它表明非終結符exp可能還以exp開頭。于是往集合First(exp)中添加集合First(exp)的所有內容 ( 求并集 )。但集合First(exp)為空集，沒有產生變化。

處理編號為(2)式子，exp -> term，表明非終結符exp可能以非終結符term開頭。于是往集合First(exp)中添加集合First(term)的所有內容 ( 求并集 )。但集合First(term)還是空集，沒有產生變化。

接著處理(3)、(4)式子，addop -> +、addop -> -，表明非終結符addop可能以終結符 +、- 開頭。于是往集合First(addop)中加入 +、- 。得到First(addop) = { +、- }，F(xiàn)irst集合群產生變化，如下。

First(exp) = {}
First(addop) = { +, - }
First(term) = {}
First(mulop) = {}
First(factor) = {}

接著處理(5)、(6)式子，但沒有產生變化。

接著處理(7)式子，mulop -> *，得到First(mulop) = { * }，F(xiàn)irst集合群產生變化，如下。

First(exp) = {}
First(addop) = { +, - }
First(term) = {}
First(mulop) = { * }
First(factor) = {}

接著處理(8)、(9)式子，得到First(factor) = { (, number }，產生變化。

First(exp) = {}
First(addop) = { +, - }
First(term) = {}
First(mulop) = { * }
First(factor) = { (, number }

到此第一次遍歷完成，由于此次遍歷中First集合群有產生變化，所以還需要從頭再遍歷一次。

第二遍處理(1), (2)式子，由于目前First集合群中First(exp)和First(term)還是都為空集，所以(1), (2)式子還是沒有產生變化。

第二遍處理(3), (4)式子，結果是再往集合First(addop)中加入 +、-，沒有產生變化。

第二遍處理(5), (6)式子，結果是往集合First(term)加入集合First(factor)的全部內容，產生變化。

First(exp) = {}
First(addop) = { +, - }
First(term) = { (, number }
First(mulop) = { * }
First(factor) = { (, number }

第二遍處理(7), (8), (9)式子，都沒有產生變化。

到此第二次遍歷結束，由于此次遍歷中First集合群有產生變化，所以還需從頭再遍歷一次。

第三遍，只有(2)式子產生變化，往集合First(exp)中加入集合First(term)的內容。

First(exp) = { (, number }
First(addop) = { +, - }
First(term) = { (, number }
First(mulop) = { * }
First(factor) = { (, number }

到此第三次遍歷結束，由于本次遍歷產生變化，還需要再來一次。

第四次遍歷，集合群沒有產生變化，求解結束，最終答案如下。

First(exp) = { (, number }
First(addop) = { +, - }
First(term) = { (, number }
First(mulop) = { * }
First(factor) = { (, number }

再來解一道例題，并考慮一種特殊的情況。

虛構的文法

A = a | ε
B = b | ε
C = A B c

PS: a, b, c 為終結符，ε 為空字符

步驟一、二，展開并編號，寫出要求的First集合群

(1) A -> a
(2) A -> ε

(3) B -> b
(4) B -> ε

(5) C -> A B c

First(A) = {}
First(B) = {}
First(C) = {}

步驟三，遍歷處理

處理(1), (2), (3), (4)得到，F(xiàn)irst(A) = { a, ε }、First(B) = { b, ε }。

處理(5)，得到非終結符C可能以非終結符A開頭，得到First(C) = { a, ε }。

注意此時遇到特殊情況，由于非終結符A的First集中包含空字符ε，意味著即使非終結符A為空也是合法的。試想，若A為空則非終結符C也可能以非終結符B開頭。

PS: 存在定理，當且僅當First(A)包含ε時，非終結符A為可空的。

繼續(xù)處理(5)，實際上是處理式子C -> B c。得到First(C) = { a, b, ε }。集合First(B)也包含ε，繼續(xù)處理C -> c，得到First(C) = { a, b, c, ε }。

由于First集合群產生變化，再循環(huán)處理一遍。

第二次循環(huán)處理無變化，求解結束，最終答案如下。

First(A) = { a, ε }
First(B) = { b, ε }
First(C) = { a, b, c, ε }

接著嘗試將上述的方法整理成代碼，使用Javascript語言，使用用面向對象的方法來表示終結符、非終結符、空符號與產生式。代碼中也將嘗試求解上述的兩個例子。

// 原型繼承輔助函數(shù)，配合繼承屬性的xxx.call(this, xxx)使用
function extend (superClass, subClass) {
  var prototype = clean(superClass.prototype)
  prototype.constructor = subClass
  subClass.prototype = prototype

  function clean (prototype) {
    var F = function () {}
    F.prototype = prototype
    return new F()
  }

  return subClass
}

// 終結符類
function Terminator (symbol) {
  this.symbol = symbol
}

// 特殊的終結符，空符號
var NullTerminator = extend(Terminator, function () {
  Terminator.call(this, "ε")
})

// 非終結符類
function NonTerminator (symbol) {
  this.symbol = symbol
}

// 產生式類
function Production (leftItem, rightItemList) {
  this.leftItem = leftItem
  this.rightItemList = rightItemList
}

// 求并集工具函數(shù)
function union (main, sub, judge) {
  var added = null

  var _judge = function (a, b) {
    return a === b
  }

  if (judge) {
    _judge = judge
  }

  for (var i = 0; i < sub.length; i++) {
    var subItem = sub[i]

    for (var j = 0; j < main.length; j++) {
      var mainItem = main[j]
      if (_judge(subItem, mainItem)) {
        break
      }
    }

    if (j >= main.length) {
      main.push(subItem)
      if (!added) {
        added = []
      }
      added.push(subItem)
    }
  }

  return added
}

// 求給定productionList ( 產生式列表 ) ，firstSetGroup ( First集合群對象 ) 的First集合
function solvefirstSet (productionList, firstSetGroup) {
  while(firstSetGroup.changed) {
    firstSetGroup.changed = false
    for (var i = 0; i < productionList.length; i++) {
      var production = productionList[i]
      dealWith(production)
    }
  }

  function dealWith (production) {
    var main = firstSetGroup.group[production.leftItem.symbol]
    var subList = []

    // 遍歷式子右側，逐個處理
    for (var i = 0; i < production.rightItemList.length; i++) {
      var rightItem = production.rightItemList[i]

      // sub為右側單個項目對應的First集合
      var sub = null
      if (rightItem instanceof NonTerminator) {
        sub = firstSetGroup.group[rightItem.symbol]
      } else {
        sub = [rightItem]
      }
      subList.push(sub)

      // 如果sub中不包含空符號，則可跳出循環(huán)，否則繼續(xù)處理下一項
      var canBreak = true
      for (var j = 0; j < sub.length; j++) {
        if (sub[j] instanceof NullTerminator) {
          canBreak = false
        }
      }

      if (canBreak) {
        break
      }
    }

    // 遍歷subList中的sub，每個子集合都合并到main中
    for (var i = 0; i < subList.length; i++) {
      var sub = subList[i]
      var changed = union(main, sub, function (a, b) {
        return a.symbol === b.symbol
      })

      if(changed) {
        firstSetGroup.changed = true
      }
    }
  }

  return firstSetGroup
}

// 準備數(shù)據(jù)
var productionList = []

var firstSetGroup = {
  // 初始標記為true，方便第一次遍歷處理
  changed: true,
  group: {
  }
}

// 初始化簡單整型表達式文法
var exp = new NonTerminator("exp")
var addop = new NonTerminator("addop")
var term = new NonTerminator("term")
var mulop = new NonTerminator("mulop")
var factor = new NonTerminator("factor")

var plus = new Terminator("+")
var minus = new Terminator("-")
var multiple = new Terminator("*")
var leftBracket = new Terminator("(")
var rightBracket = new Terminator(")")
var number = new Terminator("number")

productionList.push(new Production(exp, [exp, addop, term]))
productionList.push(new Production(exp, [term]))

productionList.push(new Production(addop, [plus]))
productionList.push(new Production(addop, [minus]))

productionList.push(new Production(term, [term, mulop, factor]))
productionList.push(new Production(term, [factor]))

productionList.push(new Production(mulop, [multiple]))

productionList.push(new Production(factor, [leftBracket, exp, rightBracket]))
productionList.push(new Production(factor, [number]))


firstSetGroup.group.exp = []
firstSetGroup.group.addop = []
firstSetGroup.group.term = []
firstSetGroup.group.mulop = []
firstSetGroup.group.factor = []

/*
var A = new NonTerminator("A")
var B = new NonTerminator("B")
var C = new NonTerminator("C")

var a = new Terminator("a")
var b = new Terminator("b")
var c = new Terminator("c")

var nt = new NullTerminator()

productionList.push(new Production(A, [a]))
productionList.push(new Production(A, [nt]))

productionList.push(new Production(B, [b]))
productionList.push(new Production(B, [nt]))

productionList.push(new Production(C, [A, B, c]))

firstSetGroup.group.A = []
firstSetGroup.group.B = []
firstSetGroup.group.C = []
*/

console.log(solvefirstSet(productionList, firstSetGroup))

我想著，如何不帶目的性地做好自己喜歡的，寫出來的文章水分少一點干貨多一些，互相溝通不要好為人師（不裝B）認真傾聽探討重點.....
還想著，許多聽不清的聲音，不連貫的畫面，不清晰的笑顏......
于是，迷（Riddle）一樣地就有了這篇。
感覺好多事情我都做不好，其中就包括如何把感情傳達給別人（不帶目的性地）。
有時就只能打個表情了，?(? ? ?ω? ? ?)?