编译原理练习题，给定一个文法的LM,RM推导

Question

给定一个Grammer:S -> S+S|SS|(S)|S*|a with a string (a+a)*a
(1) Give a LM derivation, a RM derivation and a parser tree for the string; Justify whether the grammar is ambiguous or not
给出它的最左和最右推导以及分析树，并判断这个文法是否有歧义

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

最左推导： S → SS → (S)S → (S+S)S → (a+S)S → (a+a)S → (a+a)*S → (a+a)*a 最右推导： S → SS → S(S) → S(S+S) → S(a+S) → S(a+a) → S*(a+a) → (S)*a → (S+S)*a → (a+a)*a 分析树：

    S
    |
    S
 / / | \ \
S  + S *  a
|    |
S    a
 |
 a

上面的推导和分析树都没有歧义，因此这个文法也是无歧义的。 代码示例： 这里给出利用Python实现上述最左推导、最右推导和分析树的代码示例：

# Grammar and input string
grammar = {
    'S': ['S+S', 'SS', '(S)', 'S*', 'a'],
}
input_str = 'a+a*a'
# Leftmost derivation
def leftmost_derivation(start_symbol, string):
    if string == '':
        return [start_symbol]
    for i in range(len(string)):
        for production in grammar[start_symbol]:
            if production == string[:len(production)]:
                return [start_symbol] + leftmost_derivation(production, string[len(production):])
    return None
print(leftmost_derivation('S', input_str))
# Rightmost derivation
def rightmost_derivation(start_symbol, string):
    if string == '':
        return [start_symbol]
    for i in reversed(range(len(string))):
        for production in grammar[start_symbol]:
            if production == string[i-len(production)+1:i+1]:
                return rightmost_derivation(production, string[:i]) + [start_symbol]
    return None
print(rightmost_derivation('S', input_str))
# Parse tree
class Node:
    def __init__(self, symbol, children=None):
        self.symbol = symbol
        self.children = [] if children is None else children
    def add_child(self, child):
        self.children.append(child)
def parse_tree(start_symbol, string):
    if string == '':
        return Node(start_symbol)
    for production in grammar[start_symbol]:
        if string.startswith(production):
            node = Node(start_symbol)
            for symbol in production.split():
                child_node = parse_tree(symbol, string[len(symbol):])
                node.add_child(child_node)
            return node
    return None
def print_tree(node, depth=0):
    print('  ' * depth + node.symbol)
    for child in node.children:
        print_tree(child, depth+1)
tree = parse_tree('S', input_str)
print_tree(tree)