一、实验目的
加深对LL(1)语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。
二、实验内容
用预测分析法编制语法分析程序，语法分析程序的实现可以采用C、Java或python编程语言和工具。
三、实验要求：
其相应文法为:
?E—>TG
?T—>FS
?G—>+TG|ε
?S—>*FS|ε
?F—>(E)|i
?1、根据LL（1）分析法总控流程图，编写一个语法分析程序，该语法分析程序实现LL（1）算法的分析过程。可根据自己的能力情况，选择以下其中一项作为分析算法的输入：
（1）直接输入根据已知文法构造的分析表M。
（2）输入已知文法的集合FIRST（x）和FOLLOW（U），由程序自动生成该文法的分析表M。
（3）输入已知文法，由程序自动生成该文法的分析表M。
2.展示i+i*i语句的识别过程
四、实验步骤
在这里，我选择第（3）项，即输入已知文法，由程序自动生成该文法的分析表M。完成以下几个步骤：
1. 构造FIRST集合和FOLLOW集合。
2. 根据文法和FIRST、FOLLOW集合生成预测分析表M。
3. 编写语法分析程序，利用预测分析表M进行语法分析，基本思路按照文法从上至下逐步推导输入串，直到处理完整个串或者出现错误。
具体来说，分析器会先对输入串进行初始化，然后将 '#' 和文法的起始符号 'E' 压入分析栈中，接着从输入串中读取一个字符，并将分析栈栈顶元素取出。如果栈顶元素是终结符，则判断是否与当前读取的字符相等。如果相等，则将下一个字符读入，并继续处理；否则说明出现了错误，返回错误信息。如果栈顶元素是非终结符，则根据预测分析表获取相应的产生式，并将产生式的右部逆序压入分析栈中。如果预测分析表中没有对应的产生式，则说明出现了错误，返回错误信息。最后，不断重复上述步骤，直到分析成功或出现错误。
实现代码：
#include?<iostream>
#include?<string>
#include?<fstream>
#include?<vector>
#include?<cstring>
using?namespace?std;
const?string?ExpFileName = "./exp.txt";
char?analyeStack[20]; ??????????????????????????/*分析栈*/
char?restStack[20]; ????????????????????????????/*剩余栈*/
const?string?v1 = "i+*()#"; /*终结符 */
const?string?v2 = "EGTSF"; ?????/*非终结符 ??*/
int?top, ridx, len; /*len为输入串长度 ?ridx：用来追踪下一个需要处理的字符在剩余中的位置。 top:分析栈栈顶位置*/
struct?type?{ /*产生式类型定义 ?????*/
????char?origin; ??/*产生式左部 大写字符 ?*/
????string?array; /*产生式右部 */
????int?length; ???/*存储字符个数*/
????type() :origin('N'), array(""), length(0) {}
????void?init(char?a, string?b) {/*分析栈、剩余栈的初始化*/
????????origin = a;
????????array =?b;
????????length = array.length();
????}
};
type?e, t, g, g1, s, s1, f, f1; /* 产生式结构体变量 */
type?C[10][10]; ????????????????/* 预测分析表 */
void?print() {/*输出分析栈和剩余栈 */
????for?(int?i = 0; i <= top + 1; ++i) ??/*输出分析栈 ?*/
????????cout <<?analyeStack[i];
????cout <<?"\t\t";
????for?(int?i = 0; i < ridx; ++i) /*输出对齐符*/
????????cout <<?' ';
????for?(int?i = ridx; i <= len; ++i) ??/*输出剩余串*/
????????cout <<?restStack[i];
????cout <<?"\t\t\t";
}
// 读文件
vector<string> readFile(string?fileName) {
????vector<string> res;
????try?{
????????ifstream?fin;//输入文件流对象
????????fin.open(fileName);
????????string?temp;
????????while?(getline(fin, temp))
????????????res.push_back(temp);
????????return?res;
????}
????catch?(const?exception& e) {/*异常*/
????????cerr <<?e.what() <<?'\n';
????????return?res;
????}
}
bool?isTerminator(char?c) { // 判断是否是终结符
????return?v1.find(c) != string::npos;
}
void?init(string?exp) {
????top = ridx = 0;
????len = exp.length(); ????/*分析串长度*/
????for?(int?i = 0; i < len; ++i)
????????restStack[i] = exp[i];/*输入串入栈*/
}
void?analyze(string?exp) { ?// 分析一个文法
????init(exp);
????int?k = 0;
????analyeStack[top] = '#';
????analyeStack[++top] = 'E'; /*'#','E'进栈*/
????cout <<?"步骤\t\t分析栈 \t\t剩余字符 \t\t所用产生式 "?<<?endl;
????while?(true) {
????????char?ch = restStack[ridx];
????????char?x = analyeStack[top--]; /*x为当前栈顶字符*/
????????cout <<?++k <<?"\t\t";
????????if?(x == '#') {
????????????cout <<?"分析成功！AC！\n"?<<?endl; /*接受 */
????????????return;
????????}
????????if?(isTerminator(x)) {//判断终结符
????????????if?(x == ch) { ?// 匹配上了
????????????????print();
????????????????cout <<?ch <<?"匹配"?<<?endl;
????????????????ch = restStack[++ridx]; /*下一个输入字符*/
????????????}
????????????else?{ ????????????/*出错处理*/
????????????????print();
????????????????cout <<?"分析出错，错误终结符为"?<<?ch <<?endl; /*输出出错终结符*/
????????????????return;
????????????}
????????}
????????else?{ ???/*非终结符处理*/
????????????int?m, n=0; ??// 非终结符下标， 终结符下标
????????????v2.find(x) != string::npos ? m = v2.find(x) : -1; ??// m为-1则说明找不到该非终结符，出错
????????????v1.find(ch) != string::npos ? n = v1.find(ch) : -1; // n为-1则说明找不到该终结符，出错
????????????if?(m == -1 || n == -1) { /*出错处理*/
????????????????print();
????????????????cout <<?"分析出错，错误非终结符为"?<<?x <<?endl; /*输出出错非终结符*/
????????????????return;
????????????}
????????????type?nowType = C[m][n];/*用来接受C[m][n]*/
????????????if?(nowType.origin != 'N') {/*判断是否为空*/
????????????????print();
????????????????cout <<?nowType.origin <<?"->"?<<?nowType.array <<?endl; /*输出产生式*/
????????????????for?(int?j = (nowType.length - 1); j >= 0; --j) /*产生式逆序入栈*/
????????????????????analyeStack[++top] = nowType.array[j];
????????????????if?(analyeStack[top] == '^') /*为空则不进栈*/
????????????????????top--;
????????????}
????????????else?{ /*出错处理*/
????????????????print();
????????????????cout <<?"分析出错，错误非终结符为"?<<?x <<?endl; /*输出出错非终结符*/
????????????????return;
????????????}
????????}
????}
}
int?main() {
????e.init('E', "TG"), t.init('T', "FS");
????g.init('G', "+TG"), g1.init('G', "^");
????s.init('S', "*FS"), s1.init('S', "^");
????f.init('F', "(E)"), f1.init('F', "i"); /* 结构体变量 */
????/*填充分析表*/
????C[0][0] =?C[0][3] =?e;
????C[1][1] =?g;
????C[1][4] =?C[1][5] =?g1;
????C[2][0] =?C[2][3] =?t;
????C[3][2] =?s;
????C[3][4] =?C[3][5] =?C[3][1] =?s1;
????C[4][0] =?f1; C[4][3] =?f;
????cout <<?"提示:本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析，每行一个读入的字符串"?<<?endl;
????cout <<?"读取的文件名为："?<<?ExpFileName <<?endl;
????vector<string> exps = readFile(ExpFileName);
????int?len = exps.size();//文件中元素数量
????for?(int?i = 0; i < len; i++) {
????????string?exp = exps[i];
????????//cout << "------------------待分析字符串" << i + 1 << "：" << exp << "--------------------" << endl;
????????bool?flag = true;
????????for?(int?j = 0; j < exp.length(); j++) {
????????????if?(!isTerminator(exp[j])) {//不是终结符
????????????????cout <<?"第"?<<?i + 1 <<?"行输入的字符串不合法，请重新输入"?<<?endl;
????????????????flag = false;
????????????????break;
????????????}
????????}
????????if?(flag) {
????????????cout <<?"字符串"?<<?"："?<<?exp <<?endl;
????????????analyze(exp);
????????}
????}
????return?0;
}