编译原理——语法分析详解

1、实验报告学院（系）名称： 计算机与通信工程学院姓名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 | T2）TT*F| T/F | F3）FPF| P4）P(E) |i实验内容：LL（1） 分析法：所谓 LL （1）分析法，就是指从左到右扫描

2、输入串（源程序） ，同时采用最左推导，且对每次 直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL （1）分析的程序又称为 LL （ 1）分析程序或 LL1 （1）分析器。一个文法要能进行 LL （ 1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因 子。当文法满足条件后，再分别构造文法每个非终结符的 FIRST 和 FOLLOW 集合，然后根 据 FIRST 和 FOLLOW 集合构造 LL（ 1）分析表，最后利用分析表，根据 LL（1） 语法分析构造 一个分析器。 LL （1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进 先出的语法分析栈，本程

3、序也是采用了同样的方法进行语法分析，该程序是采用了C 语言来编写。LL （ 1）预测分析程序的总控程序在任何时候都是按STACK 栈顶符号 X 和当前的输入符号 a 做哪种过程的。对于任何（ X ， a），总控程序每次都执行下述三种可能的动作之一： （）若 X = a = #，则宣布分析成功，停止分析过程。（）若 X = a #，则把 X 从STACK 栈顶弹出，让 a指向下一个输入符号。（）若 X是一个非终结符，则查看预测分析表M。若 MA ，a中存放着关于 X 的一个产第1页 共 15页生式，那么，首先把 X 弹出 STACK 栈顶，然后，把产生式的右部符号串按反序一一弹出 ST ACK

4、栈(若右部符号为 ，则不推什么东西进 STACK 栈)。若 MA ，a中存放着 “出错标志”， 则调用出错诊断程序 ERROR。 事实上， LL ( 1)的分析是根据文法构造的，它反映了相应 文法所定义的语言的固定特征，因此在LL (1)分析器中，实际上是以 LL (1)分析表代替相应方法来进行分析的。在构造 LL(1) 预测分析表之前， 首先要构造该文法的每个非终结符的 FIRST 和 FOLLOW 集 合，按照下面描述的算法来构造这两个集合。FIRST 集合的构造算法：(1) 若 X VT ，则 FIRST(X)=X 。(2) 若 XVN，且有产生式 X a，则把 a加入到 FIRST(X

5、) 中；若 X也是一条产 生式，则把 也加到 FIRST(X) 中。 (3)若 XY是一个产生式且 YVN ，则把 FIRS T(Y)中的所有非 -元素都加到 FIRST(X) 中；若 XY1Y2 Yk 是一个产生式， Y1， Yi- 1 都是非终结符，而且，对于任何j，1j i-1，FIRST(Yj) 都含有 (即 Y1 Yi-1* )，则把 FIRST(Yj) 中的所有非 -元素都加到 FIRST(X) 中；特别是， 若所有的 FIRST(Yj) 均含有 ， j=1,2, ， k ，则把 加到 FIRST(X)中。连续使用上面的规则，直至每个集合 FIRST 不再增大为止。 FOLLOW

6、集合的构造算法：(1)对于文法的开始符号 S，置 #于 FOLLOW(S) 中； (2)若 AB是一个产生式，则 把 FIRST( )| 加至 FOLLOW(B) 中；(3) 若 AB 是一个产生式，或 AB是一个产生式而 (即FIRST( )，则 把 FOLLOW(A) 加至 FOLLOW(B) 中。 连续使用上面的规则，直至每个集合 FOLLOW 不再增大为止。 现在来构造 个矩阵。A 为非终结符， 指出当 A 面临输入符号 A 根本不该面临输入符号GE的 LL ( 1)预测分析表。预测分析表 MA, a 是如下形式的一 a是终结符或 #。矩阵元素 MA, a 中存放这一条关于 A 的产生

7、式， a 是所应采用的规则。 MA, 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

8、 lineBra61000 = 0;/ 括号和行数的对应关系，第一维代表左右 6 种括号 int static_iden_number = 0;/ 模拟标志符的地址，自增/Token 节点第2页 共 15页NormalNode * normalHead;/ 首结点/ 错误节点struct ErrorNodechar content30;/ 错误内容 char describe30;/ 错误描述 int type;int line;/ 所在行数ErrorNode * next;/ 下一个节点;ErrorNode * errorHead;/ 首节点/ 标志符节点struct IdentiferNo

9、dechar 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-de

10、scribe,); 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(idenHe

11、ad-describe,); idenHead-type = -1;第3页 共 15页 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,con

12、tent); 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-desc

13、ribe,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*第4页 共 15页*endlendl;coutsetw(30) 内容setw(10) 描 述t 种别码 t 地址 t 号type = IDENTIFER) coutsetw(30)contentsetw(10)describetty

14、petaddr tlineendl;else coutsetw(30)contentsetw(10)describettypett linenext;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 = t

15、erminalSymboli;if (s = t)pos = i;break;return pos;第5页 共 15页 int getNonTerminalSymbolPos(string nt)int pos = -1;for(int i = 0; i x; i+)if (nonterminalSymboli = nt)pos = i; break;return pos;/ 读入 chchar GetChar(ifstream& infileStream)char cRet;infileStream.get(cRet);return cRet;/ 读入空格char GetBC(ifstrea

16、m& 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)第6页 共

17、 15页 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 = _) Co

18、ncat(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;elsecout ( 10 , / strToken /) enter; lexicalType a;a.strToken.append(strToken, s

19、trlen(strToken);a.pos = 10; return a;/ 判断数值的情况第7页 共 15页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 = /

20、)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; elseConcat(strToken, ch);cout ( 29 , / strToken /) enter; lexicalType a;a.strToken.append(strToken, strlen(strToken);a.pos

21、 = 29; return a;/ 判断所有没有歧义的单目运算符else if (ch = +)cout ( 13 , / + /) enter; lexicalType a;a.strToken.append(1, +);a.pos = 13;return a;第8页 共 15页else if (ch = -)cout ( 14 , lexicalType a;a.strToken.append(1, -); a.pos = 14;return a;else if (ch = *)cout ( 15 , lexicalType a;a.strToken.append(1, *); a.pos

22、 = 15;return a;else if (ch = /)cout ( 16 , lexicalType a;a.strToken.append(1, /); a.pos = 16;return a;else if (ch = =)cout ( 25 , lexicalType a;a.strToken.append(1, =); a.pos = 25;return a;else if (ch = )cout ( 30 , lexicalType a;a.strToken.append(1, ); a.pos = 30;return a;else if (ch = )cout ( 31 ,

23、 lexicalType a;a.strToken.append(1, ); - /) enter; * /) enter; / /) enter; = /) enter; /) enter; /) enter;第 9页 共 15页a.pos = 31; return a;else if (ch = ,)cout ( 32 , / lexicalType a;a.strToken.append(1, ,);a.pos = 32;return a;, /) enter;elseif (ch = ;)cout ( 26 , / lexicalType a;a.strToken.append(1,

24、;);a.pos = 26;return a; /) enter;else if (ch = ()cout ( 27 , / /) enter;lexicalTypea;a.strToken.append(1, ();a.pos = 27; return a;elseif (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 =

25、 21; return a;第 10 页 共 15 页else if (ch = =)cout ( 22 , / = /) enter; lexicalType a;a.strToken = =;a.pos = 22;return a;elsecout ( 20 , / /) enter; Retract(infileStream);lexicalType a;a.strToken.append(1, )ch = GetChar(infileStream);if (ch = =)cout ( 24 , / = /) =;a.pos = 24;return a;elsecout ( 23 , /

26、 /) );a.pos = 23;return a;/ 判断 :和 :=else if (ch = :)ch = GetChar(infileStream); if (ch = =)第 11 页 共 15 页cout ( 18 , := ) enter; lexicalType a;a.strToken = :=;a.pos = 18;return a;elsecout ( 17 , / : /) enter; Retract(infileStream);lexicalType a;a.strToken.append(1, :);a.pos = 17;return a;else if (ch

27、= #)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

28、.fail()cout open file error/n ;return;第 12 页 共 15 页 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;ret

29、urn;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 != -1 )if (