首页 > 其他分享 >LR分析表语法分析

LR分析表语法分析

时间：2023-11-23 15:55:59浏览次数：48  
标签：分析 status ch 语法分析 int back LR inputStr

 一、实验目的

1、掌握LR法进行语法分析的原理

2、掌握语法分析器的设计与调试

二、实验原理与要求

1、原理：

LR分析表分析是一种自底向上的语法分析。LR分析表内包含几种操作：①跳转；②归约；③接受。通过构造项目集簇的状态转换表实现不同状态的跳转或归约，最后归约为文法的开始符号，从而接受。

2、要求：

（1）定义语言子集的文法

（2）构造LR分析表

（3）理解LR分析的流程，构造LR分析代码。

（4）测试要满足对文法的每个个候选项的覆盖。

三、实验设备

配置有VC开发环境的计算机设备。

四、实验内容

采用LR分析法实现表达式文法的语法检验。

五、实验步骤

1．定义LR(1)分析法实验设计思想及算法

  ①若ACTION[sm , ai] = s则将s移进状态栈，并把输入符号加入符号栈，则三元式变成为：(s0s1…sm s , #X1X2…Xm ai , ai+1…an#)；

  ②若ACTION[sm , ai] = rj则将第j个产生式A->β进行归约。此时三元式变为(s0s1…sm-r s , #X1X2…Xm-rA , aiai+1…an#)；

  ③若ACTION[sm , ai]为“接收”，则三元式不再变化，变化过程终止，宣布分析成功；

  ④若ACTION[sm , ai]为“报错”，则三元式的变化过程终止，报告错误。

  2．定义语法构造的代码，与主代码分离，写为头文件LR.h。

  3．编写主程序利用上文描述算法实现本实验要求。

实验结果

  1. 实验文法为程序既定的文法，写在头文件LR.h中，运行程序，用户可以自由输入测试语句。
  2. 实验测试结果：
  测试结果符合预期结果，程序能够对用户的语句利用LR（1）分析法构建分析表，利用分析栈进行正误分析。实验截图如下所示：

 

 

六、实验结论

  1．实验利用自定义的源程序进行测试，结果正确，符合预期结果，测试源码及结果截图和说明如上所示。
  2．实验源码码分为头文件（LR.h）和主文件（test5）。均如下所示：

#ifndef _LR_

#define _LR_

 

using namespace std;

 

class Grammar{

public:

    //产生式的个数

    int grammarNum ;

    //定义产生式数组

    string formula[100] = {" ","E->E+T","E->T","T->T*F","T->F","F->(E)","F->i"};

 

    Grammar(){

        grammarNum = 6;

    }

};

//定义LR文法的分析表

class LRAnalyseTable{

public:

    char terminalChar[100]={'i','+','*','(',')','#'};

    //定义终结符的个数

    int terNum =6;

    char nonTerminalChar[100]={'E','T','F'};

    //定义非终结符的个数

    int nonTerNum = 3;

    //定义状态数

    int statusNum = 12;

    string action[12][6]={{"s5","","","s4","",""},{"","s6","","","","acc"},{"","r2","s7","","r2","r2"},{"","r4","r4","","r4","r4"},{"s5","","","s4","",""},{"","r6","r6","","r6","r6"},{"s5","","","s4","",""}

    ,{"s5","","","s4","",""},{"","s6","","","s11",""},{"","r1","s7","","r1","r1"},{"","r3","r3","","r3","r3"},{"","r5","r5","","r5","r5"}};

    int goTo[12][3] = {{1,2,3},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{8,2,3},{-1,-1,-1},{-1,9,3},{-1,-1,10},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1}};

   //获取终结符的索引

    int getTerminalIndex(char var){

        for(int i=0;i<terNum;i++){

            if(terminalChar[i] == var){

                return i;

            }

        }

        return -1;

    }

    //获取非终结符的索引

    int getNonTerminalIndex(char var){

        for(int i=0;i<nonTerNum;i++){

            if(nonTerminalChar[i] == var){

                return i;

            }

        }

        return -1;

    }

};

 

#endif // _LR_

Tset5

#include <iostream>

#include <vector>

#include <iomanip>

#include <cstring>

#include <sstream>

#include "LR.h"

 

using namespace std;

 

//定义状态栈

vector<int> status;

//定义符号栈

vector<char> sign;

//定义输入的字符串

vector<char> inputStr;

//记录输入的字符串

string inputVal;

//定义文法

Grammar grammar;

//定义LR分析表

LRAnalyseTable analyseTable;

//读取输入的字符串

void readStr();

//对栈容器进行输出,i=0,返回status中的字符串,i=1,返回sign中的字符串，i=2返回inputStr

string vectTrancStr(int i);

//总控，对输入的字符串进行分析

void LRAnalyse();

 

int main()

{

    readStr();

    LRAnalyse();

    return 0;

}

//读取输入的字符串

void readStr(){

    char ch;

    cout<<"LR（1）分析程序，编制人：xxx"<<endl;

    cout<<"请输入分析的字符串：";

    cin>>ch;

    while( ch != '#'){

        inputVal += ch;

        inputStr.push_back(ch);

        cin>>ch;

    }

   //把#加入容器

   inputStr.push_back('#');

   inputVal += '#';

}

//对栈容器进行输出,i=0,返回status中的字符串,i=1,返回sign中的字符串，i=2返回inputStr中的字符串

string vectTrancStr(int i){

    char buf[100];

    int count = 0;

    //输出状态栈

    if(i == 0){

        vector<int>::iterator it =status.begin();

        //将数字转化为字符串

        string str,tempStr;

        for(it;it!= status.end();it++){

            stringstream ss;

            ss << *it;

            ss >> tempStr;

            str+=tempStr;

        }

        return str;

    }

    //输出符号栈

    else if(i == 1){

        vector<char>::iterator it = sign.begin();

        for(it ; it != sign.end() ;it++){

            buf[count] = *it;

            count++;

        }

    }

    //输出待分析的字符串

    else{

        vector<char>::iterator it = inputStr.begin();

        for(it ; it != inputStr.end();it++){

            buf[count] = *it;

            count++;

        }

    }

    buf[count] = '\0';

    string str(buf);

    return str;

}

//总控，对输入的字符串进行分析

void LRAnalyse(){

    //步骤

    int step = 1;

    //把状态0入栈

    status.push_back(0);

    //把#加入符号栈

    sign.push_back('#');

    //输出初始栈状态

    cout<<setw(10)<<"步骤"<<setw(10)<<"状态栈"<<setw(10)<<"符号栈"<<setw(10)<<"输入串"<<setw(25)<<"动作说明"<<endl;

    //初始状态

    int s =0;

    //保存之前的状态

    int oldStatus;

    //获取初始符号

    char ch = inputStr.front();

    //如果action[s][ch] =="acc" ，则分析成功

    while(analyseTable.action[s][analyseTable.getTerminalIndex(ch)] != "acc"){

        //获取字符串

        string str = analyseTable.action[s][analyseTable.getTerminalIndex(ch)];

        //如果str为空，报错并返回

        if(str.size() == 0){

            cout<<"出错"<<endl;

            cout<<inputVal<<"为非法符号串"<<endl;

            return ;

        }

        //获取r或s后面的数字

        stringstream ss;

        ss << str.substr(1);

        ss >> s;

        //如果是移进

        if(str.substr(0,1) == "s"){

            cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0)<<setw(10)<<vectTrancStr(1)<<setw(10)<<vectTrancStr(2)<<setw(10)<<"A"<<"CTION["<<status.back()<<","<<ch<<"]=S"<<s<<","<<"状态"<<s<<"入栈"<<endl;

            //输入符号入栈

            sign.push_back(ch);

            inputStr.erase(inputStr.begin());

            //将状态数字入栈

            status.push_back(s);

        }

        //如果是归约

        else if(str.substr(0,1) == "r"){

            //获取第S个产生式

            string formu = grammar.formula[s];

            //cout<<s<<endl;

            int strSize = formu.size();

            //将产生式转化为字符数组

            char buf[100];

            strcpy(buf,formu.c_str());

            //获取产生式的首字符

            char nonTerCh = buf[0];

            //获取符号栈的出栈次数

            int popCount = strSize - 3;

            //反向迭代

            vector<int>::reverse_iterator rit = status.rbegin();

            int i= 0;

            for(rit;rit != status.rend();rit++){

                i++;

                if(i == popCount+1){

                    oldStatus = * rit;

                    break;

                }

            }

            int r = s;

            //修改s

            s = analyseTable.goTo[oldStatus][analyseTable.getNonTerminalIndex(nonTerCh)];

            cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0)<<setw(10)<<vectTrancStr(1)<<setw(10)<<vectTrancStr(2)<<setw(10)<<"r"<<r<<(string)":"+grammar.formula[r]+(string)"归约,GOTO{"<<oldStatus<<","<<nonTerCh<<")="<<s<<"入栈"<<endl;

            //对符号栈进行出栈和状态栈进行出栈

            for(int i=0 ;i< popCount;i++){

                sign.pop_back();

                status.pop_back();

            }

            //再对产生式的开始符号入栈

            sign.push_back(nonTerCh);

            //再把新的状态入栈

            status.push_back(s);

        }

        else{

           //什么都不处理

        }

        //步骤数加1

        step++;

 

        //获取栈顶状态

        s = status.back();

        //获取输入的字符

        ch = inputStr.front();

    }

    cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0)<<setw(10)<<vectTrancStr(1)<<setw(10)<<vectTrancStr(2)<<setw(10)<<"A"<<"cc:分析成功"<<endl;

    cout<<inputVal<<"为合法符号串"<<endl;

}

实验小结

  1．本次实验是利用LR（1）分析法进行语法分析，通过代码实现后更加了解了LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

  2．LR分析法小结：

   LR(0)构造的DFA，但是由LR（0）的DFA来构造分析表往往是不可行的，也就是说很少有语言是LR(0)的。

   如果LR(0)的冲突可以根据当前输入的字符来解决，则构造的分析表为SLR分析表，SLR分析表跟LR(0)的dfa是相同的。

   LR(1)构造的DFA考虑当前输入的字符，所以构造的DFA中存在的冲突比较少，也就是说它接受的语言就比较多。构造分析表时，不用额外的约束，因为它在构造dfa时就已经考虑了当前的输入字符。

   考虑到LR(1)的dfa包含的状态太多，而且许多状态的不同仅仅是因为预测符的不同而已。通过合并不会产生冲突的状态，可以减少dfa的状态数，这就产生了LALR分析法。所以说LALR分析法只是对LR(1)的一种简化：通过合并同心集。

   分析法的分析能力比较：LR(1)>LALR>SLR(1)>LR(0)。

 

 

标签：分析,status,ch,语法分析,int,back,LR,inputStr
From： https://www.cnblogs.com/ai5277/p/17851742.html

相关文章

  • 羚通视频智能分析平台：安全帽佩戴识别监测系统，让安全无处不在
    在建筑工地、矿山、化工等高风险行业，安全帽的佩戴是保障工人生命安全的重要措施。然而，传统的人工巡查方式效率低下，无法做到实时监控，而羚通视频智能分析平台的安全帽佩戴识别监测系统，却能有效地解决这个问题。羚通视频智能分析平台是一款基于人工智能技术的视频分析系统......
  • 线上ES集群参数配置引起的业务异常案例分析
    作者：vivo互联网数据库团队-LiuHuang本文介绍了一次排查Elasticsearchnode_concurrent_recoveries引发的性能问题的过程。一、故障描述1.1故障现象1.业务反馈业务部分读请求抛出请求超时的错误。2.故障定位信息获取故障开始时间19:30左右开始故障抛出异常......
  • 数据分析从入门到高级，10分钟帮你构建知识体系！
    数据分析是一种通过收集、整理、解释和可视化数据来获得洞察力和做出决策的过程。它在各行各业都起着至关重要的作用，包括市场营销、金融、医疗保健、人力资源等领域。在本文中，我将为你介绍数据分析的入门知识，并逐步向你介绍一些高级概念和技巧。入门知识1.数据分析的基本概念......
  • 大数据分析使用哪些工具？
    大数据分析常用的工具包括但不限于以下几种：Hadoop：Hadoop是一个开源的分布式存储和计算框架，包括HDFS（Hadoop分布式文件系统）和MapReduce（分布式计算框架）。Hadoop可以处理大规模数据，并且提供容错性、高可用性和高性能。Spark：ApacheSpark是一个快速、通用的大数据处理引擎，它提供了基......
  • NS-3源码学习（三）Pcap文件分析
    NS-3源码学习（三）Pcap文件分析Pcap文件生成NS-3生成.pcap文件相关函数有EnablePcap()和EnalePcapAll(),支持第一个函数的类有ns3::YansWifiPhyHelperPointToPointEmuHelperCsmaHelper支持第二个函数的类有ns3::YansWifiPhyHelperPointToPointInternetStackHelper......
  • CHC6072 软件分析与测试
    在本课程中，您需要单独担任软件质量保证和测试工程师，对给定的基于web的应用程序进行测试和分析，并为应用程序的自动回归测试开发测试套件申请是曼彻斯特大学的网站URLhttps://www.manchester.ac.uk/。这个待测试的基于网络的应用程序的具体功能是查找大学提供的本科生课程的在线设施......
  • 三种初始化以及内存分析
    packagearray;publicclassArrayDemo02{publicstaticvoidmain(String[]args){//静态初始化:声明+创建+赋值一起做好了int[]a={1,2,3,4};System.out.println(a[0]);//动态初始化：包含默认初始化没有被赋值的如果想输......
  • U-BOOT分析之顶层Makefile文件
    U-BOOT分析（二）之顶层Makefile文件(1)U-BOOT版本u-boot版本:   u-boot-2021.01.tar.bz2Makefile&&make简介      Makefile：是一个描述文件定义一系列的规则来指定源文件编译的先后顺序，拥有特定的语法规则，makefile文件描述了整个工程中所有文件的__编译顺序，编译规......
  • 羚通视频智能分析平台烟雾火焰识别算法 安防视频监控森林防火烟雾火焰算法识别
    随着科技的飞速发展，人工智能技术已经深入到各个领域，其中安防视频监控是其重要的应用场景之一。在众多安防视频监控应用中，森林防火烟雾火焰识别尤为重要，因为森林火灾的发生往往会带来巨大的生态破坏和人员伤亡。为了更有效地预防和控制森林火灾，羚通视频智能分析平台推出了一款具有......
  • 记一次sql查询慢的原因分析（金仓）
    在进行数据筛选时，遇到了一个处理4000万条数据的问题（时序数据），在发现这个表很大后，就对其加了索引，然后金仓执行以下sqlSELECTA,B,C，timeFROMTableWHEREid=#{param.id}ORDERBYtime  ，但是发现并没有什么用，查询时间需要7秒左右，就很超乎我的想象，但是有时候就会特别快，大概......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99