Sicily1000. 输入输出LL(1)语法分析程序

题目

输入开始符号&＃xff0c;非终结符&＃xff0c;终结符&＃xff0c;产生式&＃xff0c;LL(1)分析表
输出LL(1)分析表

G[E]:E →E&＃43;T | E-T | T
T →T*F | T/F | F
F →(E) | D
D →x | y | z

消除左递归G1[E]:
E →TA
A →&＃43;TA | -TA | e
T →FB
B →*FB | /FB | e
F →(E) | D
D →x | y | z

Input
输入开始符号&＃xff1b;
非终结符个数&＃xff0c;非终结符&＃xff0c;空格符分隔&＃xff1b;
终结符个数&＃xff0c;终结符&＃xff0c;空格符分隔&＃xff1b;
产生式的个数&＃xff0c;各产生式的序号&＃xff0c;产生式的左边和右边符号&＃xff0c;空格符分隔&＃xff1b;
LL(1)分析表中的产生式个数&＃xff0c;序号&＃xff0c;行符号&＃xff0c;列符号&＃xff0c;产生式编号&＃xff0c;空格符分隔&＃xff1b;

Output
第一行&＃xff1a;空&＃xff0c;安终结符循序输出终结符&＃xff0c;结束符‘#’&＃xff0c;每个符号占5格&＃xff1b;
其余行&＃xff1a;非终结符符号&＃xff0c;各对应终结符的产生式的右边&＃xff0c;每个符号占5格&＃xff1b;

Sample Input

Sample Output

解题分析

通过题目的例子我们不难发现&＃xff0c;题目就是要求我们根据产生式构造出LL(1)分析表。我们先结合上面的例子来看看LL(1)分析表是如何构建的。
可以看到&＃xff0c;LL(1)分析表的行是各个非终结符&＃xff0c;列是各个终结符。然后结合输入的产生式&＃xff0c;比如第一个LL(1)分析表产生式是&＃xff1a;1 E ( 1。通过题目我们知道这个式子表示行为E、列为(对应的位置是1号产生式&＃xff0c;即1 E TA。其它式子依此类推&＃xff0c;就可以得到LL(1)分析表。

现在问题的关键是如何将非终结符、终结符、产生式、LL(1)产生式进行存储。根据题目的例子&＃xff0c;我们知道上面每个都有几个表项&＃xff0c;因此不难想到要用结构体。想到了这一点&＃xff0c;问题就好办多了。
根据题目的样例&＃xff0c;我们知道&＃xff0c;#也属于终结符&＃xff0c;但输入中并没有体现&＃xff0c;因此&＃xff0c;在输入的最后还要将其进行特殊处理、加入到终结符中。
然后根据我们上面提到的构造LL(1)分析表的思路&＃xff0c;我们对所有的LL(1)分析表产生式进行遍历&＃xff0c;根据产生式的行符号、列符号和产生式序号进行一一对应填充&＃xff0c;最后将其输出&＃xff0c;就顺利解决了。

源代码

#include
#include
using namespace std;struct non_terminal
{int count;string sign[100];string LL[100][100];
};struct terminal
{int count;string sign[100];
};struct produce
{int count;int number[100];string left[100];string right[100];
};struct LL1_produce
{int count;int number[100];string row[100];string col[100];int order[100];
};int main() {non_terminal non_terminal;terminal terminal;produce produce;LL1_produce LL1_produce;string start;cin >> start;cin >> non_terminal.count;for (int i &＃61; 0; i cin >> non_terminal.sign[i];}cin >> terminal.count;for (int i &＃61; 0; i cin >> terminal.sign[i];}cin >> produce.count;for (int i &＃61; 0; i cin >> produce.number[i] >> produce.left[i] >> produce.right[i];}cin >> LL1_produce.count;for (int i &＃61; 0; i cin >> LL1_produce.number[i] >> LL1_produce.row[i] >> LL1_produce.col[i] >> LL1_produce.order[i];}terminal.sign[terminal.count] &＃61; "#";terminal.count&＃43;&＃43;;for (int i &＃61; 0; i int row, col;for (int j &＃61; 0; j if (non_terminal.sign[j] &＃61;&＃61; LL1_produce.row[i]) {row &＃61; j;break;}}for (int k &＃61; 0; k if (terminal.sign[k] &＃61;&＃61; LL1_produce.col[i]) {col &＃61; k;break;}}non_terminal.LL[row][col] &＃61; produce.right[LL1_produce.order[i] - 1];}cout <<" ";for (int i &＃61; 0; i cout <<" " <cout <for (int i &＃61; 0; i for (int j &＃61; 0; j <5 - non_terminal.sign[i].size(); j&＃43;&＃43;) {cout <<" ";}cout <for (int j &＃61; 0; j for (int k &＃61; 0; k <5 - non_terminal.LL[i][j].size(); k&＃43;&＃43;) {cout <<" ";}cout <cout <return 0;
}

以上是我对这道问题的一些想法&＃xff0c;有问题还请在评论区讨论留言~