实验2《预测分析法设计与实现》（C语言版）

本实验旨在让学生通过实现预测分析法，加深对于语法分析的理解和掌握。

## 实验要求

1. 学习预测分析法的原理和算法；
2. 实现预测分析法的代码；
3. 使用所实现的代码对给定的文法进行语法分析，并输出语法树或语法分析结果；
4. 对所实现的预测分析法做出必要的优化。

## 实验内容

### 1. 预测分析法

预测分析法是一种自顶向下的语法分析方法，它的本质是根据给定的文法，构建出预测分析表，然后根据该表进行语法分析。

在构建预测分析表时，需要分析每个非终结符号的产生式，确定其可以推导出的终结符号，以及在遇到该非终结符号时应该选择哪个产生式。这个过程中，需要用到First集和Follow集。

First集：对于文法符号串而言，它所能推导出的终结符号串的首符号集合。

Follow集：对于文法的每个非终结符号而言，它所能推导出的终结符号串的后继符号集合。

预测分析表：对于每个非终结符号A和每个终结符号a，表格中的元素M[A,a]包含A可以推导出的所有产生式中，右部符号串的First集合中包含a的那些产生式的编号。

构建预测分析表的算法如下：

1. 将预测分析表初始化为空；
2. 对于每个产生式A→α，找到First(α)中所有元素a，将M[A,a]中填入该产生式的编号；
3. 如果ε∈First(α)，则对于任何终结符号b∈Follow(A)，令M[A,b]中填入该产生式的编号；
4. 重复以上两个步骤，直到预测分析表不再改变。

预测分析过程如下：

1. 首先将待分析串和分析栈初始化；
2. 每次从分析栈的栈顶取出一个符号，如果它是终结符号，则将待分析串中的第一个符号与之比较，如果相同，则将待分析串中的第一个符号弹出，并将分析栈顶的符号也弹出，继续下一次分析；
3. 如果栈顶符号是非终结符号，则在预测分析表中查找该非终结符号和待分析串中第一个符号的交点，如果该交点为空，则出错；否则，将该交点所对应的产生式中的符号逆序压入分析栈中；
4. 重复以上两个步骤，直到分析完成或出错。

### 2. 实现预测分析法的代码

请根据上述算法，实现预测分析法的代码。

### 3. 使用所实现的代码对给定的文法进行语法分析，并输出语法树或语法分析结果

请使用所实现的代码，对如下文法进行语法分析，并输出语法树或语法分析结果。

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id

### 4. 对所实现的预测分析法做出必要的优化

请分析所实现的预测分析法存在的问题，进行必要的优化。并给出分析和优化的代码实现。