編譯原理——語法分析

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

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

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

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

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

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

7、A, a中存放這一條關(guān)于A的產(chǎn)生式，指出當(dāng)A面臨輸入符號(hào)a是所應(yīng)采用的規(guī)則。MA, a也可能存放一條“出錯(cuò)標(biāo)志”，指出當(dāng)A根本不該面臨輸入符號(hào)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;/左小括號(hào) int rightSmall = 0;/右小括號(hào) int leftMiddle = 0;/左中括號(hào) int rightMiddle = 0;/右中括號(hào) int leftBig = 0;/左大括號(hào) int rightBig = 0;/右大括號(hào) int lineBra61000 = 0;/括號(hào)和行數(shù)的對(duì)應(yīng)關(guān)系，第一維代表左右6種括號(hào)&#

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

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

11、60; int addr;/入口地址     int line;/所在行數(shù)     IdentiferNode * next;/下一個(gè)節(jié)點(diǎn)  IdentiferNode * idenHead;/首節(jié)點(diǎn)  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"<<" 行號(hào)"<<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; / 連接單詞符號(hào) 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;/ 判斷標(biāo)識(shí)符的情況 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; / 判斷所有沒有歧義的單目運(yùn)算符 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(