本项目实现LR(1)语法分析器的自动构造,可以判定给定的文法是否为LR(1)文法。若是,则自动生成给定的LR(1)文法分析表,并对任一输入串进行分析,判定其是否为给定文法的句子。关于LR(0)和SLR分析相关程序设计可以查看Python实现LR0(SLR)语法分析器(保姆级别注释),由于不同的文法对应不同的错误处理程序,难以自动生成,所以本项目没有错误处理程序。用到的知识有自底向上分析概述LR(1)分析、[LR分析法概述](https://www.xiaoheidiannao.com/Overview-Of-LR-Analysis-Method.html)等。

LR(1)自动机的形式化定义

文法

G = (VN , VT , P, S )

LR(1)自动机

M = (C, VN∪VT , GOTO, I0 , F )

C={I0}∪{I | ∃J∈C, X∈VN∪VT, I=GOTO(J,X ) }

I0=CLOSURE({S' →·S, $})

F={ CLOSURE({S'→S· , $}) }

LR分析器(自动机)总体结构如下:

由上图可以知道,LR分析器由分析表(包括动作表和转移表)、产生式序列、输入缓冲区、LR主控程序、状态/符号栈构成。其中产生式序列可以根据输入的文法很容易就得到,输入缓冲区也就是输入的文法句子面加个"$"符号,也很容易得到,状态/符号栈在LR分析算法中会用到,而最重要的也是最难的就是分析表的自动生成。

上图是LR自动机,分析表构造过程需要用到,会用到以下函数:

CLOSURE(I)函数:计算项目集I闭包,也就是图中的I0...I13,需要传入一个参数,也就是项目集I。

GOTO(I,X)函数:返回项目集I对应于文法符号X的后继项目集闭包,例如上图所示如果传入I0和S那么求得得结果就是项目集闭包I1

items()函数:构造LR自动机的状态集,也就是生成I0到I13,在此函数中会调用到CLOSURE函数和GOTO函数。

analysis_table()函数:构造LR分析表,需要用到items()函数构造的自动机状态机。

analyze()函数:实现LR分析法逻辑,只需要传入某个句子即可识别该句子是否为输入文法的合法句子。在识别过程中会将用到的归约产生式输出,如果需要输出状态/符号栈的内容可以在此方法中添加相应的代码就可以实现。

is_lr1()函数:判断是否为LR1文法,原理也很简单,判断对应项目含有的操作个数(长度)是否大于等于2即可,如果长度是2以上的话就说明有冲突,即该文法不是LR1文法。

LR 分析算法

  • 输入:串w和LR语法分析表,该表描述了文法G的ACTION函数和GOTO函数。
  • 输出:如果w在 L(G)中,则输出w的自底向上语法分析过程中的归约步骤;否则给出一个错误指示。
  • 方法:初始时,语法分析器栈中的内容为初始状态s0,输入缓冲区中的内容为w$。然后,语法分析器执行下面的程序:
令a为w$的第一个符号;
while(1) { /* 永远重复*/ 
    令s是栈顶的状态;
    if ( ACTION [s,a] = st ) {
        将t压入栈中;
        令a为下一个输入符号;
    } else if (ACTION [s,a] =归约A → β ) {
        从栈中弹出│ β │个符号;
        将GOTO [t,A]压入栈中;
        输出产生式 A → β ;
    } else if (ACTION [s,a] =接受) break; /* 语法分析完成*/
    else调用错误恢复例程;
}

对应python代码

 # LR分析,w表示输入的输入的字符串
    def analyze(self, w):
        lr_table = self.table
        w = w + "$"
        count = 0  # 记录输入字符串的索引
        a = w[count]  # 指针指向的输入的字符
        vt = self.grammar["vt"]  # vt表示终结符集合
        vn = self.grammar["vn"]  # vn表示非终结符集合
        action = lr_table[0]  # ACTION表
        goto = lr_table[1]  # GOTO表
        status_stack = [0]  # 初始状态下状态栈中只有状态0
        while True:
            s = status_stack[len(status_stack) - 1]  # 当前栈顶露出的状态
            operation = action[s][vt.index(a)][0]  # 获取当前操作
            if "s" in operation:  # 移入操作
                status_stack.append(int(operation[1:]))  # 将s后面的状态压入栈顶
                count += 1  # 输入指针指向下一个字母
                a = w[count]  # 赋值
            elif "r" in operation:  # 归约操作
                b = int(operation[1:])  # 获取对应的产生式编号
                p = self.production[b]  # 获取产生式
                right = p.get("right")
                left = p.get("left")
                num = len(right)  # 产生式右部符号个数
                for i in range(num):
                    status_stack.pop()  # 弹出状态
                c = vn.index(left)
                s = status_stack[len(status_stack) - 1]
                status_stack.append(int(goto[s][c][0]))
                print(left + "→" + right)  # 输出产生式
            elif operation == "acc":  # 语法分析完成
                break
            else:  # 其他就是出错了,需要调用错误恢复函数,此处就不写错误恢复函数了
                raise Exception("语法分析错误")

LR(1)项目集闭包

计算给定项目集I的闭包

CLOSURE( I ) = I ∪{ [B→·γ, b] | [A→α·Bβ, a] ∈ CLOSURE( I ), B→γ∈P, b∈FIRST(βa)}

SetOfltems CLOSURE ( I ) {
    repeat
    for ( I中的每个项[A → α·Bβ,a ]) 
        for (G'的每个产生式B → γ) 
            for ( FIRST (βa)中的每个符号b ) 
                将[ B → · γ ,b]加入到集合I中;
    until 不能向I中加入更多的项;
    return I ; 
}

对应python代码

    def closure(self, i):
        # j是每个LR1项目,是一个列表,有两个元素,第一个元素为LR0项目(此处为了方便用{"left":"","right":""}表示),只有在遇到第二个元素时才可以使用第一个项目对应的产生式进行归约
        vn = self.grammar["vn"]
        for j in i:
            item = j[0]  # 产生式项目
            right = item.get("right")  # 产生式右部
            indx = right.index("·")
            if indx < (len(right) - 1):  # 原点不在最后
                b = right[indx + 1]
                if b in vn:  # b为非终结符
                    for k in self.production:  # 遍历文法产生式的所有项目
                        if b == k.get("left"):  # b为产生式左部
                            bta = None
                            if indx < (len(right) - 2):
                                bta = right[indx + 2]
                            else:
                                bta = j[1]
                            first_b = self.multi_first(bta)
                            for li in first_b:  # li表示first_b中的一个终结符
                                f = {
                                    "left": b,
                                    "right": "·" + k.get("right")
                                }
                                obj = [f, li]
                                i.append(obj)
        return i

GOTO 函数

返回项目集I对应于文法符号X的后继项目集闭包

GOTO( I, X ) = CLOSURE({[A→αX·β,a]|[A→α·Xβ, a]∈I })

SetOfltems GOTO ( I,X ) { 
    将J 初始化为空集;
    for ( I 中的每个项[A → α·Xβ,a ]) 
        将项[ A → αX·β,a]加入到集合J 中;
    return CLOSURE ( J ); 
}

对应python代码

    def go_to(self, i, x):
        j = []
        for k in i:
            f = k[0]  # LR0项目
            a = k[1]  # 展望符
            left = f.get("left")  # LR0项目左部
            right = f.get("right")  # LR0项目右部
            indx = right.find("·")
            if indx == -1:
                raise Exception("非法LR1项目")
            elif indx < (len(right) - 1) and right[indx + 1] == x:  # A → α·Xβ,存在X
                if indx < (len(right) - 2):  # 存在bta
                    j.append([
                        {
                            "left": left,
                            "right": right[:indx] + right[indx + 1] + "·" + right[indx + 2:]
                        },  # LR0项目
                        a  # 展望符
                    ])
                else:  # 不存在bta
                    j.append([
                        {
                            "left": left,
                            "right": right[:indx] + right[indx + 1] + "·"
                        },  # LR0项目
                        a  # 展望符
                    ])
        return self.closure(j)

为文法G' 构造LR(1)项集族

void items (G' ) {
    将C初始化为{CLOSURE ({[ S' → · S, $]} )} ;
    repeat
        for ( C中的每个项集 I ) 
            for ( 每个文法符号X ) 
                if (GOTO(I,X )非空且不在C中) 
                    将GOTO(I,X )加入C中;
    until 不再有新的项集加入到C中;
}

对应python代码

#  构造LR(1)自动机的状态集
    def items(self):
        # 注意这里self.closure的参数
        start = {
            "left": self.production[0].get("left"),
            "right": "·" + self.production[0].get("right")
        }
        c = [self.closure([[start, "$"]])]
        vt = self.grammar["vt"]
        vn = self.grammar["vn"]
        all_character = []  # 文法符号集合
        for i in vt:
            all_character.append(i)
        for i in vn:
            all_character.append(i)
        for i in c:
            for x in all_character:
                temp = self.go_to(i, x)
                if len(temp) != 0 and temp not in c:
                    c.append(temp)
        return c

LR分析表构造算法

  • 构造G'的规范LR(1)项集族C = { I0, I1, … , In}

  • 根据Ii构造得到状态i。状态i 的语法分析动作按照下面的方法决定:

    • if [A→α·aβ, b ] ∈Ii and GOTO( Ii , a )=Ij then ACTION[ i, a ]=sj

    • if [A→α·Bβ,b ] ∈Ii and GOTO( Ii , B )=Ij then GOTO[ i, B ]=j

    • if [A→α·, a ] ∈Ii且A ≠ S' then ACTION[ i, a ]=rj(j是产生式A→α的编号)

    • if [S'→S·, $ ] ∈Ii

    then ACTION [i, $ ]=acc;

  • 没有定义的所有条目都设置为“error”

如果LR(1)分析表中没有语法分析动作冲突,那么给定的文法就称为LR(1)文法

 def analysis_table(self, c):
        status = 0
        vt = self.grammar["vt"]
        vn = self.grammar["vn"]
        len3 = len(c)  # 状态集个数
        len1 = len(self.grammar["vt"])  # 终结符个数
        action = []  # ACTION集合,可以看作二维数组,如果每个元素也是一个数组,如果数组中没有元素则表示没有对应项目,初次之外可以是rn,sn,n,acc,如果数组中存在多个元素表示有冲突
        for i in range(len3):
            temp = []
            for j in range(len1):
                temp.append([])
            action.append(temp)
        len2 = len(self.grammar["vn"])  # 非终结符个数
        goto = []  # GOTO集合
        for i in range(len3):
            temp = []
            for j in range(len2):
                temp.append([])
            goto.append(temp)
        for i in c:  # i表示一个项目集
            for j in i:  # j表示项目集中的每个项目 [A→α·aβ, b ]
                lr0 = j[0]  # 第一个元素为lr0项目
                right = lr0.get("right")
                left = lr0.get("left")
                indx = right.find("·")
                if indx == -1:
                    raise Exception("LR1项目有误")
                else:
                    if indx < (len(right) - 1):  # 非归约项目,存在下一个状态
                        n = right[indx + 1]  # 圆点后面的文法符号
                        ij = self.go_to(i, n)
                        if n in vt:  # 下一个符号是终结符
                            action[status][vt.index(n)].append("s" + str(c.index(ij)))
                        else:
                            goto[status][vn.index(n)].append(str(c.index(ij)))
                    else:  # 归约项目或者接收项目
                        if left == "S'" and right == (self.grammar["start"] + "·") and j[1] == "$":
                            # 接收项目
                            action[status][vt.index("$")].append("acc")
                        elif left != "S'":  # 归约项目
                            count = 0  # 规约项目对应的产生式的编号
                            s = right.replace("·", "")
                            for li in self.production:
                                if left == li.get("left") and s == li.get("right"):
                                    action[status][vt.index(j[1])].append("r" + str(count))
                                    break
                                count += 1
            status += 1
        return [action, goto]

判断某个文法是否为LR1文法

# 判断是否为LR1文法,lr_table为生成的LR分析表,原理也很简单,判断对应项目含有的操作个数(长度)是否大于等于2即可,如果长度是2以上的话就说明有冲突,即该文法不是LR1文法。
    def is_lr1(self):
        lr_table = self.table
        for i in lr_table:
            for j in i:
                if len(j) >= 2:
                    return True
        return False

完整源程序代码可以在微信公众号小海电脑回复LR1语法分析获得。

最后修改日期:2020年6月7日

留言

撰写回覆或留言