LR(0) Parsing实例

看了一些关于Shift-Reduce的资料，一直没有去仔细推敲，似懂非懂，这几天在Wikipedia上看了关于LR parsing的示例，感觉清楚了不少。

没有什么比示例更容易能让人学会，因此，就Wiki上的示例，将之用python语言实现出来，真实的看看效果，以加强自己对此算法的理解。

# 语法规则

语法规则
(1) E -> E * B (2) E -> E + B (3) E -> B (4) B -> 0 (5) B -> 1

语法规则如上表，一个简单的上下文无关文法，并且满足LR(0)语言规则。按照WIKI上的描述，建立rules数据结构，action_table, goto_table. 用python内建的数据结构进行描述，结构清晰，明白易懂。程序如下：

书本上一般将动作表(action table)和跳转表（goto table）合并成一个表，因为其第一列都是状态索引。在本python程序中，将之分成了两个表。

动作表中，‘r’开头代表规约(reduce)，其后面的数字代表使用了第几条规则； ‘s’开头的代表移进(shift).其后面的数字代表要跳转到第几个状态；‘er’代表错误(error).

跳转表中的数字代表规约之后，根据规约之后的状态以及规约成的非终结符(NonTerminal)，要跳转到的新状态。

移进(shift)和规约(reduce)做成了子函数，此程序可以扩展为SLR(1)语法，LALR(1)语法，以及LR(1)语法，他们的差别也仅仅是shift/reduce表创建的方式不一样，从而导致状态也不一样。而对于词法分析算法来说，一旦action_table和goto table创建好了，执行的算法流程没有不同。

程序源代码

#!/usr/bin/python
#  LR(0) Parsing:
#  Rule:  左递归
#    (1) E -> E * B
#    (2) E -> E + B
#    (3) E -> B
#    (4) B -> 0
#    (5) B -> 1
################################################################
import sys
from pprint import pprint
DEBUG = 1

def print_table(tbl):
    for i in tbl:
        print ' -> '.join(i)

rules = [
    ('S' , 'E'),   # Rule 0 : S -> E
    ('E' , 'E*B'), # Rule 1 : E -> E * B
    ('E' , 'E+B'), # Rule 2 : E -> E + B
    ('E' , 'B'),   # Rule 3 : E -> B
    ('B' , '0'),   # Rule 4 : B -> 0
    ('B' , '1'),   # Rule 5 : B -> 1
]

goto_table = [
    {'E' :  3, 'B' :  4}, #S0
    {'E' : -1, 'B' : -1}, #S1  -1 indicate an error occured
    {'E' : -1, 'B' : -1}, #S2
    {'E' : -1, 'B' : -1}, #S3
    {'E' : -1, 'B' : -1}, #S4
    {'E' : -1, 'B' :  7}, #S5
    {'E' : -1, 'B' :  8}, #S6
    {'E' : -1, 'B' : -1}, #S7
    {'E' : -1, 'B' : -1}, #S8
]

action_table = [
    {'*' : 'er', '+' : 'er', '0' : 's1', '1' : 's2', '$' : 'er'},  #S0
    {'*' : 'r4', '+' : 'r4', '0' : 'r4', '1' : 'r4', '$' : 'r4'},  #S1
    {'*' : 'r5', '+' : 'r5', '0' : 'r5', '1' : 'r5', '$' : 'r5'},  #S2
    {'*' : 's5', '+' : 's6', '0' : 'er', '1' : 'er', '$' : 'ac'},  #S3
    {'*' : 'r3', '+' : 'r3', '0' : 'r3', '1' : 'r3', '$' : 'r3'},  #S4
    {'*' : 'er', '+' : 'er', '0' : 's1', '1' : 's2', '$' : 'er'},  #S5
    {'*' : 'er', '+' : 'er', '0' : 's1', '1' : 's2', '$' : 'er'},  #S6
    {'*' : 'r1', '+' : 'r1', '0' : 'r1', '1' : 'r1', '$' : 'r1'},  #S7
    {'*' : 'r2', '+' : 'r2', '0' : 'r2', '1' : 'r2', '$' : 'r2'},  #S8
]

# initial:
rpt = 0  # input read pointer
state = 0
stack = [0]

def shift(s):
    global rpt
    global state
    state = s
    stack.append(s)
    rpt += 1
    if DEBUG:
        print "shift", s, '[stack:]', stack, '[rpt:]', rpt

def reduce(r):
    global state
    rule = rules[r]
    if DEBUG : print 'rule[%d]: %s' % (r, rule)
    left, right = rule
    for i in range(len(right)):
        stack.pop()
    state = stack[-1]
    if DEBUG : print 'GOTO[%d][%s] :=> %d' % (state, left, goto_table[state][left])
    state = goto_table[state][left]
    if state < 0 : err(); sys.exit(1)
    stack.append(state)
    if DEBUG:
        print "reduce", r, '[stack:]', stack, '[rpt:]', rpt

def accept():
    global rpt
    rpt += 1
    print 'accept', '[stack:]', stack, '[rpt:]', rpt

def err():
    global rpt
    rpt += 1
    print 'Error', '[stack:]', stack, '[rpt:]', rpt


def lr_parse(inputs) :
    global rpt
    global state
    global stack
    state = 0
    stack = [0]
    rpt = 0
    while rpt <= len(inputs):
        if rpt == len(inputs) : token = '$'
        else : token = inputs[rpt]
        print '-'*64
        if DEBUG : print 'state: ', state, 'token:', token

        action = action_table[state][token]
        if DEBUG : print 'action: ', action

        if action[0] == 's' : # shift
            shift( int(action[1]) )
        elif action[0] == 'r' : # reduce
            reduce( int(action[1]) )
        elif action == 'ac' : # accept
            accept()
            break
        elif action == 'er' : # error
            err()
            break
        else :
            err()
            break

if __name__ == '__main__':
    print "rules = "
    print_table(rules)
    print "action_table = "
    pprint(action_table)
    print "\ngoto_table = "
    pprint( goto_table)

    lr_parse('1+1')

    print '*'*64
    lr_parse("1+0*1")

芯有所想

about

LR(0) Parsing实例

程序源代码