目录
一、实验目的
掌握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运行截图
输入表达式：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 |
参考资料
- 语法制导的翻译（C++）：https://blog.csdn.net/shl_shl/article/details/53535809
- Python实现: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://blog.csdn.net/weixin_43442778/article/details/114972009，如有侵权，请联系删除。
