对于一个文法若消除了左递归,提取了左公共因子后是否一定为LL(1)文法?试对 A→Ab|Ba A→aA|a B→a进行改写,并对改写后的文法进行判断

对于一个文法若消除了左递归，提取了左公共因子后并不一定为LL(1)文法。将文法 A→Ab|Ba 改写为 A→aA'，A'→bA|ε；B→a。对改写后的文法进行判断：

1. 首先，由于 A→aA' 和 B→a 的非终结符的首字符都是 a，因此需要查看 FOLLOW(A') 和 FOLLOW(B) 是否存在交集。但是，FOLLOW(A')={b,$}，FOLLOW(B)={$}，它们没有交集。

2. 判断 A' 的候选式之间是否存在 FIRST/FOLLOW 冲突。但是，A' 的候选式中不存在一个非终结符的 FIRST 集合和 FOLLOW(A') 集合的交集。

综上所述，改写后的文法是 LL(1) 文法。

相关问题

对文法G(S)： S→(T) | aS | a T→T,S | S （1）消去文法的左递归和提取公共左因子

首先我们来看一下文法G(S)：

S → (T) | aS | a
T → T,S | S

1. 消去文法的左递归

为了消除左递归，我们需要对S的产生式进行改写。S的产生式中存在左递归，因此我们可以将其拆分为两个产生式：

S → aS'
S' → (T)S' | ε

接下来，我们需要对T的产生式进行改写。T的产生式中也存在左递归，因此我们可以将其拆分为两个产生式：

T → ST'
T' → ,ST' | ε

最终，消除左递归后的文法为：

S → aS'
S' → (T)S' | ε
T → ST'
T' → ,ST' | ε

2. 提取公共左因子

在消除左递归的基础上，我们可以进一步提取公共左因子。在这个文法中，S的产生式中存在公共左因子a，因此我们可以将其提取出来：

S → aS'
S' → (T)S' | ε
T → ST'
T' → ,ST' | ε

变成：

S → aS'
S' → (T)S' | ε
T → ST'
T' → aT' | ,ST' | ε

最终，经过消除左递归和提取公共左因子后的文法为：

S → aS'
S' → (T)S' | ε
T → ST'
T' → aT' | ,ST' | ε

用python写一个能够提取左公共因子、消除直接左递归、判断是否为ll1文法、能够利用预测分析表来判断句子能否产生的完整可运行代码

下面是一个能够提取左公共因子、消除直接左递归、判断是否为 LL(1) 文法、利用预测分析表来判断句子能否产生的完整 Python 代码：

from collections import defaultdict

def extract_left_factor(grammar):
    non_terminals = grammar.keys()
    for A in non_terminals:
        productions = grammar[A]
        first_symbols = set([production[0] for production in productions])
        for a in first_symbols:
            common_prefix = []
            for production in productions:
                if production[0] == a:
                    common_prefix.append(production)
            if len(common_prefix) > 1:
                # extract left factor
                new_non_terminal = A + "'"
                new_productions = [(common_prefix[0][0], new_non_terminal)]
                for production in common_prefix:
                    new_productions.append((production[1:],))
                grammar[new_non_terminal] = new_productions
                grammar[A] = [production for production in productions if production not in common_prefix]
                grammar[A].append((a, new_non_terminal))
                return True
    return False

def eliminate_left_recursion(grammar):
    non_terminals = grammar.keys()
    for i, A in enumerate(non_terminals):
        productions = grammar[A]
        for j, beta in enumerate(productions):
            if beta[0] == A:
                # eliminate left recursion
                new_non_terminal = A + "'"
                new_productions = [production[1:] + (new_non_terminal,) for production in productions[:j]]
                new_productions.append((new_non_terminal,))
                for production in productions[j+1:]:
                    new_productions.append(production[1:] + (new_non_terminal,))
                grammar[A] = [(production[1:], A+"'") for production in new_productions]
                grammar[new_non_terminal] = [(production[1:], A+"'") for production in productions if production[0] != A] + [((),)]
                return True
    return False

def is_ll1_grammar(grammar):
    first_sets = compute_first_sets(grammar)
    follow_sets = compute_follow_sets(grammar, first_sets)
    for A in grammar.keys():
        productions = grammar[A]
        for i in range(len(productions)):
            for j in range(i+1, len(productions)):
                if first_sets[A][i].intersection(first_sets[A][j]):
                    return False
                if set(productions[i][1:]).intersection(follow_sets[A]).intersection(set(productions[j][1:])):
                    return False
    return True

def compute_first_sets(grammar):
    first_sets = defaultdict(lambda: set())
    for A in grammar.keys():
        productions = grammar[A]
        for beta in productions:
            if beta == ():
                first_sets[A].add(())
            elif beta[0] not in grammar.keys():
                first_sets[A].add(beta[0])
            else:
                for symbol in beta:
                    if symbol not in grammar.keys():
                        first_sets[A].add(symbol)
                        break
                    if () not in grammar[symbol]:
                        first_sets[A] = first_sets[A].union(first_sets[symbol])
                        break
                    else:
                        first_sets[A] = first_sets[A].union(first_sets[symbol].difference({()}))
                        if symbol != beta[-1]:
                            continue
                        else:
                            first_sets[A].add(())
                            break
    return first_sets

def compute_follow_sets(grammar, first_sets):
    follow_sets = defaultdict(lambda: set())
    start_symbol = list(grammar.keys())[0]
    follow_sets[start_symbol].add('$')
    while True:
        is_updated = False
        for A in grammar.keys():
            productions = grammar[A]
            for beta in productions:
                for i, B in enumerate(beta):
                    if B in grammar.keys():
                        if i == len(beta) - 1:
                            follow_sets[B] = follow_sets[B].union(follow_sets[A])
                        else:
                            for b in first_sets[beta[i+1]]:
                                if b != ():
                                    if b not in follow_sets[B]:
                                        follow_sets[B].add(b)
                                        is_updated = True
                            if () in first_sets[beta[i+1]] and i == len(beta) - 2:
                                follow_sets[B] = follow_sets[B].union(follow_sets[A])
                                is_updated = True
        if not is_updated:
            break
    return follow_sets

def construct_predictive_table(grammar):
    first_sets = compute_first_sets(grammar)
    follow_sets = compute_follow_sets(grammar, first_sets)
    table = defaultdict(lambda: defaultdict(list))
    for A in grammar.keys():
        productions = grammar[A]
        for i, beta in enumerate(productions):
            for a in first_sets[A][i]:
                table[A][a].append(i)
            if () in first_sets[A][i]:
                for b in follow_sets[A]:
                    table[A][b].append(i)
    return table

def parse_sentence(sentence, table):
    stack = ['$']
    sentence = sentence.split()
    sentence.append('$')
    current_symbol = stack[-1]
    i = 0
    while True:
        if current_symbol == sentence[i]:
            stack.pop()
            i += 1
        else:
            if current_symbol not in table.keys():
                return False
            if sentence[i] not in table[current_symbol].keys():
                return False
            production = table[current_symbol][sentence[i]][0]
            stack.pop()
            if grammar[current_symbol][production] != ():
                stack += list(reversed(grammar[current_symbol][production]))
        if stack == ['$'] and sentence[i] == '$':
            return True
        elif stack == [] or i >= len(sentence):
            return False
        else:
            current_symbol = stack[-1]

# example grammar
grammar = {
    'S': [('A', 'B'), ('B', 'a')],
    'A': [('A', 'c'), ()],
    'B': [('B', 'b'), ()]
}

# extract left factor
while extract_left_factor(grammar):
    pass

# eliminate left recursion
while eliminate_left_recursion(grammar):
    pass

# check if it is LL(1) grammar
if is_ll1_grammar(grammar):
    table = construct_predictive_table(grammar)
    print(table)
    # parse sentence
    sentence = 'a b $'
    is_accepted = parse_sentence(sentence, table)
    print(is_accepted)
else:
    print("Not an LL(1) grammar")

在上面的代码中，我们首先定义了四个函数：

- `extract_left_factor`：用于提取左公共因子；
- `eliminate_left_recursion`：用于消除直接左递归；
- `is_ll1_grammar`：用于判断是否为 LL(1) 文法；
- `compute_first_sets` 和 `compute_follow_sets`：用于计算 First 集和 Follow 集。

然后，我们使用给定的文法进行左公共因子提取和直接左递归消除，如果得到的文法是 LL(1) 文法，则构造预测分析表，并使用给定的句子进行语法分析，判断该句子是否能够被该文法所接受。