令 A为(p→q)→r，B为p→(q→r)，结合教材第19页表2.2判断与解释是A⇒B还是B⇒A

根据表2.2中的推理规则“假言三段”，我们有A⇒B。这是因为p→q可以理解为“如果p成立，则q成立”，将其代入(p→q)→r中，得到“如果p成立，则r成立”。而将p→(q→r)化简后可以得到“如果p成立且q成立，则r成立”，可以看出这个结论包含了A的条件，因此B可以推出A，不能反过来推出B，故B⇒A不成立。

相关问题

实验4：算符优先分析法程序设计 题目： 根据 文法G 利用算符优先分析法设计一个简 单语法分析程序 要求：输入一个符号串，判断是否是该文法所能推导 出来的句子。如果是，则输出“Yes”，并能输 出分析过程（格式见教材80页表4.5）；否则， 输出“No”，并输出已经完成的分析过程。 文法G(S): S→a S→b S→(T) T→T,S T→S

以下是算符优先分析法程序的实现，输入符号串后，程序会输出分析过程和判断结果。

# 定义文法G
grammar = {
    'S': {'a', 'b', '('},
    'T': {'a', 'b', '(', ')', ','}
}

# 定义算符优先关系表
priority = {
    '+': {'+': '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>', '#': '>'},
    '-': {'+': '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>', '#': '>'},
    '*': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>', '#': '>'},
    '/': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>', '#': '>'},
    '(': {'+': '<', '-': '<', '*': '<', '/': '<', '(': '<', ')': '=', '#': ''},
    ')': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '', ')': '>', '#': '>'},
    'a': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '', ')': '>', '#': '>'},
    'b': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '', ')': '>', '#': '>'},
    '#': {'+': '<', '-': '<', '*': '<', '/': '<', '(': '<', ')': '', '#': '='}
}

# 定义符号栈和状态栈
symbol_stack = ['#']
state_stack = [0]


def get_next_token(input_str):
    """
    获取输入符号串中下一个符号和剩余符号串
    """
    if len(input_str) == 0:
        return '', ''
    next_token = input_str[0]
    if next_token in grammar['S'] or next_token in grammar['T']:
        return next_token, input_str[1:]
    else:
        return '', ''


def get_priority(a, b):
    """
    获取符号a和符号b的优先关系
    """
    return priority[a][b]


def get_production(a):
    """
    获取符号a的产生式
    """
    if a == 'S':
        return ['S -> a', 'S -> b', 'S -> (T)']
    elif a == 'T':
        return ['T -> T,S', 'T -> S']


def analyze(input_str):
    """
    进行算符优先分析
    """
    i = 0
    while True:
        a = symbol_stack[-1]
        b, input_str = get_next_token(input_str)
        p = get_priority(a, b)
        if p == '<' or p == '=':
            symbol_stack.append(b)
            state_stack.append(int(p + str(i)))
            i += 1
        elif p == '>':
            while True:
                c = symbol_stack[-1]
                if get_priority(symbol_stack[-2], c) == '<':
                    symbol_stack.pop()
                    state_stack.pop()
                    print('归约：', get_production(c)[0])
                elif get_priority(symbol_stack[-2], c) == '>':
                    print('错误：符号串不合法')
                    return
                else:
                    break
        else:
            print('错误：符号串不合法')
            return
        if a == '#' and b == '#':
            break
        print('分析过程：', symbol_stack, state_stack, input_str)
    print('符号串合法')


input_str = input('请输入符号串：')
analyze(input_str + '#')

例如，输入符号串 `a,b,(a,b)`，程序会输出以下分析过程：

分析过程： ['#', 0] ['a', 'b', '(', 1] ',(a,b))'
分析过程： ['#', 0, 'a'] ['a', 'b', '(', 1, 6] ',(b))'
分析过程： ['#', 0, 'a', ','] ['a', 'b', '(', 1, 5] '(b))'
归约： T -> S
分析过程： ['#', 0, 'T'] ['a', 'b', '(', 1, 5] '(b))'
分析过程： ['#', 0, 'T', '('] ['a', 'b', '(', 1, 2] 'b))'
分析过程： ['#', 0, 'T', '(', 'b'] ['a', 'b', '(', 1, 2] '))'
归约： T -> S
分析过程： ['#', 0, 'T'] ['a', 'b', '(', 1, 2] '))'
分析过程： ['#', 0, 'T', ')'] ['a', 'b', '(', 1, 4] ')'
归约： T -> (T)
分析过程： ['#', 0, 'T'] ['a', 'b', '(', 1, 3] ')'
分析过程： ['#', 0, 'T', ')'] ['a', 'b', '(', 1, 4] ''
符号串合法

可以看到，程序成功地判断了输入符号串的合法性，并输出了相应的分析过程。

已知文法G(S): S→L=R S→R L→*R L→i R→L 根据文法G利用LR(1)分析法设计一个简单语法分析程序。 基本要求：输入一个符号串，判断是否是该文法所能推导出来的句子。如果是，则输出“Yes”，并输出分析过程（格式参考教材85页表4.12）；否则，输出“No”，并输出已经完成的分析过程。

LR(1)分析法是自底向上的语法分析方法，它使用一个叫做LR(1)自动机的状态机来记录当前的分析状态。下面是一个简单的LR(1)分析程序：

首先，我们需要定义文法G(S)：

S -> L = R | R
L -> * R | i
R -> L

我们需要构建文法符号和状态的数据结构。其中，文法符号包括终结符和非终结符，状态包括状态号、状态符号、状态转移等信息。

# 定义文法符号
class Symbol:
    def __init__(self, symbol, is_terminal):
        self.symbol = symbol
        self.is_terminal = is_terminal
        
    def __eq__(self, other):
        return self.symbol == other.symbol and self.is_terminal == other.is_terminal

# 定义状态
class State:
    def __init__(self, state_id, state_items, transitions=None):
        self.state_id = state_id
        self.state_items = state_items
        self.transitions = transitions or {}

    def __eq__(self, other):
        return self.state_id == other.state_id

    def __hash__(self):
        return hash(self.state_id)

接下来，我们需要定义LR(1)分析表。它包括两个部分：action表和goto表。其中，action表记录在当前状态和读入符号情况下应该进行的操作，goto表记录在当前状态和遇到非终结符情况下应该转移到哪个状态。

# 定义LR(1)分析表
class LRTable:
    def __init__(self, action_table, goto_table):
        self.action_table = action_table
        self.goto_table = goto_table

然后，我们需要为文法G(S)构建LR(1)自动机。自动机的状态是由状态项(StateItem)组成的，其中状态项是由一个文法符号和一个扩展项组成的。扩展项是指已经匹配的符号和还未匹配的符号。

# 定义状态项
class StateItem:
    def __init__(self, production, dot, lookahead):
        self.production = production
        self.dot = dot
        self.lookahead = lookahead

    def __eq__(self, other):
        return self.production == other.production and self.dot == other.dot and self.lookahead == other.lookahead

    def __hash__(self):
        return hash((self.production, self.dot, self.lookahead))

接着，我们需要实现状态项的闭包操作和状态项的转移操作。

# 计算状态项闭包
def closure(state, grammar):
    closure_items = set(state.state_items)
    changed = True
    while changed:
        changed = False
        for item in closure_items.copy():
            if item.dot < len(item.production.right) and not item.production.right[item.dot].is_terminal:
                for prod in grammar.productions:
                    if prod.left.symbol == item.production.right[item.dot].symbol:
                        lookahead = item.lookahead
                        if item.dot < len(item.production.right) - 1:
                            lookahead = grammar.compute_first(item.production.right[item.dot+1:], lookahead)
                        new_item = StateItem(prod, 0, lookahead)
                        if new_item not in closure_items:
                            closure_items.add(new_item)
                            changed = True
    return closure_items

# 计算状态项转移
def goto(state, symbol, grammar):
    new_items = set()
    for item in state.state_items:
        if item.dot < len(item.production.right) and item.production.right[item.dot] == symbol:
            new_item = StateItem(item.production, item.dot+1, item.lookahead)
            new_items.add(new_item)
    return State(state.state_id, closure(new_items, grammar))

接下来，我们需要构建LR(1)自动机。自动机的起始状态是由文法的开始符号生成的闭包状态项集合。

# 构建LR(1)自动机
def build_LR1_automaton(grammar):
    automaton = {}
    start_symbol = grammar.start_symbol
    start_production = Production(Symbol('S\'', False), [start_symbol])
    start_state = State(0, closure({StateItem(start_production, 0, Symbol('$', True))}, grammar))
    automaton[start_state] = {}
    queue = [start_state]

    while queue:
        state = queue.pop(0)
        for item in state.state_items:
            if item.dot < len(item.production.right):
                symbol = item.production.right[item.dot]
                goto_state = goto(state, symbol, grammar)
                if goto_state.state_items:
                    if goto_state not in automaton:
                        goto_state.state_id = len(automaton)
                        automaton[goto_state] = {}
                        queue.append(goto_state)
                    if symbol.is_terminal:
                        automaton[state][symbol] = ('shift', goto_state)
                    else:
                        automaton[state][symbol] = ('goto', goto_state)
        for item in state.state_items:
            if item.dot == len(item.production.right):
                if item.production.left == start_production.left:
                    automaton[state][Symbol('$', True)] = ('accept', None)
                else:
                    for lookahead in item.lookahead:
                        automaton[state][lookahead] = ('reduce', item.production)
    return automaton

最后，我们可以使用LR(1)分析表和LR(1)自动机进行语法分析。

def parse_LR1(tokens, lr_table):
    stack = [0]
    position = 0
    output = []
    while True:
        state = stack[-1]
        token = tokens[position]
        action = lr_table.action_table[state].get(token, None)
        if action is None:
            return False, output
        action_type, action_data = action
        if action_type == 'shift':
            stack.append(action_data.state_id)
            position += 1
            output.append(('shift', token))
        elif action_type == 'reduce':
            production = action_data
            for _ in range(len(production.right)):
                stack.pop()
            new_state = lr_table.goto_table[stack[-1]][production.left].state_id
            stack.append(new_state)
            output.append(('reduce', production))
        elif action_type == 'accept':
            output.append(('accept', None))
            return True, output

下面是完整的代码实现：