编译原理——语法分析

1、精选优质文档-倾情为你奉上实验报告学院（系）名称：计算机与通信工程学院姓名Sky学号专业计算机科学与技术班级2班实验名称语法分析课程名称编译原理课程代码实验时间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）分析法，就是指从左到右扫描输

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的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出ST

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

5、a，则把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不再增大为止。  FO

6、LLOW集合的构造算法：  （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是终结符或#。矩阵元素 M

7、A, a中存放这一条关于A的产生式，指出当A面临输入符号a是所应采用的规则。MA, a也可能存放一条“出错标志”，指出当A根本不该面临输入符号a。 程序源码：#include <iostream> #include <fstream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <vector> #include <iomanip> 

8、;#include "LexAnalysis.h"  using namespace std;  int leftSmall = 0;/左小括号 int rightSmall = 0;/右小括号 int leftMiddle = 0;/左中括号 int rightMiddle = 0;/右中括号 int leftBig = 0;/左大括号 int rightBig = 0;/右大括号 int lineBra61000 = 0;/括号和行数的对应关系，第一维代表左右6种括号&#

9、160;int static_iden_number = 0;/模拟标志符的地址，自增 /Token节点   NormalNode * normalHead;/首结点  /错误节点 struct ErrorNode      char content30;/错误内容     char describe30;/错误描述     int type;     in

10、t line;/所在行数     ErrorNode * next;/下一个节点   ErrorNode * errorHead;/首节点  /标志符节点 struct IdentiferNode      char content30;/内容     char describe30;/描述     int type;/种别码   

11、60; int addr;/入口地址     int line;/所在行数     IdentiferNode * next;/下一个节点  IdentiferNode * idenHead;/首节点  vector<pair<const char *,int> > keyMap; vector<pair<const char *,int> > operMap; vector<pair<const

12、 char *,int> > limitMap;void initNode()      normalHead = new NormalNode();     strcpy(normalHead->content,"");     strcpy(normalHead->describe,"");     normalHead->type = -1; 

13、;    normalHead->addr = -1;     normalHead->line = -1;     normalHead->next = NULL;      errorHead = new ErrorNode();     strcpy(errorHead->content,"");     s

14、trcpy(errorHead->describe,"");     errorHead->line = -1;     errorHead->next = NULL;      idenHead = new IdentiferNode();     strcpy(idenHead->content,"");     str

15、cpy(idenHead->describe,"");     idenHead->type = -1;     idenHead->addr = -1;     idenHead->line = -1;     idenHead->next = NULL;   void createNewNode(char * content,char *descirbe

16、,int type,int addr,int line)      NormalNode * p = normalHead;     NormalNode * temp = new NormalNode();      while(p->next!=NULL)              p = p->next; &#

17、160;         strcpy(temp->content,content);     strcpy(temp->describe,descirbe);     temp->type = type;     temp->addr = addr;     temp->line = line;   

18、60; temp->next = NULL;      p->next = temp;  void createNewError(char * content,char *descirbe,int type,int line)      ErrorNode * p = errorHead;     ErrorNode * temp = new ErrorNode();     

19、; strcpy(temp->content,content);     strcpy(temp->describe,descirbe);     temp->type = type;     temp->line = line;     temp->next = NULL;     while(p->next!=NULL)   &

20、#160;          p = p->next;          p->next = temp;  void printNodeLink()      NormalNode * p = normalHead;     p = p->next;     cout&l

21、t;<"*分析表*"<<endl<<endl;     cout<<setw(30)<<"内容"<<setw(10)<<"描 述"<<"t"<<"种别码"<<"t"<<"地址"<<"t"<<" 行号"<<endl;&#

22、160;    while(p!=NULL)              if(p->type = IDENTIFER)                      cout<<setw(30)<<p->content

23、<<setw(10)<<p->describe<<"t"<<p->type<<"t"<<p->addr<<"t"<<p->line<<endl;                  else     

24、                 cout<<setw(30)<<p->content<<setw(10)<<p->describe<<"t"<<p->type<<"t"<<"t"<<p->line<<endl;   

25、;               p = p->next;          cout<<endl<<endl; int getSymbolPosOfKey(string t)int pos = -1;for (int i = 0; i < KEYLENGTH; i+)if (!_stricmp(keyi, t.c_str()pos = i;b

26、reak;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 Get

27、Char(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;

28、 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(ifstre

29、am& 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 &

30、lt;< '(' << pos << ", " << strToken << ')' << enter; lexicalType a;a.strToken.append(strToken, strlen(strToken);a.pos = pos;return a;else cout << '(' << 10 << ", /'" << strToken << "/&

31、#39;)" << 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 << ", /'" &l

32、t;< 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(

33、infileStream); if (ch != '/'') cerr << "String is too long - more than 1024 bytes!" << endl; else Concat(strToken, ch); cout << '(' << 29 << ", /'" << strToken << "/')" << enter;lexicalType a;a.

34、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

35、;return a;else if (ch = '-') cout << '(' << 14 << ", /'" << '-' << "/')" << enter;lexicalType a;a.strToken.append(1, '-');a.pos = 14;return a;else if (ch = '*') cout << '(' <<

36、15 << ", /'" << '*' << "/')" << enter;lexicalType a;a.strToken.append(1, '*');a.pos = 15;return a;else if (ch = '/') cout << '(' << 16 << ", /'" << '/' << "/&#

37、39;)" << enter;lexicalType a;a.strToken.append(1, '/');a.pos = 16;return a;else if (ch = '=') cout << '(' << 25 << ", /'" << '=' << "/')" << enter;lexicalType a;a.strToken.append(1, '='

38、);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 << '('

39、<< 31 << ", /'" << '' << "/')" << enter; lexicalType a;a.strToken.append(1, '');a.pos = 31;return a;else if (ch = ',') cout << '(' << 32 << ", /'" << ',' << &

40、quot;/')" << enter; lexicalType a;a.strToken.append(1, ',');a.pos = 32;return a;else if (ch = '') cout << '(' << 26 << ", /'" << '' << "/')" << enter; lexicalType a;a.strToken.append(1, 

41、9;');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 << &

42、#39;(' << 28 << ", /'" << ')' << "/')" << enter; lexicalType a;a.strToken.append(1, ')');a.pos = 28;return a;else if (ch = '<') ch = GetChar(infileStream); if (ch = '>') cout << '(' <

43、< 21 << ", /'" << "<>"<< "/')" << enter; lexicalType a;a.strToken = "<>"a.pos = 21;return a;else if (ch = '=') cout << '(' << 22 << ", /'" << '<=' &

44、lt;< "/')" << enter; lexicalType a;a.strToken = "<="a.pos = 22;return a;else cout << '(' << 20 << ", /'" << '<' << "/')" << enter; Retract(infileStream); lexicalType a;a.strToken.ap

45、pend(1, '<');a.pos = 20;return a; else if (ch = '>') ch = GetChar(infileStream); if (ch = '=') cout << '(' << 24 << ", /'" << '>=' << "/')" << enter; lexicalType a;a.strToken = ">

46、="a.pos = 24;return a;else cout << '(' << 23 << ", /'" << '>' << "/')" << enter;Retract(infileStream); lexicalType a;a.strToken.append(1, '>');a.pos = 23;return a; / 判断:和:= else if (ch = ':') c

47、h = GetChar(infileStream);if (ch = '=') cout << '(' << 18 << ", " << ":=" << ")" << enter; lexicalType a;a.strToken = ":="a.pos = 18;return a;else cout << '(' << 17 << ", /'

48、" << ':' << "/')" << enter; Retract(infileStream); lexicalType a;a.strToken.append(1, ':');a.pos = 17;return a; else if (ch = '#')cout << '(' << 0 << ", /'" << '#' << "/'

49、)" << 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 << "Please input the Grammer file name (grammer.tx

50、t): "cin >> 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;fi

51、leName = "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 << "Please input Source file name(