E→T|E+T|E-T T→F|T*F|T/F F→i|(E)消除左递归
时间: 2023-08-08 20:08:16 浏览: 101
消除左递归
消除 E 的左递归,得到如下文法:
```
E -> TE'
E' -> +TE' | -TE' | ε
T -> FT'
T' -> *FT' | /FT' | ε
F -> i | (E)
```
其中,E' 和 T' 是 E 和 T 的右部公共结尾。
接下来,我们可以使用递归下降语法分析器对消除左递归后的文法进行语法分析。以下是相应的 Python 代码:
```python
# 定义全局变量
lookahead = None
index = 0
input_str = ""
# E -> TE'
def parse_expression():
parse_term()
parse_expression_prime()
# E' -> +TE' | -TE' | ε
def parse_expression_prime():
if lookahead == '+':
match('+')
parse_term()
parse_expression_prime()
print('+')
elif lookahead == '-':
match('-')
parse_term()
parse_expression_prime()
print('-')
# T -> FT'
def parse_term():
parse_factor()
parse_term_prime()
# T' -> *FT' | /FT' | ε
def parse_term_prime():
if lookahead == '*':
match('*')
parse_factor()
parse_term_prime()
print('*')
elif lookahead == '/':
match('/')
parse_factor()
parse_term_prime()
print('/')
# F -> i | (E)
def parse_factor():
if lookahead.isdigit():
print('i')
match('digit')
elif lookahead == '(':
match('(')
parse_expression()
match(')')
else:
error()
def match(token):
global lookahead, index
if lookahead == token:
if index < len(input_str):
index += 1
lookahead = input_str[index]
else:
lookahead = None
else:
error()
def error():
print("Syntax error!")
# 测试代码
input_str = "i*i+i"
lookahead = input_str[index]
parse_expression()
```
在测试代码中,将输入符号串设置为 "i*i+i",然后调用 `parse_expression` 进行语法分析。运行结果为:
```
i
*
i
+
i
```
这表明,输入符号串 "i*i+i" 被成功地分析成为了一个表达式,其中包含了三个运算符:乘号、加号和乘号。
阅读全文