Geekerstar

编译原理实验(二)语法分析器的设计
1 概述通过某种高级语言(如C/C++,Java)实现语法分析器的功能。2 实验目标理解并掌握语法分析的原理与方法...
扫描右侧二维码阅读全文
18
2018/02

编译原理实验(二)语法分析器的设计

1 概述

通过某种高级语言(如C/C++,Java)实现语法分析器的功能。

2 实验目标

  1. 理解并掌握语法分析的原理与方法。
  2. 能够使用某种语言实现语法分析程序。
  3. 对编译的基本概念,原理和方法有完整和清楚的理解,并能正确而熟练的运用。

3 实验描述

3.1 实验要求

选用某种语言(如C/C++)实现语法分析程序。语法分析程序的主要任务如下:

    • 输入词法分析输出的单词序列,判断单词序列构成的程序是否符合语法语法规则。
    • 记录语法错误信息,统一输出错误信息。

    3.2 本实验概述

    3.2.1 用扩充的BNF表示如下:

    编制一个递归下降分析程序,实现对词法分析程序所提供的单词序列的语法检查和结构分析。

    利用C++编写递归下降分析程序,并对PL/0语言进行语法分析。

    <程序>::=begin<语句串>end

    <语句串>::=<语句>{;<语句>}

    <语句>::=<赋值语句>

    <赋值语句>::=ID:=<表达式>

    <表达式>::=<项>{+<项> | -<项>}

    <项>::=<因子>{*<因子> | /<因子>

    <因子>::=ID | NUM | (<表达式>)

    4 技术分析

    4.1语法分析

    语法分析是编译过程的核心,分析的任务是根据语法规则分析源程序的语法结构,并在分析过程中,对源程序进行语法检查,如果语法没有错误,则给出正确的语法结构,为语义分析和代码生成做准备。

    目前语法分析方法有多种多样,大致分为自顶而下和自底而上两大类。自顶而下又分为LL(1)分析方法和递归下降分析方法。自底而上又分为简单优先文法、算符优先文法、LR(K)分析方法。下面主要介绍自底而上的LR(K)分析方法。

    自底向上分析法,也称移进-归约分析法。它的实现思想是对输入符号串自左向右进行扫描,并将输入符逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,(该句柄对应某产生式的右部),就用该产生式的左部非终结符代替相应右部的文法符号串,这称为移步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功,也就确认输入串是文法的句子。否则,分析失败,表示输入符号串不是文法的一个句子,其中必定存在语法错误。

    5 设计与实现

    5.1设计思路

    编制一个递归下降分析程序,实现对词法分析程序所提供的单词序列的语法检查和结构分析。利用C++编写递归下降分析程序,并对PL/0语言进行语法分析。

    核心思想就是,从开始状态开始,按照文法展开式,逐级进行状态分析,直到分析完毕,如果在此期间出现状态不匹配,即语法错误,停止分析。当然在实际的语法分析器要有错误恢复机制,以发现其他的语法错误。即一次报告多个语法错误。此外要想实现语法分析,必须先有词法分析,用词法分析的结果进行语法分析。

    5.2实现方法

    本实验采用C++编码,其中主要编写了以下几个函数及功能:

    Void fun_yufa() //判断语法是否有错误
    
    Void fun_op() //处理运算符(\*和/)
    
    Void exp() //处理运算符(+和-)
    
    Void fun_yuju() //判断是否有语句错误(:=)
    
    Void fun_end() //判断程序是否结束
    
    Void yufa() //采用递归下降的语法分析

    输入词法分析的结果,如果是文法正确的句子,则输出成功信息,打印“语法分析成功!”,否则输出“语法分析错误(错误原因)”。

    这里,我们采取从文本读入之前词法分析的结果,然后程序进行语法分析,直接输出语法分析的结果,如果有错误,则返回错误信息。

    其中核心部分语法分析代码如下:

    核心代码图

    递归下降语法分析

    图1 语法分析相关函数代码

    5.3测试用例


    项目/软件语法分析器程序版本V1.0
    功能模块名语法分析模块编制人XX
    用例编号T1.0编制时间207.11.10
    功能特性语法定义分析判断
    测试目的判断语法是否正确
    测试数据(begin,1) (a,10) (:=,18) (4,20) (;,26) (b,10) (:=,18) (2,20) (*,15) (3,20) (;,26) (c,10) (:=,18) (a,10) (+,13) (b,10) (;,26) (end,6)
    测试用例操作描述代码期望结果实际结果测试状态
    1运行程序,读入前面词法分析程序生成的二元组(begin,1) (a,10) (:=,18) (4,20) (;,26) (b,10) (:=,18) (2,20) (*,15) (3,20) (;,26) (c,10) (:=,18) (a,10) (+,13) (b,10) (;,26) (end,6)语法分析正确语法分析正确良好
    2更改之前生成的二元组,删除第一行(a,10) (:=,18) (4,20) (;,26) (b,10) (:=,18) (2,20) (*,15) (3,20) (;,26) (c,10) (:=,18) (a,10) (+,13) (b,10) (;,26) (end,6)语法分析错误! 缺少开始语句语法分析错误! 缺少开始语句良好
    3更改之前生成的二元组,删除最后一行(begin,1) (a,10) (:=,18) (4,20) (;,26) (b,10) (:=,18) (2,20) (*,15) (3,20) (;,26) (c,10) (:=,18) (a,10) (+,13) (b,10) (;,26)缺语法分析错误! 缺少结束符缺语法分析错误! 缺少结束符良好

    5.4实验结果及分析

    词法分析的结果我们保存到TXT后,语法分析程序读入结果,开始语法
    分析并返回结果及错误报告。

    试验结果图

    图2 语法分析结果

    如果有错误,将返回错误报告。

    6 总结

    本实验还存在不足,比如定义的错误类型有限,语法分析尚不完善,存在着不少漏洞,目前只选取了少量文法规则进行语法分析。在下一次实验报告中有改进后的语法分析程序。

    7 参考文献

    1.互联网:百度,CSDN博客。

    2.教材:《编译技术》张莉 高等教育出版社。

    3.教材:C++ primer plus(第六版)

    8 代码展示

    #include "cstdio"
    #include "string"
    #include "iostream"
    #include "algorithm"
    #include "cstring"
    using namespace std;
    
    char str[1000];            //从键盘输入
    char bzf[8];      //判断是否是关键字
    char ch;
    char *keyword[6]={"begin","if","then","while","do","end"};
    int num,p,m,n,sum;
    int x;
    
    void term();
    void exp();
    void fun_yufa()   //判断语法是否错误
    {
        if((num==10)||(num==11))//关键字,数字
        {
            cifa();
        }
        else if(num==27)
        {
            cifa();
            exp();
    
            if(num==28)
            {
                cifa();          /*读下一个单词符号*/
            }
            else
            {
                printf("缺少‘(’\n");
                x=1;
            }
        }
        else
        {
            printf("语法错误\n");
            x=1;
        }
        return;
    }
    void fun_op()  //处理运算符
    {
        fun_yufa();
        while((num==15)||(num==16))//  '*'和'/'
        {
            cifa();             /*读下一个单词符号*/
            fun_yufa();
        }
        return;
    }
    
    void exp()   //处理运算符
    {
        fun_op();
        while((num==13)||(num==14))   //+和-
        {
            cifa();               /*读下一个单词符号*/
            fun_op();
        }
    
        return;
    }
    
    
    void fun_yuju()  //判断是否有语句错误
    {
        if(num==10)
        {
            cifa();        /*读下一个单词符号*/
            if(num==18)
            {
                cifa();      /*读下一个单词符号*/
                exp();              }
            else
            {
                printf("':='错误\n");
                x=1;
            }
        }
        else
        {
            printf("语法错误!\n");
            x=1;
        }
    
        return;
    }
    
    void fun_end()  //判断程序结束的标志
    {
        fun_yuju();         /*调用函数statement();*/
    
        while(num==26)
        {
            cifa();          /*读下一个单词符号*/
            if(num!=6)
                fun_yuju();          /*调用函数statement();*/
        }
    
        return;
    }
    
    void yufa()  //递归下降语法分析
    {
        if(num==1)
        {
            cifa();
            fun_end();
            if(num==6)
            {
                cifa();
                if((num==0)&&(x==0))
                printf("语法分析正确!\n");
            }
            else
            {
                if(x!=1) printf("缺少end!\n");
                x=1;
            }
        }
        else
        {
            printf("缺少begin!\n");
            x=1;
        }
    
        return;
    }
    
    int main()
    {
        p=x=0;
        printf("请输词法分析结果: \n");
        do
        {
            scanf("%c",&ch);
            str[p++]=ch;
        }while(ch!='#');
        p=0;
        yufa();
        return 0;
    }
    

    版权声明:本文为原创文章,版权归 Geekerstar 所有。

    本文链接:http://www.geekerstar.com/technology/98.html

    除了有特殊标注文章外欢迎转载,但请务必标明出处,格式如上,谢谢合作。

    最后修改:2018 年 02 月 25 日 11 : 49 AM
    如果觉得我的文章对你有用,请随意赞赏

    发表评论