编译原理程序设计3语义分析By坏学长一、 实验题目和要求题目：语义分析程序的设计与实现。

实验内容：编写语义分析程序，实现对算术表达式的类型检查和求值。

要求所分析算术表达式由如下的文法产生。

numE idF F F T F T T T T E T E E |)(||/|*||→→-+→ 实验要求：用自底向上的语法制导翻译技术实现对表达式的分析和翻译。

(1) 写出满足要求的语法制导定义或翻译方案。

(2) 编写分析程序，实现对表达式的类型进行检查和求值，并输出： ① 分析过程中所有产生式。

② 识别出的表达式的类型。

③ 识别出的表达式的值。

(3) 实验方法：可以选用以下两种方法之一。

① 自己编写分析程序。

② 利用YACC 自动生成工具。

二、 实验分析1. 自底向上的LR 分析 ◆ 该文法的拓广文法E' -> EE -> E + T E -> E - T E -> T T -> T *F T -> T / F T -> F F -> id F ->( E ) F ->num◆ FIRST 和FOLLOW 集◆该文法的LR(0)项目集规范族：●CLOUSURE I0E' -> .EE -> .E+TE -> .E-TE -> .TT -> .T*FT -> .T/FT -> .FF -> .idF -> .(E) F -> .num●CLOUSURE I1E' -> E. E -> E.+TE -> E.-T●CLOUSURE I2E -> T. T -> T.*FT -> T./F●CLOUSURE I3T -> F.●CLOUSURE I4F -> id.●CLOUSURE I5F -> num.●CLOUSURE I6F -> (.E) E -> .E+TE -> .E-TE -> .TT -> .T*FT -> .T/FT -> .FF -> .idF -> .(E) F -> .num●CLOUSURE I7E -> E+.TT -> .T*FT -> .T/FT -> .FF -> .idF -> .(E) F -> .num●CLOUSURE I8E -> E-.TT -> .T*FT -> .T/FT -> .FF -> .idF -> .(E) F -> .num●CLOUSURE I9T -> T*.FF -> .idF -> .(E) F -> .num●CLOUSURE I10T -> T/.FF -> .idF -> .(E) F -> .num●CLOUSURE I11F -> (E.) E -> E.+TE -> E.-T●CLOUSURE I12E -> E+T. T -> T.*FT -> T./F●CLOUSURE I13E -> E-T. T -> T.*FT -> T./F●CLOUSURE I14T -> T*F.●CLOUSURE I15T -> T/F.●CLOUSURE I16F -> (E).构造SLR(1)分析表2.S属性定义的制导翻译自底向上的制导翻译需要在ＬＲ分析的基础上进行扩展，进行综合属性的记录和计算，完成类型检查和结果计算．◆扩充分析栈目的：用于保存综合属性实现：栈由state和value类的容器类实现，state元素是指向LR(1)分析表中状态的指针（或索引），val中就存放分析树中对应的属性值。

假设综合属性刚好在每次归约前计算A->XYZ对应的语义规则是A.a=f(X.x,Y.y,Z.z)定义一个结构栈，value结构里有两个变量，一个为val, 一个为type。

Val存在两种情况，一个表示int时的值，一个表示float时的值，因为无法公用一个类型的变量。

定义type只有三种情况，一种为int, 一种为float, 一种为type_error(由于输入值只有int 和float两种类型，所以type_error即类型不同时，四则运算默认结果为float)。

◆改造分析程序综合属性记录：终结符号的综合属性值由词法分析程序产生,当分析程序执行移进操作时，其属性值随终结符号（或状态符号）一起入栈。

为每个语义规则编写一段代码，以计算属性值。

归约计算：在归约时完成类型检查和求值。

对每一个产生式A->XYZ,把属性值的计算与归约动作联系起来:归约前，执行与产生式相关的代码段归约时，右部符号及其属性出栈,左部符号及其属性入栈◆翻译方案}..),"int(",..{}..),)"(int(",..){(}..),"int(",..{}..),"int(",..{};_.;..)..({)}"/int(",./..{/};_.;..)..({)}"*int(",.*..{*}..),"int(",..{};_.;..)..({)}"int(",...{};_.;..)..({)}"int(",...{111111111111type num type F num F pr val num val F num F type E type F E F pr val E val F E F type id type F id F pr val id val F id F type F type T F T pr val F val T F T error type type T elsetype F type T type F type T if F T T pr val F val T val T F T T error type type T elsetype F type T type F type T if F T T pr val F val T val T F T T type T type E T E pr val T val E T E error type type E elsetype T type E type T type E if T E E pr val T val E val E T E E error type type E elsetype T type E type T type E if T E E pr val T val E val E T E E =→=→=→=→=→=→=→=→====→=→====→=→=→=→====-→-=-→====+→+=+→三、 主要算法分析词法分析：void Lexval （string ）；对输入子串进行分解，由单个string 按照不同类型，int ，float ，运算符等，得到字符串数组，方便语法分析处理。

终结符处理：相对于语法分析，扩展了栈，需要将终结符的属性即类别和数值进栈保存，运算符进栈，属性值默认-1，行为根据action 表格进行操作，action 表格以数组形式存储，根据符号位置直接定位判断行为。

int action[17][9]={{-1,-1,-1,-1,14,16,15,-1,-1},{17,18,-1,-1,-1,-1,-1,-1, 0},{ 3, 3,19,20,-1,-1,-1, 3, 3},{ 6, 6, 6, 6,-1,-1,-1, 6, 6},{ 7, 7, 7, 7,-1,-1,-1, 7, 7},{-1,-1,-1,-1,14,16,15,-1,-1},{ 9, 9, 9, 9,-1,-1,-1, 9, 9},{-1,-1,-1,-1,14,16,15,-1,-1},{-1,-1,-1,-1,14,16,15,-1,-1},{-1,-1,-1,-1,14,16,15,-1,-1},{-1,-1,-1,-1,14,16,15,-1,-1},{17,18,-1,-1,-1,-1,-1,26,-1},{ 1, 1,19,20,-1,-1,-1, 1, 1},{ 2, 2,19,20,-1,-1,-1, 2, 2},{ 4, 4, 4, 4,-1,-1,-1, 4, 4},{ 5, 5, 5, 5,-1,-1,-1, 5, 5},{ 8, 8, 8, 8,-1,-1,-1, 8, 8}};归约处理：归约的同时，按照翻译方案计算结果，归约行为根据action表格进行，同时goto表如下intgo_to[17][3]={{ 1, 2, 3},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{11,2 ,3},{-1,-1,-1},{-1,12 ,3},{-1,13 ,3},{-1,-1,14},{-1,-1,15},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1}};在程序最终，输出结果result和类型type四、代码实现（见附件）#include<iostream>#include<string>#include<vector>#include<stack>#include<stdio.h>#include<stdlib.h>using namespace std;intGoto[17][3]={{ 1, 2, 3},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{11, 2, 3},{-1,-1,-1},{-1,12 ,3},{-1,13 ,3},{-1,-1,14},{-1,-1,15},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1}};int action[17][9]={{-1,-1,-1,-1,14,16,15,-1,-1},{17,18,-1,-1,-1,-1,-1,-1, 0},{ 3, 3,19,20,-1,-1,-1, 3, 3},{ 6, 6, 6, 6,-1,-1,-1, 6, 6},{ 7, 7, 7, 7,-1,-1,-1, 7, 7},{-1,-1,-1,-1,14,16,15,-1,-1},{ 9, 9, 9, 9,-1,-1,-1, 9, 9},{-1,-1,-1,-1,14,16,15,-1,-1},{-1,-1,-1,-1,14,16,15,-1,-1},{-1,-1,-1,-1,14,16,15,-1,-1},{-1,-1,-1,-1,14,16,15,-1,-1},{17,18,-1,-1,-1,-1,-1,26,-1},{ 1, 1,19,20,-1,-1,-1, 1, 1},{ 2, 2,19,20,-1,-1,-1, 2, 2},{ 4, 4, 4, 4,-1,-1,-1, 4, 4},{ 5, 5, 5, 5,-1,-1,-1, 5, 5},{ 8, 8, 8, 8,-1,-1,-1, 8, 8}};class Value //Value类{public:Value(intType,doublenum){type = Type;val = num;};int type;doubleval;};vector <Value>ValueStack;//Value栈容器类vector <int> State;//state状态栈容器类bool error=false;//定义一个变量表示出错intlen=0;string Input[200],str;//输入缓冲区intInputType[200]={0};//将早准备好的action和go-to表准备好stringgene[10]={"E'->E","E->E+T","E->E-T","E->T","T->T*F","T->T/F","T->F","F->i","F->(E)","F-> n"};//原拓展文法char Vt[]={'+','-','*','/','i','n','(',')','$'}; //终结符集合char Vn[]={'E','T','F'}; //非终结符集合char* type[]={"int","float"}; //定义两种类型intnum_Vt=9,num_Vn=3,num_State=17,num_Gn=10; //定义一些常数，非终结符个数为9，终结符个数为3等等void Lexval(string str);//词法分析int Palce2(char c);//定位int Palce1(char c);int Judge();//判断结尾int Analysis();//分析Value Reduce(intnum);//归约int main(){inti,len;cout<<"\t\t\t【拓广文法】"<<endl;for(i=0;i<num_Gn;i++){cout<<"\t\t\t "<<i<<") "<<gene[i]<<endl;}if(Analysis()==1){cout<<"Accept!!"<<endl;len=(int)str.size();cout<<"算术表达式结果为："<<str.substr(0,len-1)<<"="<<ValueStack[ValueStack.size()-1].val<<endl;cout<<"算术表达式的类型为："<<type[ValueStack[ValueStack.size()-1].type]<<endl;}else if(Analysis()==0)cout<<"不可接受字符串!"<<endl;system("pause");}int Palce2(char c)//寻找非终结符的位置{for(inti=0;i<3;i++){if(Vn[i]==c)returni;}return -1;}int Palce1(char c)//寻找终结符位置{for(inti=0;i<9;i++){if(Vt[i]==c)returni;}return -1;}int Judge()//判断是不是"$"{intlen=(int)str.size();if(str[len-1]!='$')return 0;else return 1;}int Analysis()//对输入串进行分析的函数{intip=0,S,a,i,top;cout<<"请输入运算表达式"<<endl;cin>>str;while(!Judge()){cout<<"输入错误，请以$作为输入终止符。