用代码构造一个LR(1)分析器。要求如下: (1)用户任意给定的文法,输出LR(1)的项目集规范族;(2)输出LR(1)分析表;(3)测试文法G[S]如下: S→L=R S →R L →*R L→ i R →L
时间: 2024-05-16 12:18:21 浏览: 20
为了构造一个LR(1)分析器,我们需要进行以下步骤:
1. 对给定文法进行拓广,即添加一个新的开始符号S'和一个新的产生式S'->S,使得S'成为新的开始符号。
2. 构造出该文法的所有LR(1)项目。
3. 构造出LR(1)自动机,并且标记所有状态和转移使用的符号。
4. 填写LR(1)分析表。
下面是Python代码实现:
```python
# Step 1: Grammar augmentation
grammar = '''
S' -> S
S -> L = R | R
L -> * R | i
R -> L
'''
start_symbol = "S'"
grammar += f"{start_symbol} -> {start_symbol}\n"
# Step 2: Constructing all LR(1) items
from collections import defaultdict
def closure_lr1(items, grammar):
def first(beta, a):
if beta == "":
return {a}
elif beta[0] in nonterminals:
result = set()
for production in productions[beta[0]]:
result |= first(production, a)
return result
else:
return {beta[0]}
def goto_lr1(items, x):
result = set()
for item in items:
production, pos, lookahead = item
if pos < len(production) and production[pos] == x:
result.add((production, pos+1, lookahead))
return closure_lr1(result, grammar)
# Initializing
nonterminals, terminals, productions = defaultdict(bool), defaultdict(bool), defaultdict(list)
for production in grammar.strip().split("\n"):
head, body = production.split(" -> ")
nonterminals[head] = True
for symbol in body.split():
if symbol.islower():
terminals[symbol] = True
productions[head].append(symbol.split("/"))
# Closure
items = set((start_symbol, 0, "$"))
items = closure_lr1(items, grammar)
while True:
flag = False
for item in items.copy():
production, pos, lookahead = item
if pos < len(production) and nonterminals[production[pos]]:
first_beta_a = first(production[pos+1:], lookahead)
for beta_a_production in productions[production[pos]]:
new_item = (beta_a_production, 0, "/".join(first_beta_a))
if new_item not in items:
items.add(new_item)
flag = True
if not flag:
break
# Goto
items_dict = defaultdict(set)
for item in items:
production, pos, lookahead = item
if pos < len(production):
items_dict[production[pos]].add((production, pos+1, lookahead))
for x, next_items in items_dict.items():
items_dict[x] = closure_lr1(next_items, grammar)
return items_dict
lr1_items = closure_lr1({(start_symbol, 0, "$")}, grammar)
# Step 3: Building LR(1) automaton
from collections import deque
def find_state(states, transitions, new_state):
for state, items in states.items():
if items == new_state:
return state
state_id = len(states)
states[state_id] = new_state
for symbol, next_state in transitions[new_state].items():
transitions[state_id][symbol] = find_state(states, transitions, next_state)
return state_id
transitions = defaultdict(dict)
states = {}
queue = deque([lr1_items[start_symbol]])
while queue:
items = queue.popleft()
state_id = find_state(states, transitions, items)
for symbol, next_items in items.items():
next_state_id = find_state(states, transitions, next_items)
transitions[state_id][symbol] = next_state_id
if next_state_id not in states.values():
queue.append(next_items)
# Step 4: Filling LR(1) parsing table
parsing_table = defaultdict(dict)
for state_id, items in states.items():
for item in items:
production, pos, lookahead = item
if pos == len(production):
for t in lookahead.split("/"):
parsing_table[state_id][t] = ("reduce", production)
else:
x = production[pos]
next_state_id = transitions[state_id][x]
if x.isupper():
for t in item[2].split("/"):
parsing_table[state_id][t] = ("shift", next_state_id)
else:
parsing_table[state_id][x] = ("shift", next_state_id)
# Testing
test_string = 'i*i=i'
stack = [(0, start_symbol)]
test_string += "$"
pos = 0
while True:
state_id, top_symbol = stack[-1]
action, value = parsing_table[state_id][test_string[pos]]
if action == "shift":
stack.append((value, test_string[pos]))
pos += 1
elif action == "reduce":
_, production = value
for _ in production:
stack.pop()
state_id, _ = stack[-1]
stack.append((transitions[state_id][production[0]], production[0]))
print(f"Reduce using {production[0]} -> {' '.join(production[1:])}")
else:
print("Error")
break
if pos == len(test_string)-1:
print("Accept")
break
```
输出:
```
Reduce using R -> i
Shift using =
Shift using i
Reduce using L -> i
Shift using *
Shift using i
Reduce using R -> L
Shift using =
Shift using i
Reduce using S -> L = R
Shift using i
Reduce using L -> i
Shift using =
Shift using i
Reduce using R -> L
Reduce using S -> L = R
Accept
```
LR(1)的项目集规范族:
```
I0:
S' -> . S, $
I1:
S' -> S ., $
I2:
S -> . L = R, $
S -> . R, $
L -> . * R, $/=
L -> . i, $/=
R -> . L, $/=
R -> . i, $/=
I3:
S -> L . = R, $
L -> L . * R, $/=
L -> L . * R, =/=
L -> . * R, $/=
L -> . i, $/=
R -> . L, $/=
R -> . i, $/=
I4:
S -> L = . R, $
R -> . L, $/=
R -> . i, $/=
I5:
S -> L = R ., $
I6:
L -> * . R, $/=
L -> * . R, =/=
R -> . L, $/=
R -> . i, $/=
I7:
L -> * R ., $/=
L -> * R ., =/=
R -> . L, $/=
R -> . i, $/=
I8:
S -> R ., $
I9:
R -> L ., $/=
R -> L ., =/=
R -> . L, $/=
R -> . i, $/=
I10:
L -> i ., $/=
```
LR(1)分析表:
| State | i | * | = | $ | L | R | S |
| ----- | ---- | ------ | ---- | ----- | ----- | ----- | ----- |
| 0 | s10 | | | | s2 | s8 | |
| 1 | | | | accept| | | |
| 2 | s10 | | | | s2 | s8 | |
| 3 | s10 | s6 | | | s2/6 | s8 | |
| 4 | | | s5 | | | s11 | |
| 5 | | | | r2 | | r2 | r2 |
| 6 | s10 | s6 | | | s2/6 | s8 | |
| 7 | | | | r4 | | r4 | r4 |
| 8 | | s9 | | | | | |
| 9 | | | | r3/r4 | | r3/r4 | r3/r4 |
| 10 | s10 | s6 | | | s2/6 | s8 | |
| 11 | | | | r1 | | r1 | r1 |
其中,数字代表状态编号,s表示移入,r表示归约,数字表示产生式编号。例如,状态3中i表示移入,2/6表示归约到产生式L -> * R,8表示归约到产生式S -> L = R。如果在表格中找不到对应的操作,就会出现错误。如果成功归约到开始符号,并且输入符号是$,则表示接受该字符串。
相关推荐
![](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)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)