实验3：文法问题处理器

一、实验内容

设计一个应用软件，以实现文法的化简及各种问题的处理。

二、实验要求

1. 必做内容

   1. 系统需要提供一个文法编辑界面，让用户输入文法规则（可保存、打开存有文法规则的文件）

   2. 化简文法：检查文法是否存在有害规则和多余规则并将其去除。系统应该提供窗口以便用户可以查看文法化简后的结果。

   3. 检查该文法是否存在着左公共因子（可能包含直接和间接的情况）。如果存在，则消除该文法的左公共因子。系统应该提供窗口以便用户可以查看消除左公共因子的结果。【从某个非终结符号开始只需要消除做4次推导内就可以发现的左公共因子，如果超过4次推导还存在左公共因子就直接产生出错处理即可】

   4. 检查该文法是否存在着左递归（可能包含直接和间接的情况），如果存在，则消除该文法的左递归。系统应该提供窗口以便用户可以查看消除左递归后的结果。

   5. 求出经过前面步骤处理好的文法各非终结符号的first集合与follow集合，并提供窗口以便用户可以查看这些集合结果。【可以采用表格的形式呈现】

   6. 如果输入的文法规则是线性规则（左线性规则或右线性规则），则将该文法对应的有穷自动机生成出来，系统应该提供界面让用户可以查看转换得到的有穷自动机（可以使用状态表的方法来呈现）。【注意：如果该有穷自动机是NFA，还需要把该NFA转为DFA并呈现，并再进行DFA的最小化并呈现，你可以使用实验二的算法来完成】

   7. 软件的操作界面应该是windows界面

   8. 应该书写完善的软件文档

2. 选做内容

   1. 对于必做内容中的第（6）个要求，使用画图的算法设计把DFA图，NFA图等直观图示呈现在窗口中。

注意事项

文法规则为了处理上的简单，输入时可以只输入单一个大写字母作为非终结符号，单一个小写字母作为终结符号，用@表示空串。

如，可以这样输入：

E->E+T
T->a

补充说明

4次推导才发现左公共因子的举例：

S->Aa | Ba
A->Cb
B->Dc
C->Ed
D->Fe
E->fe
F->fd

如果超过4次才发现的左公共因子的就产生出错，如果少于等于4次推导的就要把左公共因子进行消除。