针对SysY语言中简单算术表达式文法G[E]: E→TE’ ; E’→ATE’|ε ; T→FT’ ; T’→MFT’ |ε ; F→(E) | i ; A → + | - ; M → * | / 求解相应的FIRST、FOLLOW集,构造预测分析表,并编写LL(1)语法分析程序
时间: 2024-03-08 21:49:45 浏览: 110
LL(1)型文法的判断、求first集、FOLLOW集、select集、LL(1)文法判别、构造预测分析表、非LL(1)文法转换
首先,我们来求解该文法的FIRST集和FOLLOW集。
FIRST集:
- FIRST(E) = {i, (}
- FIRST(E') = {+, -, ε}
- FIRST(T) = {i, (}
- FIRST(T') = {*, /, ε}
- FIRST(F) = {i, (}
- FIRST(A) = {+, -}
- FIRST(M) = {*, /}
FOLLOW集:
- FOLLOW(E) = {$, )}
- FOLLOW(E') = {$, )}
- FOLLOW(T) = {+, -, $, )}
- FOLLOW(T') = {+, -, $, )}
- FOLLOW(F) = {*, /, +, -, $, )}
- FOLLOW(A) = {i, (}
- FOLLOW(M) = {i, (}
然后,我们可以构造预测分析表。
| | i | ( | ) | + | - | * | / | $ |
|---|-----|-----|-----|-----|-----|-----|-----|-----|
| E | TE' | TE' | | | | | | |
| E'| | | ε | ATE'| ATE'| | | ε |
| T | FT' | FT' | | | | | | |
| T'| | | ε | ε | ε | MFT'| MFT'| ε |
| F | i | (E) | | | | | | |
最后,我们可以编写LL(1)语法分析程序。以下是Python代码实现:
```python
class LL1Parser:
def __init__(self, grammar):
self.grammar = grammar
self.table = self.construct_table()
def construct_table(self):
table = {}
for i, production in enumerate(self.grammar.productions):
X = production.left
alpha = production.right
first_alpha = self.grammar.first(alpha)
follow_X = self.grammar.follow(X)
for terminal in first_alpha:
if terminal != "epsilon":
table[X, terminal] = i
if "epsilon" in first_alpha:
for terminal in follow_X:
table[X, terminal] = i
if "epsilon" in first_alpha and "$" in follow_X:
table[X, "$"] = i
return table
def parse(self, input_tokens):
stack = ["$", self.grammar.start]
input_tokens.append("$")
input_pos = 0
while stack:
top = stack.pop()
if isinstance(top, Symbol):
if top == input_tokens[input_pos]:
input_pos += 1
else:
raise Exception("Error: unexpected token '{}'".format(input_tokens[input_pos]))
elif (top, input_tokens[input_pos]) in self.table:
production = self.grammar.productions[self.table[top, input_tokens[input_pos]]]
for symbol in reversed(production.right):
stack.append(symbol)
else:
raise Exception("Error: unexpected token '{}'".format(input_tokens[input_pos]))
return True
```
该程序接受一个文法对象作为输入,并且在初始化时构造预测分析表。它还实现了一个parse方法,该方法接受一个输入符号串,并返回True或抛出异常。
阅读全文