给定下列 LL(1)文法,编写递归下降程序,分析表达式 i+i*2 的合法性,并 能显示出分析过程。 E→TE1 E1→+TE1|-TE1|ε T→FT1 T1→*FT1|/FT1|ε F→(E)|i
时间: 2024-01-05 15:10:48 浏览: 77
LL(1)文法的递归下降分析程序例题
5星 · 资源好评率100%
以下是该 LL(1)文法的递归下降程序(使用 Python 语言实现):
```python
def E():
T()
E1()
def E1():
if lookahead == '+':
match('+')
T()
E1()
elif lookahead == '-':
match('-')
T()
E1()
else:
pass
def T():
F()
T1()
def T1():
if lookahead == '*':
match('*')
F()
T1()
elif lookahead == '/':
match('/')
F()
T1()
else:
pass
def F():
if lookahead == '(':
match('(')
E()
match(')')
elif lookahead == 'i':
match('i')
else:
raise SyntaxError("Invalid token")
def match(token):
global lookahead
if lookahead == token:
lookahead = next_token()
else:
raise SyntaxError("Unexpected token")
def next_token():
global position
if position < len(expression):
token = expression[position]
position += 1
return token
else:
return None
```
假设输入的表达式为 "i+i*2",初始时 `lookahead` 为 "i",`position` 为 0。程序开始执行 `E()`,调用 `T()`,`lookahead` 不是 "*" 或 "/",所以调用 `F()`。`lookahead` 是 "i",匹配成功,调用 `match('i')`,此时 `lookahead` 变为 "+",再调用 `T1()`。`lookahead` 是 "*",匹配成功,调用 `match('*')`,`lookahead` 变为 "2",再调用 `F()`。`lookahead` 是 "2",匹配成功,调用 `match('2')`,`lookahead` 变为 None。此时整个表达式已经被成功分析,程序结束。
分析过程如下:
```
E()
T()
F()
i
T1()
E1()
+
T()
F()
i
T1()
*
F()
2
T1()
```
因此,该表达式是合法的。
阅读全文