WHILE循环语句的翻译程序设计———LL（1）法、三地址表示

本论文在其他论文栏目，由论文格式网整理,转载请注明来源www.lwgsw.com,更多论文,请点论文格式范文查看

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