从键盘读入要分析的文法,并判断正误;若无误,由程序自动构造FIRST、FOLLOW 集以及SELECT集合,判断是否为LL (1)文法;
时间: 2024-05-14 13:19:05 浏览: 27
以下是一个简单的 Python 代码实现,可以读入一个文法并进行分析:
```python
# 读入文法
grammar = {}
while True:
line = input().strip()
if not line:
break
left, right = line.split(' -> ')
right = right.split('|')
grammar[left] = [r.split() for r in right]
# 计算 FIRST 集
first = {}
for symbol in grammar:
first[symbol] = set()
for symbol in grammar:
for production in grammar[symbol]:
if production[0] not in grammar:
first[symbol].add(production[0])
else:
for i in range(len(production)):
if production[i] not in grammar:
first[symbol].add(production[i])
break
else:
first[symbol].update(first[production[i]])
if 'ε' not in first[production[i]]:
break
# 计算 FOLLOW 集
follow = {}
for symbol in grammar:
follow[symbol] = set()
follow[grammar['S'][0][0]].add('$')
for symbol in grammar:
for production in grammar[symbol]:
for i in range(len(production)):
if production[i] in grammar:
if i == len(production) - 1:
follow[production[i]].update(follow[symbol])
else:
if production[i+1] not in grammar:
follow[production[i]].add(production[i+1])
else:
follow[production[i]].update(first[production[i+1]])
if 'ε' in first[production[i+1]]:
follow[production[i]].update(follow[symbol])
# 计算 SELECT 集
select = {}
for symbol in grammar:
select[symbol] = []
for production in grammar[symbol]:
if 'ε' in production:
select[symbol].extend(follow[symbol])
select[symbol].remove('ε')
else:
select[symbol].extend(first[production[0]])
for i in range(1, len(production)):
if 'ε' in first[production[i-1]]:
select[symbol].extend(first[production[i]])
else:
break
# 判断是否为 LL(1) 文法
is_ll1 = True
for symbol in grammar:
for i in range(len(grammar[symbol])):
for j in range(i+1, len(grammar[symbol])):
if len(set(select[symbol][i]) & set(select[symbol][j])) > 0:
is_ll1 = False
print('Is LL(1) grammar:', is_ll1)
```
代码首先读入文法,然后计算 FIRST 集、FOLLOW 集和 SELECT 集。最后,判断是否为 LL(1) 文法,即对于每个非终结符的每个产生式,它们的 SELECT 集是否没有交集。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)