编译原理与实践

First集合

理解

求非终结符A的First集合，就是求A所有可能打头出现的终结符的集合。

假设有个文法 ( 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) = { +、- }，First集合群产生变化，如下。

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

接着处理(5)、(6)式子，但没有产生变化。

接着处理(7)式子，mulop -> *，得到First(mulop) = { * }，First集合群产生变化，如下。

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)得到，First(A) = { a, ε }、First(B) = { b, ε }。

处理(5)，得到非终结符C可能以非终结符A开头，得到First(C) = { a, ε }。

注意此时遇到特殊情况，由于非终结符A的First集中包含空字符ε，意味着即使非终结符A为空也是合法的。试想，若A为空则非终结符C也可能以非终结符B开头。

PS: 存在定理，当且仅当First(A)包含ε时，非终结符A为可空的。

继续处理(5)，实际上是处理式子C -> B c。得到First(C) = { a, b, ε }。集合First(B)也包含ε，继续处理C -> c，得到First(C) = { a, b, c, ε }。

由于First集合群产生变化，再循环处理一遍。

第二次循环处理无变化，求解结束，最终答案如下。

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

代码

接着尝试将上述的方法整理成代码，使用Javascript语言，使用用面向对象的方法来表示终结符、非终结符、空符号与产生式。代码中也将尝试求解上述的两个例子。

// 原型继承辅助函数，配合继承属性的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
}

// 求并集工具函数
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中不包含空符号，则可跳出循环，否则继续处理下一项
      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
}

// 准备数据
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）一样地就有了这篇。
感觉好多事情我都做不好，其中就包括如何把感情传达给别人（不带目的性地）。
有时就只能打个表情了，⁄(⁄ ⁄ ⁄ω⁄ ⁄ ⁄)⁄