編譯原理課程設(shè)計(jì)-ll1文法分析器設(shè)計(jì)_第1頁(yè)
已閱讀1頁(yè),還剩32頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

3、做出簡(jiǎn)單的錯(cuò)誤處理,給出簡(jiǎn)單的錯(cuò)誤提示,保證順利完成語(yǔ)法分析過(guò)程。 </p><p>  關(guān)鍵詞:語(yǔ)法分析;FIRST集合;FOLLOW集合;分析表</p><p><b>  一、設(shè)計(jì)內(nèi)容及要求</b></p><p>  (1) 基于PL/0語(yǔ)言,通過(guò)編程判斷該文法是否為L(zhǎng)L(1)文法; </p><p>

4、  (2)計(jì)算出文法的First() Follow()</p><p>  (3)構(gòu)造相應(yīng)文法的預(yù)測(cè)分析表</p><p>  (4)對(duì)某個(gè)輸入句子進(jìn)行語(yǔ)法分析</p><p><b>  二、實(shí)現(xiàn)原理</b></p><p><b>  1.LL(1)文法</b></p><p

5、>  LL(1)文法是一類可以進(jìn)行確定的自頂向下語(yǔ)法分析的文法。就是要求描述語(yǔ)言的文法是無(wú)左遞歸的和無(wú)回溯的。根據(jù)LL(1)文法的定義,對(duì)于同一非終結(jié)符A的任意兩個(gè)產(chǎn)生式A:=a和A:=b,都要滿足:SELECT(A:=a )∩SELECT(A:=b)=Ø。</p><p><b> ?。?)文法的左遞歸</b></p><p>  當(dāng)一個(gè)文法是左遞歸

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

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

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

9、法一】采用代入法把間接左遞歸變成直接左遞歸。</p><p>  【方法二】直接改寫(xiě)文法:設(shè)有文法G10[S]:</p><p>  S→Aα|β ⑴</p><p>  A→Sγ ⑵</p><p>  因?yàn)镾AαSγα,所以S是一個(gè)間接遞歸的非終結(jié)符。為了消除這種間接左遞歸,將⑵式代入⑴式,即可得到與原文法等價(jià)的文法(可

10、以證明):</p><p>  S→Sγα|β ⑶</p><p> ?、鞘绞侵苯幼筮f歸的,可以采用前面介紹的消除直接左遞歸的方法,對(duì)文法進(jìn)行改寫(xiě)后可得文法:S→βS′</p><p><b>  S′→γαS′|ε</b></p><p>  2. 計(jì)算First集</p><p>  (1)

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

12、都能推導(dǎo)出ε時(shí),(其中1≤i≤n),則First(Y1)-{ε}, First(Y2)-{ε},…, First(Yi)都包含在First(X)中</p><p>  (5)當(dāng)(4)中所有Yi都能推導(dǎo)出ε,(i=1,2,…,n),則First(X)=First(Y1)∪First(Y2)∪…First(Yn)∪{ε}</p><p>  反復(fù)使用上述步驟直到每個(gè)符合的First集合不再增大

13、為止。</p><p>  3. 計(jì)算Follow集</p><p>  對(duì)文法中的每個(gè)A∈VN,計(jì)算Follw(A):</p><p>  (1) 設(shè)S為文法的開(kāi)始符合,把{#}加入Follow(S)中;</p><p>  (2) 若A→αBβ是一個(gè)產(chǎn)生式,則把First(β)的非空元素加入Follow(B)中,如果β能推導(dǎo)出ε,則把Fo

14、llow(A)也加入(B)中;</p><p>  (3) 反復(fù)使用以上步驟直到每個(gè)非終結(jié)符號(hào)的Follow集不再增大為止。</p><p><b>  4. 預(yù)測(cè)分析方法</b></p><p>  預(yù)測(cè)分析方法是自頂向下分析的另一種方法,一個(gè)預(yù)測(cè)分析器是由三個(gè)部分組成:預(yù)測(cè)分析程序;先進(jìn)后出棧;預(yù)測(cè)分析表。</p><p

15、>  預(yù)測(cè)分析程序的框圖如下:</p><p><b>  正文:</b></p><p><b>  1.系統(tǒng)分析</b></p><p><b>  1.1選題要求</b></p><p>  根據(jù)某一文法編制調(diào)試LL(1) 文法語(yǔ)法分分析程序,以便對(duì)任意輸入的符 號(hào)

16、串進(jìn)行分析。本次課程設(shè)計(jì)的目的主要是加深對(duì)預(yù)測(cè)分析LL(1)文法語(yǔ)法分析法的理解。</p><p><b>  1.2預(yù)期目標(biāo)</b></p><p>  構(gòu)造LL(1)文法語(yǔ)法分析程序,任意輸入一個(gè)文法符號(hào)串,并判斷它是否為文法的一個(gè)句子。程序要求為該文法構(gòu)造預(yù)測(cè)分析表,并按照預(yù)測(cè)分析算法對(duì)輸入串進(jìn)行語(yǔ)法分析,判別程序是否符合已知的語(yǔ)法規(guī)則,如果不符合(編譯出錯(cuò)),

17、則輸出錯(cuò)誤信息。</p><p><b>  程序流程圖</b></p><p><b>  2.1.總流程圖</b></p><p>  2.2.First集和Follow集的流程圖</p><p>  2.3.預(yù)測(cè)分析表流程:</p><p><b>  代碼編

18、寫(xiě)</b></p><p><b>  3.1檢查左遞歸:</b></p><p>  3.2 first集合</p><p>  3.3 follow集合</p><p><b>  3.4 分析表輸出</b></p><p><b>  4. 程

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

20、gt;  串分析:</b></p><p><b>  總 結(jié)</b></p><p><b>  指導(dǎo)教師評(píng)語(yǔ)</b></p><p><b>  源碼:LL1.h</b></p><p>  #include <iostream></p>

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

22、<p><b>  {</b></p><p><b>  public:</b></p><p><b>  Parser();</b></p><p>  Parser(const Parser&);</p><p>  friend ostream&a

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

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

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

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

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

28、is();</p><p><b>  private:</b></p><p><b>  int num;</b></p><p>  string ter,non,end,stack,instack;</p><p>  string *content;</p><p>

29、;  string *first;</p><p>  string *follow;</p><p>  string **table;</p><p><b>  };</b></p><p><b>  LL1.cpp</b></p><p>  #include &q

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

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

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

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

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

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

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

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

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

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

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

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

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

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

44、b>  {</b></p><p>  unsigned int j=0;</p><p>  char filename[255];</p><p>  cout<<"請(qǐng)輸入文件名:";</p><p>  input>>filename;</p><p>

45、;  ifstream infile(filename,ios::in);</p><p>  if(!infile){</p><p>  cout<<"無(wú)法打開(kāi)文件!"<<endl;</p><p><b>  exit(0);</b></p><p><b> 

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

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

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

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

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

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

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

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

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

55、eturn 'A';</p><p>  case 1:return 'B';</p><p>  case 2:return 'C';</p><p>  case 3:return 'D';</p><p><b>  }</b></p>

56、<p>  return 'D';</p><p><b>  }</b></p><p>  int Parser::Check()</p><p><b>  {</b></p><p>  unsigned int j=0;</p><p>&

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

58、gt;  cout<<"文法句"<<content[i]<<"長(zhǎng)度不對(duì)!"<<endl;</p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  if(content[i][1

59、]!='-'||content[i][2]!='>') </p><p><b>  {</b></p><p>  cout<<"文法句"<<content[i]<<"未來(lái)使用推導(dǎo)符\"->\"!"<<endl;

60、</p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  int n=StrNum(content[i]);</p><p><b>  int s=0;</b></p><p>  char

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

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

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

64、推導(dǎo)!"<<endl;</p><p><b>  return 0;</b></p><p><b>  }</b></p><p><b>  if(s==1)</b></p><p>  DelLeft(i); </p><p&g

65、t;<b>  i++;</b></p><p><b>  }</b></p><p><b>  return 1;</b></p><p><b>  }</b></p><p>  Parser& Parser::DelLeft(int i

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

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

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

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

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

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

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

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

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

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

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

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

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

79、 }</b></p><p><b>  }</b></p><p><b>  return a;</b></p><p><b>  }</b></p><p>  string Parser::Delchar(char x,string a)</p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

96、b>  else k++;</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  return ch;</p><p><b>  

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

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

99、;  if(!Findid(x))</p><p><b>  {</b></p><p><b>  ch+="$";</b></p><p><b>  ch+=' ';</b></p><p><b>  }</b>

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

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

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

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

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

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

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

107、;</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  return ch;</p><p><b>  }</b></p><p>  Parser& Parser::Firs

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

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

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

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

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

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

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

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

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

117、t;  return *this;</p><p><b>  }</b></p><p>  Parser::~Parser()</p><p><b>  {</b></p><p>  delete[] content;</p><p>  delete[] first

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

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

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

121、gt;<b>  {</b></p><p><b>  Pop(); </b></p><p>  instack.erase(0,1);</p><p><b>  return 1;</b></p><p><b>  }</b></p>

122、<p>  else return 0;</p><p><b>  }</b></p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  char Parser::Top()</p><

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

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

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

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

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

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

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

130、endl;</p><p>  while(x!='$')</p><p><b>  {</b></p><p><b>  x=Top();</b></p><p><b>  c=Ip();</b></p><p>  cout&l

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

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

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

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

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

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

137、("<<c<<"不屬于FIRST("<<x<<"))!"<<endl;</p><p><b>  flag=1;</b></p><p>  instack.erase(0,1);</p><p><b>  k++;<

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

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

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

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

142、gt;<p><b>  }</b></p><p><b>  else</b></p><p><b>  {</b></p><p>  cout<<"["<<k<<"]出錯(cuò)(未能識(shí)別的字符)!"<&

143、lt;endl;</p><p><b>  flag=1;</b></p><p>  instack.erase(0,1);</p><p><b>  k++;</b></p><p><b>  }</b></p><p><b>  

144、}</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  int main()</p><p><b>  {</b></p><p>  Parser LL1;</p>&

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

溫馨提示

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

評(píng)論

0/150

提交評(píng)論