编译原理——语法分析.doc

实验报告学院（系）名称：计算机与通信工程学院姓名Sky学号专业计算机科学与技术班级2班实验名称语法分析课程名称编译原理课程代码0668056实验时间2016年4月21日08:00-10:002016年4月26日10:00-13:00实验地点7-220批改意见成绩教师签字： 实验内容与要求： 实现如下表达式文法的语法分析器，可选择LL1分析法、算符优先分析法、LR分析法之一完成实验，要求输出全部分析过程：（1）EE+T | E-T | T（2）TT*F | T/F | F（3）FPF | P（4）P(E) | i实验内容： LL(1)分析法：所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C语言来编写。 LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（）若X=a=#，则宣布分析成功，停止分析过程。（）若X=a#，则把X从STACK栈顶弹出，让a指向下一个输入符号。（）若X是一个非终结符，则查看预测分析表M。若MA，a中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为，则不推什么东西进STACK栈）。若MA，a中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。 在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法来构造这两个集合。FIRST集合的构造算法：（1）若XVT，则FIRST（X）=X。（2）若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。（3）若XY是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有（即Y1Yi-1*），则把FIRST(Yj)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j=1,2,，k，则把加到FIRST(X)中。连续使用上面的规则，直至每个集合FIRST不再增大为止。FOLLOW集合的构造算法：（1）对于文法的开始符号S，置#于FOLLOW(S)中；（2）若AB是一个产生式，则把FIRST()|加至FOLLOW(B)中；（3）若AB是一个产生式，或AB是一个产生式而（即FIRST()），则把FOLLOW(A)加至FOLLOW(B)中。连续使用上面的规则，直至每个集合FOLLOW不再增大为止。现在来构造GE的LL（1）预测分析表。预测分析表MA,a是如下形式的一个矩阵。A为非终结符，a是终结符或#。矩阵元素MA,a中存放这一条关于A的产生式，指出当A面临输入符号a是所应采用的规则。MA,a也可能存放一条“出错标志”，指出当A根本不该面临输入符号a。 程序源码：#include #include #include #include #include #include #include #include LexAnalysis.husing namespace std;int leftSmall = 0;/左小括号int rightSmall = 0;/右小括号int leftMiddle = 0;/左中括号int rightMiddle = 0;/右中括号int leftBig = 0;/左大括号int rightBig = 0;/右大括号int lineBra61000 = 0;/括号和行数的对应关系，第一维代表左右6种括号int static_iden_number = 0;/模拟标志符的地址，自增/Token节点NormalNode * normalHead;/首结点/错误节点struct ErrorNode char content30;/错误内容 char describe30;/错误描述 int type; int line;/所在行数 ErrorNode * next;/下一个节点;ErrorNode * errorHead;/首节点/标志符节点struct IdentiferNode char content30;/内容 char describe30;/描述 int type;/种别码 int addr;/入口地址 int line;/所在行数 IdentiferNode * next;/下一个节点;IdentiferNode * idenHead;/首节点vectorpair keyMap;vectorpair operMap;vectorpair limitMap;void initNode() normalHead = new NormalNode(); strcpy(normalHead-content,); strcpy(normalHead-describe,); normalHead-type = -1; normalHead-addr = -1; normalHead-line = -1; normalHead-next = NULL; errorHead = new ErrorNode(); strcpy(errorHead-content,); strcpy(errorHead-describe,); errorHead-line = -1; errorHead-next = NULL; idenHead = new IdentiferNode(); strcpy(idenHead-content,); strcpy(idenHead-describe,); idenHead-type = -1; idenHead-addr = -1; idenHead-line = -1; idenHead-next = NULL;void createNewNode(char * content,char *descirbe,int type,int addr,int line) NormalNode * p = normalHead; NormalNode * temp = new NormalNode(); while(p-next!=NULL) p = p-next; strcpy(temp-content,content); strcpy(temp-describe,descirbe); temp-type = type; temp-addr = addr; temp-line = line; temp-next = NULL; p-next = temp;void createNewError(char * content,char *descirbe,int type,int line) ErrorNode * p = errorHead; ErrorNode * temp = new ErrorNode(); strcpy(temp-content,content); strcpy(temp-describe,descirbe); temp-type = type; temp-line = line; temp-next = NULL; while(p-next!=NULL) p = p-next; p-next = temp;void printNodeLink() NormalNode * p = normalHead; p = p-next; cout*分析表*endlendl; coutsetw(30)内容setw(10)描 述t种别码t地址t 行号type = IDENTIFER) coutsetw(30)contentsetw(10)describettypetaddrtlineendl; else coutsetw(30)contentsetw(10)describettypettlinenext; coutendlendl;int getSymbolPosOfKey(string t)int pos = -1;for (int i = 0; i KEYLENGTH; i+)if (!_stricmp(keyi, t.c_str()pos = i;break;return pos;int getTerminalSymbolPos(string t)int pos = -1;for(int i = 0; i y; i+)string s = terminalSymboli;if (s = t)pos = i;break;return pos;int getNonTerminalSymbolPos(string nt)int pos = -1;for(int i = 0; i x; i+)if (nonterminalSymboli = nt)pos = i;break;return pos;/ 读入ch char GetChar(ifstream& infileStream) char cRet; infileStream.get(cRet); return cRet; / 读入空格 char GetBC(ifstream& infileStream) char cRet; infileStream.get(cRet); while (cRet = ) infileStream.get(cRet); return cRet; / 连接单词符号 void Concat(char *str, char c) size_t n = strlen(str); strn+ = c; strn = /0; / 判断是否为保留字 int Reserve(const char* str) int bRet = -1; for (int i = 0; i KEYLENGTH; i+) if (_stricmp(keyi, str) = 0) bRet = i; break; return bRet; / 回调字符 char Retract(ifstream& infileStream) infileStream.seekg(-1, ios:cur); return /0; lexicalType lexical(ifstream& infileStream)char ch;char strToken1024 = ;ch = GetChar(infileStream);int pos = -1;/ 判断标识符的情况 if (isalpha(ch) while (isalpha(ch) | isdigit(ch) | ch = _) Concat(strToken, ch); ch = GetChar(infileStream); ch = Retract(infileStream); if (pos = Reserve(strToken) != -1) cout ( pos , strToken ) enter; lexicalType a;a.strToken.append(strToken, strlen(strToken);a.pos = pos;return a;else cout ( 10 , / strToken /) enter; lexicalType a;a.strToken.append(strToken, strlen(strToken);a.pos = 10;return a;/ 判断数值的情况 else if (isdigit(ch) while (isdigit(ch) Concat(strToken, ch); ch = GetChar(infileStream); Retract(infileStream); cout ( 11 , / strToken /) enter; lexicalType a;a.strToken.append(strToken, strlen(strToken);a.pos = 11;return a; / 判断字符串的情况 else if (ch = /) Concat(strToken, ch); ch = GetChar(infileStream); while (ch != /) Concat(strToken, ch); ch = GetChar(infileStream); if (ch != /) cerr String is too long - more than 1024 bytes! endl; else Concat(strToken, ch); cout ( 29 , / strToken /) enter;lexicalType a;a.strToken.append(strToken, strlen(strToken);a.pos = 29;return a; / 判断所有没有歧义的单目运算符 else if (ch = +) cout ( 13 , / + /) enter; lexicalType a;a.strToken.append(1, +);a.pos = 13;return a;else if (ch = -) cout ( 14 , / - /) enter;lexicalType a;a.strToken.append(1, -);a.pos = 14;return a;else if (ch = *) cout ( 15 , / * /) enter;lexicalType a;a.strToken.append(1, *);a.pos = 15;return a;else if (ch = /) cout ( 16 , / / /) enter;lexicalType a;a.strToken.append(1, /);a.pos = 16;return a;else if (ch = =) cout ( 25 , / = /) enter;lexicalType a;a.strToken.append(1, =);a.pos = 25;return a;else if (ch = ) cout ( 30 , / /) enter; lexicalType a;a.strToken.append(1, );a.pos = 30;return a;else if (ch = ) cout ( 31 , / /) enter; lexicalType a;a.strToken.append(1, );a.pos = 31;return a;else if (ch = ,) cout ( 32 , / , /) enter; lexicalType a;a.strToken.append(1, ,);a.pos = 32;return a;else if (ch = ;) cout ( 26 , / ; /) enter; lexicalType a;a.strToken.append(1, ;);a.pos = 26;return a;else if (ch = () cout ( 27 , / ( /) enter; lexicalType a;a.strToken.append(1, ();a.pos = 27;return a;else if (ch = ) cout ( 28 , / ) /) enter; lexicalType a;a.strToken.append(1, );a.pos = 28;return a;else if (ch = ) cout ( 21 , / /) enter; lexicalType a;a.strToken = ;a.pos = 21;return a;else if (ch = =) cout ( 22 , / = /) enter; lexicalType a;a.strToken = =;a.pos = 22;return a;else cout ( 20 , / /) enter; Retract(infileStream); lexicalType a;a.strToken.append(1, ) ch = GetChar(infileStream); if (ch = =) cout ( 24 , / = /) =;a.pos = 24;return a;else cout ( 23 , / /) );a.pos = 23;return a; / 判断:和:= else if (ch = :) ch = GetChar(infileStream);if (ch = =) cout ( 18 , := ) enter; lexicalType a;a.strToken = :=;a.pos = 18;return a;else cout ( 17 , / : /) enter; Retract(infileStream); lexicalType a;a.strToken.append(1, :);a.pos = 17;return a; else if (ch = #)cout ( 0 , / # /) enter; lexicalType a;a.strToken.append(1, #);a.pos = 0;return a;elselexicalType a = lexical(infileStream);return a;void main()stkGrammer.push(#);stkGrammer.push(Proc);string fileName;cout fileName;fstream G_fileStream;G_fileStream.open(&fileName0 , ios_base:in);if (G_fileStream.fail()cout open file error/n ;return;readGrammer(&G_fileStream);G_fileStream.close();/ 读取语法分析表cout Loading analyze.txt. endl;fileName = analyze.txt;fstream G_A_fileStream;G_A_fileStream.open(fileName.c_str(), ios_base:in);if(G_A_fileStream.eof()cout open the anylyze file error!/n;return;readGrammerAnalyze(&G_A_fileStream);G_A_fileStream.close();cout load anylyze.txt done/n;/ 读源文件cout fileName;ifstream infileStream(fileName.c_str();if(infileStream.eof()cout open source file error/n;return;lexicalType lexicaltype;while(!infileStream.eof()lexicaltype = lexical(infileStream);while(1)int i = getSymbolPosOfKey(stkGrammer.top();if (lexicaltype.pos = 0)cout Okay, the sentence is good checked by LL(1) syntax endl;exit(0);if ( i !=