一、试验名称

主动生成LR(0)剖析表

 

二、试验目标

1、实现计算闭包函数CLOSURE的算法。

2、实现转向函数GO(I,X)的算法。

3、实现ACTION子表和GOTO子表的结构算法。

4、输出任意的压缩了的上下文无关文法,输入相应的LR(0)剖析表(以表格模式输入)。

 

三、试验原理

1、闭包closure(I)

若文法G已拓广为G’,而S为文法G的开始符号,拓广后减少产生式S’->S。如果I是文法G’的一个我的项目集,定义和结构I的闭包closure(I)如下:

a.I的我的项目在closure(I)中。

b.若A->•B属于closure(I),则每一形如B->•的我的项目也属于closure(I)。

c.反复b直到不呈现新的我的项目为止。即closure(I)不再扩充。

2、转换函数GO(I,X)

GO(I,X)=closure(J)

其中:I为蕴含某一我的项目集的状态。

X为一文法符号,X∈Vn∪Vt

J={任何形如A->•X的我的项目|A->X•属于I}

3、ACTION子表和GOTO子表的结构

a.若我的项目A→.a属于Ik且GO (Ik, a)= Ij, a为终结符,则置ACTION[k, a]为“把状态j和符号a移进栈”,简记为“sj”;

b.若我的项目A→.属于Ik,那么,对任何终结符a,置ACTION[k,a]为“用产生式A→进行规约”,简记为“rj”;其中,假设A→为文法G'的第j个产生式

c.若我的项目S'→S.属于Ik, 则置ACTION[k, #]为“承受”,简记为“acc”;

d.若GO (Ik, A)= Ij, A为非终结符,则置GOTO[k, A]=j;

e.剖析表中凡不能用上述1至4填入信息的空白格均置上“出错标记”。 按上述算法结构的含有ACTION和GOTO两局部的剖析表,如果每个入口不含多重定义,则称它为文法G的一张LR(0)剖析表。具备LR(0)表的文法G称为一个LR(0)文法,LR(0)文法是无二义的。

 

四、试验思路

本次试验采纳python实现。

1、输出

结构一个LR类,输出非终结符,终结符,开始符以及产生式别离存于LR类的成员:Vn,Vt,start,production。

2、建设我的项目

构造函数Project,依据产生式建设我的项目,对每一条产生式的右部进行解决,顺次在右部的每个终结符和非终结符前增加原点,并在最初增加原点。

3、closure算法

构造函数closure,求一个我的项目的闭包closure。分三种状况探讨,对于S->·和E->·a这两种状况,返回本身。对于E->b·B这种状况,对我的项目的右部进行解决,持续求B->·r闭包,因而这是一个递归函数。最终函数以列表的模式返回每个我的项目集。

4、转向函数GO(I,X)的算法

构造函数GO,求一个我的项目集的GO(I,X)。建设字典go寄存最终后果,对不是S->a·模式的我的项目进行探讨,对我的项目的右部进行解决,将原点后移一位,利用closure函数失去圆点后移失去的我的项目的我的项目集,退出go中。直到解决完该我的项目集的所有我的项目。

5、建设状态及对应的我的项目集

构造函数createDFA,建设状态及对应的我的项目集。首先,从拓广文法的第一个我的项目开始,建设初态,定义number寄存状态编号,初始值为0。设立字典status寄存状态编号及对应的我的项目集。将初态退出一个队列qu中。每次从qu中取出一个状态,求该状态的我的项目集的Go(I,x),再对失去的我的项目集进行判断,若该我的项目集是已知的状态,则不做解决,若该我的项目集是新的状态,则将其退出队列qu中,number加1。每次从qu中取出一个状态反复上述操作,直到队列为空,阐明已求得所有状态。

6、ACTION子表的结构

分两种状况探讨:我的项目集只有一个我的项目和我的项目集不止一个我的项目。对于第一种状况,再分两种状况,看该我的项目是否对应了初态,若是,则将#对应为acc,其余终结符对应为error,若不是,则求得该我的项目去掉圆点之后的产生式的编号i,终结合乎#对应为ri。对于我的项目集不止一个我的项目的状况,顺次对终结符和#寻找在该状态的的GO(I,X)下是否有所对应,有则求得编号对应为Si,没有则对于error。

7、GOTO子表的结构

对于每个状态的GO(I,X)函数进行遍历,寻找是否有对应的终结符,若有则返回对应的我的项目集的编号,若没有则返回error。

 

五、试验小结

通过本次试验,理解了LR(0)剖析表的结构,对于结构过程所须要的一些算法有了深刻的理解,通过理论的编写程序代码实现LR(0)剖析表的结构,对于程序的编写能力有了肯定的晋升。在试验过程中,次要对于closure闭包函数的结构以及状态的设置有问题。Closure闭包函数用了递归的构造,因而对于递归的完结条件须要标注分明。对于状态的建设,须要留神每次通过GO(I,X)失去的新的我的项目集是否是曾经存在的状态,若是则不做解决。对于状态的遍历应用队列来实现,每次新的状态都退出队列中,队列为空阐明状态遍历结束。有一点问题值得注意,因为状态编号的我的项目集的存储构造应用了字典,字典是无序的构造,因而每次遍历失去的状态编号都不同,程序的每次运行失去的最终LR(0)剖析表不惟一。

 

六、附件

1、源代码
import copyimport queueclass LR:    def __init__(self):        self.Vn = []        self.Vt = []        self.start = None  # 开始符号        self.production = []  # 产生式        self.project = []  # 我的项目        self.status = {}  # 寄存状态编号及对应的我的项目集        self.goto = {}  # 寄存goto表  {0:{E:'1',A:'error',B:'error'}}        self.action = {}  # 寄存action表  {0:{a:'S2',b:'S3'}}    def setVn(self):        Vn = input('输出非终结符(以空格辨别, 回车完结):')        self.Vn = Vn.split(' ')    def setVt(self):        Vt = input('输出终结符(以空格辨别, 回车完结):')        self.Vt = Vt.split(' ')    def setS(self):        S = input('输出开始符号(以回车完结):')        self.start = S    def setf(self):  # 生成产生式        n = int(input('输出产生式数目:'))        print('输出产生式(以回车辨别):')        for i in range(n):            f = input()            self.production.append(f)    def Project(self):  # 建设我的项目        for f in self.production:            temporary = copy.deepcopy(f)  # temporary与f雷同            temporary = temporary.split('->')            l = temporary[0]  # 产生式左部            r = list(temporary[1])  # 产生式右部            for i in range(len(r)+1):  # 对产生式右部解决                temporary1 = copy.deepcopy(r)                temporary1.insert(i,'·')                newf = l+'->'+''.join(temporary1)                self.project.append(newf)    def closure(self, pro):  # 求一个我的项目pro的闭包  E->· E->·b E->b·B  返回列表        temporary = []  # 最终返回的后果        temporary.append(pro)  # 将pro本身退出        l1 = pro.split('->')[0]  # 左部        r1 = pro.split('->')[1]  # 右部        x = list(r1)  # 寄存右部的列表        index = x.index('·')  # 失去圆点地位        if len(x) == 1:  # S->·            return temporary        else:            if index == len(r1)-1 or x[index+1] in self.Vt:  #E->·a                return temporary            else:  # E->b·B                for elem in range(len(self.project)):                    l = self.project[elem].split('->')[0]  # 左部                    r = self.project[elem].split('->')[1]  # 右部                    if l == x[index+1] and r.startswith('·'):  # 持续求B->·r闭包                        conlist = self.closure(self.project[elem])                        if len(conlist) == 0:                            pass                        else:                            temporary.extend(conlist)                return temporary    def GO(self, project):  # 计算一个我的项目集的GO(I,x),返回字典模式        go = {}  # 寄存Go(I,x)后果,模式为{a:[],b:[]}        for elem in project:            l = elem.split('->')[0]  # 我的项目左部            r = elem.split('->')[1]  # 我的项目右部            index = list(r).index('·')  # 返回·的地位            if not r.endswith('·'):   # 不是S->a·模式                if go.get(list(r)[index+1]) == None:  # 阐明x所对应的go中没有我的项目                    temporary = list(r)                    temporary.insert(index+2, '·')                    temporary.remove('·')   # 将·后移一位                    x = l+'->'+''.join(temporary)  # 产生一个残缺的我的项目                    go[list(r)[index+1]] = self.closure(x)  # 将该我的项目对应的我的项目集退出x的go中                else:  # 阐明x所对应的go中已有我的项目                    temporary = list(r)                    temporary.insert(index+2,'·')                    temporary.remove('·')   # 将·后移一位                    x = l+'->'+''.join(temporary)  # 产生一个残缺的我的项目                    go[list(r)[index+1]].extend(self.closure(x))        return go    def createDFA(self):  # 建设辨认活前缀的DFA        number = 0  # 初始状态编号为0        first = 'S->·'+self.start  # 初态        x = self.closure(first)  # 初态闭包        self.status[number] = x        qu = queue.Queue()  # 结构队列,用于寄存失去的状态        qu.put({number:self.status[number]})  # 把初始状态退出队列中        number = number+1        while not qu.empty():   # 队列不为空,阐明状态没有遍历结束            temporary = qu.get()  # 队列中取出一个状态            for k, v in temporary.items():                y = self.GO(v)  # 求我的项目集的Go(I,x)                for key, value in y.items():                    flag = -1  # 标记位,判断value是否是新的状态                    for ke, va in self.status.items():                        if set(va) == set(value):                            flag = ke  # 状态已存在,返回状态编号                            break                    if flag == -1:  # 新的状态,退出状态集中                        self.status[number] = value                        qu.put({number:self.status[number]})                    else:  # 已有状态                        pass  # 不作解决    def GOTO(self):  # goto表        for i in range(len(self.status)):            self.goto[i] = {}            temp = self.GO(self.status[i])  # 每个状态的GO            for vn in self.Vn:   # 对非终结符遍历                if vn in temp.keys():  # 非终结符存在于状态的Go中                    for key, value in  self.status.items():                        if set(value) == set(temp[vn]):                            number = key  # 记录编号                            break                    self.goto[i][vn] = number                else:                    self.goto[i][vn] = 'error'    def ACTION(self):        vtx = copy.deepcopy(self.Vt)        vtx.append('#')  # 终结符加‘#’        for i in range(len(self.status)):            self.action[i] = {}            if len(self.status[i]) == 1:  # 我的项目集只有一个我的项目                if self.status[i][0].startswith('S'):  # S->E·                    for vt in self.Vt:                        self.action[i][vt] = 'error'                    self.action[i]['#'] = 'acc'                else:  #  填写rj的我的项目  E->aA·                    temp = self.status[i][0].rstrip('·')  # 删去我的项目的·  E->aA                    for n in range(len(self.production)):                        if self.production[n] == temp:                            m = n+1   # 产生式在G'中下标从1开始                            break                    for vt in vtx:                        self.action[i][vt] = 'r'+str(m)            else:  # 填写Sj的我的项目                temp = self.GO(self.status[i])  # 字典模式{a:[],b:[]}                for vt in vtx:                    if vt in temp.keys():                        for key, value in self.status.items():  # 确定到哪一个状态                            if set(value) == set(temp[vt]):                                number = key  # 返回状态编号                                break                        self.action[i][vt] = 'S'+str(number)                    else:                        self.action[i][vt] = 'error'    def output(self):   # 输入LR(0)剖析表 表格模式        print('LR(0)剖析表'.center(85))        print('状态'.center(5), 'ACTION'.center(50), 'GOTO'.center(30))        print('  '.center(10),end='')        for vt in self.Vt:  # action            print(vt.center(10),end='')        print('#'.center(10),end='')        for vn in self.Vn:  # goto            print(vn.center(10),end='')        print() # 换行        vtx = copy.deepcopy(self.Vt)        vtx.append('#')        for i in range(len(self.status)):  # 输入每一行            print(str(i).center(10),end='')            for vt in vtx:                for key in self.action[i]:  # {0:{'b':'S1'}}                    if vt == key:                        print(self.action[i][key].center(10),end='')                        break            for vn in self.Vn:                for key in self.goto[i]:                    if vn == key:                        print(str(self.goto[i][key]).center(10),end='')                        break            print() # 换行    def show(self):  # 显示各个状态及对应的我的项目集        print('所有状态及对应的我的项目集:')        for key, value in self.status.items():            print(key, value)if __name__ == '__main__':    a = LR()    a.setVn()    a.setVt()    a.setS()    a.setf()    a.Project()    a.createDFA()    a.ACTION()    a.GOTO()    a.show()    a.output()

2、程序运行后果

语法分析表/1.png)

语法分析表/2.png)