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

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

二、实验任务

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

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

三、实验原理

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

假设拓展后的分析栈由状态数组_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_的值减２，覆盖_Ａ_的状态放进_state[top]（即_X_原来的位置），综合属性的值_A.a_放进_val[top]_。

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

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

注：这里_val_为_stack.val_，如_val[top-2]=stack[top-2].val_.

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

四、实验过程

以词法分析和语法分析部分的上机结果为基础，添加语义分析部分。即以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时的动作

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

图 5.2：python运行截图

<table cellspacing="0" border="1"><tbody><tr><td style="vertical-align:top;width:414.8pt;">输入表达式：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</td></tr></tbody></table>

参考资料

语法制导的翻译（C++）：https://blog.csdn.net/shl_shl/article/details/53535809
Python实现:https://blog.csdn.net/qq_36614557/article/details/85848199

附录

1 C++运行代码

<table cellspacing="0" border="1"><tbody><tr><td style="vertical-align:top;width:414.8pt;">#include <iostream>#include <string.h>#include<stack>using namespace std;/*E->E+TE->TT->T*FT->FF->(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                                    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;}</td></tr></tbody></table>

3 Python运行代码

<table cellspacing="0" border="1"><tbody><tr><td style="vertical-align:top;width:414.8pt;">import reaction=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=0while 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=0number=re.findall(r'[0-9]+',input_string)changed=input_stringfor 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("------------------------------------------------------")</td></tr></tbody></table>

3 'wx.txt'内容

*注：最后一行有换行。

本文转自 https://blog.csdn.net/weixin_43442778/article/details/114972009，如有侵权，请联系删除。