LR(1)文法详解

一、基本概念

LR(1)文法是指能够通过查看输入符号和一个状态栈的看广度为1的后缀来进行最左推导的文法。

在LR(1)中，L表示从左至右遍历输入符号串，R代表使用右规则进行规约，1代表广度为1的向后查看符号数。

在使用LR(1)进行分析时，会将输入符号串和当前状态栈的后缀作为一个整体来进行分析，以确定下一步的动作。

二、LR(1)分析器的构造

在构造LR(1)分析器时，需要完成以下几个步骤：

1. 构建项集

首先，需要根据文法构建每个非终结符的项集。

具体来说，项集是指由一个非终结符及其右侧推导出的一部分符号组成的集合。

例如，对于文法：
S -> A
A -> B c
B -> b | ε

构建项集S'，有以下4个项：
S' -> . S
S -> . A
A -> . B c
B -> . b
B -> .

2. 构建LR(1)自动机

接着，可以使用项集来构建LR(1)自动机。

LR(1)自动机是一个有向图，每个节点代表一个项集，每条边代表一个文法符号。

在自动机中，将箭头指向的下一个状态以及对应的文法符号称为转移。

例如，对于项集S'，可以进行如下转移：
S' -> S.
S  -> A.
A  -> B . c

此时可以根据c进行一次转移和规约。

3. 构建动作表和转移表

最后，可以根据LR(1)自动机构建动作表和转移表，用于分析输入符号串。

动作表和转移表是两个二维表格，动作表中的每个格子对应一个状态和一个终结符，转移表中的每个格子对应一个状态和一个非终结符。

动作表中的每个格子可能包含以下三种动作：移进、规约和接受。

转移表中的每个格子记录的是从当前状态进行某个非终结符转移时所到达的下一个状态。

三、代码示例

1. 构建项集

def closure(I):
    J = set(I)
    while True:
        lenJ = len(J)
        for item in J:
            if not item.hasNext():
                continue
            B = item.peek()
            for rule in grammar[B]:
                newItem = LR1Item(B, 0, rule.lookaheads)
                if newItem not in J:
                    J.add(newItem)
        if len(J) == lenJ:
            break
    return J

2. 构建LR(1)自动机

states = []
state0 = closure([LR1Item('S\'', 0, ['$'])])
states.append(state0)

for state in states:
    GOTO = {}
    for item in state:
        if item.hasNext():
            nextSymbol = item.peek()
            if nextSymbol not in GOTO:
                GOTO[nextSymbol] = []
            newItem = item.shift()
            GOTO[nextSymbol].append(newItem)
    for symbol, items in GOTO.items():
        nextState = closure(items)
        if nextState not in states:
            states.append(nextState)
        transition = (states.index(state), symbol, states.index(nextState))
        transitions.append(transition)

3. 构建动作表和转移表

动作表

actions = [{} for i in range(len(states))]
for i, state in enumerate(states):
    for item in state:
        if item.hasNext():
            continue
        for lookahead in item.lookaheads:
            if item.production.left == 'S\'':
                actions[i][lookahead] = ('accept', None)
            else:
                actions[i][lookahead] = ('reduce', item.production)
    for symbol, nextState in getGOTO(state).items():
        actions[i][symbol] = ('shift', nextState)

转移表

transitions = [{} for i in range(len(states))]
for i, state in enumerate(states):
    for symbol, nextState in getGOTO(state).items():
        transitions[i][symbol] = nextState

四、LR(1)分析器的应用

LR(1)分析器常用于编译器的前端设计中，能够快速准确地进行语法分析和语义分析。

例如在编写C++、Java等大型编译器时，LR(1)分析器是不可或缺的工具。

除此之外，LR(1)分析器也常用于正则表达式、自然语言处理、数据库查询优化等领域。