条件语句的翻译分析程序设计
        --LR方法、输出四元式
1.问题描述
对条件语句：  if 〈布尔表达式〉〈赋值语句〉  else 〈赋值语句〉， 进行词法，语法分析，并根据语法制导翻译方法将条件语句翻译成四元式中间代码形式，最后输出翻译后的四元式代码。
2.文法及属性文法描述
2.1 if-else语句的LR文法：
采用LR方法，因此可以得到如下文法：
G[S]： S→if(B) S else S
            S→if(B)S
            S→i=E
            B→B&&B
B→B||B
B→!B
B→E relop E
            E→E+E
      　E→E*E
      　E→-E
      　E→(E)
      　E→i
  其中relop是终结符号，代表关系运算符<,<=,>,>=,!=等。
  通过一遍扫描来产生布尔表达式和控制语句的代码的主要问题在于，当生成某些转移语句时还不知道该语句将要转移到的目标是什么。为了解决这个问题，可以在生成形式分之的跳转指令时暂时不确定跳转目标，而建立一个链表，把转向这个目标的跳转指令的标号键入这个链表。一旦目标确定后再把
它填入有关的跳转指令中，因此将上述文法扩展为：
      P→SM
      S→if(B)M1S1NelseM2S2
      S→if(B)MS1
      S→i=E
      B→B1&&MB2
      B→B1||MB2
      B→!B1
      B→E1 relop E2
      E→E1+E2
      E→E1*E2
      E→-E1
      E→(E1)
      E→i
      M→￠  ；代表的是空
    N→￠  ；代表的是空
2.2 if-else语句的LR属性文法：
    由以上扩展的文法可得到如下的属性文法：
P→SM             
  　{list!=￠) then list, M.pos);
  　}
S→if(B)M1S1NelseM2S2
{uelist,M1.pos);
backpatch(B.falselist,M2.pos);
}
S→if(B)MS1           
{uelist,M.pos);
}
S→i=E   
  　{p=lookup(i.name);
    if(p!=Null then genquad("=",E.place,"",p.place);
  　}
  　B→B1&&MB2       
  　{ uelist, M1.pos);
    B.truelist=B2 .truelist;
    B.falselist=merge(B1.falselist, B2.falselist);
    }
  　B→B1||MB2           
{backpatch(B1.falselist, M1.pos);
  　B.falselist=uelist);
  　B.falselist=B2.falselist;
  　}
B→!B1
    {B.truelist=B1.falselist;
B.falselist= B2.falselist;
  　}
    B→E1 relop E2
  { B.truelist=makelist(nexpos+1);
    B.false=makelist(nextpos+2);
    genquad(relop, E1.place, E2.pl
ace,"_");
    genquad("J","","","_"); 
}
    E→E1+E2
    { e=newtemp;
      e.place=E1.place+E2.place;
    genquad("+", E1.place, E2.place,e.place);
}
    E→E1*E2
  { e=newtemp;
    e.place=E1.place*E2.place;
genquad("*", E1.place, E2.place,e.place);
}
    E→-E1
{ e=newtemp;
e.place=－E.place;
  　genquad("uminus", E.place, "",e.place);
}
    E→(E1)
  {E.place=E1.place;
}
    E→i
    {E.place=i.value;
    }   
    M→￠ 
{M.pos=nextpos+1;
}
  　N→￠ 
  　{ N.next=makelist(nextpos+1);
    genquad("J","","","_");
  　}
  其中relop可为任意的关系运算符，i可以为标识符，也可以为常数。M以及N是为了便于分析生成四元式而设的。
3. 语法分析方法及中间代码形式的描述
3.1 LR方法的基本思想
  一个LR分析器实质上是一个带先进后出存储器的确定有限状态自动机。我们将把"历史"和"展望"材料综合地抽象成某些"状态"。分析栈用来存放状态。栈里的每个状态概括了从分析开始直到某一归约阶段的全部"历史"和"展望"资料。任何时候，栈顶的状态都代表了整个的历史和已推测出的展望。因此，在任何时候都可从栈顶状态得知所想了解的一切，而绝对没有必要从称底而上翻阅整个栈。LR分析器的每一步工作都是由栈顶
状态和现行输入符号所唯一决定的。为了有助于明确归约手续，我们把已归约出的文法符号串也同时放在栈里。于是，我们可以把栈的结构看成是:
栈的每一项内容包括状态S和文法符号X两部分。（S0，#）为分析开始前预先放到栈里的初始状态和句子括号。栈顶状态为SM，符号串XM是至今已移进归约出的部分。
3.2 LR分析器模型
  LR分析器模型如下图:
LR分析器的核心部分是一张分析表。这张分析表包括两部分，一是"动作"（ACTION）表，另一个是"状态转换表"（GOTO）表。它们都是二维数组。ACTION[s，a]规定了当状态s面临输入符号a时应采取什么动作。GOTO[s，a]规定了状态s面对文法符号X（终结符或非终结符）时下一个状态是什么。显然GOTO[S，x]定义了一个以文法符号为字母表的DFA。
每一项ACTION[s，a]所规定的动作不外是下述四种可能之一：
1. 移进  把（S，A）的下一状态S＝GOTO[S，A]和输入符号A推进栈，下一输入符号变成现行输入状态。
2. 规约  指用某一产生式A－> 进行规约。假若 的长度为r，归约动作是A，去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把（Sm-r，A）的下一状态S1＝GOTO[Sm-r,A]和文法符号A推进栈。归约动作不改变现行输
入符号。执行归约动作意味着（＝Xm）已呈现于栈顶而且是一个相对于A的句柄。
3. 接受  宣布分析成功，停止分析器的工作。
4. 报错  发现源程序含有错误，调用出错处理程序。
LR分析器的总控程序本身的工作是非常简单。它的任何一步只需要按栈顶状态和现行输入符号a执行ACTION[S，a]所规定的动作。不管什么分析表，总控程序都是一样地工作。
一个LR分析器的工作过程可看成是栈里的状态序列，已归约串和输入串所构成的三元式的变化过程。分析地的初始三元式（S0,#,an#）其中，S0为分析器的初态；#为句子的左括号；an为
输入串；其后的#为结束符。分析过程每步的结果可表示为（sm,# ,ai....an#）分析器的下一步动作是由栈顶状态Sm和现行输入符号ai所唯一决定。即，执行ACTION[Sm,ai]所规定的动作。经执行每种可能的动作之后，三元式的变化的情形是：
（1） 若ACTION[Sm,ai]为移进，且S=GOTO[Sm,ai]，则三元式变成：
（Sm,#Xmaian#）
（2） 若ACTION[Sm,ai]＝{A－> }，则按产生式A－> 进行归约。此时三元式变为
(Sm-rS,#X1...Xm-rA,an#)
此处S ＝GOTO[Sm-r,A]，r为 的长度， ＝Xm。
（3） 若ACTION[Sm,ai]为：接受，则三元式不再变化，变化过程终止，宣布分析成功。
（4） 若ACTION[Sm,ai]为"报错"，则三元式的变化过程终止，报告错误。
一个LR分析器的工作过程就是一步一步地变换三元式，直至执行"接受"或"报错"为止。
3.3对中间代码四元式的描述
一个四元式是一个带有四个域的记录结构，这四个域分别称为op、arg1、arg2及result。域op包含一个代表运算符的内部码。三地址语句x=y op z可以表示为：将y 置于arg1域,z置于 arg2域， x置于 result域， =为运算符。带有一元运算符的语句如 x=-y或者 x=y的表示中不用 arg2。条件和无条件转移语句将目标标号置于 result域中。通常，四元式中的arg1,arg2和result的内容都是一个指针，此指针指向有关名字的符号表示入口。这样，临时变量名也要填入符号表。
例如对于条件语句if(a>b) c=d+f；对应的一串四元式为：
Op arg1 arg2 result (0)
(1)
(2)
(3)
(4)      J>
J
+
=
a
d
T1
b
f
(2)
(4)
T1
c
表一    四元式
4.简要的分析与概要设计
本课程设计需要写一个条件语句的LR文法及其属性文法，运用LR分析方法对此文法进行语法和语义分析，中间代码采用四元式输出。在这个条件语句的翻译分析程序设计中，主要通过以下四个过程来完成：
  1.词法分析。由于编译程序是在单词的级别上来分析和翻译源程序的，那么在这里，词法分析的任务是：从左至右逐
个字符地对源程序进行扫描，产生一个一个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。所以词法分析是编译的基础。在此程序中是将词法分析作为一遍处理的，通过一次分析把全部的字符串都分析完成，并将其保存在数组中便于下一步进行语法分析。 
2.语法分析。在完成词法分析的基础上对条件语句进行语法分析，在这里我采用了自下而上分析法LR(1)分析方法，来分析判定程序的语法结构是否符合语法规则，在分析前首先要构造LR(1)分析表，然后在进行语法分析，在此程序中，以'；'为结束符号来判断一条条的条件语句，并且独立的对每条语句进行语法分析，若分析正确便在DOS环境下显示"一个条件语句的分析完成！！！"，若语法分析错误，便会输出"ERROR"。
  3.语义分析、输出四元式。在进行语法分析的同时进行语义分析，在此次设计中式将二者结合起来作为一遍进行处理的。在进行语义时同时生成中间语言四元式。
  4.出错处理。如果在词法分析时遇到非法字符就会输出出错信息，同时输出从出错点开始往后的一串字符，但是它仍然能跳过该非法字符继续分析；如果在语法分析中有错误的话，就会显示在DOS环境下输出"ERROR"，但是它能跳过出错的地方继续往后执行，分析出一部分结果并保存在文件中。
5.详细的算法描述
5.1词法分析：
本程序中，选用C程序设计语言的部分常用的单词作为词法分析的对象，词法分析后，将识别的所有单词符号以及相关信息保存在数组中，以便后面语法分析和语意分析及中间代码生成使用，同时将识别出的单词符号输出到文件中，一便进行查看。
词法分析过程过程中采用了三个数组保存分析的结果，定义如下：
struct mymap
{ int code,value;
};
string *var=new string[20];//保存标识符
float  *myconst=new float[20];//保存常数
mymap *result=new mymap[40];//code用来保存所识别的单词的机内码，当该单词为标识符或常数时，value保存该标识符或常数在标识符数组或常数数组中的下标，而当该单词为其它的关键字时，value的值为0。
该词法分析程序从文件进行输入，词法分析中各个函数描述如下：
void renewresult()；
当result数组空间满时，对其重新分配，并保存一以前的值。
void renewvar()；
当var数组空间满时，对其重新分配，并保存一以前的值。
void renewconst()；
当myconst数组空间满时，对其重新分配，并保存一以前的值。
bool isletter(char c)；
判断当前输入的字符是否为字母。
bool isdigital(char c)；
判断当前输入的字符是否为数字。
int reserve(char c[],int i)；
查保留字表，并返回它的编码，否则返回0。
void insertresult(int code,int value)；
将当前识别出的单词的种别编码和其值保存到result数组中。如果该单词为标识符或常数，则其value值为其在var或myconst数组中的下标，否则其值为0。
void insertid(char c[],int i)；
将当前识别出的标识符保存到数组var中，并将其下标保存到数组result的value中。
void insertconst(char c[],int i)；
将当前识别出的常数保存到数组myconst中，并将其下标保存到数组result的value中。
void wordanalyse()；
词法分析的总控函数，控制整个词法分析过程。
5.2语法分析：
在做语法分析时首先要构造条件语句的LR(1)分析表，此表为：
ACTION GOTO  if  ( ) else = && || ! relop + * - i ； P S B E M N 0 S3            S4  1 2    1              acc      2 r14            r14 r14    5  3  S6                  4    S7                5              r1      6  S12      S9  S11 S13    8 10  7  S12          S11 S13    14  8  S15    S16 S17        18 10  9  S12      S9  S11 S13        10          S19 S20 S21        11  S12          S11 S13    22  12  S12          S11 S13    23  13  r13 r13  r13 r13  r13 r13 r13 r13  r13      14    r4      S20 S21  r4      15 r14            r14 r14    24  16 r14            r14 r14    25  17 r14            r14 r14    26  18      r7 r7              19  S12          S11 S13    27  20  S12          S11 S13    28  21  S12          S11 S13    29  22  r11 r11  r11 r11  r11 r11 r11  r11      23  S30      S20 S1          24 S3            S4  31    25  S12      S9    S11 S13  32 10  26  S12      S9    S11 S13  33 10  27  r8  r8 r8  S
20 S21          28  r9 r9  r9 r9  r9 r9 S21          29  r10 r10  r10 r10  r10 r10 r10  r10      30  r12 r12  r12 r12  r12 r12 r12  r12      31    r15          r3      34 32  r5  r5 r5              33  r6  S16 r6              34    S35                35 r14            r14 r14    36  36 S3            S3  37    37    r2          r2        此表中引用记号的意义是：
（1）sj          把下一状态j和现行输入符号a移进栈；
（2）rj          按第j个产生式进行规约；
（3）acc        接受；
（4）空白格      出错标志，报错；
在做语法分析时，需对此表进行编码并用数组table[38][20]保存，其中将错误即空白格设为100，而将接受设为110，对于状态就按表中的数字表示，而规约所需的产生式编码为从61到75分别对应15条产生式。
语法分析中的输入为词法分析的结果，即上述的三个数组，现将语法分析中所用到的数据结构和函数描述如下：
struct analyse
  {  int state;
char sign;
};//该结构体即为分析栈的结构，state表示当前的状态，sign表示当前的单词的种别编码。
int tindex2(int c)；
该函数接受单词的种别编码，返回该单词在tabel数组中的第二维下标。
void tiaojian()；
该函数为条件语句的总控函数，识别所有的单词利用分析表，应用LR分析法对输入的单词进行移入和规约，以及错误处理。
void phraseanalyse()；
该函数为语法分析函数，函数tiaojian()只能分析一条条件语句，而利用此函数调用函数tiaojian()可以实现多条条件语句的语法分析。
5.3语义分析
  语义分析是和语法分析同时进行的，在进行语法分析遇到规约项目时就调用对应的语义分析函数进行语义分析并同时生成四元式。
现将语义分析中所用到的数据结构和函数描述如下：
      struct list
  { int value;
      struct list *next;
  };//该结构体用于定义以下的栈，做回填时用。
  stack<list *> stknext;//保存当前还未回填的所有链表的头指针。
  stack<list *> stktrue;//保存当前还未回填的所有链表的头指针。
  stack<list *> stkfalse;//保存当前还未回填的所有链表的头指针。
  stack<int> stkpos;//保存当前还未回填的M的值。
  stack<mymap> stktemp;//保存常量，变量以及临时变量
  mymap gen[100][4];//保存生成的四元式。
  使用栈结构可以保证当前进行规约的所有的信息都在栈的顶部，然后将规约后的信息再保存到栈顶，以便下一次进行规约。
  void backpatch(list *list1,int t)；
  该函数的功能完成"回填"，把list1所链接的每个四元式的第四区段都填为t.编程语言翻译
  list* mymerge(list *list1,list *list2)；
  该函数的功能把以list1和list2为链首的两条链合并为一，作为函数值，回送合并后的链首。
  void tiaojian_1()； 
  该函数实现产生式P->SM的语义分析及四元式的生成。
  void tiaojian_2()；
该函数实现产生式S->if ( B ) M1 S1 N else M2 S2的语义分析及四元式的生成。
  void tiaojian_3()； 
  该函数实现产生式S->if ( B ) M S1的语义分析及四元式的生成。
  void tiaojian_4()； 
  该函数实现产生式S->i=E的语义分析及四元式的生成。
  void tiaojian_5()；
  该函数实现产生式B->B1 && M B2的语义分析及四元式的生成。
  void tiaojian_6()； 
  该函数实现产生式B->B1 || M B2的语义分析及四元式的生成。
  void tiaojian_7()； 
  该函数实现产生式B->!B1的语义分析及四元式的生成。
  void tiaojian_8()； 
  该函数实现产生式B->E1 relop E2的语义分析及四元式的生成。
  void tiaojian_9()；   
  该函数实现产生式E->E1+E2的语义分析及四元式的生成。
  void tiaojian_10()；   
  该函数实现产生式E->E1*E2的语义分析及四元式的生成。
  void ti

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。