编写:1. 输入:文法四元组 2. 输出:输出:判定给定文法是否为LL(1)文法
时间: 2024-02-10 16:15:45 浏览: 33
以下是输入文法四元组,判断是否为LL(1)文法的代码实现:
```python
# 输入文法四元组
grammer = {
'S': ['aA', 'bB'],
'A': ['cA', 'd'],
'B': ['eB', 'f']
}
terminals = ['a', 'b', 'c', 'd', 'e', 'f']
non_terminals = ['S', 'A', 'B']
# 构建FIRST集合
first = {}
for symbol in terminals + non_terminals:
first[symbol] = set()
for terminal in terminals:
first[terminal].add(terminal)
for non_terminal in non_terminals:
first[non_terminal] = set()
for non_terminal in non_terminals:
for production in grammer[non_terminal]:
if production[0] in terminals:
first[non_terminal].add(production[0])
else:
first[non_terminal] |= first[production[0]]
# 构建FOLLOW集合
follow = {}
for non_terminal in non_terminals:
follow[non_terminal] = set()
follow['S'].add('$')
while True:
updated = False
for non_terminal in non_terminals:
for production in grammer[non_terminal]:
for i in range(len(production)):
if production[i] in non_terminals:
if i == len(production) - 1:
if follow[non_terminal] != follow[production[i]]:
follow[production[i]] |= follow[non_terminal]
updated = True
else:
first_set = first[production[i+1]].copy()
if '' in first_set:
first_set.remove('')
if follow[non_terminal] != follow[production[i]] | first_set:
follow[production[i]] |= follow[non_terminal] | first_set
updated = True
else:
if follow[non_terminal] != first_set:
follow[production[i]] |= first_set
updated = True
if not updated:
break
# 构建LL(1)预测分析表
table = {}
for non_terminal in non_terminals:
table[non_terminal] = {}
for terminal in terminals:
table[non_terminal][terminal] = []
for non_terminal in non_terminals:
for production in grammer[non_terminal]:
first_set = set()
for i in range(len(production)):
if production[i] in terminals:
first_set = {production[i]}
break
else:
first_set |= first[production[i]]
if '' not in first[production[i]]:
break
for terminal in first_set:
table[non_terminal][terminal].append(production)
if '' in first_set:
for terminal in follow[non_terminal]:
table[non_terminal][terminal].append(production)
# 判断文法是否为LL(1)文法
is_ll1_grammer = True
for non_terminal in non_terminals:
for terminal in terminals:
if len(table[non_terminal][terminal]) > 1:
is_ll1_grammer = False
print(f"({non_terminal}, {terminal}): {table[non_terminal][terminal]}")
print("该文法是LL(1)文法" if is_ll1_grammer else "该文法不是LL(1)文法")
```
上述代码构建了文法的FIRST集合、FOLLOW集合和LL(1)预测分析表,并通过预测分析表判断该文法是否为LL(1)文法。