Приложу два файла. В одном задание, во втором код. Не могу избавиться от двух проблем.
class CFG:
def __init__(self, variables, terminals, productions, start):
self.variables = variables
self.terminals = terminals
self.productions = productions
self.start = start
def remove_unproductive(self):
productive = set()
prev_productive = set()
while productive != prev_productive:
prev_productive = productive.copy()
for variable, rules in self.productions.items():
for rule in rules:
if all([symbol in self.terminals or symbol in productive for symbol in rule]):
productive.add(variable)
break
new_productions = {variable: rules for variable, rules in self.productions.items() if variable in productive}
self.variables = productive
self.productions = new_productions
def remove_unreachable(self):
reachable = set()
prev_reachable = set()
reachable.add(self.start)
while reachable != prev_reachable:
prev_reachable = reachable.copy()
for variable in prev_reachable:
if variable in self.productions: # Add this line to fix the KeyError
for rule in self.productions[variable]:
for symbol in rule:
if symbol in self.variables:
reachable.add(symbol)
new_productions = {variable: rules for variable, rules in self.productions.items() if variable in reachable}
self.variables = reachable
self.productions = new_productions
def remove_unreachable(self):
reachable = set()
prev_reachable = set()
reachable.add(self.start)
while reachable != prev_reachable:
prev_reachable = reachable.copy()
for variable in prev_reachable:
for rule in self.productions[variable]:
for symbol in rule:
if symbol in self.variables:
reachable.add(symbol)
new_productions = {variable: rules for variable, rules in self.productions.items() if variable in reachable}
self.variables = reachable
self.productions = new_productions
def remove_epsilon(self):
nullable = set()
prev_nullable = set()
while nullable != prev_nullable:
prev_nullable = nullable.copy()
for variable, rules in self.productions.items():
for rule in rules:
if rule == 'ε' or all([symbol in nullable for symbol in rule]):
nullable.add(variable)
break
new_productions = {}
for variable, rules in self.productions.items():
new_rules = []
for rule in rules:
if rule != 'ε':
for i in range(len(rule) + 1):
for combination in itertools.combinations(range(len(rule)), i):
new_rule = ''.join([rule[j] for j in range(len(rule)) if j not in combination and rule[j] not in nullable])
new_rules.append(new_rule)
new_productions[variable] = list(set(new_rules))
self.productions = new_productions
if self.start in nullable:
new_start = 'S0'
self.variables.add(new_start)
self.productions[new_start] = [self.start, 'ε']
self.start = new_start
def remove_chain_rules(self):
chain_pairs = set()
for variable in self.variables:
visited = set()
stack = [variable]
while stack:
current = stack.pop()
if current in visited:
continue
visited.add(current)
for rule in self.productions[current]:
if len(rule) == 1 and rule in self.variables:
chain_pairs.add((variable, rule))
stack.append(rule)
new_productions = {}
for variable, rules in self.productions.items():
new_rules = []
for rule in rules:
if len(rule) == 1 and rule in self.variables:
continue
for chain in chain_pairs:
if chain[0] == variable:
new_rule = rule.replace(chain[0], chain[1])
new_rules.append(new_rule)
new_rules.append(rule)
new_productions[variable] = list(set(new_rules))
self.productions = new_productions
def remove_left_recursion(self):
new_productions = {}
for variable in self.variables:
non_recursive_rules = [rule for rule in self.productions[variable] if not rule.startswith(variable)]
recursive_rules = [rule[1:] for rule in self.productions[variable] if rule.startswith(variable)]
if recursive_rules:
new_variable = variable + "'"
self.variables.add(new_variable)
new_rules = [rule + new_variable for rule in non_recursive_rules] + [rule + new_variable for rule in recursive_rules] + ['ε']
new_productions[variable] = new_rules
else:
new_productions[variable] = self.productions[variable]
self.productions = new_productions
def remove_left_factoring(self):
def common_prefix(a, b):
for i, (x, y) in enumerate(zip(a, b)):
if x != y:
return a[:i]
return a[:min(len(a), len(b))]
def factor_rules(variable, rules):
if len(rules) <= 1:
return rules
prefix = common_prefix(rules[0], rules[1])
for rule in rules[2:]:
prefix = common_prefix(prefix, rule)
if not prefix:
return rules
new_rules = [rule[len(prefix):] for rule in rules]
new_variable = variable + "'"
self.variables.add(new_variable)
self.productions[new_variable] = factor_rules(new_variable, new_rules)
return [prefix + new_variable]
new_productions = {}
for variable, rules in self.productions.items():
new_productions[variable] = factor_rules(variable, rules)
self.productions = new_productions
def transform(self):
self.remove_unproductive()
self.remove_unreachable()
self.remove_epsilon()
self.remove_chain_rules()
self.remove_left_recursion()
self.remove_left_factoring()
def __str__(self):
result = []
for variable, rules in self.productions.items():
result.append(f"{variable} -> {' | '.join(rules)}")
return "\n".join(result)
if __name__ == '__main__':
import itertools
variables = {"S", "A", "B", "D", "E"}
terminals = {"a", "b", "c", "e"}
productions = {
"S": ["AB", "ε"],
"A": ["Aa", "S", "a"],
"B": ["bD", "bS", "b"],
"D": ["ccD"],
"E": ["eE", "e"]
}
start = "S"
grammar = CFG(variables, terminals, productions, start)
print("Original grammar:")
print(grammar)
grammar.transform()
print("\nTransformed grammar:")
print(grammar)
Как решить эту проблему не понимаю
Вот что выдаёт терминал
D -> ccD
E -> eE | e
Traceback (most recent call last):
File "c:\Users\Admin\Desktop\Zadanie\test.py", line 200, in <module>
grammar.transform()
File "c:\Users\Admin\Desktop\Zadanie\test.py", line 168, in transform
self.remove_unreachable()
File "c:\Users\Admin\Desktop\Zadanie\test.py", line 50, in remove_unreachable
for rule in self.productions[variable]:
KeyError: 'S'
PS C:\Users\Admin> & C:/Users/Admin/AppData/Local/Programs/Python/Python39/python.exe c:/Users/Admin/Desktop/Zadanie/test.py
Original grammar:
S -> AB | ε
A -> Aa | S | a
B -> bD | bS | b
D -> ccD
E -> eE | e
Traceback (most recent call last):
File "c:\Users\Admin\Desktop\Zadanie\test.py", line 200, in <module>
grammar.transform()
File "c:\Users\Admin\Desktop\Zadanie\test.py", line 168, in transform
self.remove_unreachable()
File "c:\Users\Admin\Desktop\Zadanie\test.py", line 50, in remove_unreachable
for rule in self.productions[variable]:
KeyError: 'S'
PS C:\Users\Admin>
