参照算术表达式LR分析表的设计方法,设计扩充后的算术表达式LR分析表,并对原语义加工程序修改,加入新添的内容,算术表达式文法扩充如下: E→E+E| E-E|E*E |E/E| (E) | I 试根据该文法重新设计LR分析表,并修改语义加工程序,最后验证修改的结果
时间: 2023-06-23 15:08:47 浏览: 307
byq.rar_算术表达式LR
为了设计扩充后的算术表达式LR分析表,我们需要进行以下步骤:
1. 对文法进行拓广,添加一个新的起始符号S'和一个新的产生式S'->E。
2. 构造LR(0)项集族,包括每个项集的项目以及它们的闭包项集。
3. 对于每个项集,根据输入符号的不同,进行状态转移。
4. 构造LR分析表,根据状态转移和规约动作进行填充。
下面是扩充后的算术表达式文法:
```
S' -> E
E -> E + E
| E - E
| E * E
| E / E
| (E)
| I
```
第一步,拓广文法,添加新的起始符号和产生式:
```
S' -> E
E -> E + E
| E - E
| E * E
| E / E
| (E)
| I
```
第二步,构造LR(0)项集族:
```
I0:
S' -> .E
E -> .E + E
E -> .E - E
E -> .E * E
E -> .E / E
E -> .(E)
E -> .I
I1:
S' -> E.
I2:
E -> E. + E
E -> E. - E
E -> E. * E
E -> E. / E
I3:
E -> ( .E )
E -> (.E + E)
E -> (.E - E)
E -> (.E * E)
E -> (.E / E)
E -> (.I)
I4:
E -> ( E. )
E -> (E. + E)
E -> (E. - E)
E -> (E. * E)
E -> (E. / E)
I5:
E -> E + .E
E -> E - .E
E -> E * .E
E -> E / .E
I6:
E -> E + E.
E -> E - E.
E -> E * E.
E -> E / E.
I7:
E -> (E).
I8:
E -> I.
```
第三步,进行状态转移:
```
I0:
S' -> .E
E -> .E + E
E -> .E - E
E -> .E * E
E -> .E / E
E -> .(E)
E -> .I
------------------
E -> E. -> I2
( -> .E -> I3
I -> . -> I8
I1:
S' -> E.
------------------
$ -> ACC
I2:
E -> E. + E
E -> E. - E
E -> E. * E
E -> E. / E
------------------
+ -> .E -> I5
- -> .E -> I5
* -> .E -> I5
/ -> .E -> I5
) -> .E -> I5
$ -> . -> I6
I3:
E -> ( .E )
E -> (.E + E)
E -> (.E - E)
E -> (.E * E)
E -> (.E / E)
E -> (.I)
------------------
( -> .E -> I3
E -> .E + E -> I2
E -> .E - E -> I2
E -> .E * E -> I2
E -> .E / E -> I2
I -> . -> I8
I4:
E -> ( E. )
E -> (E. + E)
E -> (E. - E)
E -> (E. * E)
E -> (E. / E)
------------------
+ -> .E -> I5
- -> .E -> I5
* -> .E -> I5
/ -> .E -> I5
) -> .E -> I7
I5:
E -> E + .E
E -> E - .E
E -> E * .E
E -> E / .E
------------------
( -> .E -> I3
I -> . -> I8
I6:
E -> E -> . -> I1
I7:
E -> (E).
------------------
+ -> .E -> I5
- -> .E -> I5
* -> .E -> I5
/ -> .E -> I5
) -> .E -> I7
I8:
E -> I.
------------------
+ -> .E -> I5
- -> .E -> I5
* -> .E -> I5
/ -> .E -> I5
) -> .E -> I7
```
第四步,构造LR分析表:
```
+ - * / ( ) I $
----------------------------------
0 | S2 S2 S2 S2 S3 - S4 -
1 | - - - - - - - ACC
2 | S5 S5 S5 S5 S3 - - -
3 | S5 S5 S5 S5 S3 - - -
4 | - - - - S6 - - -
5 | S5 S5 S5 S5 S3 - - -
6 | - - - - S7 - - -
7 | S5 S5 S5 S5 S3 - - -
8 | S5 S5 S5 S5 S3 - - -
```
其中S表示Shift,R表示Reduce,-表示Error,ACC表示接受状态。
最后,我们需要修改语义加工程序,将新添加的内容加入其中。
假设原有的语义加工程序为:
```
def reduce_add():
right = stack.pop()
left = stack.pop()
stack.append(left + right)
def reduce_sub():
right = stack.pop()
left = stack.pop()
stack.append(left - right)
def reduce_mul():
right = stack.pop()
left = stack.pop()
stack.append(left * right)
def reduce_div():
right = stack.pop()
left = stack.pop()
if right == 0:
raise ZeroDivisionError
stack.append(left / right)
def reduce_paren():
stack.pop()
expr = stack.pop()
stack.pop()
stack.append(expr)
def reduce_id(token):
stack.append(token.value)
```
我们需要添加新的reduce函数来处理新的产生式:
```
def reduce_power():
right = stack.pop()
left = stack.pop()
stack.append(left ** right)
def reduce_unary_minus():
expr = stack.pop()
stack.append(-expr)
```
然后,在规约时调用新添加的reduce函数:
```
def reduce_power():
right = stack.pop()
left = stack.pop()
stack.append(left ** right)
def reduce_unary_minus():
expr = stack.pop()
stack.append(-expr)
def reduce_add():
right = stack.pop()
left = stack.pop()
stack.append(left + right)
def reduce_sub():
right = stack.pop()
left = stack.pop()
stack.append(left - right)
def reduce_mul():
right = stack.pop()
left = stack.pop()
stack.append(left * right)
def reduce_div():
right = stack.pop()
left = stack.pop()
if right == 0:
raise ZeroDivisionError
stack.append(left / right)
def reduce_paren():
stack.pop()
expr = stack.pop()
stack.pop()
stack.append(expr)
def reduce_id(token):
stack.append(token.value)
def reduce_power():
right = stack.pop()
left = stack.pop()
stack.append(left ** right)
def reduce_unary_minus():
expr = stack.pop()
stack.append(-expr)
def execute(action, token=None):
if action == 'SHIFT':
stack.append(token.value)
state_stack.append(int(token.attr))
elif action == 'REDUCE':
reduce_func = reduce_functions[int(token.attr)]
reduce_func(token)
state = state_stack[-1]
symbol = productions[int(token.attr)].left
state = goto_table[state][symbol]
state_stack.append(state)
elif action == 'ACCEPT':
pass
elif action == 'ERROR':
raise SyntaxError
```
阅读全文