編譯原理——語法分析

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗報告學(xué)院（系）名稱：計算機與通信工程學(xué)院姓名Sky學(xué)號專業(yè)計算機科學(xué)與技術(shù)班級2班實驗名稱語法分析課程名稱編譯原理課程代碼實驗時間2016年4月21日08:00-10:002016年4月26日10:00-13:00實驗地點7-220批改意見成績教師簽字： 實驗內(nèi)容與要求： 實現(xiàn)如下表達式文法的語法分析器，可選擇LL1分析法、算符優(yōu)先分析法、LR分析法之一完成實驗，要求輸出全部分析過程：（1）EE+T | E-T | T（2）TT*F | T/F | F（3）FPF | P（4）P(E) | i實驗內(nèi)容： LL(1)分析法：所謂LL（1）分析法，就是指從左到右掃描輸

2、入串（源程序），同時采用最左推導(dǎo)，且對每次直接推導(dǎo)只需向前看一個輸入符號，便可確定當前所應(yīng)當選擇的規(guī)則。實現(xiàn)LL（1）分析的程序又稱為LL（1）分析程序或LL1（1）分析器。 一個文法要能進行LL（1）分析，那么這個文法應(yīng)該滿足：無二義性，無左遞歸，無左公因子。當文法滿足條件后，再分別構(gòu)造文法每個非終結(jié)符的FIRST和FOLLOW集合，然后根據(jù)FIRST和FOLLOW集合構(gòu)造LL（1）分析表，最后利用分析表，根據(jù)LL(1)語法分析構(gòu)造一個分析器。LL（1）的語法分析程序包含了三個部分，總控程序，預(yù)測分析表函數(shù)，先進先出的語法分析棧，本程序也是采用了同樣的方法進行語法分析，該程序是采用

3、了C語言來編寫。 LL（1）預(yù)測分析程序的總控程序在任何時候都是按STACK棧頂符號X和當前的輸入符號a做哪種過程的。對于任何（X，a），總控程序每次都執(zhí)行下述三種可能的動作之一：  （）若X = a =#，則宣布分析成功，停止分析過程。  （）若X = a #，則把X從STACK棧頂彈出，讓a指向下一個輸入符號。  （）若X是一個非終結(jié)符，則查看預(yù)測分析表M。若MA，a中存放著關(guān)于X的一個產(chǎn)生式，那么，首先把X彈出STACK棧頂，然后，把產(chǎn)生式的右部符號串按反序一一彈出ST

4、ACK棧（若右部符號為，則不推什么東西進STACK棧）。若MA，a中存放著“出錯標志”，則調(diào)用出錯診斷程序ERROR。  事實上，LL（1）的分析是根據(jù)文法構(gòu)造的，它反映了相應(yīng)文法所定義的語言的固定特征，因此在LL（1）分析器中，實際上是以LL（1）分析表代替相應(yīng)方法來進行分析的。 在構(gòu)造LL(1)預(yù)測分析表之前，首先要構(gòu)造該文法的每個非終結(jié)符的FIRST和FOLLOW集合，按照下面描述的算法來構(gòu)造這兩個集合。  FIRST集合的構(gòu)造算法：  （1）若XVT，則FIRST（X）=X。  （2）若XVN，且有產(chǎn)生式X

5、a，則把a加入到FIRST(X)中；若X也是一條產(chǎn)生式，則把也加到FIRST(X)中。  （3）若XY是一個產(chǎn)生式且YVN，則把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若XY1Y2Yk是一個產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對于任何j，1ji-1，F(xiàn)IRST(Yj)都含有（即Y1Yi-1* ），則把FIRST(Yj)中的所有非-元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有，j=1,2,，k，則把加到FIRST(X)中。 連續(xù)使用上面的規(guī)則，直至每個集合FIRST不再增大為止。  FO

6、LLOW集合的構(gòu)造算法：  （1）對于文法的開始符號S，置#于FOLLOW(S)中；  （2）若AB是一個產(chǎn)生式，則把FIRST()| 加至FOLLOW(B)中；  （3）若AB是一個產(chǎn)生式，或AB是一個產(chǎn)生式而 （即FIRST()），則把FOLLOW(A)加至FOLLOW(B)中。  連續(xù)使用上面的規(guī)則，直至每個集合FOLLOW不再增大為止。 現(xiàn)在來構(gòu)造GE的LL（1）預(yù)測分析表。預(yù)測分析表MA, a是如下形式的一個矩陣。A為非終結(jié)符，a是終結(jié)符或#。矩陣元素 M

7、A, a中存放這一條關(guān)于A的產(chǎn)生式，指出當A面臨輸入符號a是所應(yīng)采用的規(guī)則。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;/括號和行數(shù)的對應(yīng)關(guān)系，第一維代表左右6種括號&#

9、160;int static_iden_number = 0;/模擬標志符的地址，自增 /Token節(jié)點   NormalNode * normalHead;/首結(jié)點  /錯誤節(jié)點 struct ErrorNode      char content30;/錯誤內(nèi)容     char describe30;/錯誤描述     int type;     in

10、t line;/所在行數(shù)     ErrorNode * next;/下一個節(jié)點   ErrorNode * errorHead;/首節(jié)點  /標志符節(jié)點 struct IdentiferNode      char content30;/內(nèi)容     char describe30;/描述     int type;/種別碼   

11、60; int addr;/入口地址     int line;/所在行數(shù)     IdentiferNode * next;/下一個節(jié)點  IdentiferNode * idenHead;/首節(jié)點  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)<<"內(nèi)容"<<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; / 回調(diào)字符 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;/ 判斷數(shù)值的情況 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(