【编译原理】语义分析S属性定义的自下而上计算

小果果学长 等级 280 0 0

目录

一、实验目的

二、实验任务

三、实验原理

四、实验过程

五、实验结果

参考资料

附录

1 C++运行代码

3 Python运行代码

3 'wx.txt'内容


一、实验目的

掌握S属性定义的自下而上计算。

二、实验任务

针对表达式文法实现S属性定义的自下而上计算。以S属性的语法制导定义为基础,将下表(教材表4.1)的语义规则嵌套在自下而上的语法分析的过程中,即实现语法制导的翻译过程。

表 2.1:简单计算器的语法制导定义

【编译原理】语义分析S属性定义的自下而上计算

三、实验原理

属性定义的翻译器可以借助_LR_分析器的生成器来实现,如Yacc。根据S属性定义,分析器的生成器可以构造出翻译器,它在分析输入时计算属性。自下而上分析器用栈来保存已分析子树的信息。可以在分析栈中增加一个域来保存综合属性值,如下图所示。

假设拓展后的分析栈由状态数组_state_和值数组_val_实现,_state_的每个条目是_LR(1)_分析表的指针或下标(文法符号隐含在状态里,无需存放在栈中),但为直观起见,用文法符号来代替状态,这也就是分析栈中被状态盖住的那个符号。_val_数组为文法符号存放的综合属性。如果_state_的第i个符号是A,那么_val[i]_保存对应这个的分析树结点的属性值。栈顶由指针_top_指示,并假定综合属性刚好在每步归约前计算。若产生式_A__→XYZ_的语义规则是_A.a__=f(X.x,Y.y,Z.z)_,那么在_XYZ_归约成A之前,属性_Z.z_的值在_val[top]Y.y_的值在_val[top-1]X.x_的值在_val[top-2]_。如果某个符号没有属性,那么_val_数组对应条目没有定义。归约后,_top_的值减2,覆盖的状态放进_state[top]_(即X原来的位置),综合属性的值_A.a_放进_val[top]_。

【编译原理】语义分析S属性定义的自下而上计算

图 3.1:有综合属性域的分析栈

针对表2.1的台式计算器的语法制导定义,首先构造基础文法的LR分析器。为了计算属性,需要修改分析器,让它在归约前执行表2.1的语义动作,这些语义动作可以翻译成下表的栈操作代码段。这些代码段实际上就是用属性在栈中(_val_数组)的位置代替表2.1语义规则的属性得到的。

注:这里val_为_stack.val_,如_val[top-2]=stack[top-2].val.

表 3.1:用LR分析器实现计算器

【编译原理】语义分析S属性定义的自下而上计算

四、实验过程

以词法分析和语法分析部分的上机结果为基础,添加语义分析部分。即以LR文法为基础。当进行产生式归约时执行对应的语义动作。具体代码详见附录1(C++编程)和附录2(python编程)。下面简单介绍python编程的主要思路:

先把式子转化为(i+i)*i+i*i+i的形式,并把对应的数字放入数字表中,并使用指针ip指向第一个(使用正则表达式匹配数字)。

1. 定义一个符号栈(以下简称栈)和一个数字栈,其中符号栈存状态和非终结字符,数字栈存运算过程中产生的中间结果;

2. 设当前指向((i+i)*i+i*i+i)的字符为x,符号栈的栈顶状态为a:

(1)如果action[a][x]是si,则表示移进,并把x和i入栈,x指向原串的下一个字符;

(2)如果action[a][x]是acc,则表示完成,此时数字栈中仅有一个元素且为最终结果,退出即可;

(3)如果action[a][x]是ei,则表示出某错,对错误类型就行修正后继续执行:

Error 1):缺少i,入栈i和状态5;

Error 2): 多余右括号,x指向下一个(跳过右括号);

Error 3): 缺少+,入栈+和状态6;

Error 4): 缺少右括号,入栈右括号和状态11。

(4) 如果action[a][x]是ri,则表示规约:

出栈的次数为第i个产生式右端长度的二倍,出栈后把第i个产生式左部的符号入栈。

r1:把数字栈的出栈两次,弹出的两个数字相加并放入数字栈;

r3:把数字栈的出栈两次,弹出的两个数字相乘并放入数字栈;

r6:把数字表(正则表达式得到的)的ip指向的数字入栈,ip指向下一个。

3. 分析结束。

五、实验结果

运行程序,翻译器执行8+5*2时的动作如下所示,和教材中提供的翻译器执行动作相同(下表5.1为教材表4.5)。

表5.1:翻译器面临8+5*2时的动作

【编译原理】语义分析S属性定义的自下而上计算

【编译原理】语义分析S属性定义的自下而上计算

图 5.1:C++程序运行截图

【编译原理】语义分析S属性定义的自下而上计算

图 5.2:python运行截图

输入表达式:8+5*2$

该式的原型为:

a + a * a $

---------------

此时栈定状态为:0  此时输入字符为:a

--移进--

将状态5移进栈。

--------------------------------------

此时栈定状态为:5  此时输入字符为:+

--按F->id规约--

弹栈2次后,栈顶状态为0

放入F

将状态3移进栈。

放入8

--------------------------------------

此时栈定状态为:3  此时输入字符为:+

--按T->F规约--

弹栈2次后,栈顶状态为0

放入T

将状态2移进栈。

--------------------------------------

此时栈定状态为:2  此时输入字符为:+

--按E->T规约--

弹栈2次后,栈顶状态为0

放入E

将状态1移进栈。

--------------------------------------

此时栈定状态为:1  此时输入字符为:+

--移进--

将状态6移进栈。

--------------------------------------

此时栈定状态为:6  此时输入字符为:a

--移进--

将状态5移进栈。

--------------------------------------

此时栈定状态为:5  此时输入字符为:*

--按F->id规约--

弹栈2次后,栈顶状态为6

放入F

将状态3移进栈。

放入5

--------------------------------------

此时栈定状态为:3  此时输入字符为:*

--按T->F规约--

弹栈2次后,栈顶状态为6

放入T

将状态9移进栈。

--------------------------------------

此时栈定状态为:9  此时输入字符为:*

--移进--

将状态7移进栈。

--------------------------------------

此时栈定状态为:7  此时输入字符为:a

--移进--

将状态5移进栈。

--------------------------------------

此时栈定状态为:5  此时输入字符为:$

--按F->id规约--

弹栈2次后,栈顶状态为7

放入F

将状态10移进栈。

放入2

--------------------------------------

此时栈定状态为:10  此时输入字符为:$

--按T->T*F规约--

弹栈6次后,栈顶状态为6

放入T

将状态9移进栈。

弹出了2  5,放入10

--------------------------------------

此时栈定状态为:9  此时输入字符为:$

--按E->E+T规约--

弹栈6次后,栈顶状态为0

放入E

将状态1移进栈。

弹出了10  8,放入18

--------------------------------------

此时栈定状态为:1  此时输入字符为:$

接受

结果为:18

参考资料

  1. 语法制导的翻译(C++):https://www.helloworld.net/redirect?target=https://blog.csdn.net/shl_shl/article/details/53535809
  2. Python实现:https://www.helloworld.net/redirect?target=https://blog.csdn.net/qq_36614557/article/details/85848199

附录

1 C++运行代码

#include <iostream>

#include <string.h>

#include<stack>

using namespace std;

/*

E->E+T

E->T

T->T*F

T->F

F->(E)

F->id

*/

/*初始化分析表*/

void Initial(string analysis[12][9]){

         /*移进规约*/

         analysis[0][0] = "s5"; analysis[0][3] = "s4"; analysis[0][6] = "1"; analysis[0][7] = "2"; analysis[0][8] = "3";

         analysis[1][1] = "s6"; analysis[1][5] = "acc";

         analysis[2][1] = "r2"; analysis[2][2] = "s7"; analysis[2][4] = "r2"; analysis[2][5] = "r2";

         analysis[3][1] = "r4"; analysis[3][2] = "r4"; analysis[3][4] = "r4"; analysis[3][5] = "r4";

         analysis[4][0] = "s5"; analysis[4][3] = "s4"; analysis[4][6] = "8"; analysis[4][7] = "2"; analysis[4][8] = "3";

         analysis[5][1] = "r6"; analysis[5][2] = "r6"; analysis[5][4] = "r6"; analysis[5][5] = "r6";

         analysis[6][0] = "s5"; analysis[6][3] = "s4"; analysis[6][7] = "9"; analysis[6][8] = "3";

         analysis[7][0] = "s5"; analysis[7][3] = "s4"; analysis[7][8] = "10";

         analysis[8][1] = "s6"; analysis[8][4] = "ss";//表示s11

         analysis[9][1] = "r1"; analysis[9][2] = "s7"; analysis[9][4] = "r1"; analysis[9][5] = "r1";

         analysis[10][1] = "r3"; analysis[10][2] = "r3"; analysis[10][4] = "r3"; analysis[10][5] = "r3";

         analysis[11][1] = "r5"; analysis[11][2] = "r5"; analysis[11][4] = "r5"; analysis[11][5] = "r5";

         /*出现错误*/

         analysis[0][1] = analysis[0][2] = analysis[0][5] = analysis[4][1] = analysis[4][2] = analysis[4][5] = "e1";

         analysis[6][1] = analysis[6][2] = analysis[6][5] = analysis[7][1] = analysis[7][2] = analysis[7][5] = "e1";

         analysis[0][4] = analysis[1][4] = analysis[4][4] = analysis[6][4] = analysis[7][4] = "e2";

         analysis[1][0] = analysis[1][2] = analysis[1][3] = analysis[8][0] = analysis[8][2] = analysis[8][3] = "e3";

         analysis[8][5] = "e4";

         analysis[2][0] = analysis[2][3] = "r2";

         analysis[3][2] = analysis[3][3] = "r4";

         analysis[5][0] = analysis[5][3] = "r6";

         analysis[9][0] = analysis[9][3] = "r1";

         analysis[10][0] = analysis[10][3] = "r3";

         analysis[11][0] = analysis[11][3] = "r5";

 

}

/*输出移进还是规约,规约的话输出用到的产生式*/

void print(int into)

{

         if (into == 0)

         {

                  cout << "--移进--" << endl;

                  return;

         }

         cout << "--按";

         switch (into)

         {

         case 1:cout << "E->E+T"; break;

         case 2:cout << "E->T"; break;

         case 3:cout << "T->T*F"; break;

         case 4:cout << "T->F"; break;

         case 5:cout << "F->(E)"; break;

         case 6:cout << "F->id"; break;

         }

         cout << "规约--" << endl;

}

/*为终结符合非终结符编号*/

int NumOfSymbols(char c){

 

         if (c == 'a'){ return 0; }

         if (c == '+'){ return 1; }

         if (c == '*'){ return 2; }

         if (c == '('){ return 3; }

         if (c == ')'){ return 4; }

         if (c == '$'){ return 5; }

         if (c == 'E'){ return 6; }

         if (c == 'T'){ return 7; }

         if (c == 'F'){ return 8; }

}

char GetSymbol(int num){

         if (num == 0){ return 'a'; }

         if (num == 1){ return '+'; }

         if (num == 2){ return '*'; }

         if (num == 3){ return '('; }

         if (num == 4){ return ')'; }

         if (num == 5){ return '$'; }

         if (num == 6){ return 'E'; }

         if (num == 7){ return 'T'; }

         if (num == 8){ return 'F'; }

}

int Num[10];//存储数

char *Change(char*a){

         int len = strlen(a);//字符串a的长度     

         char *b = new char[len];//存储字符

         int charnum = 0;//记录b中实际有多少字符串

         int cur1 = 0;//Num[]的角标

         int cur2 = 0;//b[]的角标

         for (int i = 0; i < len; i++){

                  if (a[i] <= 59 && a[i] >= 48){

                          int num_len = 1;//大于一位数的这个数的长度

                          int num = 0;//最后记录这个数的大小

                          b[cur1] = 'a';//遇见的数字,把a放进栈

                          charnum++;

                          cur1++;//b的角标向后挪

                          int curr = i + 1;//curr指向当前处理字符的下一个字符,如果依然是数字那么就值个多位数

                          /*记录这个多位数的位数*/

                          while (a[curr] <= 59 && a[curr] >= 48){

                                   num_len++;

                                   curr++;

                          }

                          int acc = num_len;//记录循环次数,百位*10*10,千位*10*10*10

                          for (int j = i; j < i + num_len; j++){

                                   int tempsum = 1;

                                   for (int k = 0; k < acc - 1; k++){

                                            tempsum *= 10;

                                   }

                                   acc--;

                                   num += (a[j] - 48)*tempsum;

                          }

                          Num[cur2] = num;//把得到的这个数(或多位数或一位数放入数组)

                          cur2++;//Num角标后挪

                          for (int l = 0; l < num_len - 1; l++){ i++; }//多位数有几位就向后挪几位,一位数不用挪

                  }

                  else{//不是数字的话直接放入b中

                           b[cur1] = a[i];

                          charnum++;

                          cur1++;

                  }

         }

         cout << "该式的原型为:" << endl;

         char *c = new char[charnum];//重新存储一下b,因为长度不准确

         for (int i = 0; i < charnum; i++){

                  c[i] = b[i];

                  cout << c[i] << " ";

         }

         cout << endl;

         cout << "---------------" << endl;

         return c;

}

int main(){

         string analysis[12][9];

         stack<int> s;//字符栈

         stack<int> val;//数字栈

         int curr = 0;//记录Num中还未放入数字栈的角标

//       char* input = "(20+6)*5+8$";

         char* input = "8+5*2$";               

         cout << "输入表达式:" << input << endl;

         char* str = Change(input);

         /*cin >> str;*/

         int len = strlen(str);

         Initial(analysis);

         s.push(0);

         /*循环中i表示当前处理得输入串中的角标*/

         for (int i = 0; i < len;){

                  int stack_top = s.top();//记录栈顶状态

                  cout <<"此时栈定状态为:"<< stack_top;

                  cout << "  此时输入字符为:"<< str[i] << endl;

                  int lookahead = NumOfSymbols(str[i]);//记录当前输入串中,正在被处理的字符的标号

                      /*移进*/

                          if (analysis[stack_top][lookahead][0] == 's'){

                                   if (analysis[stack_top][lookahead][1] == 's'){

                                            print(0);

                                            s.push(lookahead);

                                            s.push(11);

                                            cout << "将状态11移进栈。" << endl;

                                            i++;

                                   }

                                   else{

                                            print(0);

                                            s.push(lookahead);

                                            s.push(analysis[stack_top][lookahead][1] - '0');

                                            cout << "将状态" << analysis[stack_top][lookahead][1] - '0' << "移进栈。" << endl;

                                            i++;//移进了一个后,就可以看下一个字符了

                                   }

                          }

                          /*规约*/

                          else if (analysis[stack_top][lookahead][0] == 'r'){

                                   int times;//如需规约,弹栈的次数

                                   int NumofNon_Terminal;//需要移进栈的终结符的编号

                                   print(analysis[stack_top][lookahead][1] - '0');//输出规约的式子

                                   switch (analysis[stack_top][lookahead][1] - '0'){

                                   case 1: times = 6; NumofNon_Terminal = NumOfSymbols('E'); break;

                                   case 2: times = 2; NumofNon_Terminal = NumOfSymbols('E'); break;

                                   case 3: times = 6; NumofNon_Terminal = NumOfSymbols('T'); break;

                                   case 4: times = 2; NumofNon_Terminal = NumOfSymbols('T'); break;

                                   case 5: times = 6; NumofNon_Terminal = NumOfSymbols('F'); break;

                                   case 6: times = 2; NumofNon_Terminal = NumOfSymbols('F'); break;

                                   }

                                   for (int j = 0; j < times; j++){

                                            s.pop();

                                   }                                

                                   int pre_top=s.top();//记录此时的栈顶

                                   cout << "弹栈" << times << "次后,栈顶状态为"<< pre_top << endl;

                                   s.push(NumofNon_Terminal);

                                   char c = GetSymbol(NumofNon_Terminal);//为了输出字符,通过序号找到

                                   cout << "放入"<< c << endl;

                                   /*处理数字栈中的树*/

                                   if (analysis[pre_top][NumofNon_Terminal].size() == 1){

                                            s.push(analysis[pre_top][NumofNon_Terminal][0] - '0');

                                            cout << "将状态" << analysis[pre_top][NumofNon_Terminal][0] - '0' << "移进栈。" << endl;

                                   }

                                           

                                   else{

                                            s.push(10);

                                            cout << "将状态10移进栈。" << endl;

                                   }

                                   if (analysis[stack_top][lookahead][1] - '0' == 1){

                                            int temp1 = val.top();

                                            val.pop();

                                            int temp2 = val.top();

                                            val.pop();

                                            val.push(temp1 + temp2);

                                            cout << "弹出了" << temp1 << "  " << temp2 << ",放入" << val.top() << endl;

                                   }

                                   if (analysis[stack_top][lookahead][1] - '0' == 3){

                                            int temp1 = val.top();

                                            val.pop();

                                            int temp2 = val.top();

                                            val.pop();

                                            val.push(temp1 * temp2);

                                            cout << "弹出了" << temp1 << "  " << temp2 << ",放入" << val.top() << endl;

                                   }

                                   if (analysis[stack_top][lookahead][1] - '0' == 6){

                                            val.push(Num[curr]);

                                            curr++;

                                            cout << "放入" << val.top() << endl;

                                   }

                          }

                          /*错误恢复*/

                          else if (analysis[stack_top][lookahead][0] == 'e'){

                                   cout << "出现错误" << endl;

                                   switch (analysis[stack_top][lookahead][1]){

                                   case '1':{   //期望遇到a,那就把a放进去

                                                              s.push(0);

                                                              s.push(5);

                                                              cout << "缺少运算符,加入a" << endl;

                                                              break;

                                   }

                                   case '2':{

                                                              //遇见右括号,没有左括号,说明右括号错误

                                                              i++;

                                                              cout << "不匹配的右括号,将忽略该字符" << endl;

                                                              break;

                                   }

                                   case '3':{

                                                              //期望遇见运算符,加进+

                                                              s.push(1);

                                                              s.push(6);

                                                              cout << "缺少运算符,加入a" << endl;

                                                              break;

                                   }

                                   case '4':{

                                                              //提前结束,但期望遇见右括号,那就加入有括号

                                                              s.push(4);

                                                               s.push(11);

                                                              cout << "缺少右括号" << endl;

                                                              break;

                                   }

                                   }

                          }

                          else{

                                   if (analysis[stack_top][lookahead][0] == 'a'){

                                            cout << "接受"<<endl;

                                            cout << "结果为:" << val.top() << endl;

                                            return 0;

                                   }

                                   else{

                                            cout << "无法识别,完蛋了!" << endl;

                                            return 0;

                                   }

                          }

                          cout << "--------------------------------------" << endl;

         }

         return 0;

}

3 Python运行代码

import re

action=dict()

goto=dict()

action={0: {'i': 's5', '(': 's4'},

 1: {'+': 's6', '$': 'acc'},

 2: {'+': 'r2', '*': 's7', ')': 'r2', '$': 'r2'},

 3: {'+': 'r4', '*': 'r4', ')': 'r4', '$': 'r4'},

 4: {'i': 's5', '(': 's4'},

 5: {'+': 'r6', '*': 'r6', ')': 'r6', '$': 'r6'},

 6: {'i': 's5', '(': 's4'},

 7: {'i': 's5', '(': 's4'},

 8: {'+': 's6', ')': 's11'},

 9: {'+': 'r1', '*': 's7', ')': 'r1', '$': 'r1'},

 10: {'+': 'r3', '*': 'r3', ')': 'r3', '$': 'r3'},

 11: {'+': 'r5', '*': 'r5', ')': 'r5', '$': 'r5'}}

goto={0: {'E': 1, 'T': 2, 'F': 3},

 4: {'E': 8, 'T': 2, 'F': 3},

 6: {'T': 9, 'F': 3},

 7: {'F': 10}}

 

 

gramma=open('wx.txt').readlines()

i=0

while i<len(gramma): #去掉'->'符号

    gramma[i]=gramma[i][0:1]+gramma[i][3:len(gramma[i])-1]

    i+=1

 

input_string="8+5*2$"

print("输入的计算式:   "+input_string)

stack_s=['$',0]#状态栈

stack_i=[] #放数字

stack_num=[] #放数字栈

ip=0

number=re.findall(r'[0-9]+',input_string)

changed=input_string

for i in number:

    stack_i.append(i)

    changed=changed.replace(str(i),"i")

print("转换后的字符串:     "+changed)

length=len(changed)

pro=0

 

while pro<length:

    i=changed[pro]

    top=stack_s[len(stack_s)-1]

    print("栈:"+str(stack_s)+"    字符"+i)

    print("数字栈:"+str(stack_num))

    if action[top][i][0]=='s':

        print("移进")

        stack_s.append(i)

        stack_s.append(int(action[top][i][1:]))

        print(action[top][i][1:]+"入栈")

        pro+=1

    elif action[top][i][0]=='r':

        print("规约"+gramma[int(action[top][i][1])-1][0]+"->"+gramma[int(action[top][i][1])-1][1:])

        ch=int(action[top][i][1:])

        time=2*len(gramma[int(action[top][i][1])-1][1:])

        sym=gramma[int(action[top][i][1])-1][0]

        prep=0

        while prep<time:

            stack_s.pop()

            prep+=1

        now_top=stack_s[len(stack_s)-1]

        print("弹栈"+str(time)+"次后,栈顶状态为"+str(now_top))

        stack_s.append(sym)

        print("放入"+sym)

        #处理goto表

        if sym in goto[now_top]:

            stack_s.append(int(goto[now_top][sym]))

            print("将状态"+str(goto[now_top][sym])+"入栈")

        if action[top][i][1]=='1':

            tmp1=stack_num[len(stack_num)-1]

            stack_num.pop()

            tmp2=stack_num[len(stack_num)-1]

            stack_num.pop()

            tmp=int(tmp1)+int(tmp2)

            stack_num.append(str(tmp))

            print("弹出"+str(tmp1)+"+"+str(tmp2)+"放入"+str(tmp))

        elif action[top][i][1]=='3':

            tmp1=stack_num[len(stack_num)-1]

            stack_num.pop()

            tmp2=stack_num[len(stack_num)-1]

            stack_num.pop()

            tmp=int(tmp1)*int(tmp2)

            stack_num.append(str(tmp))

            print("弹出"+str(tmp1)+"*"+str(tmp2)+"放入"+str(tmp))

        elif  action[top][i][1]=='6':

            stack_num.append(stack_i[ip])

            ip+=1

            print("放入"+str(stack_i[ip-1]))

    elif action[top][i][0]=='e':

        if action[top][i][1]=='1':

            print("error1:缺少i,添加")

            stack_s.append('i')

            stack_s.append(5)

        if action[top][i][1]=='2':

            print("error2:多余右括号,跳过")

            pro+=1

            continue

        if action[top][i][1]=='3':

            print("error3:缺少+,添加")

            stack_s.append('+')

            stack_s.append(6)

        if action[top][i][1]=='4':

            print("error4:缺少右括号,添加")

            stack_s.append('}')

            stack_s.append(11)           

    elif action[top][i]=="acc":

        print("结果为"+str(stack_num[len(stack_num)-1]))

        break

    else:

        print("error")

    print("------------------------------------------------------")

3 'wx.txt'内容

*注:最后一行有换行。

E->E+T

E->T

T->T*F

T->F

F->(E)

F->i

 

本文转自 https://www.helloworld.net/redirect?target=https://blog.csdn.net/weixin_43442778/article/details/114972009,如有侵权,请联系删除。

收藏
评论区
守株待兔
最新文章

导读