请给出SLR1分析表构建的步骤给出补充完整的代码。
SLR1分析表构建的步骤如下:
- 对于每个非终结符A,求出A的FIRST集合和FOLLOW集合。
- 对于每个产生式A → α,将FIRST(α)中的所有终结符加入到A的FOLLOW集合中。
- 对于每个产生式A → α,对于FIRST(α)中的每个终结符a,将A → α加入到ACTION[A, a]中。
- 对于每个产生式A → α,如果ε ∈ FIRST(α),则对于FOLLOW(A)中的每个终结符a,将A → α加入到ACTION[A, a]中。
- 对于每个非终结符A,对于FOLLOW(A)中的每个终结符a,将A → ε加入到ACTION[A, a]中。
- 对于每个状态i,对于每个终结符a,如果GOTO[i, a] = j,则将GOTO[i, a]加入到GOTO表中。
下面是补充完整的SLR1分析表构建代码:
# 计算某个符号的FIRST集合
def first(symbol, productions, first_dict):
if symbol in first_dict:
return first_dict[symbol]
if symbol.is_terminal():
return set([symbol])
result = set()
for production in productions[symbol]:
if production.is_empty():
result.add(epsilon)
else:
first_set = first(production[0], productions, first_dict)
result |= first_set
i = 1
while epsilon in first_set and i < len(production):
first_set = first(production[i], productions, first_dict)
result |= (first_set - set([epsilon]))
i += 1
if i == len(production) and epsilon in first_set:
result.add(epsilon)
first_dict[symbol] = result
return result
# 计算所有符号的FIRST集合
def compute_first_set(start_symbol, productions):
first_dict = {}
for symbol in productions:
first(symbol, productions, first_dict)
return first_dict
# 计算某个非终结符的FOLLOW集合
def follow(symbol, start_symbol, productions, first_dict, follow_dict):
if symbol in follow_dict:
return follow_dict[symbol]
result = set()
if symbol == start_symbol:
result.add(end_of_input)
for non_terminal in productions:
for production in productions[non_terminal]:
if symbol in production:
i = production.index(symbol)
if i == len(production) - 1:
result |= follow(non_terminal, start_symbol, productions, first_dict, follow_dict)
else:
first_set = first(production[i + 1], productions, first_dict)
result |= (first_set - set([epsilon]))
if epsilon in first_set:
result |= follow(non_terminal, start_symbol, productions, first_dict, follow_dict)
follow_dict[symbol] = result
return result
# 计算所有非终结符的FOLLOW集合
def compute_follow_set(start_symbol, productions, first_dict):
follow_dict = {}
for non_terminal in productions:
follow(non_terminal, start_symbol, productions, first_dict, follow_dict)
return follow_dict
# 构建SLR1分析表
def build_slr1_table(start_symbol, productions):
first_dict = compute_first_set(start_symbol, productions)
follow_dict = compute_follow_set(start_symbol, productions, first_dict)
table = {}
for i, state in enumerate(states):
for symbol in start_symbol + terminals:
if symbol in goto_dict[i]:
j = goto_dict[i][symbol]
if symbol in terminals:
table[(i, symbol)] = ('S', j)
else:
table[(i, symbol)] = ('G', j)
for item in state:
production = item.production
if item.dot_index == len(production):
for symbol in follow_dict[production.left]:
table[(i, symbol)] = ('R', production)
elif production[item.dot_index].is_terminal():
symbol = production[item.dot_index]
j = goto_dict[i][symbol]
table[(i, symbol)] = ('S', j)
else:
symbol = production[item.dot_index]
for a in follow_dict[production.left]:
if (i, a) in table:
raise ValueError('Conflict')
table[(i, a)] = ('R', production)
return table
``
原文地址: http://www.cveoy.top/t/topic/hjMD 著作权归作者所有。请勿转载和采集!