精华内容
下载资源
问答
  • 2020-11-08 09:40:46

    实验四 语义分析及中间代码生成
    1.实验目的
    (1)通过上机实习,加深对语法制导翻译原理的理解,掌握将语法分析 所识别的语法范畴变换为某种中间代码的语义翻译方法。
    (2)掌握目前普遍采用的语义分析方法──语法制导翻译技术。
    (3)给出 PL/0 文法规范,要求在语法分析程序中添加语义处理,对于语法正确的表达式,输出其中间代码;对于语法正确的算术表达式,输出其计算值。
    2.实验内容
    (1)已给 PL/0 语言文法,在实验二或实验三的表达式语法分析程序里,添加语义处理部分,输出表达式的中间代码,用四元式序列表示。
    (2) PL/0 算术表达式的语义计算:
    PL/0 算术表达式,例如:2+35 作为输入。
    输出: 17
    PL/0 表达式的中间代码表示
    PL/0 表达式,例如: a
    (b+c)。
    输出: (+,b,c,t1) (,a,t1,t2)
    3.设计思想
    (1)语义规则: 属性计算的过程即是语义处理的过程对于文法的每一个产生式配备一组属性的计算规则,则称为语义规则。
    终结符只有综合属性,它由词法分析器提供。
    非终结符既可以有综合属性也可以有继承属性,文法开始符号的所有继承属性作为属性计算前的初始值。
    产生式右边符号的继承属性和产生式左边符号的综合属性都必须提供一个计算规则。
    产生式左边符号的继承属性和产生式右边符号的综合属性由其它产生式的属性规则计算。
    (2)基于递归下降翻译器的设计
    递归下降分析法的原理是利用函数之间的递归调用来模拟语法树自上而下的构建过程。从根节点出发,自顶向下为输入串中寻找一个最左匹配序列,建立一棵语法树。对于每个非终结符的继承属性当作形式参数,函数的返回值当作非终结符的继承属性;对于终结符要初始化所有的继承属性。再进行分析过程中,非终结符根据当前的输入符号决定使用哪个产生式候选。
    (3) 加入递归下降翻译器子程序伪码
    表达式递归下降子程序为:
    function表达式:string;
    string s1, s2, s3, result;
    BEGIN
    IF SYM=’+’ OR SYM=’-’ THEN
    ADVANCE;
    ELSE IF SYM =FIRST(项)
    ELSE ERROR;
    BEGIN s1:=项;
    END;
    WHILE SYM=’+’ OR SYM=’-’ THEN
    BEGIN
    ADVANCE;
    S2:=项;
    result := newtemp();
    emit(SYM,s1,s2,result);
    s1:= result;
    END;
    Return result;
    END;
    项递归下降子程序为:
    function 项:string;
    string s1, s2, s3, result;
    BEGIN
    IF SYM =FIRST(因子) THEN
    BEGIN
    s1:=因子;
    END;
    ELSE ERROR;
    WHILE SYM =’
    ’OR SYM=’/’ THEN
    IF SYM =FIRST(因子) THEN
    BEGIN
    ADVANCE;
    S2:=因子;
    result := newtemp();
    emit(SYM,s1,s2,result);
    s1:= result;
    END;
    Return result;
    END;
    ELSE ERROR;
    因子递归下降子程序为:
    function 因子:string;
    string s;
    BEGIN
    IF SYM =’(’ THEN
    ADVANCE;
    s:=表达式;
    ADVANCE;
    IF SYM=’)’ THEN
    ADVANCE;
    Return s;
    ELSE ERROR;
    ELSE IF SYM =FIRST(因子) THEN
    ADVANCE;
    ELSE ERROR;
    END;

    4.程序流程图

    5.实验结果

    6.实验总结
    (1)编写代码之前需要写出递归下降翻译器的伪代码,重点就是要找到对于每个非终结符的属性哪些是继承属性,哪些是综合属性。然后将继承属性作为参数,综合属性作为返回值,进行计算。利用实验二所写的递归下降分析器的伪代码做出改写,加入参数返回值以及一些初始化。
    (2)编写代码的时候,需要用到实验一和实验二的代码,写实验一代码的时候没考虑到后面会用到,直接将结果输出并没有保存中间结果,以至于自己在编码的时候需要先将实验一的结果存放在一个自定义的结构体中,里面包含词法分析的两个因素:值和类型。而分析器分析的时候,直接调取这个结构体的内容,四元式的结果也会放在一个特殊的结构体,里面记录了四元式的四个值,方便输出。如果是数字运算式,可以模拟计算器对于这四个值进行计算,并且需要数组和判定运算符函数来判断是数字还是辅助变量,根据对应符号进行运算。
    (3)通过这次实验,从词法分析到语法分析到语义分析的知识点有了大致的回顾,并且重点回顾了每个阶段输入什么,输出什么,这些信息怎么存储,用什么算法来计算。还需要进一步优化自己的代码,比如在这次的实验代码过程中,需要改进的是将词法分析和语法分析合并,降低时间复杂度,提高执行效率。
    (4)通过这四次的实验过程,让我对于编译原理这门课有了比较清晰的认识,可能理论课当时听懂了,过一会可能就会遗忘。但实验课不一样,花费了很久时间然后又是动手敲代码,又是写实验报告梳理思路更加深了对于这门课的理解。通过学习编译原理,感觉用到了数据结构,算法等思维理解,又需要对于许多概念的理解记忆。这也是这门课的难点所在。通过这次学习,懂得更要注重对于基础科目的掌握,不断加强和拓展自己的计算机思维。
    7.附录(实验代码)
    #include <bits/stdc++.h> //万能头文件
    using namespace std;
    struct sv
    {
    string s; //词法分析的类型
    string v; //词法分析变量的值
    };
    struct sc
    {
    string fuhao; //符号
    string a; //第一个操作数
    string b; //第二个操作数
    string result; //结果
    };
    string input; //输入全局
    int cnt; //全局变量
    int k=0; //sv输入
    int lala=0;
    sv result[200];//存放结果
    sc shuchu[200];//存放输出的四元组
    int xxx=0;//sc 的下标
    int ans=0;//遍历的时候的下标
    bool error=true;//出错标志
    int isletter=0;
    int t[1001];
    string biaodashi();
    string xiang();
    string yinzi();
    string newtemp() ///产生新变量名t1,t2等
    {
    char pq;
    char mm[18];
    pq=(char
    )malloc(18);
    lala++;
    //itoa(lala,mm,10);
    snprintf(mm,sizeof(mm),"%d",lala);
    strcpy(pq+1,mm);
    pq[0]=‘t’;
    string s;
    s=pq;
    return s;
    }
    bool judge (string input, string s) ///判断是否和目标串匹配
    {
    int i=0;
    if (input.length()!=s.length()) return false;
    else
    {
    for(i=0;i<s.length();i++)
    {
    if(input[i]!=s[i]) return false; ///遍历
    }
    return true;
    }
    }
    bool judge1 (string input, string s) ///判断是否和目标串匹配
    {
    if(input[0]==s[0]) return true;
    // if (input.length()!=s.length()) return false;
    else return false;

    }
    void feifuhao(string p) ///判断非符号的程序,包含判断关键字,标识符,常数
    {
    if(judge (p,“begin”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“beginsym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“call”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“callsym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“const”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“constsym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“do”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“dosym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“end”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“endsym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“if”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“ifsym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“odd”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“oddsym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“procedure”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“proceduresym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“read”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“readsym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“var”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“varsym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“then”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“thensym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“write”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“writesym”;
    result[k].v=p;
    k++;
    }
    else if(judge (p,“while”)) ///判断是否跟目标串相同,相同的话输出结果
    {
    result[k].s=“whilesym”;
    result[k].v=p;
    k++;
    }
    else
    {
    int flag=0;
    for(int i=0;i<p.length();i++)
    {
    if(!isdigit(p[i])) //判断是否是标识符
    {
    flag=1;
    result[k].s=“ident”;
    result[k].v=p;
    k++;
    break;
    }
    }
    if(!flag) //判断是否是数字
    {
    result[k].s=“number”;
    result[k].v=p;
    k++;
    }
    }
    }
    int change(string aa,int cnt) ///防止多个运算符组成,返回正确下标
    {
    int x=0;
    char f[15]={’+’,’-’,’’,’/’,’=’,’<’,’>’,’:’,’(’,’)’,’,’,’;’,’.’};
    for(int i=0;i<13;i++)
    {
    if(aa[cnt]f[i])
    {
    x=i;
    }
    }
    if(x
    5)
    {
    if(aa[cnt+1]’>’) //如果运算符是两个符号组成,cnt+1
    {
    cnt=cnt+1;
    return cnt;
    }
    else if(aa[cnt+1]
    ’=’) //判断两个运算符相连
    {
    cnt=cnt+1;
    return cnt;
    }
    }
    if(x==7) //判断:=
    {
    cnt=cnt+1;
    return cnt;
    }
    return cnt;
    }
    void fuhao (string aa,int cnt) ///对运算符和界符的输出
    {
    int x=0;
    char f[15]={’+’,’-’,’
    ’,’/’,’=’,’<’,’>’,’:’,’(’,’)’,’,’,’;’,’.’};
    for(int i=0;i<13;i++)
    {
    if(aa[cnt]f[i])
    {
    x=i;
    }
    }
    if(x
    0)
    {
    result[k].s=“plus”;
    result[k].v=f[x];
    k++;
    }
    if(x1)
    {
    result[k].s=“minus”;
    result[k].v=f[x];
    k++;
    }
    if(x
    2)
    {
    result[k].s=“times”;
    result[k].v=f[x];
    k++;
    }
    if(x3)
    {
    result[k].s=“slash”;
    result[k].v=f[x];
    k++;
    }
    if(x
    4)
    {
    result[k].s=“eql”;
    result[k].v=f[x];
    k++;
    }
    if(x5)
    {
    if(aa[cnt+1]
    ’>’)
    {
    cnt=cnt+1;
    result[k].s=“neq”;
    result[k].v="<>";
    k++;
    }
    else if(aa[cnt+1]’=’)
    {
    result[k].s=“leq”;
    result[k].v="<=";
    k++;
    }
    else
    {
    result[k].s=“lss”;
    result[k].v="<";
    k++;
    }
    }
    if(x
    6)
    {
    if(aa[cnt+1]’=’)
    {
    result[k].s=“geq”;
    result[k].v=">=";
    k++;// cout<<"(geq,>=)"<<endl;
    }
    else
    {
    result[k].s=“gtr”;
    result[k].v=">";
    k++;
    }
    }
    if(x
    7)
    {
    result[k].s=“becomes”;
    result[k].v=":=";
    k++; // cout<<"(becomes,:=)"<<endl;
    }
    if(x8)
    {
    result[k].s=“lparen”;
    result[k].v="(";
    k++;
    }
    if(x
    9)
    {
    result[k].s=“rparen”;
    result[k].v=")";
    k++;
    }
    if(x10)
    {
    result[k].s=“comma”;
    result[k].v=",";
    k++;
    }
    if(x
    11)
    {
    result[k].s=“semicolon”;
    result[k].v=";";
    k++;
    }
    if(x==12)
    {
    result[k].s=“period”;
    result[k].v=".";
    k++;
    }
    }
    void cifa() ///词法分析
    {
    string aa;
    while(cin>>aa)
    {
    cnt=0;
    const char d = " ±/=<>:(),;.";
    char p;
    ///运用空格和运算符和界符分割字符串并且遍历
    char buf[1001] ;
    strcpy(buf , aa.c_str()); //字符串转成数组
    p = strtok(buf,d); //p是一个char

    while§
    {
    if(aa[cnt]==p[0]) //当前无符号
    {
    feifuhao§;
    cnt=cnt+strlen§;
    }
    else ///当前是符号
    {
    while(aa[cnt]!=p[0])
    {
    fuhao(aa,cnt);
    cnt=change(aa,cnt);
    cnt=cnt+1;
    }
    feifuhao§;
    cnt=cnt+strlen§;
    }
    // printf("%s\n",p);
    p=strtok(NULL,d); //下移一位,进行遍历
    }
    for(int i=cnt;i<aa.length();i++)
    {
    //cout<<aa[i];
    fuhao(aa,i); //防止最后有多个符号
    }
    }
    }
    void hasletter() ///判断是那种类型的计算
    {
    for(int i=0;i<k;i++)
    {
    if(judge(result[i].s,“ident”))
    {
    isletter=1;
    break;
    }
    }
    }
    string biaodashi() ///表达式的递归下降分析函数
    {
    string ss;
    string s1,s2,s3;
    if(ans>k) return NULL;
    if(judge(result[ans].v,"+") || judge(result[ans].v,"-")) ///加减符号
    {
    ans++;
    if(ans>k)
    {
    cout<<1<<endl;
    error=false;///错误判定
    }
    s1=xiang();
    }
    else if( judge(result[ans].v,"(") ||judge(result[ans].s,“ident”) ||judge(result[ans].s,“number”))
    {
    s1=xiang();//项目判定,前面条件是first集合
    }
    else
    {
    cout<<2<<endl;
    error=false;///错误判定
    }//
    while(judge(result[ans].v,"+") || judge(result[ans].v,"-"))
    {
    int anstemp=ans;
    ans++;
    if(ans>k)
    {
    cout<<3<<endl;
    error=false;///错误判定
    }
    s2=xiang(); //项目循环
    shuchu[xxx].fuhao=result[anstemp].v;
    shuchu[xxx].a=s1;
    shuchu[xxx].b=s2;
    shuchu[xxx].result=newtemp();
    ss=shuchu[xxx].result;
    s1=ss;
    xxx++;
    }
    return ss;
    }
    string xiang() ///项的递归下降分析函数
    {
    string ss;
    string s1,s2,s3;
    if(ans>k) return NULL;
    s1=yinzi(); //因子判断
    while(judge(result[ans].v,"") || judge(result[ans].v,"/"))
    {
    int anstemp=ans;
    ans++;
    if(ans>k)
    {
    cout<<4<<endl;
    error=false;///错误判定
    }
    s2=yinzi();
    shuchu[xxx].a=s1;
    shuchu[xxx].fuhao=result[anstemp].v;
    shuchu[xxx].b=s2;
    shuchu[xxx].result=newtemp();
    ss=shuchu[xxx].result;
    s1=ss;
    xxx++;
    }
    return s1;
    }
    string yinzi() ///因子的递归下降分析函数
    {
    string ss;
    if(ans>=k) return NULL;
    if(judge(result[ans].s,“ident”) ||judge(result[ans].s,“number”)) //开头字母或数字
    {
    ss=result[ans].v;
    ans++;
    if(ans>k)
    {
    cout<<5<<endl;
    error=false;///错误判定
    }
    }
    else if(judge(result[ans].v,"(")) //左括号
    {
    ans++;
    ss= biaodashi(); //表达式
    if(judge(result[ans].v,")")) //右括号
    {
    ans++;
    if(ans>k)
    {
    cout<<6<<endl;
    error=false;///错误判定
    }
    }
    }
    else
    {
    cout<<7<<endl;
    error=false;///错误判定
    }
    return ss;
    }
    string delet(string s) ///删除第一个字母
    {
    char c[101];
    for(int i=0;i<s.length()-1;i++)
    {
    c[i]=s[i+1];
    }
    return c;
    }
    void jisuan(int i)
    {
    char
    end;
    if(judge(shuchu[i].fuhao,"*")) //如果是乘法
    {
    if(!judge1(shuchu[i].a,“t”)) //判断第一个符号是字母还是数字
    {
    if(!judge1(shuchu[i].b,“t”))
    {
    //强制类型转换
    t[i+1]=static_cast(strtol(shuchu[i].a.c_str(),&end,10))*static_cast(strtol(shuchu[i].b.c_str(),&end,10));
    }
    }
    }
    else
    {
    if(!judge1(shuchu[i].b,“t”))
    {
    string cc;
    cc=delet(shuchu[i].a);
    //强制类型转换
    int zz=static_cast(strtol(cc.c_str(),&end,10));
    t[i+1]=t[zz]*static_cast(strtol(shuchu[i].b.c_str(),&end,10));
    }
    else
    {
    string d;
    d=delet(shuchu[i].a);
    int yy=static_cast(strtol(d.c_str(),&end,10));
    string cc;
    cc=delet(shuchu[i].b);
    int zz=static_cast(strtol(cc.c_str(),&end,10));
    t[i+1]=t[yy]*t[zz];
    }
    if(judge(shuchu[i].fuhao,"+"))
    {
    if(!judge1(shuchu[i].a,“t”))
    {
    if(!judge1(shuchu[i].b,“t”))
    {
    t[i+1]=static_cast(strtol(shuchu[i].a.c_str(),&end,10))+static_cast(strtol(shuchu[i].b.c_str(),&end,10));
    }
    else
    {
    string cc;
    cc=delet(shuchu[i].b);
    int yy=static_cast(strtol(shuchu[i].a.c_str(),&end,10));
    int zz=static_cast(strtol(cc.c_str(),&end,10));
    t[i+1]=yy+t[zz];
    }
    }
    else
    {
    if(!judge1(shuchu[i].b,“t”))
    {
    string cc;
    cc=delet(shuchu[i].a);
    int zz=static_cast(strtol(cc.c_str(),&end,10));
    t[i+1]=t[zz]+static_cast(strtol(shuchu[i].b.c_str(),&end,10));
    }
    else
    {
    string d;
    d=delet(shuchu[i].a);
    int yy=static_cast(strtol(d.c_str(),&end,10));
    string cc;
    cc=delet(shuchu[i].b);
    int zz=static_cast(strtol(cc.c_str(),&end,10));
    t[i+1]=t[yy]+t[zz];
    }
    }
    }
    }

    }
    int main()
    {
    cifa(); //词法分析函数
    hasletter();//判断类型
    biaodashi();//语法分析和语义分析
    if(isletter==1)//进行输出
    {
    for(int i=0;i<xxx;i++)
    {
    cout<<"("<<shuchu[i].fuhao<<","<<shuchu[i].a<<","<<shuchu[i].b<<","<<shuchu[i].result<<")"<<endl;
    }
    }
    else //进行输出,计算结果
    {
    for(int i=0;i<xxx;i++)
    {
    jisuan(i);
    }
    cout<<t[xxx]<<endl;
    }
    return 0;
    }

    更多相关内容
  • 中间代码生成实验报告.doc
  • 实验课上写的编译原理的语义分析和四元式代码的生成。
  • 编译原理语义分析和中间代码生成实验报告,基于VS2010开发的纯C#的程序,附程序执行截图
  • 一个简单的编辑器 编译原理课设 对简单的程序进行语义分析并将中间代码生成
  • 编译原理实验指导:词法分析,语法分析以及中间代码生成及优化。使用Linux下的flex,bison和gcc实现。指导书很详细,每个部分一份指导书。
  • 编译原理课程词法分析器,语法分析器(递归实现),中间代码生成;
  • 编译原理 词法分析,语法分析,中间代码生成 源代码 重庆理工大学编译原理实验。
  • 中间代码生成

    2013-09-26 22:08:00
    花了很长时间,从词法分析,用预测分析表实现语法,到表达式生成中间代码,后来生成if和while语句的中间代码,终于可以截稿了。
  • 编译原理中间代码生成器实现C++编译原理中间代码生成器实现C++
  • 表达式中间代码生成 二、实验目的 熟悉算术表达式的语法分析与中间代码生成原理。 三、实验内容 1. 构造算术表达式的四元式翻译文法 2. 设计算术表达式的递归下降子程序分析算法 3. 设计算术表达的四元式生成算法...
  • 编译原理实验,实现了一个词法分析器生成Token序列。中间代码、四元式生成。含有实验报告。
  • 中间代码生成四元式设计

    热门讨论 2012-01-06 09:48:46
    中间代码生成四元式设计 实验报告,从文件中读入表达式,输出其四元式的结果序列 本程序只能生成赋值语句及算数表达式中间代码的四元式 不能生成逻辑表达式及其他复杂语句中间代码的四元式,其功能还需要进一步完善
  • 一、过程调用和函数调用的中间代码 1. 背景信息 形参种类: 值参、变量参数、函数参数 需要的信息: 形参的种类、传送的内容、偏移、传送的个数、函数类型(实在函数、形式函数) 过程调用和函数调用的语法形式 ...

    一、过程调用和函数调用的中间代码

    1. 背景信息

    1. 形参种类:
      值参、变量参数、函数参数
    2. 需要的信息:
      形参的种类、传送的内容、偏移、传送的个数、函数类型(实在函数、形式函数)
    3. 过程调用和函数调用的语法形式
       ProcFunCall -> id (E1, …… , En)
    

    2. 中间代码结构

    在这里插入图片描述

    1. 首先生成参数E1,E2,E3…的中间代码
    2. 然后将实参的计算结果传递到行参中,后面的ti就是前面实参通过中间代码生成的结果
    3. 最后通过四元式(CALL,<f>,true/false,Result)定位到具体id对应的函数体部分执行,

    关于动态确定转向地址的解释:比如函数的行参是另一个函数function f(G:func):int return{G(1)+G(2)}对于G(1)这个形式的函数调用,G的地址是动态确定的,因为当前不知道具体哪个函数G会被真正的传入function f中作为参数,所以是动态确定的。

    3. 过程调用和函数调用的中间代码

    Gem目前的情况:
    知道参数个数在Gem中取出参数id和前面的压入的语义信息中的中间代码是否相同
    (En.typ,En语义信息)
    ...
    (E1.typ,E1语义信息)
    (-,id)
    

    要检查的语义错误:

    1. id是不是函数名
    2. 每个实参Ei和形参Xi的类型和种类方面是否匹配
    3. 实参个数和行参个数是否相同

    假设有实在函数调用 f(X+1,Y),并且 x 是一般整型变量,Y 是变参整型变量,f函数名,同时假定 f 的两个形参第一个是值参、整数类型,第二个是变参、整数类型,则对应的中间代码如下:

    (+,X,1,t1)
    (ValACT,t1,Offset1,1)//如果是值参=ValACT
    (VarACT,Y,Offset1+1,1)//如果是变参(地址)=VarACT
    (CALL,f,true,t2)
    //Offset1和Offset1+1分别代表函数f的第1、2个参数的偏移量
    

    4. 过程调用和函数调用的动作文法

    这里是用自底向上的分析来添加的动作文法,由于自底向上的动作文法只能添加到尾部,为了同样实现在“任意位置插入”,通过一个间接推导的方式实现:
    Recall->ID(visit)
    ID->id # 语义动作
    原:Recall->id (visit) 希望在id后添加语义动作

    <ProcFunCall> -> M(List) #send_turn 
    M -> id #push1  
    List -> E #nextlist
    List -> List,E #nextlist
    
    1. #push1的语义动作:将id压入Sem栈,参数计数器i为0
    2. #nextlist的语义动作:E已经在栈中,参数计数器累加,i++
    3. #send_turn的语义动作:
      a. 取出id:sem(s-i-1)的所有语义信息;
      b. 依此检查形、实参个数是否一致,检查形、实参类型是否相容;
      c. 产生送实参信息到形参信息的ValAct/VarAct中间代码;
      d. 根据f是实在过程(函数)名或形式过程(函数)名产生相应的CALL代码;
      e. 删除当前过程 ⁄ 函数调用语句所占的i+1个语义栈单元,如果f是函数,则把返回值的类型和语义信息压入Sem栈。

    例题:
    x + f (H(10), g(Y))
    【其中:x是整型变量,H为返回值是整型的形参函数名,H的 形参为整型值参,f,g为返回值是整型的实在函数名,f的参数均为整型值参,g的参数为变参。】

    //Offset1表示函数H、g以及f的第一个参数的偏移量
    (ValACT,10,Offset1,1)
    (CALL,H,false,t1)//H是行参函数名,所以是false;f、g是整型的实在函数名所以是true
    (VarACT,Y,Offset1,1)
    (CALL,g,true,t2)
    (ValACT,t1,Offset1,1)
    (ValACT,t2,Offset1+1,1)
    (CALL,f,true,t3)
    (+,x,t3,t4)
    

    二、控制语句的中间代码生成

    1. GOTO语句和标号定位的中间代码

    goto L的中间代码(JMP,-,-,L)
    L:S的中间代码(Label,-,-,L)S.code//S的中间代码
    
    动作文法、代码生成算法:
    S -> goto L #goto  
    S -> DL: S 
    DL -> L #label
    
    对于标号表有定义情况:
    1. #goto 的语义动作
      L是指向标号表中对应的位置。
      Gen(goto,-,-,sem(s-1)) pop(1)
    2. #label 的语义动作
      Gen(label,-,-,sem(s-1)) pop(1)
    对于标号表没有定义的情况、且标号无需声明的语言,要在过程中创建标号表ArrayL:

    地址回填技术
    由于goto语句跳转分为两种情况:向前跳转/向后跳转。向前跳转的时候一般转移地址已知,向后跳转的时候一般跳转地址尚未确定。所以需要先使用当前生成的四元式的标号代替,当知道转移地址的真实值之后再将转移地址填入。

    1. #goto 的语义动作
      (1)查ArrayL,如果没有则产生一条缺欠(需回填)转移地址的中间代码: (JMP , — , — ,— ),并把标号Li、该四元式的地址以及表示该标号为未定位的标记,添加到ArrayL 。若有则: Li是已经定位的了,从ArrayL中取出它的地址LLi,然后产生中间代码 :
    ( JMP ,,,  LLi )

    Li是未定位的,则从ArrayL中取出它的地址LLi,然后产生需回填转移地址的中间代码 :

    ( JMP ,,, LLi )

    ArrayL( Li )的地址填入上述中间代码编号。

    具体实现的时候,先知道当前是JMP,但是后面的转移地址还未知,先将后面的转移地址部分用0填充,等到执行到跳转部分可以得出转移地址之后,再生成一个JMP部分为0,但转移地址部分为已知LLi的四元式而后将二者合并

    1. #label的语义动作:
      产生中间代码: ( LABEL , — , — , L), 然后查ArrayL:
      如果没有标号L则把该标号及其相应的语义信息加入中ArrayL,并且标记为已定位;
      如果有标号Li并标为未定位,则往对应的所有四元式回填地址

    具体GOTO语句和标号定位中间代码的示例:(为了回填的速度快一点,属于实现方式)

    在这里插入图片描述

    首先第一个goto语句要转移到的地方L1地址未知,当前标号未定位,内部标号的位置将当前生成的四元式的序号填入

    在这里插入图片描述
    继续执行下一个goto语句,很自然的将这个生成的四元式的转移地址部分写上ArrayL中内部标号的内容也就是m,然后当前的四元式执行到第n条,再更新ArrayL中的内部标号为n。

    在这里插入图片描述
    操作同上。
    在这里插入图片描述

    执行到40语句知道L1转移地址,可以将当前地址更新为LL1,然后将前面第m、n、p语句的四元式中的转移地址部分填入LL1,最后更改ArrayL中的内部标号部分为LL1.
    在这里插入图片描述
    将之前没有填入具体的转移地址部分的四元式替换为转移地址生成为LL1已经确定的语句。

    在这里插入图片描述
    最后50语句正常执行。

    2. 条件语句的中间代码

    在这里插入图片描述
    解释说明:
    第一个(then,,-,-)判断当前条件是否成立,然后转移到S1还是S2部分
    第二个(else,-,-,-)的作用是当满足执行E1的条件成立的时候如果执行S1结束之后需要跳过S2部分才能继续执行,所以这里起到一个转移定位的作用

    在这里插入图片描述

    条件语句的动作文法:

    同样是自底向上,不能直接插入语句的任意部分,所以间接操作一下。
    在这里插入图片描述
    从LR分析的角度来说,当出现移入-归约冲突的时候采用移入优先的规则
    在这里插入图片描述

    3. while语句的中间代码

    在这里插入图片描述
    解释说明:
    首先是(while,-,-,-)因为执行完每次循环体之后都要返回到循环的开始部分重新判断条件是否满足;
    然后是E判断部分的中间代码:
    然后是(do,e.form,-,-)的条件判断是否可以执行
    然后执行while的循环体部分代码
    最后要有一个定位转移到while位置的四元式(endwhile,-,-,-)

    在这里插入图片描述

    三、过程/函数声明的中间代码生成

    在这里插入图片描述
    进入函数之前写一句:(entry,Q,-,-)
    函数执行之后写一句:(endproc/endfunction,-,-,-)结束函数或过程体
    在这里插入图片描述
    函数声明的中间代码主要由函数体的中间代码组成,其中函数体则有语句序列组成,而我们已经知道语句的中间代码及其生成方法,因此只需要考虑补充哪些中间代码。把符号表中与目标代码生成期间需要的有关函数信息以中间代码的形式保存起来,例如函数的入口标号、空间大小、层数信息等。
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 编译器前端对中间代码进行优化 编译器后端对目标代码进行优化 两个编译器必须等价,编译的结果必须是正确的,即使有99.99%的可能性是不正确的,但是效率很好也不行,正确性是根本。 二、中间代码优化的分类 从...

    一、代码优化的阶段

    欲提高源程序的运行速度,需要经过几个阶段的优化:

    1. 用户对源程序进行优化(和编译器无关,与coder设计的算法有关)
    2. 编译器前端对中间代码进行优化
    3. 编译器后端对目标代码进行优化

    两个编译器必须等价,编译的结果必须是正确的,即使有99.99%的可能性是不正确的,但是效率很好也不行,正确性是根本。

    二、中间代码优化的分类

    从优化的种类来看,中间代码的优化可有如下分类:

    1. 局部优化

    循环上的优化(所有优化方法效果最好的)
    1. 循环不变体外提
    循环中不因循环而改变的部分可以提到循环的外部
    2. 削减运算强度
    在一些循环上的计算转换成另一种计算方式实现,比如b=a*2 -> b=a+a
    基本块的优化(按照某些规则划分成基本块)
    1. 常表达式节省
    2. 公共子表达式节省

    1. 全局优化

    全局数据流分析,从而使优化的效果更好
    考虑基本块里如何优化,已经得到的值和变量的表,全局得到更多的信息进行分析。
    在局部优化的基础上进行全局优化才有更大的提高,否则直接进行全局优化的提升效果不明显。

    三、常见的编译优化的种类

    1. 数学上的优化

    情况一:(主要是在生成中间代码的时候会产生)

    (-,a,0,t1) (*,a,1,t2)
    //这种a+0,和a*1的没有太大意义的运算,这样的四元式可以删除
    //正常写普通的代码一般不会出现这种情况
    //但是在一些不明显的地方,比如计算数组中的元素a[i]时,用【i-(数组下界)】xsize
    //数组下界为0的时候和size=1的时候都会产生上面的四元式
    //可直接换但是还要将运算结果进行处理
    

    情况二:

    2*a->a+a
    a^2->a*a
    

    原则上说,可以不计算的直接删去其四元式,直接写出结果;高运算强度的可以转化成低运算强度的。

    2. 表达式短路问题

    在这里插入图片描述
    如果在计算一个表达式的时候可以不用将整个表达式的值都计算出来就可以确定表达式的结果,在这种情况下,后面的计算可以省略。
    或运算:如果计算出第一个表达式的结果是1可以直接返回 true
    与运算:如果计算出第一个表达式的结果是0可以直接返回false

    3. 常表达式的节省

    • 计算过程中有一个表达式是33.14,这个实际上是两个常数,他的结果我是可以计算出来的,这样我们在编译的过程中把33.14算出来,在目标程序的进行中就不用进行计算了。
    • 通过编译程序将可以计算出的结果直接计算出来然后将相应位置替换成计算出的结果。
    • 把有关工作交给编译程序进行可以提高生成的目标程序的运行效率,编译程序可以稍微慢些的工作,因为最后看的还是生成的目标程序的运行效率。

    4. 公共子表达式节省(消除重复操作)

    在这里插入图片描述

    • 所谓公共子表达式即两个子表达式的计算结果是一样的,不需要重复的进行计算,第一次计算出来之后,后面的计算可以利用前面的计算结果。例如前面有表达式ab,后面又有表达式也是ab,而且在第二个表达式和第一个表达式中间,a和b的值没有被改变过,那第二个a*b表达式实际上是可以不用计算的,只需要把前面的计算结果拿过来就可以达到计算的目的。
    • 这种情况在下标变量的计算中体现的非常明显,比方说a[i][j]和a[i][k],下标变量的计算先计算a[i]的地址然后计算j,然后计算a[i][j]的地址,a[i][k]也是一样先计算a[i]的地址在根据k计算a[i][k]的地址,所以前面关于a[i]的计算结果是完全一样的。这样就可以不用重复计算,利用前面的结果达到计算目的。

    5. 循环不变量式外提

    在这里插入图片描述
    循环不变式外提,在循环中,如果有一个表达式的值在循环中不会改变,就需要把它提到循环体的外面去。比方说有一个双重循环1-100和1-100,那么整个两重循环计算下来就是1万次,比方说里面有一个ab的表达式,在循环过程中ab的值如果不改变,那他就重复计算了9999次,假如把ab提到循环体的外面只需要计算1次,在循环里只需要用到它的计算结果。所以这样的表达式在循环体里面是不变的,我们要把他提到循环体的外面,从而提高我们的执行效率,这种效率的提高是最高的。特别是计算量很大的情况下,比方说有多重循环,这种循环不不变式外提可以大大提高程序的执行效率,这种提高的效率大概可以提高十几倍甚至是几十倍,串式程序的并行处理很大的一个研究重点,都是放在循环的并行计算上,比方说1~1000次的循环把它分成段,在不同的处理机上进行执行,从而提高程序的执行效率

    6. 削减程序的运算强度

    在这里插入图片描述
    削减程序的运算强度。这个也通常是针对循环的,一种特例的情形,比方说在程序设计语言中通常来说,一般的程序循环有三种方式分别是:
    1)for循环(有的语言中也称作是步长式的循环),循环形式是for i=e1 to e2 ;step e3{} 也就是说它的执行是i开始获取一个循环初值e1,然后每次循环i都加上e3的值,一直当i大于e2就结束循环,比方说for1=1to 100;step 1,就是1-100步长是1执行100次。
    2)while循环,“当型循环”()
    3)直到型循环 do until ~~的形式

    7. 寄存器优化

    在这里插入图片描述

    生成目标代码的时候一定是和目标机相关的,对于目标机来说提供多少个寄存器,比方说提供了8个,当目标程序真正执行的时候,这8个寄存器是如何被分配的,这是一个问题。简单的说假如说寄存器有空闲的时候,分配方案比较简单,空闲的就分配,这个没问题,什么时候会有问题呢?
    有这样几种情况:
    要用寄存器的时候,是否有空闲的寄存器,如果没有空闲的怎么办?需要剥夺一个寄存器,如何来剥夺?类似的还有内存和外存进行淘汰页的算法是类似的,只不过这个是在更高一级的层面上,寄存器和内存间的变换。这是寄存器分配优化

    8. 消除无用语句,消除冗余代码

    在这里插入图片描述

    消除无用语句,消除冗余代码,假如一个条件语句,if e s1 else s2 ,如果表达式E的值是一个true,那么s2是不可能用到了,所以这个命令就可以删掉了,这个命令也直接可以用s1来替换掉,当然这是一种特殊的情形,产生冗余代码实际上也是这么产生的

    9. 中间变量优化

    在这里插入图片描述

    中间变量的优化,生成中间代码的时候会产生大量的临时变量,大量的临时变量的特点一般都是产生之后使用一次就会不再用了,如果是说有一些临时变量和另外一些临时变量之间没有交集的话,不需要为每一个临时变量都分配独立的存储单元。最简单的方式,把产生临时变量一直到使用临时变量这个区域比方说把它定义为临时变量的活动区,假如两个临时变量的活动区不相交,实际上他们可以共用同一个存储单元,那么这种优化实际上就是临时变量的存储空间上的优化

    10. 目标代码优化

    在这里插入图片描述

    是目标代码的优化,可以通过确定目标代码来减少目标程序的指令个数来提高目标程序的执行效率,比方说有一个变量的值在寄存器里,运算出来的中间结果在寄存器里,假如直接让他参与运算之后,就不用往内存中存了,什么时候需要存,什么时候不存,什么时候需要把它放在寄存器里,这就是需要对目标程序进行的一种优化,根据使用情况来进行。

    11. 全局优化

    在这里插入图片描述
    总而言之这种优化还有很多,比方说全局的数据流分析和全局的优化,因为前面考虑实现的时候由于优化的技术可能比较复杂,都是在局部区做的,比方说一个基本块上做的,要想做到全局的需要对全局的程序做全局的数据流分析,这样的话可能就更复杂了,如果没有特殊需求,一般来说是不做这样的优化的:
    第一个原因就是编译代价太大,因为要做各种各样的分析,导致编译代价很大。
    第二就是提高的效率也并不是十分的明显。

    如果说没有特殊的需求,前面做的局部优化已经能达到想要的效果,全局优化就不用做了,特殊需求的时候才想办法处理。

    ⚠️优化中要注意的一个问题就是优化是在保证正确的情况下进行的,任何一个程序的优化也不能做到最优,而是在一定程度上来提高程序的执行效率。所以优化的过程一定是在保证程序正确的前提下来进行的。

    四、基本块

    (一)基本块的定义

    在这里插入图片描述

    • 基本快:是一个命令的序列,每一条命令都是按照顺序来执行的,进入基本块只能从第一条命令进入,退出基本块只能从最后一条命令退出,也就是说基本块是一个整体,要执行的话就全都执行从头到尾的顺序执行,这样一个特性对于程序进行分析或者是对中间代码进行分析有什么好处呢?对程序基本块中变量的性质是可判定的,假如不是基本块的话,x=10;L y=x+1;如果说只能从x=10这条语句顺序执行的话,y=x+1,这个x就是一个已知的,就是10,y就是11.但是假如说它有另外一个入口,其他地方有一个goto L,就不能判断x的值是不是10,因为外面有一个转移,比方说x=1; goto L x的值就不一定是10了,不是基本块的话程序的性质就不太好判断
    • 假如说是一个基本块都是顺序往下执行的话,那么每一个变量的值是怎么获取的、怎么传播出来的,就可以判断出来,这对我们的处理就非常有意义。因此在基本块上做优化使得问题变的相对简单了。

    (二)基本块的划分原则

    在这里插入图片描述

    1. 进入一个程序,(整个程序的第一条)四元式就是一个基本块的入口四元式;
    2. 遇到一个转移性的四元式,这条转移性的四元式是结束了一个基本块,它的后续四元式就可以作为下一个基本块的第一条四元式;
    3. 遇到一个定位性的四元式或者是标号性的四元式,就结束一个基本块,并作为下一个基本块的第一条四元式;
    4. 那么遇到一些函数的结束标示,就结束当前的四元式。例如p=&x; *p=5; y=x+x; 因为p是间接取址的,所以要结束这个标准块,否则也还是不知道如何来判断。

    在这里插入图片描述
    比方说goto还有(then t1,- ,-)目标程序运行到这的时候要判断t1是真是假,如果是假的话就要跳过t1,所以一定是要产生一个跳转指令的,还比如else这种,也就是说s1执行完一定要产生一个跳转指令跳过s2。
    在这里插入图片描述
    比方说循环指令中的while四元式,当循环体循环结束之后要产生一个跳转指令,要转移到前面重复计算的表达式的位置,假如没有这样一个四元式, 就没有办法确定转移到什么地方。这样的四元式就起到一个定位型四元式,还有比方说endif等等。还有对间接变量的赋值,也表示一个基本块的结束,这是基本块划分的原则,总的来说最关键的两点就是遇到转移型四元式和定位型四元式的开始
    在这里插入图片描述
    在这里插入图片描述

    五、常表达式节省

    在编译过程中能够计算出值的表达式,就在中间代码这级给它计算一个结果,这样就不需要在目标程序执行的时候进行计算了。
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    1. 首先构造一个表,即变量的值表,表中元素是一个二元组,表项左部是一个变量名或者是一个临时变量,右边是已知它的值是什么,就填到这里。
    2. 以后的优化算法也就比较简单,通常来说是这样做的:进入到一个基本快的时候把这个表清空,遇到一个运算型的四元式,比方说有算符 a b t1,首先看一下a和b是不是常量,如果是常量当然可以进行计算,就把t1填到表里。如果是变量的话,就要去表中查一下有没有变量对应的值,如果有值,就把这个变量用值来替换然后来看看可不可以进行计算,能计算就进行计算,不能计算替换完了之后,值就放到四元式中。
    3. 如果遇到一个赋值型四元式,比方说b=a,就要到表里去查a有没有值,如果a是已知的,就把b填到表里,把a的值取出来填给b。按照这样顺序进行计算,能够算出常量值的四元式就被节省掉了。这里要注意,运算型的四元式实际上第一步,严格来说,用常量值替代运算符,比方说3*3.14 t1,就算出t1的结果,以后用到t1的时候就从表里取t1的值就可以了
    4. 中间可以夹杂着用常量定值表对原有四元式进行替换,如果四元式都变成常量的就删除,否则就留着

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 文章目录1 实验目的和内容1.1 实验目的1.2 实验内容...(1)通过上机实习,加深对语法制导翻译原理的理解,掌握将语法分析 所识别的语法范畴变换为某种中间代码的语义翻译方法。 (2)掌握目前普遍采用的语义分析方法─

    1 实验目的和内容

    1.1 实验目的

    (1)通过上机实习,加深对语法制导翻译原理的理解,掌握将语法分析 所识别的语法范畴变换为某种中间代码的语义翻译方法。

    (2)掌握目前普遍采用的语义分析方法──语法制导翻译技术。

    (3)给出 PL/0 文法规范,要求在语法分析程序中添加语义处理,对于语法正确的表达式,输出其中间代码;对于语法正确的算术表达式,输出其计算值。

    1.2 实验内容

    已给 PL/0 语言文法,在实验二或实验三的表达式语法分析程序里,添加语义处理部分,输出表达式的中间代码,用四元式序列表示。

    1.3 实验要求

    (1)语义分析对象重点考虑经过语法分析后已是正确的语法范畴,本实 验重点是语义子程序。

    (2)在实验二或实验三“语法分析器”的里面添加 PL/0 语言“表达式”部分的语义处理,输出表达式的中间代码,计算表达式的语义值。

    (3)中间代码用四元式序列表示。

    2 设计思想

    2.1 语义规则

    属性计算的过程即是语义处理的过程对于文法的每一个产生式配备一组属性的计算规则,则称为语义规则。

    (1)终结符只有综合属性,它由词法分析器提供。

    (2)非终结符既可以有综合属性也可以有继承属性,文法开始符号的所有继承属性作为属性计算前的初始值。

    (3)产生式右边符号的继承属性和产生式左边符号的综合属性都必须提供一个计算规则。

    (4)产生式左边符号的继承属性和产生式右边符号的综合属性由其它产生式的属性规则计算。

    2.2 递归下降翻译器

    递归下降分析法的原理是利用函数之间的递归调用来模拟语法树自上而下的构建过程。从根节点出发,自顶向下为输入串中寻找一个最左匹配序列,建立一棵语法树。对于每个非终结符的继承属性当作形式参数,函数的返回值当作非终结符的继承属性;对于终结符要初始化所有的继承属性。再进行分析过程中,非终结符根据当前的输入符号决定使用哪个产生式候选。

    2.3 递归下降子程序伪代码

    (1)表达式

    function表达式:string;
    string s1, s2, s3, result;
    BEGIN
      IF SYM=+’ OR SYM=-’ THEN
      ADVANCE;
      ELSE IF SYM =FIRST() 
      ELSE ERROR;
      BEGIN s1:=;
      END;
      WHILE SYM=+’ OR SYM=-’ THEN
      BEGIN
        ADVANCE;
        S2:=;
        result := newtemp();
        emit(SYM,s1,s2,result);
        s1:= result;
      END;
      Return result;
    END;
    

    (2)项

    function 项:string;
    string s1, s2, s3, result;
    BEGIN
      IF SYM =FIRST(因子) THEN
      BEGIN
        s1:=因子;
      END;
      ELSE ERROR;
      WHILE SYM =*’OR SYM=/’ THEN
    IF SYM =FIRST(因子) THEN 
      BEGIN 
        ADVANCE;
        S2:=因子;
        result := newtemp();
        emit(SYM,s1,s2,result);
        s1:= result;
      END;
      Return result;
    END;
    ELSE ERROR;
    

    (3)因子

    function 因子:string;
    string s;
    BEGIN
      IF SYM =(’ THEN
      ADVANCE;
      s:=表达式;
    ADVANCE; 
      IF SYM=)’ THEN
      ADVANCE;
    Return s; 
    ELSE ERROR; 
      ELSE IF SYM =FIRST(因子) THEN
    ADVANCE;
      ELSE ERROR;
    END;
    

    3 算法流程

    算法流程图如下所示,首先输入表达式,然后进行词法分析,把词法分析的结果存在结构体中,之后调用递归下降分析器中的表达式子程序进行分析,最后得到四元组并存在相应的结构体中,下一步进行判断,如果是算术表达式,就计算该算术表达式的值并输出,如果不是算术表达式,就不做处理,直接输出四元组,最后判断程序的输入是否结束,如果没有结束,就再次输入表达式,重复上述步骤,如果结束,则程序退出。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fM7peODy-1634978806002)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7B8D.tmp.jpg)]

    图1 算法流程图

    4 源程序

    #include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    using namespace std; 
    
    //存储词法分析的结果
    struct cf_tv
    {
      string t;  //词法分析的类型
      string v;  //词法分析变量的值
    };
    
    //存储四元组
    struct qua
    {
      string symbal;  //符号
      string op_a;   //第一个操作数
      string op_b;   //第二个操作数
      string result;  //结果
    };
    
    string input; //全局输入
    int cnt;    //全局变量
    int k=0;    //tv输入
    int ljw=0;
    cf_tv result[200]; //存放结果
    qua output[200];  //存放输出的四元组
    int x=0;      //qua 的下标
    int ans=0;     //遍历的时候的下标
    bool error=true;  //出错标志
    int is_letter=0;
    int t[1001];    //临时存放空间
    string item();
    string factor();
    
    //产生新变量名t1,t2等
    string new_temp()
    {
      char *pq;
      char mm[18];
      pq=(char*)malloc(18);
      ljw++;
      //转换成字符串格式
      snprintf(mm,sizeof(mm),"%d",ljw);
      strcpy(pq+1,mm);
      pq[0]='t';
      string s;
      s=pq;
      return s;
    }
    
    //判断是否和目标串匹配
    bool judge (string input, string s)
    {
      if (input.length()!=s.length()) return false;
      else
      {
        for(unsigned int i=0;i<s.length();i++)
        {
          if(input[i]!=s[i]) return false;  //遍历
        }
        return true;
      }
    }
    
    //判断是否和目标串匹配
    bool judge1 (string input, string s)
    {
      if(input[0]==s[0]) return true;
      else return false;
    }
    
    //判断非符号的程序,包含判断关键字,标识符,常数
    void not_fh(string p)
    {
      //判断是否跟目标串相同,相同的话输出结果
      if(judge (p,"begin"))
         {
           result[k].t="beginsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"call"))
         {
           result[k].t="callsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"const"))
         {
           result[k].t="constsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"do"))
         {
           result[k].t="dosym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"end"))
         {
           result[k].t="endsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"if"))
         {
           result[k].t="ifsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"odd"))
         {
           result[k].t="oddsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"procedure"))
         {
           result[k].t="proceduresym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"read"))
         {
           result[k].t="readsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"var"))
         {
           result[k].t="varsym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"then"))
         {
           result[k].t="thensym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"write"))
         {
           result[k].t="writesym";
           result[k].v=p;
           k++;
         }
         //判断是否跟目标串相同,相同的话输出结果
         else if(judge (p,"while"))
         {
           result[k].t="whilesym";
           result[k].v=p;
           k++;
         }
         else
         {
           int flag = 0;
           for(unsigned int i=0;i<p.length();i++)
           {
             //判断是否是标识符
             if(!isdigit(p[i]))
             {
               flag = 1;
               result[k].t="ident";
               result[k].v=p;
               k++;
               break;
             }
           }
           //判断是否是数字
           if(!flag)
           {
             result[k].t="number";
             result[k].v=p;
             k++;
           }
         }
    }
    
    //防止多个运算符组成,返回正确下标
    int change(string str,int cnt)
    {
      int y=0;
      char fh[15]={'+','-','*','/','=','<','>',':','(',')',',',';','.'};
      for(int i=0;i<13;i++)
      {
        if(str[cnt]==fh[i])
        {
          y=i;
        }
      }
      if(y==5)
      {
        //如果运算符是两个符号组成,cnt+1
        if(str[cnt+1]=='>')
        {
          cnt=cnt+1;
          return cnt;
        }
        //判断两个运算符相连
        else if(str[cnt+1]=='=')
        {
          cnt=cnt+1;
          return cnt;
        }
      }
      //判断:=
      if(y==7)
      {
        cnt=cnt+1;
        return cnt;
      }
      return cnt;
    }
    
    //对运算符和界符的输出
    void fh_1(string str,int cnt)
    {
      int y=0;
      char fh[15]={'+','-','*','/','=','<','>',':','(',')',',',';','.'};
      for(int i=0;i<13;i++)
      {
        if(str[cnt]==fh[i]) y=i;
      }
      //plus
      if(y==0)
      {
         result[k].t="plus";
         result[k].v=fh[y];
         k++;
      }
      //minus
      if(y==1)
      {
         result[k].t="minus";
         result[k].v=fh[y];
         k++;
      }
      //times
      if(y==2)
      {
         result[k].t="times";
         result[k].v=fh[y];
         k++;
      }
      //slash
      if(y==3)
      {
         result[k].t="slash";
         result[k].v=fh[y];
         k++;
      }
      //eql
      if(y==4)
      {
         result[k].t="eql";
         result[k].v=fh[y];
         k++;
      }
      if(y==5)
      {
        //neq
        if(str[cnt+1]=='>')
        {
          cnt=cnt+1;
          result[k].t="neq";
          result[k].v="<>";
          k++;
        }
        //leq
        else if(str[cnt+1]=='=')
        {
           result[k].t="leq";
           result[k].v="<=";
           k++;
        }
        //lss
        else
        {
           result[k].t="lss";
           result[k].v="<";
           k++;
        }
      }
      if(y==6)
      {
        //geq
        if(str[cnt+1]=='=')
        {
           result[k].t="geq";
           result[k].v=">=";
           k++;
        }
        //gtr
        else
        {
           result[k].t="gtr";
           result[k].v=">";
           k++;
        }
      }
      //becomes
      if(y==7)
      {
        result[k].t="becomes";
        result[k].v=":=";
        k++;
      }
      //lparen
      if(y==8)
      {
        result[k].t="lparen";
        result[k].v="(";
        k++;
      }
      //rparen
      if(y==9)
      {
        result[k].t="rparen";
        result[k].v=")";
        k++;
      }
      //comma
      if(y==10)
      {
        result[k].t="comma";
        result[k].v=",";
        k++;
      }
      //semicolon
      if(y==11)
      {
        result[k].t="semicolon";
        result[k].v=";";
        k++;
      }
      //period
      if(y==12)
      {
        result[k].t="period";
        result[k].v=".";
        k++;
      }
    }
    
    //词法分析
    void cifa()
    {
      string str;
      while(cin>>str)
      {
        cnt=0;
        const char *d = " +-*/=<>:(),;.";
        char *p;
        //运用空格和运算符和界符分割字符串并且遍历
        char buf[1001] ;
        //字符串转成数组
        strcpy(buf , str.c_str());
        //p是一个char*
        p = strtok(buf,d);
        while(p)
        {
          //当前无符号
          if(str[cnt]==p[0])
          {
             not_fh(p);
             cnt=cnt+strlen(p);
          }
          //当前是符号
          else
          {
            while(str[cnt]!=p[0])
            {
              fh_1(str,cnt);
              cnt=change(str,cnt);
              cnt=cnt+1;
            }
            not_fh(p);
            cnt=cnt+strlen(p);
          }
          //下移一位,进行遍历
          p=strtok(NULL,d);
        }
        for(unsigned int i=cnt;i<str.length();i++)
        {
          //防止最后有多个符号
          fh_1(str,i);
        }
      }
    }
    
    //判断是哪种类型的计算
    void judge_type()
    {
      for(int i=0;i<k;i++)
      {
        if(judge(result[i].t,"ident"))
        {
          is_letter=1;
          break;
        }
      }
    }
    
    //表达式的递归下降分析函数
    string bds()
    {
      string s;
      string s1,s2,s3;
      if(ans>k) return NULL;
      //加减符号
      if(judge(result[ans].v,"+") || judge(result[ans].v,"-"))
      {
        ans++;
        if(ans>k)
        {
          cout<<1<<endl;
          //error
          error=false;
        }
        s1=item();
      }
      else if( judge(result[ans].v,"(") ||judge(result[ans].t,"ident") ||judge(result[ans].t,"number"))
      {
        //项目判定,前面条件是first集合
        s1=item();
      }
      else
      {
        cout<<2<<endl;
        //error
        error=false;
      }//
      while(judge(result[ans].v,"+") || judge(result[ans].v,"-"))
      {
        int ans_temp=ans;
        ans++;
        if(ans>k)
        {
          cout<<3<<endl;
          //error
          error=false;
        }
        //项目循环
        s2=item();
        output[x].symbal=result[ans_temp].v;
        output[x].op_a=s1;
        output[x].op_b=s2;
        output[x].result=new_temp();
        s=output[x].result;
        s1=s;
        x++;
      }
      return s;
    }
    
    //项的递归下降分析函数
    string item()
    {
      string s;
      string s1,s2,s3;
      if(ans>k) return NULL;
      //因子判断
      s1=factor();
      while(judge(result[ans].v,"*") || judge(result[ans].v,"/"))
      {
        int ans_temp=ans;
        ans++;
        if(ans>k)
        {
          cout<<4<<endl;
          //error
          error=false;
        }
        s2=factor();
        output[x].op_a=s1;
        output[x].symbal=result[ans_temp].v;
        output[x].op_b=s2;
        output[x].result=new_temp();
        s=output[x].result;
        s1=s;
        x++;
      }
      return s1;
    }
    
    //因子的递归下降分析函数
    string factor()
    {
      string s;
      if(ans>=k) return NULL;
      //开头字母或数字
      if(judge(result[ans].t,"ident") ||judge(result[ans].t,"number"))
      {
        s=result[ans].v;
        ans++;
        if(ans>k)
        {
          cout<<5<<endl;
          //error
          error=false;
        }
      }
      //左括号
      else if(judge(result[ans].v,"("))
      {
        ans++;
        //表达式
        s = bds();
        //右括号
        if(judge(result[ans].v,")"))
        {
         ans++;
         if(ans>k)
         {
           cout<<6<<endl;
           //error
           error=false;
         }
        }
      }
      else
      {
        cout<<7<<endl;
        //error
        error=false;
      }
      return s;
    }
    
    //删除第一个字母
    string del(string s)
    {
      char c[101];
      for(unsigned int i=0;i<s.length()-1;i++)
      {
        c[i]=s[i+1];
      }
      return c;
    }
    
    void js(int i)
    {
      char* end;
      //如果是乘法
      if(judge(output[i].symbal,"*"))
      {
        //判断第一个符号是字母还是数字
        if(!judge1(output[i].op_a,"t"))
        {
          if(!judge1(output[i].op_b,"t"))
          {
            //强制类型转换
            t[i+1]=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10))*static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
          }
        }
      }
      else
      {
        if(!judge1(output[i].op_b,"t"))
        {
          string ss;
          ss=del(output[i].op_a);
          //强制类型转换
          int z=static_cast<int>(strtol(ss.c_str(),&end,10));
          t[i+1]=t[z]*static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
        }
        else
        {
          string s;
          s=del(output[i].op_a);
          int yy=static_cast<int>(strtol(s.c_str(),&end,10));
          string ss;
          ss=del(output[i].op_b);
          int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
          t[i+1]=t[yy]*t[zz];
        }
      if(judge(output[i].symbal,"+"))
      {
        if(!judge1(output[i].op_a,"t"))
        {
          if(!judge1(output[i].op_b,"t"))
          {
            t[i+1]=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10))+static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
          }
          else
          {
            string ss;
            ss=del(output[i].op_b);
            int yy=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10));
            int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
            t[i+1]=yy+t[zz];
          }
        }
        else
        {
          if(!judge1(output[i].op_b,"t"))
          {
            string ss;
            ss=del(output[i].op_a);
            int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
            t[i+1]=t[zz]+static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
          }
          else
          {
            string s;
            s=del(output[i].op_a);
            int yy=static_cast<int>(strtol(s.c_str(),&end,10));
            string ss;
            ss=del(output[i].op_b);
            int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
            t[i+1]=t[yy]+t[zz];
          }
        }
      }
     }
    }
    
    int main()
    {
      //词法分析函数
      cifa();
      //判断类型
      judge_type();
      //语法分析和语义分析
      bds();
      //进行输出
      if(is_letter==1)
      {
         for(int i=0;i<x;i++)
        {
          cout<<"("<<output[i].symbal<<","<<output[i].op_a<<","<<output[i].op_b<<","<<output[i].result<<")"<<endl;
        }
      }
      //进行输出,计算结果
      else
      {
        for(int i=0;i<x;i++)
        {
          js(i);
        }
        cout<<t[x]<<endl;
      }
      return 0;
    }
    

    5 调试数据

    5.1 测试样例一

    【样例输入】
    2+3*5
    
    【样例输出】
    17
    

    样例一结果如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RjiL6KMD-1634978806011)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7C1B.tmp.jpg)]

    图2 样例一测试结果

    5.2 测试样例二

    【样例输入】
    2+3*5+7
    
    【样例输出】
    24
    

    样例二结果如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OdYoOdcP-1634978806014)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7C2C.tmp.jpg)]

    图3 样例二测试结果

    5.3 测试样例三

    【样例输入】
    a*(b+c) 
    
    【样例输出】
    (+,b,c,t1)
    (*,a,t1,t2)
    

    样例三结果如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2ElSTqE0-1634978806025)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7C2D.tmp.jpg)]

    图4 样例三测试结果

    5.4 测试样例四

    【样例输入】
    a*(b+c)+d
    
    【样例输出】
    (+,b,c,t1)
    (*,a,t1,t2)
    (+,t2,d,t3)
    

    样例四结果如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3TAgwESy-1634978806030)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wps7C2E.tmp.jpg)]
    图5 样例四测试结果

    6 实验调试情况及体会

    6.1 实验调试情况

    由上一步中的四个测试样例可以得到,所有的测试样例均得到了相应的输出结果,说明代码编写成功,并且在代码中设置了出错处理,以便解决其他情况。

    6.2 实验体会

    这次实验在上课之前及时的进行了预习,在编写代码之前需要写出递归下降翻译器的伪代码,重点就是要找到对于每个非终结符的属性哪些是继承属性,哪些是综合属性。然后将继承属性作为参数,综合属性作为返回值,进行计算。

    编写代码的时候,需要用到实验一和实验二的代码,写实验一代码的时候没考虑到后面会用到,直接将结果输出并没有保存中间结果,以至于自己在编码的时候需要先将实验一的结果存放在一个自定义的结构体中,里面包含词法分析的两个因素:值和类型。而分析器分析的时候,直接调取这个结构体的内容,四元式的结果也会放在一个特殊的结构体,里面记录了四元式的四个值,方便输出。如果是数字运算式,可以模拟计算器对于这四个值进行计算,并且需要数组和判定运算符函数来判断是数字还是辅助变量,根据对应符号进行运算。

    通过这次实验,从词法分析到语法分析到语义分析的知识点有了大致的回顾,并且重点回顾了每个阶段输入什么,输出什么,这些信息怎么存储,用什么算法来计算。还需要进一步优化自己的代码,比如在这次的实验代码过程中,需要改进的是将词法分析和语法分析合并,降低时间复杂度,提高执行效率。

    通过这四次的实验过程,让我对于编译原理这门课有了比较清晰的认识,可能理论课当时听懂了,过一会可能就会遗忘。通过学习编译原理,感觉用到了数据结构,算法等思维理解,又需要对于许多概念的理解记忆。这也是这门课的难点所在。通过这次学习,懂得更要注重对于基础科目的掌握,不断加强和拓展自己的计算机思维。

    最后感谢刘善梅老师对我一学期的悉心指导,不胜感激,我会继续努力学好接下来的每一门专业课程,不负老师厚望!

    展开全文
  • 编译原理-中间代码的生成

    千次阅读 2020-03-30 19:17:46
    一、中间代码简介 中间代码应具备的特性: 1)便于语法制导翻译 2)既与机器指令的结构相近,又与具体机器无关 使用中间代码的好处: 1)一是便于编译器程序的开发和移植 2)二是代码进行优化处理 中间代码的...
  • 语法分析(递归下降)以及中间代码生成语法分析代码详解分割字符读入要分析的程序。主程序。程序的入口(因为是用 jupyter notebook 写的)判断是进入哪一个块。一开始程序的三大块。常量说明,变量说明,语句。...
  • 编译原理--中间代码生成

    千次阅读 2020-01-08 15:25:16
    文章目录基础DAG三地址代码问题声明语句的翻译表达式和赋值语句的翻译控制流翻译布尔表达式的翻译switch 语句的翻译过程调用的翻译回填 基础 DAG 语法树是一种图形化的中间表示。但语法树中,公共子表达式每出现一次...
  • 第五章 语法制导翻译与中间代码生成;第五章 语法制导翻译与中间代码生成;第五章 语法制导翻译与中间代码生成;第五章 语法制导翻译与中间代码生成;第五章 语法制导翻译与中间代码生成;第五章 语法制导翻译与中间代码...
  • 中间代码生成器的设计c++

    热门讨论 2009-01-02 13:03:04
    中间代码生成器的设计,用c++设计。 实验目的 熟悉算术表达式的语法分析与中间代码生成原理。 实验内容 (1) 设计语法制导翻译生成表达式的四元式的算法; (2) 编写代码并上机调试运行通过。 输入——算术表达式 ...
  • 一、生成中间代码的目的 便于优化 让生成的目标代码效率更高 优化不等同于对代码的精简和算法的优化 (对于高级程序设计语言中可能不能继续进行优化,但是仍然可以在编译中进行优化) 比方说多维下标变量地址计算...
  • 编译原理-中间代码生成

    千次阅读 2019-04-17 10:43:52
    如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和质量都比较低,移植性差。 1.2 表示形式 逆波兰式(后缀式)、三地址码(三元式、四元式)、...
  • 编译原理实验七:中间代码生成器

    万次阅读 2019-04-13 12:08:02
    实现一门语言的中间代码生成器(4小时) 实验目的 通过本次实验,加深对中间代码生成的理解,学会编制中间代码生成器。 实验任务 用C、JAVA或其他语言编写一门语言的中间代码生成器,所选实现语言应与之前语言...
  • (2) 编写代码并上机调试运行通过。 ·输入——算术表达式 ·输出——语法分析结果 相应的四元式序列 (3) 本实验已给出递归子程序法的四元式属性翻译文法的设计,鼓励学生在此基础上进行创新,即设计LL(1)分析法或LR...
  • 编译原理之中间代码生成

    千次阅读 2020-04-07 12:35:44
    中间代码定义 源程序的一种内部表示,不依赖目标机的结构,易于机械生成目标代码的中间表示。 如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和...
  • ①掌握中间代码生成的基本方法。 ②掌握语法制导翻译模式。 ③完成算术表达式的中间代码生成程序。 重点及难点:掌握语法制导翻译模式的核心思想和工作原理,在此基础上完成基于算数表达式的中间代码生成程序的设计...
  • 编译原理实验 语义分析与中间代码生成 Sample语言的语义和代码生成规则,熟悉Sample语言的语义分析和代码生成过
  • 编译原理:中间代码生成

    千次阅读 2020-08-22 15:42:19
    翻译为中间语言的好处: (1)便于进行与机器无关的代码优化; (2)使编译程序改变目标机更容易;易于编译器的移植 (3)使编译程序的结构在逻辑上更为简单明确,以中间语言为界面,编译前端和后端的接口更清晰...
  • 另一个称为执行表,它按照三元式的执行顺序,依次列出相应各三元式在三元式表中的位置,也就是说我们用一个三元式表连同执行表来表示中间代码。通常我们称这种表示方法为间接三元式。 3.三元式、四元式、间接三元式...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,292,411
精华内容 516,964
关键字:

中间代码

友情链接: 2DBspline.rar