实验二 LL(1)语法分析法设计与实现

一、实验目的

加深对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;

}