[编译原理与实践]求解First集合，并尝试用Javascript实现
星愿 2019-06-21
编译原理与实践
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）一样地就有了这篇。
感觉好多事情我都做不好，其中就包括如何把感情传达给别人（不带目的性地）。
有时就只能打个表情了，⁄(⁄ ⁄ ⁄ω⁄ ⁄ ⁄)⁄
