算术文法E->E+T|T T->T*F|F F->(E)|i 的LL1分析表

| 文法符号 | + | * | ( | ) | i | $ |
| :--------: | :--: | :---: | :---: | :---: | :---: | :---: |
| E | E+T | | E+T | | E+T | |
| T | | T*F | | | T*F | |
| F | | | (E) | | i | |

注意：表格中空白处表示“错误”或者“空串”

其中，第一行表示文法符号，第一列表示输入符号（包括终结符和非终结符），表格中每个元素表示对应的产生式。

例如，表格中第一个元素E+T表示当当前处理的文法符号为E，输入符号为+时，应该采用E -> E+T这个产生式进行推导。

需要注意的是，这个文法不是LL1文法，因为存在左递归。需要对其进行改写，才能得到LL1分析表。

相关问题

针对SysY语言中简单算术表达式文法G[E]: E→TE’ ; E’→ATE’|ε ; T→FT’ ; T’→MFT’ |ε ; F→(E) | i ; A → + | - ; M → * | / 求解相应的FIRST、FOLLOW集，构造预测分析表，并编写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代码实现：

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或抛出异常。

将正则表达式(a|b)*(aa|bb)(a|b)* 改写成ll1文法 并给出 first集 follow集和select集还有预测分析表

这是一个正则表达式，可以转化为以下的 LL(1) 文法：

S -> AB
A -> aA | bA | ε
B -> aaC | bbC
C -> aD | bE
D -> aC | bC | ε
E -> aC | bC | ε

其中 `S` 是起始符号，`A`、`B`、`C`、`D`、`E` 是非终结符号，`a`、`b` 是终结符号，`ε` 表示空串。

该文法的 FIRST 集合和 FOLLOW 集合如下：

FIRST(S) = {a, b}
FIRST(A) = {a, b, ε}
FIRST(B) = {aa, bb}
FIRST(C) = {a, b}
FIRST(D) = {a, b, ε}
FIRST(E) = {a, b, ε}

FOLLOW(S) = {$}
FOLLOW(A) = {aa, bb}
FOLLOW(B) = {a, b}
FOLLOW(C) = {a, b, aa, bb}
FOLLOW(D) = {a, b, aa, bb}
FOLLOW(E) = {a, b, aa, bb}

该文法的 SELECT 集合如下：

SELECT(S -> AB) = {a, b}
SELECT(A -> aA) = {a}
SELECT(A -> bA) = {b}
SELECT(A -> ε) = {aa, bb}
SELECT(B -> aaC) = {aa}
SELECT(B -> bbC) = {bb}
SELECT(C -> aD) = {a}
SELECT(C -> bE) = {b}
SELECT(D -> aC) = {a}
SELECT(D -> bC) = {b}
SELECT(D -> ε) = {aa, bb}
SELECT(E -> aC) = {a}
SELECT(E -> bC) = {b}
SELECT(E -> ε) = {aa, bb}

该文法的预测分析表如下：

| 非终结符 | a | b | aa | bb | $ |
| :------: | :---: | :---: | :---: | :---: | :--: |
| S | A | B | | | √ |
| A | a | b | ε | ε | |
| B | aaC | bbC | | | |
| C | aD | bE | | | |
| D | aC | bC | ε | ε | |
| E | aC | bC | ε | ε | |

其中 `√` 表示对应的产生式可以推导出对应的终结符，空表示无法推导。