編譯原理課程設(shè)計-ll1文法分析器設(shè)計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：33 大?。?.65MB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩32頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　編譯原理課程設(shè)計報告　　選題名稱: LL（1）文法分析 　　院（系）: 計算機工程學院　　專業(yè): 計算機科學與技術(shù)　　摘要：選題要求：根據(jù)某一文法編制調(diào)試LL(

2、1) 文法語法分分析程序，以便對任意輸入的符號串進行分析。本次課程設(shè)計的目的主要是加深對預測分析LL(1)文法語法分析法的理解。具體如下：1、對語法規(guī)則有明確的定義；2、編寫的分析程序能夠?qū)o定文法進行正確的語法分析；3、對輸入給定的文法，手工計算FIRST、FOLLOW集合和select集合，應能判斷識別是否為給定文法的句子，并給出推導過程。4、對輸入給定的文法，由程序自動構(gòu)造FIRST、FOLLOW集合。5、對于遇到的語法錯誤，能夠

3、做出簡單的錯誤處理，給出簡單的錯誤提示，保證順利完成語法分析過程。 　　關(guān)鍵詞：語法分析；FIRST集合；FOLLOW集合；分析表　　一、設(shè)計內(nèi)容及要求　　(1) 基于PL/0語言，通過編程判斷該文法是否為LL(1)文法；

4、　　(2)計算出文法的First() Follow()　　(3)構(gòu)造相應文法的預測分析表　　(4)對某個輸入句子進行語法分析　　二、實現(xiàn)原理　　1．LL(1)文法<p

5、>　　LL(1)文法是一類可以進行確定的自頂向下語法分析的文法。就是要求描述語言的文法是無左遞歸的和無回溯的。根據(jù)LL(1)文法的定義，對于同一非終結(jié)符A的任意兩個產(chǎn)生式A:=a和A:=b，都要滿足：SELECT(A：=a )∩SELECT(A:=b)=Ø。　　（1）文法的左遞歸　　當一個文法是左遞歸

6、文法時，采用自頂向下分析法會使分析過程進入無窮循環(huán)之中。所以采用自頂向下語法分析需要消除文法的左遞歸性。文法的左遞歸是指若文法中對任一非終結(jié)符A有推導AA…，則稱該文法是左遞歸的。　　左遞歸又可以分為直接左遞歸和間接左遞歸。　　● 直接左遞歸　　若文法中的某一產(chǎn)生式形如A→A

7、α，α∈V*，則稱該文法是直接左遞歸的。　　消除直接左遞歸的方法：　　設(shè)有產(chǎn)生式是關(guān)于非終結(jié)符A的直接左遞歸：A→Aα|β （α,β∈V*，且β不以A開頭）　　對A引入一個新的非終結(jié)符A′，把上式改寫為：　　A →βA′ <

8、;/p>　　A′→αA′|ε 　　● 間接左遞歸　　若文法中存在某一非終結(jié)符A，使得AA…至少需要兩步推導，則稱該文法是間接左遞歸的。　　消除間接左遞歸的方法：　　【方

9、法一】采用代入法把間接左遞歸變成直接左遞歸。　　【方法二】直接改寫文法：設(shè)有文法G10[S]：　　S→Aα|β ⑴　　A→Sγ ⑵　　因為SAαSγα，所以S是一個間接遞歸的非終結(jié)符。為了消除這種間接左遞歸，將⑵式代入⑴式，即可得到與原文法等價的文法（可

10、以證明）：　　S→Sγα|β ⑶　?、鞘绞侵苯幼筮f歸的，可以采用前面介紹的消除直接左遞歸的方法，對文法進行改寫后可得文法：S→βS′　　S′→γαS′|ε　　2. 計算First集　　(1)

11、若X∈VT ，則First(X)={X}　　(2) 若X∈VN ，且有產(chǎn)生式X→a…, a∈VT則First(X)={X}　　(3) 若X∈VN ，且有產(chǎn)生式X→ε,則First(X)={X}　　(4) 若X，Y1 ，Y2 ，…，Yn 都∈VN，而由產(chǎn)生式X→Y1 Y2 …Yn 。當Y1 ，Y2 ，…，Yi-1

12、都能推導出ε時，（其中1≤i≤n），則First(Y1)-{ε}, First(Y2)-{ε},…, First(Yi)都包含在First(X)中　　(5)當(4)中所有Yi都能推導出ε，（i=1，2，…，n），則First(X)=First(Y1)∪First(Y2)∪…First(Yn)∪{ε}　　反復使用上述步驟直到每個符合的First集合不再增大

13、為止。　　3. 計算Follow集　　對文法中的每個A∈VN，計算Follw(A)：　　(1) 設(shè)S為文法的開始符合，把{#}加入Follow(S)中；　　(2) 若A→αBβ是一個產(chǎn)生式，則把First(β)的非空元素加入Follow(B)中，如果β能推導出ε，則把Fo

14、llow(A)也加入(B)中；　　(3) 反復使用以上步驟直到每個非終結(jié)符號的Follow集不再增大為止。　　4. 預測分析方法　　預測分析方法是自頂向下分析的另一種方法，一個預測分析器是由三個部分組成：預測分析程序；先進后出棧；預測分析表。<p

15、>　　預測分析程序的框圖如下：　　正文：　　1.系統(tǒng)分析　　1.1選題要求　　根據(jù)某一文法編制調(diào)試LL(1) 文法語法分分析程序，以便對任意輸入的符號

16、串進行分析。本次課程設(shè)計的目的主要是加深對預測分析LL(1)文法語法分析法的理解。　　1.2預期目標　　構(gòu)造LL(1)文法語法分析程序，任意輸入一個文法符號串，并判斷它是否為文法的一個句子。程序要求為該文法構(gòu)造預測分析表，并按照預測分析算法對輸入串進行語法分析，判別程序是否符合已知的語法規(guī)則，如果不符合（編譯出錯），

17、則輸出錯誤信息。　　程序流程圖　　2．1.總流程圖　　2.2.First集和Follow集的流程圖　　2.3.預測分析表流程：　　代碼編

18、寫　　3.1檢查左遞歸：　　3.2 first集合　　3.3 follow集合　　3.4 分析表輸出　　4. 程

19、序調(diào)試　　導入正確的文法：　　符合文法的串　　不符合文法的串　　導入有左遞歸的文法：<b&

20、gt;　　串分析：　　總結(jié)　　指導教師評語　　源碼：LL1.h　　#include <iostream>

21、　　#include <cstring>　　#include <cstdlib>　　#include <fstream>　　using namespace std;　　class Parser

22、　　{　　public:　　Parser();　　Parser(const Parser&);　　friend ostream&a

23、mp; operator<<(ostream& output,const Parser& rs);　　friend istream& operator>>(istream& input,Parser& rs);　　int Findid(char);

24、　int Check();　　string Checkstr(string&);　　string Delchar(char,string);　　int Findchar(char,string);　　int StrNum(const string&);&l

25、t;/p>　　char RandChar();　　string GetSub(int,const string&,char);　　Parser& DelLeft(int);　　string First(char);　　strin

26、g First(const string&);　　string Follow(char);　　Parser& FirstAndFollow();　　Parser& CreateTable();　　~Parser();<

27、p>　　char Pop();　　int Mate(char,char);　　char Top();　　char Ip();　　Parser& Push(const string&);　　int Analys

28、is();　　private:　　int num;　　string ter,non,end,stack,instack;　　string *content;

29、;　　string *first;　　string *follow;　　string **table;　　};　　LL1.cpp　　#include &q

30、uot;LL1.h"　　Parser::Parser()　　{　　content=new string[255];　　first=new string[255];　　follow=n

31、ew string[255];　　table=new string *[255];　　}　　Parser::Parser(const Parser& rs)　　{&

32、lt;p>　　ter=rs.ter;　　non=rs.non;　　end=rs.end;　　num=rs.num;　　content=new string[255];　　first=new string[255];</

33、p>　　follow=new string[255];　　table=new string *[255];　　for(int i=0;i<=num;i++)　　content[i]=rs.content[i];　　FirstAndFoll

34、ow();　　CreateTable();　　}　　ostream& operator<<(ostream& output,const Parser& rs)　　{</b&g

35、t;　　output<<"文法內(nèi)容(共"<<rs.num<<"條):"<<endl;　　int i=0;　　while(i<rs.num)&

36、lt;b>　　{　　output<<rs.content[i++]<<endl;　　}　　output<<"結(jié) 終符:"<<rs.ter<<endl;

37、;　　output<<"非結(jié)終符:"<<rs.non<<endl;　　cout<<"非終結(jié)符的FIRST集合 "<<endl;　　for(unsigned int j=0;j<rs.non.size();j++)</p&g

38、t;　　cout<<"FIRST("<<rs.non[j]<<") = {"<<rs.first[j]<<"}\t"<<endl;　　cout<<"非終結(jié)符的FOLLOW集合 "<<endl;<

39、/p>　　for(unsigned int j=0;j<rs.non.size();j++)　　cout<<"FOLLOW("<<rs.non[j]<<") = {"<<rs.follow[j]<<"}\t"<<endl;</

40、p>　　output<<"預測分析表:"<<endl<<"\t";　　for(unsigned int j=0;j<rs.ter.size();j++)　　output<<rs.ter[j]<<"\t"

41、;　　output<<"$"<<endl;　　for(unsigned int j=0;j<rs.non.size();j++)　　{　　output<<rs.non[j]

42、<<"\t";　　for(unsigned int k=0;k<=rs.ter.size();k++)　　cout<<rs.table[j][k]<<"\t";　　output<<endl;<

43、;p>　　}　　return output;　　}　　istream& operator>>(istream& input,Parser& rs)<

44、b>　　{　　unsigned int j=0;　　char filename[255];　　cout<<"請輸入文件名:";　　input>>filename;

45、;　　ifstream infile(filename,ios::in);　　if(!infile){　　cout<<"無法打開文件！"<<endl;　　exit(0);

46、　}　　while(1)　　{ 　　unsigned int i=0;　　infile>>rs.end; 　　rs

47、.content[j++]=rs.end;　　if(infile.eof()) break;　　while(i<rs.end.size())　　{　　if(rs.end[i]=='|'||rs.end[i]==&

48、#39;^');　　else if(i==1||i==2) i++;　　else if(rs.end[i]>='A'&&rs.end[i]<='Z'){　　if(std::string::npos==rs.non.find(rs.end[i]))

49、 rs.non.append(1,rs.end[i]);　　}　　else if(std::string::npos==rs.ter.find(rs.end[i])) rs.ter.append(1,rs.end[i]);　　i++;&l

50、t;/p>　　}　　}　　rs.num=j-1;　　if(rs.Check()==0)　　{<p&g

51、t;　　exit(0);　　}　　rs.FirstAndFollow();　　rs.CreateTable();　　return input;<b&

52、gt;　　} 　　int Parser::Findid(char a)　　{　　int i=0;　　while(i<num)&l

53、t;b>　　{　　if(content[i][0]==a) return i;　　i++;　　}　　return -1;<

54、b>　　}　　char Parser::RandChar()　　{　　switch(rand()%3)　　{　　case 0:r

55、eturn 'A';　　case 1:return 'B';　　case 2:return 'C';　　case 3:return 'D';　　}

56、　　return 'D';　　}　　int Parser::Check()　　{　　unsigned int j=0;&

57、lt;b>　　int i=0;　　while(i<num)　　{　　if(content[i].size()<=3)　　{<p&

58、gt;　　cout<<"文法句"<<content[i]<<"長度不對!"<<endl;　　return 0;　　}　　if(content[i][1

59、]!='-'||content[i][2]!='>') 　　{　　cout<<"文法句"<<content[i]<<"未來使用推導符\"->\"!"<<endl;

60、　　return 0;　　}　　int n=StrNum(content[i]);　　int s=0;　　char

61、z=content[i][0];　　int m=0;　　for(int k=1;k<=n;k++)　　{　　string tmp=GetSub(k,content[i],'|'

62、;);　　if(z==tmp[0])　　{　　s=1;　　m++;　　}<

63、;/p>　　}　　if(m==n)　　{　　cout<<"文法句"<<content[i]<<"將形成無窮

64、推導！"<<endl;　　return 0;　　}　　if(s==1)　　DelLeft(i); <p&g

65、t;　　i++;　　}　　return 1;　　}　　Parser& Parser::DelLeft(int i

66、)　　{　　int n=StrNum(content[i]);　　char c=RandChar();　　char z=content[i][0];　　int s=0;<

67、;/b>　　for(int k=1;k<=n;k++)　　{　　string tmp=GetSub(k,content[i],'|');　　if(z==tmp[0]) s=1;&

68、lt;p>　　}　　if(s==0) return *this;　　cout<<"文法句"<<content[i]<<"含有直接左遞歸,";　　while(1)</b&g

69、t;　　{　　if(Findchar(c,non)==-1) break;　　else c=RandChar();　　}　　cout<<&qu

70、ot;隨機產(chǎn)生非終結(jié)符為:"<<c<<endl;　　non.append(1,c);　　string temp;　　temp+=z;　　temp+="->";</p&g

71、t;　　string next;　　next+=c;　　next+="->";　　for(int k=1;k<=n;k++)　　{</p

72、>　　string t=GetSub(k,content[i],'|');　　if(z==t[0]) 　　{　　t.erase(0,1);　　t+=c;

73、　　next+=t;　　next+='|';　　}　　else　　{</b&

74、gt;　　if(t=="^") t.clear();　　t+=c;　　temp+=t;　　temp+='|';<

75、;b>　　}　　}　　next+='^';　　temp.erase(temp.size()-1,1);　　content[i]=temp;　　num=

76、num+1;　　content[num]=end;　　for(int j=num-1;j>i;j--)　　content[j]=content[j-1];　　content[i+1]=next;　　return *this;

77、　　}　　string Parser::Checkstr(string & a)　　{　　unsigned int i=0,j=0;　　for(;

78、i<a.size();i++){　　for(j=i+1;j<a.size();j++){　　if(a[i]==a[j]){ 　　a.erase(j,1);　　}

79、　}　　}　　return a;　　}　　string Parser::Delchar(char x,string a)

80、;　　{　　int j,i=int(a.size());　　for(j=0;j<i;j++)　　if(a[j]==x)　　a.erase(j,1);

81、;　　return a;　　}　　int Parser::Findchar(char x,string a)　　{　　unsigned int i=0;

82、　　while(i<a.size())　　{　　if(a[i]==x) return i; 　　i++;　　}

83、　　return -1;　　}　　string Parser::GetSub(int i,const string& a,char c='|')　　{

84、　　string ch;　　int j[255];　　int n=1;　　j[0]=2;　　if(i>=int(a.size())) return ch;<p&

85、gt;　　for(unsigned int k=3;k<a.size();k++)　　if(a[k]==c) j[n++]=k;　　for(unsigned int k=j[i-1]+1;k<a.size();k++)　　{

86、;　　if(a[k]==c) break;　　else if(std::string::npos==ch.find(a[k])) ch.append(1,a[k]);　　}　　return ch;　　}</b&

87、gt;　　int Parser::StrNum(const string& a)　　{　　int n=0;　　for(unsigned int i=3;i<a.size();i++)

88、　　if(a[i]=='|') n++;　　return n+1;　　}　　string Parser::First(char x)　　{

89、　　string ch="";　　if(Findchar(x,ter)!=-1) 　　{ ch.append(1,x);　　ch.append(1,' ');　　}&l

90、t;/b>　　else if(Findchar(x,non)!=-1)　　{　　int i=Findid(x);　　if(i!=-1)<b&g

91、t;　　{　　string q=content[i];　　unsigned int k=3;　　while(k<q.size())　　{　　if(q[k-1]==&#

92、39;|'||k==3)　　{　　if(Findchar(q[k],ter)!=-1||q[k]=='^') 　　{　　ch.append(1,q[k]); </p

93、>　　ch.append(1,' ');　　} 　　else 　　{　　if(k==3||q[k+1]=='|'||k=

94、=q.size()-1) ch+=First(q[k]);　　else　　{　　string temp=First(q[k-1]);　　if(Findchar('^',tem

95、p)!=-1) ch+=First(q[k]);　　}　　}　　k++;　　} <

96、b>　　else k++;　　}　　}　　}　　return ch;

97、}　　string Parser::First(const string& a)　　{　　return First(a[0]);　　}<p

98、>　　string Parser::Follow(char x)　　{　　string ch;　　if(Findchar(x,non)!=-1)　　{

99、;　　if(!Findid(x))　　{　　ch+="$";　　ch+=' ';　　}

100、;　　int i=0;　　while(i<num)　　{　　string q=content[i];　　unsigned int k=3;</

101、p>　　char c=content[i][0]; 　　while(k<q.size())　　{　　while(q[k]==x)　　{<

102、/p>　　if(k<q.size()-1&&q[k+1]!='|')　　{　　string temp=Delchar('^',First(q[k+1]));　　if(ch.find(temp)=

103、=string::npos) ch+=temp;　　if(Findchar('^',First(q[k+1]))!=-1)　　{ 　　string follow_c = Follow(c);　　if(ch!=fo

104、llow_c&&ch.find(follow_c)==std::string::npos) 　　ch+=follow_c;　　}　　}　　else if(k==q.size()-

105、1)　　{ 　　string follow_c = Follow(c);　　if(ch.find(follow_c)==std::string::npos) ch+=follow_c;　　} <

106、;/b>　　k++;　　}　　k++;　　}　　i++

107、;　　}　　}　　return ch;　　}　　Parser& Parser::Firs

108、tAndFollow()　　{　　unsigned int i=0;　　while(i<non.size())　　{　　first[i]=First

109、(non[i]);　　follow[i]=Follow(non[i]);　　i++;　　}　　return *this;　　}</

110、b>　　Parser& Parser::CreateTable()　　{　　for(unsigned int i=0;i<=non.size();i++)　　table[i]=new string[255];<

111、;/p>　　for(unsigned int i=0;i<non.size();i++)　　{　　string temp=content[i];　　int w=Findchar(temp[0],this->non);

112、　　int n=StrNum(temp);　　for(int k=1;k<=n;k++)　　{　　string tmp=GetSub(k,temp);　　string fir=First(tmp);<

113、/p>　　for(unsigned int j=0;j<fir.size();j++)　　{　　int idz=Findchar(fir[j],ter);　　if(idz!=-1) 　　table[w

114、][idz]=tmp;　　} 　　if(Findchar('^',fir)!=-1||tmp[0]=='^') 　　{ 　　string fol=Follow(temp[0]);&

115、lt;/p>　　for(unsigned int j=0;j<fol.size();j++)　　{　　int z=Findchar(fol[j],ter);　　if(z==-1) z=int(ter.size());&

116、lt;p>　　table[w][z]=tmp;　　} 　　}　　}　　}<p&g

117、t;　　return *this;　　}　　Parser::~Parser()　　{　　delete[] content;　　delete[] first

118、;　　delete[] follow;　　delete[] table;　　}　　char Parser::Pop()　　{<

119、;p>　　char x=stack[stack.size()-1];　　stack.erase(stack.size()-1,1);　　return x;　　}　　int Parser::M

120、ate(char x,char ip)　　{　　if(Findchar(x,ter)!=-1)　　{　　if(x==ip)<p&

121、gt;　　{　　Pop(); 　　instack.erase(0,1);　　return 1;　　}

122、　　else return 0;　　}　　return 0;　　}　　char Parser::Top()<

123、;p>　　{　　return stack[stack.size()-1];　　}　　char Parser::Ip()　　{&l

124、t;p>　　return instack[0];　　}　　Parser& Parser::Push(const string& rs)　　{　　if(rs.empty())

125、return *this;　　string temp=rs;　　temp.replace(temp.begin(),temp.end(),temp.rbegin(),temp.rend());　　stack.append(temp);　　return *this;<

126、/p>　　}　　int Parser::Analysis()　　{　　stack.append("$");　　char chose;</p&g

127、t;　　cout<<"是否輸入分析串(y or n):";　　cin>>chose;　　while(chose=='y')　　{　　stack+=non

128、[0];　　cout<<"請輸入分析串<退出(q)>：";　　cin>>instack;　　if (instack=="q") exit(0);　　if(instack[instack.size(

129、)-1]!='$') instack+="$";　　int k=1,flag=0; 　　char x=Top();　　char c=Ip();　　cout<<"分析棧\t當前輸入\t動作"<<

130、endl;　　while(x!='$')　　{　　x=Top();　　c=Ip();　　cout&l

131、t;<stack<<"\t"<<instack<<"\t\t";　　if(Findchar(x,ter)!=-1)　　{　　if(Mate(x,c))&

132、lt;b>　　{ 　　k++;　　cout<<"匹配"<<c<<endl;　　}　　else&l

133、t;/b>　　{　　cout<<"["<<k<<"]出錯(終結(jié)符不匹配)！"<<endl;　　flag=1;<p&

134、gt;　　if(x==')') Pop();　　else instack.erase(0,1);　　k++;　　}　　}

135、　　else if(Findchar(x,non)!=-1)　　{　　int idf=Findchar(x,non);　　int idz=Findchar(c,ter);　　if(idz==-1) idz=int(

136、ter.size());　　string temp=table[idf][idz];　　if(temp.empty()) 　　{　　cout<<"["<<k<<"]出錯

137、（"<<c<<"不屬于FIRST("<<x<<")）！"<<endl;　　flag=1;　　instack.erase(0,1);　　k++;<

138、;/b>　　}　　else　　{　　Pop();　　if(temp!=&

139、quot;^") 　　{　　Push(temp);　　cout<<x<<"->"<<temp<<endl;　　}</b&g

140、t;　　else cout<<x<<"->"<<temp<<endl;　　}　　}　　else if(x=='$&

141、#39;&&c=='$')　　{　　if(flag==0) cout<<"正確"<<endl;　　else cout<<"錯誤"<<endl;</p&

142、gt;　　}　　else　　{　　cout<<"["<<k<<"]出錯(未能識別的字符)！"<&

143、lt;endl;　　flag=1;　　instack.erase(0,1);　　k++;　　}

144、}　　}　　}　　int main()　　{　　Parser LL1;&

145、lt;p>　　cin>>LL1;　　cout<<LL1;　　LL1.Analysis();　　return 0;　　}</

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

編譯原理課程設(shè)計-ll1文法分析器設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

編譯原理課程設(shè)計-ll1文法分析器設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

免費下載