实验:LR分析器实现

内容

• 构造LR(0)分析表
• 对输入字符串进行LR分析检测

1. 基本原理

• 略

2. 代码

from collections import defaultdict, deque
import tkinter as tk
from tkinter import ttk, messagebox
import string

punc = string.punctuation
f = defaultdict(list)           # 函数关系 A->a
Fn = list()           # 非终结符集
Ft = set('#')            # 终结符集
it = list()          # 项目集 Item0,Item1...
its = defaultdict(set)          # 项目集族 I0、I1..
GO = dict()
ACTION = defaultdict(bool)
GOTO = defaultdict(bool)
global cnt
cnt = 0           # 序号上限


class Item():
    '''
    项目结构体
    记录：
        [A]：key
        [a]：value
        圆点所在的位置(同时指向圆点后的值)：dot_pos
                S-> a a b
                   0 1 2 3
        尾端序号：last
        列表序号：index
        产生式序号： s_index
    '''
    pass


def closure(index):
    '''
    输入：
        项目集I == its[index] 
    输出： 
        项目集族{I1, I2 ...} -- 增加Go函数关系
        确定Ii = {...} 
    '''
    global cnt
    for ch, j in getDict(index).items():
        tp = set()
        for i in j:
            if it[i].dot_pos == it[i].last:         # S->aaB.
                continue
            t = i+1           # new dot_pos
            tp.add(t)            # I中的每一个项目都属于closure(I);
            if it[t].dot_pos == it[t].last:           # S->aaB.
                continue
            t = it[t].value[it[t].dot_pos]
            if t in Ft:          # S->a.aB
                pass
            elif t in Fn:          # S->aa.B
                for k in it:
                    if k.key == t and k.dot_pos == 0:
                        tp.add(k.index)
        if tp != set():
            if tp not in its.values():
                cnt += 1          # new index
                its[cnt] = tp
                GO[(index, ch)] = cnt
            else:
                x = [x for x in its if its[x] == tp][0]
                GO[(index, ch)] = x


def getDict(index):
    '''
    输入：
        I={1,2....n}
    输出：
        I={{1,2},...{n}}
    '''
    ts = defaultdict(set)
    for i in its[index]:
        if it[i].dot_pos == it[i].last:
            continue
        ts[it[i].value[it[i].dot_pos]].add(i)
    return ts


def getTable():
    for k, v in GO.items():
        if k[1] in Ft:
            ACTION[k] = ('S', v)
        elif k[1] in Fn:
            GOTO[k] = v
    for j in range(cnt+1):
        for i in its[j]:
            if it[i].dot_pos == it[i].last:
                for t in Ft:
                    if(it[i].s_index != 0):
                        ACTION[(j, t)] = ('R', it[i].s_index)
    ACTION[(1, '#')] = ('acc')


def setItem():
    '''
    初始化项目
    '''
    j = 0
    sn = 0
    for k, _ in f.items():
        for v in _:
            for i in range(len(v)+1):
                t = Item()
                t.key = k
                t.value = v
                t.index = j
                t.dot_pos = i
                t.last = len(v)
                t.s_index = sn
                it.append(t)
                j += 1
            sn += 1


def setItems():
    '''
    初始化项目集
    '''
    its[0] = set()
    its[0].add(it[0].index)
    stk = list(it[0].value)
    while(stk != list()):
        _ = stk.copy()
        for i in it:
            if i.key in stk and i.dot_pos == 0 and i.key != i.value[0]:
                if i.key in _:
                    _.remove(i.key)
                its[0].add(i.index)
                if i.value[0] in Fn:
                    _.append(i.value[0])
        stk = _


def draw():
    window = tk.Tk()
    window.title('LR分析')
    window.geometry('700x500')
    l1 = tk.Label(window,
                  text='输入文法',
                  bg='pink',
                  font=('Arial', 12),
                  height=2)
    l1.pack()
    e1 = tk.Entry(window)
    e1.insert(40, '[A]->a')
    e1.pack()
    e2 = tk.Entry(window)
    e2.insert(40, 'A->[a]')
    e2.pack()

    def inputDict():
        A = str(e1.get())
        if(A not in Fn):
            Fn.append(A)
        rstr = str(e2.get())
        rstr = rstr.split('|')
        for ch in rstr:
            a = list()
            if(ch == 'ε'):
                a.append('null')
            else:
                for i in ch:
                    a.append(i)
                    if(i in punc or i.islower()):
                        Ft.add(i)
                    else:
                        if(i not in Fn):
                            Fn.append(i)
            s = (A+"->"+ch+'\n')
            txt2.insert(tk.END, s)
            txt2.update()
            f[A].append(a)

    def run():
        setItem()
        setItems()
        while(True):
            t = its.copy()
            for i in range(len(t)):
                closure(i)
            if len(t) == len(its):
                break
        getTable()

    def checkString(wstr):
        stat = [0]
        inpt = deque(wstr)
        char = []
        cnt = 0
        tr = ttk.Treeview(window, height=10, column=('col0', 'col1', 'col2'))
        tr.column('col0', width=100, anchor='center')
        tr.column('col1', width=100, anchor='center')
        tr.column('col2', width=200, anchor='center')
        tr.heading('col0', text='state')
        tr.heading('col1', text='input')
        tr.heading('col2', text='char')
        while(inpt != deque()):
            # TypeError: sequence item 0: expected str instance, int found
            tp = [str(x) for x in stat]
            tr.insert("", cnt, values=(tp, "".join(inpt), "".join(char)))
            cnt += 1
            tp = ACTION[(stat[-1], inpt[0])]
            if tp == False:
                tk.messagebox.showerror(title='ERROR', message="匹配出错")
                exit(0)
            elif tp[0] == 'S' and inpt[0] in Ft:
                stat.append(tp[1])
                char.append(inpt.popleft())
            elif tp[0] == 'R' and inpt[0] in Ft:
                for i in it:
                    if i.s_index == tp[1]:
                        _ = deque()
                        while(list(_) != i.value):
                            _.appendleft(char.pop())
                            stat.pop()
                        char.append(i.key)
                        stat.append(GOTO[(stat[-1], char[-1])])
                        break
            elif tp == 'acc' and inpt[0] == '#':
                tk.messagebox.showinfo(title='SUCCESS', message="匹配成功")
                break
        tr.pack()
    b1 = tk.Button(window, text='输入文法', width=15,
                   height=2, command=inputDict)
    b1.pack()
    b2 = tk.Button(window, text='已输入全部文法', width=15,
                   height=2, command=run)
    b2.pack()
    l2 = tk.Label(window,
                  text='输入字符串运算',
                  bg='pink',
                  font=('Arial', 12),
                  height=2)
    l2.pack()
    e3 = tk.Entry(window)
    e3.insert(40, '[a-zA-Z+*/()]')
    e3.pack()

    def inputdata():
        wstr = str(e3.get())
        wstr += '#'
        checkString(wstr)
    b3 = tk.Button(window, text='确认', width=15,
                   height=2, command=inputdata)
    b3.pack()
    txt2 = tk.Text(window, width=55, height=7)
    txt2.pack()
    window.mainloop()


if __name__ == "__main__":
    draw()

简要说明

• Item类：项目数据类型
• setItem函数：将函数关系f转化为项目数据类型Item，并依次存储在项目列表it
• setItems函数：求项目集$I_0$，存储到项目集列表its
  • 一次遍历it，用栈实现
  • 注意： LR解析器应当可以处理左递归
• getDict函数：数据结构转换，对$A\rightarrow a_{.}Xb$，将$X$相同元素的划分到同一集合
  • $ts[X]={1,2}$
• getTable函数：$GO\Rightarrow GOTO+ACTION$
  • 本实验未实现GOTO表和ACTION表的输出，但你可以 很轻易地 改为支持

3. 结果展示

程序界面

* 输入文法支持`|`

匹配成功

* 由于界面大小限制，分析过程表需要下滑来查看隐藏部分 * 如果匹配出错，不会输出分析过程表

4. 参考资料

LR分析法 - 百度文库