E→T|E+T|E-T T→F|T*F|T/F F→i|(E) 消去上面文法的左递归 , 按消去左递归的文法,写出对应的递归下降语法分析器。
时间: 2023-09-22 14:08:29 浏览: 96
消除左递归后的文法如下:
E → TE'
E' → +TE' | -TE' | ε
T → FT'
T' → *FT' | /FT' | ε
F → i | (E)
对应的递归下降语法分析器如下:
```python
def parse_E():
parse_T()
parse_E_prime()
def parse_E_prime():
if lookahead == "+":
match("+")
parse_T()
parse_E_prime()
elif lookahead == "-":
match("-")
parse_T()
parse_E_prime()
else:
# E' → ε
pass
def parse_T():
parse_F()
parse_T_prime()
def parse_T_prime():
if lookahead == "*":
match("*")
parse_F()
parse_T_prime()
elif lookahead == "/":
match("/")
parse_F()
parse_T_prime()
else:
# T' → ε
pass
def parse_F():
if lookahead == "i":
match("i")
elif lookahead == "(":
match("(")
parse_E()
match(")")
else:
raise SyntaxError("Invalid input")
def match(token):
global lookahead
if lookahead == token:
lookahead = next_token()
else:
raise SyntaxError("Invalid input")
def next_token():
global token_index
if token_index < len(tokens):
token_index += 1
return tokens[token_index - 1]
else:
return None
# 初始化
tokens = ["i", "+", "i", "*", "(", "i", "/", "i", ")", "$"]
lookahead = tokens[0]
token_index = 0
# 开始解析
parse_E()
if lookahead == "$":
print("Parsing succeeded")
else:
print("Parsing failed")
```
其中,`tokens` 是输入的 token 序列,`lookahead` 表示当前读入的 token,`token_index` 表示当前读到了第几个 token。`parse_E`、`parse_E_prime`、`parse_T`、`parse_T_prime` 和 `parse_F` 分别对应文法中的非终结符号,`match` 用于匹配当前读入的 token,`next_token` 返回下一个 token。最后判断是否解析成功,如果成功则输出 `Parsing succeeded`,否则输出 `Parsing failed`。
阅读全文