构造一个SLR(1)分析器。要求如下: (1)用户任意给定文法,输出识别活前缀的DFA、LR(0)的项目集规范族、所有非终结符的FOLLOW集合; (2)输出SLR(1)分析表; (3)测试文法G[E]如下: S→bASB|bA A→dSa|e B→cAa|c (4)使用python
时间: 2023-11-28 17:48:27 浏览: 185
基于C语言实现SLR(1)类文法判定及其分析器构造【100012260】
5星 · 资源好评率100%
对于这个问题,我们可以采用 Python 语言来实现。下面是该问题的一个完整解决方案。
首先,我们需要定义文法以及一些必要的数据结构来存储文法信息和分析表信息。代码如下:
```python
# 定义文法
grammar = {
'S': [['b', 'A', 'S', 'B'], ['b', 'A']],
'A': [['d', 'S', 'a'], ['e']],
'B': [['c', 'A', 'a'], ['c']]
}
# 定义特殊符号
start_symbol = 'S'
end_symbol = '$'
# 定义项目
class Item:
def __init__(self, production, dot_pos):
self.production = production
self.dot_pos = dot_pos
def __str__(self):
return self.production[0] + ' -> ' + ' '.join(self.production[1][:self.dot_pos]) + ' . ' + ' '.join(self.production[1][self.dot_pos:])
def __eq__(self, other):
return self.production == other.production and self.dot_pos == other.dot_pos
def __hash__(self):
return hash(str(self))
# 定义状态
class State:
def __init__(self, items):
self.items = items
def __str__(self):
return '\n'.join(str(item) for item in self.items)
def __eq__(self, other):
return set(self.items) == set(other.items)
def __hash__(self):
return hash(frozenset(self.items))
# 定义 LR(0) 项目集规范族
def lr0_items(grammar):
start_production = ['S', [start_symbol]]
start_item = Item(start_production, 0)
closure = set([start_item])
changed = True
while changed:
changed = False
for item in closure.copy():
if item.dot_pos < len(item.production[1]) and item.production[1][item.dot_pos] in grammar:
for production in grammar[item.production[1][item.dot_pos]]:
new_item = Item([item.production[1][item.dot_pos], production], 0)
if new_item not in closure:
closure.add(new_item)
changed = True
state_list = [State(closure)]
changed = True
while changed:
changed = False
for state in state_list.copy():
for symbol in symbols(grammar):
goto_state = goto(state, symbol, grammar)
if goto_state and goto_state not in state_list:
state_list.append(goto_state)
changed = True
return state_list
# 定义 FOLLOW 集合
def follows(grammar):
follow = {symbol: set() for symbol in symbols(grammar)}
follow[start_symbol].add(end_symbol)
changed = True
while changed:
changed = False
for lhs, rhs_list in grammar.items():
for rhs in rhs_list:
for i in range(len(rhs)):
if rhs[i] in follow:
rest = rhs[i + 1:]
if not rest:
follow_set = follow[lhs]
else:
follow_set = first(rest, grammar)
if '' in follow_set:
follow_set.remove('')
follow_set |= follow[lhs]
old_len = len(follow[rhs[i]])
follow[rhs[i]] |= follow_set
if len(follow[rhs[i]]) > old_len:
changed = True
return follow
# 定义 LR(1) 分析表
def slr1_table(grammar):
table = {state: {symbol: None for symbol in symbols(grammar)} for state in lr0_items(grammar)}
for i, state in enumerate(lr0_items(grammar)):
for item in state.items:
if item.dot_pos == len(item.production[1]):
if item.production[0] == start_symbol:
table[state][end_symbol] = ('accept', None)
else:
for symbol in follow[item.production[0]]:
if symbol in table[state]:
if table[state][symbol] is not None:
raise ValueError('SLR(1) conflict')
table[state][symbol] = ('reduce', item.production)
else:
symbol = item.production[1][item.dot_pos]
goto_state = goto(state, symbol, grammar)
if goto_state is not None:
if symbol in terminals(grammar):
if table[state][symbol] is not None:
raise ValueError('SLR(1) conflict')
table[state][symbol] = ('shift', goto_state)
else:
if table[state][symbol] is not None:
raise ValueError('SLR(1) conflict')
table[state][symbol] = ('goto', goto_state)
return table
# 定义辅助函数
def symbols(grammar):
return set(grammar.keys()).union(set(t for rhs_list in grammar.values() for rhs in rhs_list for t in rhs if t not in grammar))
def terminals(grammar):
return set(t for rhs_list in grammar.values() for rhs in rhs_list for t in rhs if t not in grammar)
def first(rhs, grammar):
first_set = set()
i = 0
while i < len(rhs) and '' in first_set:
first_set -= {''}
first_set |= first(rhs[i], grammar)
i += 1
if i == len(rhs) and '' in first_set:
first_set.remove('')
first_set |= {''}
return first_set
def goto(state, symbol, grammar):
goto_items = set()
for item in state.items:
if item.dot_pos < len(item.production[1]) and item.production[1][item.dot_pos] == symbol:
goto_items.add(Item(item.production, item.dot_pos + 1))
if goto_items:
return State(closure(goto_items, grammar))
else:
return None
def closure(items, grammar):
closure = set(items)
changed = True
while changed:
changed = False
for item in closure.copy():
if item.dot_pos < len(item.production[1]) and item.production[1][item.dot_pos] in grammar:
for production in grammar[item.production[1][item.dot_pos]]:
new_item = Item([item.production[1][item.dot_pos], production], 0)
if new_item not in closure:
closure.add(new_item)
changed = True
return closure
```
接下来,我们可以分别调用上述函数来得到 DFA、LR(0) 项目集规范族、FOLLOW 集合和 SLR(1) 分析表。代码如下:
```python
# 输出 DFA
print('DFA:')
for i, state in enumerate(lr0_items(grammar)):
print(f's{i}:')
for item in state.items:
if item.dot_pos == len(item.production[1]):
print(f'\t{item.production[0]} -> {" ".join(item.production[1])} \u2022')
else:
print(f'\t{item.production[0]} -> {" ".join(item.production[1][:item.dot_pos])} \u2022 {" ".join(item.production[1][item.dot_pos:])}')
if item.production[0] == start_symbol and item.dot_pos == len(item.production[1]):
print('\t' + end_symbol)
print()
# 输出 LR(0) 项目集规范族
print('LR(0) 项目集规范族:')
for i, state in enumerate(lr0_items(grammar)):
print(f'I{i}:')
print(state)
print()
# 输出 FOLLOW 集合
print('FOLLOW 集合:')
for symbol, follow_set in follows(grammar).items():
print(f'{symbol}: {" ".join(follow_set)}')
print()
# 输出 SLR(1) 分析表
print('SLR(1) 分析表:')
table = slr1_table(grammar)
print(' ' * 5, end='')
for symbol in terminals(grammar):
print(f'{symbol:<5}', end='')
print(f'{end_symbol:<5}')
for i, state in enumerate(lr0_items(grammar)):
print(f's{i:<3}', end='')
for symbol in terminals(grammar) | {end_symbol}:
if table[state][symbol] is None:
print(' ' * 5, end='')
else:
action, data = table[state][symbol]
if action == 'shift':
print(f's{list(lr0_items(grammar)).index(data):<3}', end='')
elif action == 'reduce':
print(f'r{list(grammar.keys()).index(data[0])}', end='')
elif action == 'goto':
print(f's{list(lr0_items(grammar)).index(data):<3}', end='')
elif action == 'accept':
print('acc ', end='')
print(' ' * 2, end='')
print()
```
最后,我们可以对文法进行测试,看看 SLR(1) 分析表是否正确。代码如下:
```python
# 测试文法
string = 'bdadbaa$'
stack = [0]
input_string = list(string)
input_string.reverse()
while True:
state = stack[-1]
symbol = input_string[-1]
action, data = table[state][symbol]
if action == 'shift':
stack.append(data)
input_string.pop()
elif action == 'reduce':
lhs, rhs = data
for i in range(len(rhs)):
stack.pop()
state = stack[-1]
stack.append(table[state][lhs][1])
elif action == 'goto':
stack.append(data)
elif action == 'accept':
print('Accepted')
break
else:
print('Rejected')
break
```
完整代码如下:
阅读全文