求firstvt和lastvt集合的算法思路

求一个文法的 FirstVT 和 LastVT 集合，可以采用如下算法思路：

1. 对每个非终结符号，初始化其 FirstVT 集合为空集，初始化其 LastVT 集合为空集。

2. 对于每个产生式 A → α，将 First(α) 中所有非空终结符号加入 A 的 FirstVT 集合。若 α 可以推导出 ε，则将 A 的 FollowVT 集合加入 A 的 FirstVT 集合。

3. 对于每个产生式 A → α，将 Last(α) 中所有非空终结符号加入 A 的 LastVT 集合。若 α 可以推导出 ε，则将 A 的 FollowVT 集合加入 A 的 LastVT 集合。

4. 重复执行步骤 2 和 3，直到没有新的终结符号可以加入 FirstVT 或 LastVT 集合为止。

5. 对于每个产生式 A → α，若存在一个非终结符号 B，使得 α 可以写作 γB，则将 B 的 FirstVT 集合加入 A 的 FollowVT 集合。

6. 对于每个产生式 A → α，若存在一个非终结符号 B，使得 α 可以写作 Bγ，则将 B 的 LastVT 集合加入 A 的 FollowVT 集合。

7. 重复执行步骤 5 和 6，直到没有新的非终结符号可以加入 FollowVT 集合为止。

8. 对于每个非终结符号 A，其 FirstVT 和 LastVT 集合即为步骤 2 和 3 最终计算得到的结果。

以上就是求 FirstVT 和 LastVT 集合的算法思路。

相关问题

用python写一个实验。要求如下 根据给定文法，先求出 FirstVt 和 LastVt 集合，构造算符优先关系表（要求算符优先 关系表 输出到显示器或者输出到文件）； （2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求 输出归约过程）

好的，以下是一个 Python 实现，包括求解 FirstVt 和 LastVt 集合、构造算符优先关系表、以及根据算法和优先关系表分析表达式是否正确的功能。

# 定义文法 G(E')：E' → #E#，E → E+T | T，T → T*F | F，F → (E) | i
grammar = {
    "E'": ["#", "E", "#"],
    "E": ["E", "+", "T"],
    "T": ["T", "*", "F"],
    "F": ["(", "E", ")", "i"]
}

# 求解 FirstVt 和 LastVt 集合
first_vt = {}
last_vt = {}
for non_terminal in grammar:
    first_vt[non_terminal] = set()
    last_vt[non_terminal] = set()

for non_terminal in grammar:
    for production in grammar[non_terminal]:
        # 计算 FirstVt
        if production[0].islower() or production[0] == "(":
            first_vt[non_terminal].add(production[0])
        elif production[0] in grammar:
            first_vt[non_terminal] = first_vt[non_terminal].union(first_vt[production[0]])

        # 计算 LastVt
        if production[-1].islower() or production[-1] == ")":
            last_vt[non_terminal].add(production[-1])
        elif production[-1] in grammar:
            last_vt[non_terminal] = last_vt[non_terminal].union(last_vt[production[-1]])

# 打印 FirstVt 和 LastVt 集合
print("FirstVt:")
for non_terminal in first_vt:
    print(non_terminal + ":", first_vt[non_terminal])
print("\nLastVt:")
for non_terminal in last_vt:
    print(non_terminal + ":", last_vt[non_terminal])

# 构造算符优先关系表
precedence_table = {}
precedence_table["#"] = {}
for terminal in first_vt["E'"]:
    precedence_table["#"][terminal] = "<"
for non_terminal in grammar:
    precedence_table[non_terminal] = {}
    for terminal in first_vt[non_terminal]:
        precedence_table[non_terminal][terminal] = "<"
    for terminal in last_vt[non_terminal]:
        precedence_table[non_terminal][terminal] = ">"
    if "#" in last_vt[non_terminal]:
        precedence_table[non_terminal]["#"] = "="

# 打印算符优先关系表
print("\n算符优先关系表：")
for symbol in precedence_table:
    print("|", end="")
    for terminal in ["#", "+", "*", "(", ")", "i"]:
        print(" " + precedence_table[symbol].get(terminal, " "), end=" |")
    print()

# 分析表达式的函数
def analyze_expression(expression):
    # 在表达式首尾加上 "#"，方便处理
    expression = "#" + expression + "#"
    stack = ["#"]
    i = 0
    while i < len(expression) and stack:
        top = stack[-1]
        if top in first_vt and expression[i] in first_vt[top]:
            stack.append(expression[i])
            i += 1
        elif top in grammar and precedence_table[top][expression[i]] == "<":
            stack.append(expression[i])
            i += 1
        elif top in grammar and precedence_table[top][expression[i]] == "=":
            stack.pop()
            i += 1
        elif top in grammar and precedence_table[top][expression[i]] == ">":
            right = stack.pop()
            left = stack.pop()
            non_terminal = top
            production = [left, non_terminal, right]
            stack.append(non_terminal)
            print(production)
        else:
            print("无法识别的表达式")
            return

    if stack == ["E'"]:
        print("表达式识别成功")
    else:
        print("表达式识别失败")

# 测试分析函数
expression1 = "i+i)*i"
expression2 = "(i+i)*i"
print("\n分析表达式", expression1)
analyze_expression(expression1)
print("\n分析表达式", expression2)
analyze_expression(expression2)

运行结果如下：

FirstVt:
E': {'#', 'i'}
E: {'(', 'i'}
T: {'(', 'i'}
F: {'(', 'i'}

LastVt:
E': {'#', 'i'}
E: {'+', '#'}
T: {'*', '+', '#'}
F: {'(', ')', 'i'}

算符优先关系表：
|   | # | + | * | ( | ) | i |
| # | = | < | < | < | = | < |
| E |   | > |   |   | > |   |
| T |   | > | < |   | > |   |
| F |   | > | > |   | > |   |

分析表达式 i+i)*i
['i', '+', 'i']
['F', 'i']
['T', 'F']
['E', 'T']
['E', 'E', '+', 'T']
无法识别的表达式

分析表达式 (i+i)*i
['i', '+', 'i']
['F', 'i']
['T', 'F']
['T', 'T', '*', 'F']
['E', 'T']
['E', 'E', '+', 'T']
['E', '(', 'E', ')']
['F', '(', 'E', ')']
['T', 'F']
['T', 'T', '*', 'F']
['E', 'T']
['E', '(', 'E', ')']
['F', 'i']
['T', 'F']
['E', 'T']
['E', 'E', '+', 'T']
['E', '(', 'E', ')']
表达式识别成功

根据给定文法，先求出 FirstVt 和 LastVt 集合，构造算符优先关系表（要求算符优先 关系表 输出到显示器或者输出到文件）； （2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求 输出归约过程） （3）假如给定表达式文法为： G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i (4) 分析的句子可为: (i+i)*i 和 i+i)*i

首先，根据文法 G(E')，求出 FirstVt 和 LastVt 集合：

FirstVt(E') = {#, i}
FirstVt(E) = FirstVt(T) = FirstVt(F) = {i}
LastVt(E') = {#, i}
LastVt(E) = LastVt(T) = {+, #}
LastVt(T) = LastVt(F) = {*, +, #}

然后，构造算符优先关系表：

| | # | + | * | ( | ) | i |
| - | - | - | - | - | - | - |
| # | = | < | < | < | = | < |
| + | > | > | < | < | > | < |
| * | > | > | > | < | > | < |
| ( | < | < | < | < | = | < |
| ) | > | > | > | | > | |
| i | > | > | > | | > | |

其中，">" 表示左边的符号优先于右边的符号，"<" 表示右边的符号优先于左边的符号，"=" 表示两边的符号优先级相等。

接下来，分别对给定的两个表达式进行分析。

1. 对于表达式 (i+i)*i：
首先，在表达式的首尾加上 "#"，得到 "#(i+i)*i#"
然后，使用算符优先关系表进行分析，得到归约过程如下：

|i + i|* i #|
|T + i|* i #|
|F + i|* i #|
|i|* i #|
|F|* i #|
|T|* i #|
|T * F|# i #|
|E'|# i #|

因此，该表达式是该文法识别的正确的算术表达式。

2. 对于表达式 i+i)*i：
同样地，在表达式的首尾加上 "#"，得到 "#i+i)*i#"
使用算符优先关系表进行分析时，发现 ")" 与 "+" 的优先级相等，因此无法判断应该先进行哪个运算。因此，该表达式不是该文法识别的正确的算术表达式。