WHILE循環語句的翻譯程序設計———LL（1）法、三地址表示

本論文在其他論文欄目，由論文格式網整理,轉載請注明來源www.donglienglish.cn,更多論文,請點論文格式范文查看

1系統描述（問題域描述）
1.1概述
計算機上執行一個高級語言程序一般分為兩步：第一，用一個編譯程序把高級語言翻譯成機器語言程序；第二，運行所得的機器語言程序求得計算結果。
一個編譯程序的工作過程一般可以劃分為五個階段：詞法分析、語法分析、語義分析與中間代碼生成、優化、目標代碼生成。每個階段都是從上一個階段得到結果，對他進行分析，并且根據一些外部環境(例如符號表等)得到最終的輸出結果。要構造一個編譯程序，可以按照這樣的階段來分別構造，最后來連調。
現在人們已經建立了多種編制部分編譯程序或整個編譯程序的有效工具。有些能用于自動生成掃描器(如LEX)，有些可以用于自動產生語法分析器(如YACC)，有些甚至可以用來自動產生整個的編譯程序。這些構造編譯程序的工具成為編譯程序－編譯程序、編譯程序產生器或翻譯程序書寫系統，他們是按照編譯程序和目標語言的形式描述而自動產生編譯程序的。
編譯程序是一極其龐大而又復雜的系統，掌握它比較苦難。但是一旦對其掌握，對以后的程序語言設計，系統軟件分析，系統軟件設計，形式語言研究等方面都是非常有好處的。
先做好前期的設計工作和資料查詢工作，然后著手開始編制代碼。這樣做既可以減少開發周期，提高開發效率，又可以了解一些有關的軟件工程的知識。
1.2 系統功能
本程序通過一種比較具有代表性的語法分析方法----LL(1)分析法進行設計。并對常見的while循環語句（包括布爾表達式，賦值語句）進行分析。能達到如下功能：先完成一個詞法分析，根據自己設定的while循環語句的文法，用LL（1）法對詞法分析產生的單詞序列進行語法檢查，構造預測分析表，并進行語義分析，以三地址碼形式將分析后符合語法的句子輸出。
而且詞法分析器應能識別關鍵字，標示符，常量，操作符等，并將輸出作為語法分析的輸入。

2文法及屬性文法的描述
2．1 While語句的文法
因為用LL(1)法需要文法中沒有左遞歸，所以消除左遞歸后的文法如下：
S-> W (B) A=G
B -> E Y E
Y -> < || = || >
E -> (E) | i | n M
M-> REM|ε
R-> + | - | * | /
A->i
G->E
本While語句文法中的判斷語句總的比較運算符只設計到 < , = , >;賦值語句只有＋，－，×，/ 。
另外文法中的W代表While，Y代表運算符（包括＋，－，×，/）。
2．2屬性文法
產生式屬性文法
S -> while (B) A=G S.begin:=newlabel;
S.next:=newlabel;
B.true:=newlabel;
B.false:=S.next;
S1.next:=S.begin;
S.code:=gen(S.begin, ‘:’) || B.code ||gen(S.true, ‘:’) || S1.code || gen(‘goto’,S.begin) || gen(B.false, ‘:’) || gen(‘goto Lnext’);
B -> E1 Y E2 B.place:=newlabel;
B.code:=E1.code || Y.code ||E2.code ||gen(B.place ‘:=’ , E1.place , Y. place , E2.place);
Y -> < | = | > Y.place:=newlabel;
Y.code:=gen(‘<’)||gen(‘=’)||gen(‘>’);

E -> (E1)M E.place:=newlabel;
E.code:=E1.code ||M.code ||gen(E.place ‘:=’ ,‘(’, E1.place , ‘)’, M.place);
E -> iM E.palce:=newlabel;
E.code:=i.code || M.code || gen(E.palce ‘:=’ ,i.place , M.place);
E -> nM E.place:=newlabel;
E.code:=n.code || M.code || gen(E.place ‘:=’ , n.place ,M.place);
M -> +EM1 M.place:=newlabel;
M.code:=E.code || M1.code || gen(M.place‘:= + ’, E.place , M1.place);
M -> -EM1 M.place:=newlabel;
M.code:=E.code || M1.code ||gen(M.place‘:= - ’, E.place , M1.place);
M -> *EM1 M.place:=newlabel;
M.code:=E.code || M1.code ||gen(M.place‘:= * ’, E.place , M1.place);
M -> /EM1 M.place:=newlabel;
M.code:=E.code || M1.code ||gen(M.place‘:= / ’, E.place , M1.place);
M -> ε M.place:=newlabel;
M.code:=gen(M.code‘:= ε’);
A->i A.place=newlael;
A.code=gen(A.code’:=i’)
G->E G..place=newlabel
G..code=E.code|

3語法分析方法及分析表設計
3.1語法分析法——LL(1)法
3.1.1基本思想
LL(1)法師一種自頂向下的分析方法。從文法的開始符號出發，根據當前的輸入符號(單詞符號)唯一的確定選用哪個產生式替換相應非終結符以往下推導，或如何構造一棵相應的語法樹。該方法的關鍵是要確定唯一的候選式。
LL(1)的含義是：第一個L表明自頂向下分析是從左向右掃描輸入串；第二個L表明分析過程中將用最左推導，1表明只需向右看一個符號便可決定如何推導即選擇哪個產生式進行推導。
3.1.2分析步驟
1 首先要判斷該文法是否是LL(1)文法，需要計算該文法中的非終結符的First集,Follow集，從而計算出產生式的Select集，如果同一個非終結符定義的不同產生式的Select集之間交集為空，就唯一的確定下一個產生式，這樣就不會出向二義性，確保了能夠正確的完成語法分析。
2 構造文法的預測分析表，本文法的預測分析表在下面給出。
3 詞法分析輸出的單詞已經映射成一個個字符，對這些字符構成的字符串進行預測分析。
3.2根據文法得到的預測分析表
While ( ) i n < = > + - * / #
S S->While
(B)
A=G
B  B->EYE  B->EYE B->EYE
A    A->i
G  G->E  G->E G->E
Y      Y->< Y->= Y->>
E  E->(E)M  E->iM E->nM
R         R->+ R->- R->* R->/
M   M->ε      M->REM M->REM M->REM M->REM M->ε
4中間代碼形式的描述及中間代碼序列的結構設計
4.1三地址代碼的描述
在本程序中用到了三地址語句的輸出包括以下的種類：
賦值語句：x:= y Y z
復制語句：x:= y
條件判斷語句： x Y y R z Y q
其中Y代表算術運算符,R代表比較運算符。
4.2本程序中的三地址代碼
S -> while (B) A=G L0:=if (B) goto L1 else goto Lnext
A -> i  A:= i
B -> E Y E  B:= E1 Y E2
Y -> <  Y:= <
Y -> =  Y:= =
Y -> >  Y:= >
E -> (E)M  E1:= (E2) M
E -> iM  E:= i M
E -> nM  E:= n M
M -> +EM  M1:= +E M2
M -> -EM  M1:= -E M2
M -> *EM  M1:= *E M2
M -> /EM  M1:= /E M2
M ->ε  M:= ε
G ->E           G:= E
5簡要的分析與概要設計
5．1簡要分析
首先要進行詞法分析，將.txt文件中得字符串讀出來，分離成一個個的單詞。為了在后面的分析中能夠吧一個單詞當作一個字符來看，詞法分析中要用結構來保存分析出來的單詞。
LL（1）分析方法就是根據文法得出的預測分析表，來確定當棧頂符號遇到符號串的首字符是是否有產生式，用哪個產生式，并要保證唯一性，否則就不是LL(1)文法了。這需要先將 # 和文法開始符號 S 壓入符號棧中，然后判斷棧頂符號和符號串的首字符是否相同。如果相同就消除該符號和字符；否則就著到它們在預測分析表中確定的項（產生式）。將產生式的右部逆序壓入棧中來替換左部（該符號），字符串的當前指針也向后移動一個字符，來表示剩余字符串，然后重新比較棧頂符號和符號串的首字符，只到棧中只剩下＃，這時如果剩余符號串中也只剩下＃就表示該字符串語法正確。然后根據符號串的屬性，分析的結果和符號之間的優先關系按三地址形式輸出。
當然while語句中式可以還有嵌套的while語句的。但這不影響該方法的分析過程的。另外在分析過程中，用一定的格式輸出分析過程，每分析一步就輸出一次，出錯就報告錯誤，這樣就很容易在結果顯示屏幕上看出錯誤發生在哪個地方。
5．2程序的概要設計
本程序的是此案需要依次經過詞法分析，語法分析，語義分析，輸出這些步驟，且每部分的輸出是下個部分的輸入。那我就按該過程來設計程序。用一個函數來進行詞法分析，一個函數進行語法分析，一個函數進行屬性分析以輸出三地址碼。當然還要有讀取文件和輸出的函數，主函數。還要定義個結構來存取單詞的屬性，另外要有單詞的映射函數。
6詳細的算法描述
6.1程序的整體流程：在main()主函數的描述
Void main()                 mian()流程圖：
{
open();
lexical();
pasring();
output();
close();
}

6．2詞法分析算法描述
void lexical()
{                                     //存放輸入字符串和輸出單詞串的文件
  char buffer[MAX];                  //buffer數組存放單詞符號
  char curr;                         //curr存放當前輸入字符
  int c=0;
  do
  {
curr=fgetc(in);
   cout<<curr;
   chuan[c]=curr;
   c++;
  }while(curr!='#');
  rewind(in);                //將文件指針的位置倒回到文件的開頭
  int a=0;
int b=1;
int k=0;
next:
    while(isspace(curr))
    {
    curr=fgetc(in);   //去掉開始的空格
    }
    for(int i=0;i<10;i++)
    {
     if (isalpha(curr) && a==0)        //是字母，存到數組，取下一個
  {
   buffer[i]=curr;
      curr=fgetc(in);
      a=0;
   b=0;
  }
  else if(isdigit(curr))    //是數字，存到數組，取下一個
  {
   buffer[i]=curr;
      a=1;
   curr=fgetc(in);
   b=0;
  }
     else if(isspace(curr))     //是空格，輸出數組，取下一個
  {
      k=i-1;                 //記錄數組的長度
   b=1;
   break;
  }
  else if(ispunct(curr)&& curr!='#') //是符號，輸出數組，取下一個
  {
      if(b==1)             //輸出該符號
   {
            buffer[i]=curr;
         curr=fgetc(in);
      b=1;
      k=i;             //記錄數組的長度
      break;
   }
   if( b==0)          //將前面的內容輸出
   {
            b=1;
      k=i-1;             //記錄數組的長度
      break;
   }
  }
  else if(curr='#')          //控制結束
        return;
  else curr=fgetc(in);
    }
for(int p=0;p<k+1;p++)    //輸出分析的結果
    {
     cout<<"I am here";
    cout<<buffer[p];
    }
    cout<<endl;
  goto next;
}
其中用到庫函數ispunct( )， isalpha( )， isspace( )， isdigit( )來判斷掃描到的字符是符號，字母，空格還是數字。a ,b用來控制分離出來的一個單詞中，開始是數字后面就不能是字母，開始是字母后面可以是數字（如變量T2）。K用來針對遇到空格結束單詞是要將數組的長度減1。
該程序就是對輸入串進行分析，分析到不同的數據類型就相應返回它的機內碼，這樣方便在語法分析中進行分析。本程序還保存了變量和常量在結構數組中，方便在語義分析的時候使用。

6．3 語法分析算法描述
6.3.1主要過程的代碼
void pasring()                //語法分析
{
  int t,n=0,m=0;
  stack_c.push('#');                      //先將#,S存入棧中
  stack_c.push('S');
  topx=stack_c.top();                    //取符號棧頂的符號
     topy=chuan[m];                        //取輸入串首字符
  for(;;)
  {
   print_x();                          //輸出符號棧中的內容
   print_y(m);                         //輸出剩下的輸入串
   if(topx==topy)
   {
    stack_c.pop();                 //相等就消除
    m++;
    cout<<topy<<"匹配";
   }
  if(topx=='S'||topx=='B'||topx=='A'||topx=='G'||topx=='Y'||topx=='E'||top    x=='R'||topx=='M')
   {
    if(topx!='#')
    {
     dingwei();              //找出棧頂符號和首字符對應的位置
     if(table[i][j])                 //如果該位置有產生式
     {
t=13*i+j;                  //計算產生式在數組中的位置
       stack_c.pop();             //將棧頂的符號彈出，移走
       doforpush(t);              //找對應t的產生式，并反向入棧
     }
     else
     {
      cout<<"語法錯誤！"<<endl;
      break;
     }
    }
   }
   cout<<endl;
   if(topx=='#' && topy=='#')
   {
    cout<<"語法正確！"<<endl;
    break;
   }
topx=stack_c.top();
   topy=chuan[m];
  }
}
其中要控制輸出的格式—分析表，這樣便于觀察語法分析的錯誤位置。

6.3.2流程圖如下

6．4 三地址輸出
主要過程代碼：
while(ax[n]!='#')
  {

   while(ax[n]>'a')
   {
    stack_i.push(int_y[m]);
    n++;
    m++;
   }
  if(stack_i.top()>10000) {op22=stack_i.top()-10000+96;}
   op2=stack_i.top();
   stack_i.pop();
     if(stack_i.top()>10000) {op11=stack_i.top()-10000+96;}
    op1=stack_i.top();

   stack_i.pop();
   cout<<"( "<<ax[n]<<" ";
   if(op1<0 && op2>0)
    cout<<'T'<<p-2<<" "<<op2<<" "<<'T'<<p++;
   else if(op2<0 && op1>0)
    cout<<op1<<" "<<'T'<<p-2<<" "<<'T'<<p++;
   else if(op1<0 && op2<0)
    cout<<'T'<<p-3<<" "<<'T'<<p-2<<" "<<'T'<<p++;
   else
    cout<<op1<<" "<<op2<<" "<<'T'<<p++;
   cout<<" )"<<endl;
   stack_i.push(-1);
   ax[n]='i';
   n++;
  }

7程序測試和測試結果
根據文法可以知道它可以對while語句進行嵌套，條件判斷，賦值語句等的語句進行分析。而且賦值語句也可以嵌套。根據這些，我們在選擇測試用例的時候就要選擇比較典型的，盡量找到文法中有但程序中沒能很好實現的地方。
下面就用到了一個簡單的While語句進行分析
輸入字符串：While (a>b) a=a+b #
測試結果：

8研制報告
本次課程設計設計到詞法分析，語法分析和屬性分析，三地址的結構等，內容較多，且有一定的難度，程序中要綜合結構的使用，單詞到字符的映射，棧的使用等。
為了能在短短的4天里完成任務，我就使用了以前實驗時便也得詞法分析程序。并對程序做了個整體分析，設計。先寫出框架，然后再實現具體細節。
本程序主要難點是三地址的輸出。剛開始不會實現，限于時間就參考了同學的設計思想，然后針對自己的程序做了連接。這也是本次編譯原理課程設計中很遺憾的地方。
另外我看見有上屆的學長將編譯原理的詞法分析，語法分析，語義分析，中間代碼生成，語法樹的生成做成一個軟件，用戶只要在輸入框中輸入文法，軟件自動完成文法的檢查，生成預測分析表，再輸入一個句子，軟件自動檢查詞法，語法錯誤，給出分析過程，語法生成樹。實在讓我望塵莫及，只能拿來當作榜樣給自己鼓把勁。
我的程序中也有很多不足，為了減少分析的復雜度，判斷語句中只設計到比較運算符，算術運算符，而且比較運算符只用到了 <, =, >三種，這樣程序的分析范圍就大大減少。所幸還能進行嵌套分析。
這次課程設計年的程序比以往所有課程設計的程序都要復雜，我的變成能力總也算有些提高，這也算是我的收獲了。

9參考文獻
[1]陳火旺，劉春林等著,編譯原理,北京：國防工業出版社，2002.6[2]錢能著,C＋＋程序設計教程,北京：清華大學出版社，2002.7[3]張幸兒，計算機編譯原理—編譯程序構造實踐：科學出版社，2005.7

相關論文


上一篇：發光二極管走馬燈電路的設計與實..	下一篇：艾滋病療法的評價及療效的預測

Tags：WHILE 循環語句翻譯程序設計地址表示

【收藏】【返回頂部】