精华内容
下载资源
问答
  • 算符优先分析法

    2018-05-22 21:12:04
    设有文法G[S]:S→SaF | F F→FbP | P P→c | d (1) 构造G[S]的算符优先关系表 (2) 分别给出cadbdac# 和 dbcabc# 的分析过程
  • 实验三 算符优先分析算法的设计与实现 8 学时) 一 实验目的 根据算符优先分析法 对表达式进行语法分析 使其能够判断一个表达式是否正确 过算符优先分析方法的实现加深对自下而上语法分析方法的理解 二 实验要求 1...
  • 算符优先分析器 #include "stdio.h" #include "stdlib.h" #include "iostream.h" char data[20][20]; //算符优先关系 char s[100]; //模拟符号栈s char lable[20]; //文法终极符集 char input[100]; //文法输入符号...
  • 编译原理 算符优先文法 实验报告 代码 运行成功////////////
  • (Python实现,注释详细)直接输入:3+4*5,一般的...(1)第一阶段,运用算符优先分析算法完成计算器中对算术表达式的语法分析; (2)第二阶段,设计属性文法,改造第一阶段的程序,完成算术表达式的计算和相关的输出。
  • 实验3《算符优先分析法设计与实现》 一、实验目的   加深对语法分析器工作过程的理解;加强对算符优先分析法实现语法分析程序的掌握;能够采用一种编程语言实现简单的语法分析程序;能够使用自己编写的分析程序对...

    实验3《算符优先分析法设计与实现》

    一、实验目的

      加深对语法分析器工作过程的理解;加强对算符优先分析法实现语法分析程序的掌握;能够采用一种编程语言实现简单的语法分析程序;能够使用自己编写的分析程序对简单的程序段进行语法翻译。

    二、实验内容

      在实验1的基础上,用算符优先分析法编制语法分析程序,语法分析程序的实现可以采用任何一种编程语言和工具。

    三、实验方法

      1.实验采用C++程序语言进行设计,用户自定义输入文法进行分析;
      2.开发工具为Visual Studio Code。

    四、实验步骤

      1.本程序中的文法,实质上是算数表达式的计算。
      2.构建firstVT()和lastVT()这两个集合;
      3.构建优先符号表;
      4.构建词法分析的程序;
      5.编写main函数,用户输入文法对语句利用算符优先文法进行判别。
      6.算法的主体思想:
      用栈存储已经看到的输入符号,用优先关系指导移动归约语法分析器的动作 ,如果栈顶的终结符和下一个输入符之间的优先关系是<或=,则语法分析器移动,表示还没有发现句柄的右端,如果是>关系,就调用归约。

    五、实验结果
    1. 运行实验代码,用户先输入文法个数,之后输入具体文法,程序根据输入进行FIRSTVT集、LASTVT集和算符优先表的计算,之后再对句子进行文法判别。
        实验输入数据为:
    6 
    S->#E# 
    P->i 
    F->P 
    T->F 
    E->T 
    E->E+T
    

    测试结果:
      测试结果符合预期结果,能够对句子i+i进行正确判别,用户也可以自定义其他语句进行实验。实验截图如下所示:
    在这里插入图片描述
    在这里插入图片描述

    六、实验结论

      1.实验利用自定义的源程序进行测试,结果正确,符合预期结果,测试源码及结果截图和说明如上所示。
      2.实验源代码如下所示:
      test3.cpp

    /**************************
    Compiler Principle
    test3 算符优先分析法设计与实现
    author:zz
    vs code
    2019.05.05
    ***************************/
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <stack>
    #include <map>
    #include <set>
    #include <algorithm>
    #include <string>
    #include <cstdlib>
    #include <cctype>
    #define MAX 507
     
    using namespace std;
     
    class WF
    {
        public:
        string left;
        vector<string> right;
        WF ( const string& str )
        {
            left = str;
        }
        void insert ( char str[] )
        {
            right.push_back(str);
        }
        void print ( )
        {
            printf ( "%s->%s" , left.c_str() , right[0].c_str() );
            for ( int i = 1 ; i < right.size() ; i++ )
                printf ( "|%s" , right[i].c_str() );
            puts("");
        }
    };
     
    char relation[MAX][MAX];
    vector<char> VT;
    vector<WF> VN_set;
    map<string,int> VN_dic;
    set<char> first[MAX];
    set<char> last[MAX];
    int used[MAX];
    int vis[MAX];
     
    void dfs (  int x )
    {
        if ( vis[x] ) return;
        vis[x] = 1;
        string& left = VN_set[x].left;
        for ( int i = 0 ; i < VN_set[x].right.size() ; i++ )
        {
            string& str = VN_set[x].right[i];
            if ( isupper(str[0]) )
            {
                int y = VN_dic[str.substr(0,1)]-1;
                if ( str.length() > 1 && !isupper(str[1] ) )
                    first[x].insert ( str[1] );
                dfs ( y );
                set<char>::iterator it = first[y].begin();
                for ( ; it!= first[y].end() ; it++ )
                    first[x].insert ( *it );
            }
            else 
                first[x].insert ( str[0] );
        }
    }
     
    void make_first ( )
    {
        memset ( vis , 0 , sizeof ( vis ) );
        for ( int i = 0 ; i < VN_set.size() ; i++ )
            if ( vis[i] ) continue;
            else dfs ( i );
    #define DEBUG
    #ifdef DEBUG
        puts("------------FIRSTVT集-------------------");
        for ( int i = 0 ; i < VN_set.size() ; i++ )
        {
            printf ( "%s : " , VN_set[i].left.c_str() );
            set<char>::iterator it = first[i].begin();
            for ( ; it!= first[i].end() ; it++ )
                printf ( "%c " , *it );
            puts ("" );
        }
    #endif 
    }
     
    void dfs1 ( int x )
    {
        if ( vis[x] ) return;
        vis[x] = 1;
        string& left = VN_set[x].left;
        for ( int i = 0 ; i < VN_set[x].right.size() ; i++ )
        {
            string& str = VN_set[x].right[i];
            int n = str.length() -1;
            if ( isupper(str[n] ) )
            {
                int y = VN_dic[str.substr(n,1)]-1;
                if ( str.length() > 1 && !isupper(str[n-1]) )
                    last[x].insert ( str[1] );
                dfs1 ( y );
                set<char>::iterator it = last[y].begin();
                for ( ; it != last[y].end() ; it++ )
                    last[x].insert ( *it );
            }
            else 
                last[x].insert ( str[n] );
        }
    }
     
     
    void make_last ( )
    {
        memset ( vis , 0 , sizeof ( vis ) );
        for ( int i = 0 ; i < VN_set.size() ; i++ )
            if ( vis[i] ) continue;
            else dfs1 ( i );
    #define DEBUG
    #ifdef DEBUG
        puts("--------------LASTVT集---------------------");
        for ( int i = 0 ; i < VN_set.size() ; i++ )
        {
            printf ( "%s : " , VN_set[i].left.c_str() );
            set<char>::iterator it = last[i].begin();
            for ( ; it!= last[i].end() ; it++ )
                printf ( "%c " , *it );
            puts ("" );
        }
    #endif
    }
     
    void make_table ( )
    {
        for ( int i = 0 ; i < MAX ; i++ )
            for ( int j = 0 ; j < MAX ; j++ )
                relation[i][j] = ' ';
        for ( int i = 0 ; i < VN_set.size() ; i++ )
            for ( int j = 0 ; j < VN_set[i].right.size() ; j++ )
            {
                string& str = VN_set[i].right[j];
                for ( int k = 0 ; k < str.length()-1 ; k++ )
                {
                    if ( !isupper(str[k]) && !isupper(str[k+1]) )
                        relation[str[k]][str[k+1]] = '=';
                    if ( !isupper(str[k]) && isupper(str[k+1]) )
                    {
                        int x = VN_dic[str.substr(k+1,1)]-1;
                        set<char>::iterator it = first[x].begin();
                        for ( ; it != first[x].end() ; it++ )
                            relation[str[k]][*it] = '<';
                    }
                    if ( isupper(str[k]) && !isupper(str[k+1]) )
                    {
                        int x = VN_dic[str.substr(k,1)]-1;
                        set<char>::iterator it = last[x].begin();
                        for ( ; it != last[x].end() ; it++ )
                            relation[*it][str[k+1]] = '>';
                    }
                    if ( k > str.length()-2 ) continue;
                    if ( !isupper(str[k]) && !isupper(str[k+2]) && isupper(str[k+1]) )
                        relation[str[k]][str[k+2]] = '=';
                }
            }
    #define DEBUG
    #ifdef DEBUG
        for ( int i = 0 ; i < VT.size()*5 ; i++ )
            printf ("-");
        printf ( "算符优先关系表" );
        for ( int i = 0 ; i < VT.size()*5 ; i++ )
            printf ( "-" );
        puts("");
        printf ( "|%8s|" , "" );
        for ( int i = 0 ; i < VT.size() ; i++ )
            printf ( "%5c%5s" , VT[i] , "|" );
        puts ("");
        for ( int i = 0 ; i < (VT.size()+1)*10 ; i++ )
            printf ("-");
        puts("");
        for ( int i = 0 ; i < VT.size() ; i++ )
        {
            printf ( "|%4c%5s" , VT[i] , "|");
            for ( int j = 0 ; j < VT.size() ; j++ )
                printf ( "%5c%5s" , relation[VT[i]][VT[j]] , "|" );
            puts ("");
            for ( int i = 0 ; i < (VT.size()+1)*10 ; i++ )
                printf ("-");
            puts("");
        }
    #endif
    }
     
    int fa[MAX];
     
    int _find ( int x  )
    {
        return x==fa[x]?x:fa[x] = _find ( fa[x] );
    }
     
    bool judge ( char x , char y )
    {
        if ( _find ( x ) == _find ( y ) )
            return true;
        return false;
    }
     
    void _union ( char x , char y )
    {
        x = _find(x);
        y = _find(y);
        fa[x] = y;
    }
     
    void print ( string s1 , string s2 , string s3 , string s4 , string s5 , string s6 )
    {
        printf ( "%-14s|%-15s%-15s%-15s%-15s%-15s\n" , s1.c_str(), s2.c_str(), s3.c_str() ,s4.c_str(),s5.c_str() , s6.c_str() );
    }
     
    void init ( )
    {
        for ( int i = 0 ; i < MAX ; i++ )
            fa[i] = i;
        for ( int i = 0 ; i < VN_set.size() ; i++ )
        {
            string& left = VN_set[i].left;
            for ( int j = 0 ; j < VN_set[i].right.size() ; j++ )
            {
                string& str = VN_set[i].right[j];
                if ( left.length() == 1 && str.length() == 1 )
                {
                   // cout << left[0] << " " << str[0] << endl;
                    _union ( left[0] , str[0] );
                   // cout << _find(left[0]) << " " << _find ( str[0] )  << endl;
                }
            }
        }
        print("步骤","栈","优先关系","当前符号","剩余符号","动作");
    }
     
    string get_stk ( vector<char>& stk )
    {
        string ret = "";
        for ( int i = 0 ; i < stk.size() ; i++ )
            ret += stk[i];
        return ret;
    }
     
    bool check ( const string& str1 , const string& str2 )
    {
        if ( str1.length() != str2.length() ) 
            return false;
        for ( int i = 0 ; i < str1.length() ; i++ )
            if ( isupper(str1[i]) )
            {
                if ( !judge(str1[i],str2[i])) return false;
            }
            else 
            {
                if ( str1[i] != str2[i] ) return false;
            }
        return true;
    }
     
    string reduction ( string src )
    {
        for ( int i = 0 ; i < VN_set.size() ; i++ )
            for ( int j = 0 ; j < VN_set[i].right.size() ; j++ )
                if ( check ( VN_set[i].right[j] , src ) )
                    return VN_set[i].left;
        return "";
    }
     
    void move_reduction ( string src )
    {
        init ();
        //cout <<"flag : " << check ( "P+P" , "E+T" ) << endl;;
        vector<char> stk;
        int steps= 1;
        src += "#";
        stk.push_back ( '#' );
        for ( int i = 0 ; i < src.length() ; i++ )
        {
            char top = stk[stk.size()-1];
            for ( int j = stk.size()-1 ; j >= 0 ; j-- )
                if ( isupper(stk[j]) ) continue;
                else   
                {
                    top = stk[j];
                    break;
                }
            char ch = relation[top][src[i]];
            if ( ch == '<' || ch == '=' )
            {
                string temp = "";
                if ( i == src.length() - 1 )
                    print ( temp+(char)(steps+48) , get_stk( stk ) , temp+ch , temp+src[i] , "" , "移进" );
                else
                    print ( temp+(char)(steps+48) , get_stk( stk ) , temp+ch , temp+src[i] , src.substr(i+1,src.length()-i-1) , "移进" );
                stk.push_back ( src[i] );  
            }
            else
            {
                string temp ="";
                string str ="";
                int x = stk.size()-2;
                if ( i == src.length() )
                    print ( temp+(char)(steps+48) , get_stk(stk) , temp+ch , temp + src[i] , "" , "归约" );
                else 
                    print ( temp+(char)(steps+48) , get_stk(stk) , temp+ch , temp + src[i] , src.substr(i+1,src.length()-i-1) , "归约" );
                while ( true )
                {
                    if ( stk.size() == 0 ) break;
                    if ( !isupper(stk[x] ) &&relation[stk[x]][top] == '<' ) 
                            break;
                    x--;
                }
                for ( int j = stk.size()-1 ; j > x; j-- )
                {
                    str += stk[j];
                    stk.pop_back();
                }
                //cout << "YES : " << i <<" " << str <<  endl;
                str = reduction(str);
                //cout << "finish: " << i << " " << str << endl;
                for ( int j = 0 ; j < str.length() ; j++ )
                    stk.push_back ( str[j] );
                /*if ( i == src.length() )
                    print ( temp+(char)(steps+48) , get_stk(stk) , temp+ch , temp + src[i] , "" , "移进" );
                else 
                    print ( temp+(char)(steps+48) , get_stk(stk) , temp+ch , temp + src[i] , src.substr(i+1,src.length()-i-1) , "移进" );
                stk.push_back ( src[i] );*/
                i--;
            }  
            steps++;
        }
        //string temp ="";
        //cout << "result" << endl;
        //print ( temp+(char)(steps+48) , get_stk(stk) , "","","","");
    }
     
     
    int main ( )
    {
        int n;
        char s[MAX];
        while ( ~scanf ( "%d" , &n ) )
        {
            memset ( used , 0 , sizeof ( used ) );
            for ( int i = 0 ; i < n ; i++ )
            {
                scanf ( "%s" , s );
                int len = strlen(s),j;
                for ( j = 0 ; j < len ; j++ )
                    if ( s[j] == '-' ) 
                        break;
                s[j] = 0;
                if ( !VN_dic[s] )
                {
                    VN_set.push_back ( WF(s) );
                    VN_dic[s] = VN_set.size();
                }
                int x = VN_dic[s]-1;
                VN_set[x].insert ( s+j+2 );
                for ( int k = 0 ; k < j; k++ )
                    if ( !isupper(s[k] ) )
                    {
                        if ( used[s[k]] ) continue;
                        used[s[k]] = 1;
                        VT.push_back ( s[k] );
                    }
                for ( int k = j+2 ; k < len; k++ )
                    if ( !isupper(s[k] ) )
                    {
                        if ( used[s[k]] ) continue;
                        VT.push_back ( s[k] );
                        used[s[k]] = VT.size();
                    }   
            }
    #define DEBUG
    #ifdef DEBUG
            puts ("************VT集*******************");
            for ( int i = 0 ; i < VT.size() ; i++ )
                printf ( "%c " , VT[i] );
            puts ("");
            puts("*************产生式*****************");
            for ( int i = 0 ; i < VN_set.size() ; i++ )
                VN_set[i].print();
            puts("************************************");
    #endif
            make_first();
            make_last();
            make_table();
            move_reduction("i+i");
        }
    }
    
    七、实验小结
    1. 本次实验通过对文法进行处理,获取FIRSTVT()集合、LASTVT()集合和算符优先关系表,从而进一步对语句进行分析判断。通过本次实验我对语义分析有了更进一步的了解。
    2. 实验过程中遇到的问题有:
      ①FIRSTVT()和LASTVT()这两个集合的构建。
      解决方式:对书本中两个集合进一步优先,写出伪代码,进行实现。
      ②如何利用FIRSTVT()和LASTVT()集合构建算符优先关系表。
      解决方式:多次尝试可得如下伪代码,从而实现该关系表的代码化。
    FOR 每个产生式 P->X1 X2 ……Xn   
    DO  FOR  i:=1  TO   n-1    DO      
          IF  X[i]和X[i+1]均为终结符
            THEN   置 X[i]=X[i+1]        
          IF  X[i]和X[i+2]均为终结符,X[i+1]为非终结符,i≤n-2,       
            THEN   置 X[i]=X[i+2]                
          IF  X[i]为终结符, 但X[i+1]为非终结符                                    
          THEN  FOR  FIRSTVT(X[i+1])中的每个a                                    
              DO  置 X[i]<a                
          IF  Xi为非终结符, 但X i+1 为终结符                                  
              THEN  FOR  LASTVT(X i )中的每个a
                  DO   置 a>X[i+1]      
    
    1. 实验的输入输出格式可进一步调整优化,代码的注释有待增加,可读性有进一步提升空间。

    参考文章:【1】编译原理(八) 算符优先分析法(分析过程的算法和C++实现)
         【2】编译原理——算符优先分析文法(附源代码)

    展开全文
  • 编译原理 算符优先文法 实验报告 代码 运行成功
  • 以陈火旺的《编译原理》里描述的为基础,自己写的一个程序
  • java实现算符优先分析法

    热门讨论 2010-06-04 14:00:29
    编译原理课程中的算符优先分析算法,Java实现
  • 算符优先分析法原理

    2020-12-06 18:54:01
    先乘除,再加减。算符的优先关系是确定好的,根据文法来说是一定的(这保证了归约是按着推导的过程来的)(由终结符优先关系定义可知,越早需要归约的串他的优先级越高)。...这就是算法优先分析方法的原理 ...

    先乘除,再加减。算符的优先关系是确定好的,根据文法来说是一定的(这保证了归约是按着推导的过程来的)(由终结符优先关系定义可知,越早需要归约的串他的优先级越高)。同时归约一个串表示他们是同一个产生式推出的。这就是算法优先分析方法的原理

    展开全文
  • 1、 实验目的:采用算符优先分析法对表达式进行分析,掌握算符优先分析法的基本原理和实现过程。 2、 实验要求: 文法:无二义性的算术表达式的文法 (1)把词法分析作为语法分析的子程序实现(5分) (2)独立的...
  • 这是一个用c++语言实现的编译原理里面实现算符优先分析法的程序,包括创建FIRSTVT,LASTVT,和分析表。
  • 编译原理实验3-算符优先分析法#include#include#include#include#define SIZE 128char priority[6][6]; //算符优先关系表数组char input[SIZE]; //存放输入的要进行分析的句子char remain[SIZE]; //存放剩余串char ...

    编译原理实验3-算符优先分析法

    #include

    #include

    #include

    #include

    #define SIZE 128

    char priority[6][6]; //算符优先关系表数组

    char input[SIZE]; //存放输入的要进行分析的句子

    char remain[SIZE]; //存放剩余串

    char AnalyseStack[SIZE]; //分析栈

    void analyse();

    int testchar(char x); //判断字符X在算符优先关系表中的位置

    void remainString(); //移进时处理剩余字符串,即去掉剩余字符串第一个字符

    int k;

    void init()//构造算符优先关系表,并将其存入数组中

    {

    priority[1][0]='>';

    priority[1][1]='>';

    priority[1][2]='

    priority[1][3]='

    priority[1][4]='>';

    priority[1][5]='>';

    priority[2][0]='>';

    priority[2][1]='>';

    priority[2][2]='$';//无优先关系的用$表示

    priority[2][3]='$';

    priority[2][4]='>';

    priority[2][5]='>';

    priority[3][0]='

    priority[3][1]='

    priority[3][2]='

    priority[3][3]='

    priority[3][4]='=';

    priority[3][5]='$';

    priority[4][0]='>';

    priority[4][1]='>';

    priority[4][2]='$';

    priority[4][3]='$';

    priority[4][4]='>';

    priority[4][5]='>';

    priority[5][0]='

    priority[5][1]='

    priority[5][2]='

    priority[5][3]='

    priority[5][4]='$';

    priority[5][5]='=';

    }

    void analyse()//对所输入的句子进行算符优先分析过程的函数

    {

    int i,j,f,z,z1,n,n1,z2,n2;

    int count=0;//操作的步骤数

    char a; //用于存放正在分析的字符

    char p,Q,p1,p2;

    f=strlen(input); //测出数组的长度

    for(i=0;i<=f;i++)

    {

    a=input[i];

    if(i==0)

    remainString();

    if(AnalyseStack[k]=='+'||AnalyseStack[k]=='*'||AnalyseStack[k]=='i'

    ||AnalyseStack[k]=='('||AnalyseStack[k]==')'||AnalyseStack[k]=='#')

    j=k;

    else

    j=k-1;

    z=testchar(AnalyseStack[j]);//从优先关系表中查出s[j]和a的优先关系

    if(a=='+'||a=='*'||a=='i'||a=='('||a==')'||a=='#')

    n=testchar(a);

    else //如果句子含有不是终结符集合里的其它字符,不合法

    {

    printf("错误!该句子不是该文法的合法句子!\n");

    break;

    }

    p=priority[z][n];

    if(p=='$')

    {

    printf("错误!该句子不是该文法的合法句子!\n");

    return;

    }

    if(p=='>')

    { for( ; ; )

    {

    Q=AnalyseStack[j];

    if(AnalyseStack[j-1]=='+'||AnalyseStack[j-1]=='*'||AnalyseStack[j-1]=='i'

    ||AnalyseStack[j-1]=='('||AnalyseStack[j-1]==')'||AnalyseStack[j-1]=='#')

    j=j-1;

    else

    j=j-2;

    z1=testchar(AnalyseStack[j]);

    n1=testchar(Q);

    p1=priority[z1][n1];

    if(p1=='

    {

    count++;

    printf("(%d) %s\t%10c\t%5c%17s\t 归约\n",count,AnalyseStack,p,a,remain);

    k=j+1;

    i--;

    AnalyseStack[k]='N';

    int r,r1;

    r=strlen(AnalyseStack);

    for(r1=k+1;r1

    AnalyseStack[r1]='\0';

    break;

    }

    else

    continue;

    }

    }

    else

    {

    if(p=='

    {

    count++;

    printf("(%d) %s\t%10c\t%5c%17s\t 移进\n",count,AnalyseStack,p,a,remain);

    k=k+1;

    AnalyseStack[k]=a;

    remainString();

    }

    else

    {

    if(p=='=')

    {

    z2=testchar(AnalyseStack[j]);

    n2=testchar('#');

    p2=priority[z2][n2];

    if(p2=='=')

    {

    count++;

    printf("(%d) %s\t%10c\t%5c%17s\t 接受\n",count,AnalyseStack,p,a,remain);

    printf("该句子是该文法的合法句子。\n");

    break;

    }

    else

    {

    count++;

    printf("(%d) %s\t%10c\t%5c%17s\t 移进\n",count,AnalyseStack,p,a,remain);

    k=k+1;

    AnalyseStack[k]=a;

    remainString();

    }

    }

    else

    {

    printf("错误!该句子不是该文法的合法句子!\n");

    break;

    }

    }

    }

    }

    }

    int testchar(char x)

    {

    int m;

    if(x=='+')

    m=0;

    if(x=='*')

    m=1;

    if(x=='i')

    m=2;

    if(x=='(')

    m=3;

    if(x==')')

    m=4;

    if(x=='#')

    m=5;

    return m;

    }

    void remainString()

    {

    int i,j;

    i=strlen(remain);

    for(j=0;j

    remain[j]=remain[j+1];

    remain[i-1]='\0';

    }

    int main()

    {

    init();

    printf("请输入要进行分析的句子(以#号结束输入):\n");

    gets(input);//将输入的字符串存到数组中

    printf("步骤 栈 优先关系 当前符号 剩余输入串 移进或归约\n");

    k=0;

    AnalyseStack[k]='#';

    AnalyseStack[k+1]='\0';

    int length,i; //初始化剩余字符串数组为输入串

    length=strlen(input);//

    for(i=0;i

    remain[i]=input[i];

    remain[i]='\0';

    analyse();//对所输入的句子进行算符优先分析过程的函数

    return 0;

    }

    展开全文
  • 二、设计内容对简单表达式文法构造算符优先分析器。三、设计要求1、对下列简单表达式文法G[ E’]构造算符优先关系表。E’ →# E #E → E + T | TT → T * F | FF → P / F |PP → ( E )|i2、根据算符优先关系表,...

    内容简介:

    一、设计目的

    了解用算符优先法对表达进行语法分析的方法,掌握自顶向下的预测语法分析程序的手工构造方法。

    二、设计内容

    对简单表达式文法构造算符优先分析器。

    三、设计要求

    1、对下列简单表达式文法G[ E’]构造算符优先关系表。

    E’ →# E #

    E → E + T | T

    T → T * F | F

    F → P / F |P

    P → ( E )|i

    2、根据算符优先关系表,使用栈结构来实现算符优先分析:设置两个栈:存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。具体算法描述如下:

    (1)首先置操作数OPND栈为空栈,将#入运算符OPTR栈。

    (2)依次读入表达式中每个单词,若是操作数则进OPND栈,若是运算符则转(3)。

    (3)当前设读入的运算符为θ2,查找算符优先关系表,比较θ2与OPTR栈顶元素θ1 :

    若θ1﹤θ2,则θ2进OPTR栈,转(2);

    若θ1=θ2, 如θ2为#,则分析成功,否则OPTR栈顶元素θ1出栈,并转(2);

    若θ1>θ2,则出栈OPND栈顶元素存放到b,又出栈其新栈顶元素存放到a,再出栈OPTR栈顶元素至t,进行运算r=a t b (t为运算符),并将结果r存入栈OPND后转(2);

    (4)若θ1和θ2之间无优先关系,则报错。

    从键盘输入表达式,利用算符优先法求出其值,如输入表达式有错,则给出报错提示。表达式以“#”结尾。

    四、运行结果

    1、从键盘输入表达式串: 10+15*4#

    输出: 70

    2、从键盘输入表达式串:10+*15+

    输出: The expression is error!

    五、提示

    构造算符优先关系表如下:

    +-*/()i#

    +﹥﹥﹤﹤﹤﹥﹤﹥

    -﹥﹥﹤﹤﹤﹥﹤﹥

    *﹥﹥﹥﹥﹤﹥﹤﹥

    /﹥﹥﹥﹥﹤﹥﹤﹥

    (﹤﹤﹤﹤﹤=﹤

    )﹥﹥﹥﹥﹥﹥

    i﹥﹥﹥﹥﹥﹥

    #﹤﹤﹤﹤﹤﹤=

    参考严蔚敏等编著、清华大学出版社出版的C语言版《数据结构》P52-P54的表达式求值算法。

    基于算符优先分析方法的表达式语法分析器

    【设计目的】

    了解用算符优先法对表达进行语法分析的方法,掌握自顶向下的预测语法分析程序的手工构造方法。

    【设计内容】

    对简单表达式文法构造算符优先分析器。

    【设计要求】

    对下列简单表达式文法G[ E],构造算符优先关系表。

    E’ →# E #

    E → E + T | T

    T → T * F | F

    F → P / F |P

    P → ( E )|i

    2、根据算符优先关系表,使用栈结构来实现算符优先分析:设置两个栈:存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。具体算法描述如下:

    (1)首先置操作数OPND栈为空栈,将#入运算符OPTR栈。

    (2)依次读入表达式中每个单词,若是操作数则进OPND栈,若是运算符则转(3)。

    (3)当前设读入的运算符为θ2,查找算符优先关系表,比较θ2与OPTR栈顶元素θ1 :

    若θ1﹤θ2,则θ2进OPTR栈,转(2);

    若θ1=θ2, 如θ2为#,则分析成功,否则OPTR栈顶元素θ1出栈,并转(2);

    若θ1>θ2,则出栈OPND栈顶元素存放到b,又出栈其新栈顶元素存放到a,再出栈OPTR栈顶元素至t,进行运算r=a t b (t为运算符),并将结果r存入栈OPND后转(2);

    (4)若θ1和θ2之间无优先关系,则报错。

    3、从键盘输入表达式,利用算符优先法求出其值,如输入表达式有错,则给出报错提示。表达式以“#”结尾。

    【算法思想】

    本题采用算符优先关系表对一个表达式进行求值,首先我们根据文法构造算符优先关系表。如上文所说,构造两个栈:存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。首先置操作数OPND栈为空栈,将#入运算符OPTR栈。

    依次读入表达式中每个单词,若是操作数则进OPND栈,若是运算符,则将其与OPTR栈顶运算符比较优先关系,对于不同的情况做出不同处理。在此过程中,若出现左右括号不匹配,操作数栈的元素参加运算数目不够等情况则报错。

    【变量与函数说明】

    数据结构的定义:

    1、int table[7][7]://存放算符优先关系表的二维数组

    2、存放运算符的OPTR栈:

    typedef struct optr

    {

    int mem[10];

    int top;

    int bottom;

    int sizemax;

    }*OPTR;

    3、存放操作数或运算结果的OPND栈:

    typedef struct opnd

    {

    int mem[10];

    int top;

    int bottom;

    int sizemax;

    }*OPND;

    函数说明:

    1、OPTR栈的相关操作函数:

    OPTR OPTRInit();int OPTRPop(OPTR s);void OPTRPush(int s,OPTR S)

    2、OPND栈的相关操作函数:

    OPND OPNDInit();int OPNDPop(OPTR s);void OPNDPush(int s,OPND S)

    3、void main()

    主函数主要实现以下任务:

    首先置操作数OPND栈为空栈,将#入运算符OPTR栈;

    读取字符串,提取字符串中的数字, 进OPND栈;

    剩余的是运算符或括号,分别进行处理:将栈顶操作符与当前操作符进行优先对比,

    都为#,分析成功,打印结果。

    若栈顶操作符>当前操作符,则出栈OPND栈顶元素存放到i,又出栈其新栈顶元素存放到j,根据不同运算符进行计算并将结果r存入栈OPND。

    若栈顶操作符﹤当前操作符,则将当前操作符入栈OPTR。

    若栈顶操作符与当前操作符没有优先关系,报错。

    【实验源代码】

    #include ﹤stdio.h﹥

    #include ﹤string.h﹥

    #include ﹤ctype.h﹥

    #include ﹤stdlib.h﹥

    #define add 0

    #define mim 1

    #define mul 2

    #define div 3

    #define zuokuo 4

    #define youkuo 5

    #define end 6 //各个符号在算符优先关系表二维数组中的行号或列号

    。。。。。。。。。

    /*******存放运算符的OPTR栈的结构定义和相关操作函数******** */

    typedef struct optr

    {

    int mem[10];

    int top;

    int bottom;

    int sizemax;

    }*OPTR;

    OPTR OPTRInit()

    {

    OPTR s;

    s=(OPTR)malloc(sizeof(struct optr));

    s-﹥top=s-﹥bottom=-1;

    return s;

    }

    int OPTRPop(OPTR s)

    {

    int i;

    if(s-﹥top==-1) printf("The eession is error!There is no element in OPTR\n");

    else

    {

    s-﹥top--;

    i=s-﹥top+1;

    i=s-﹥mem[i];

    return i;

    }

    }

    void OPTRPush(int s,OPTR St)

    {

    int i;

    if(St-﹥top==9)printf("the OPTR is full\n");

    else

    {

    St-﹥top++;

    i=St-﹥top;

    St-﹥mem[i]=s;

    }

    }

    /************存放操作数或运算结果的OPND栈的结构定义和相关操作函数***********/

    typedef struct opnd

    {

    int mem[10];

    int top;

    int bottom;

    int sizemax;

    }*OPND;

    OPND OPNDInit()

    {

    OPND s;

    s=(OPND)malloc(sizeof(struct opnd));

    s-﹥top=s-﹥bottom=-1;

    return s;

    }

    int OPNDPop(OPND s)

    {

    int i;

    int j;

    if(s-﹥top==-1)printf("The eession is error!There is no element in OPND\n");

    else

    {

    s-﹥top--;

    i=s-﹥top+1;

    j=s-﹥mem[i];

    return j;

    }

    }

    void OPNDPush(int s,OPND St)

    {

    int i;

    if(St-﹥top==9) printf("the OPND is full\n");

    else

    {

    St-﹥top++;

    i=St-﹥top;

    St-﹥mem[i]=s;

    }

    }

    void error( char *m) /**错误输出函数**/

    {

    printf("%s\n",m);

    exit(1);

    }

    【运行结果】

    相关说明:

    1、下载本站部分资料,需要注册成为本站会员。如果你尚未注册或登录,请首先注册或登录。

    2、48小时内下载同一文件,不重复扣金币。

    3、下载后请用WinRAR或WinZIP解压缩后使用。

    4、如采用迅雷等下载工具下载失败,请直接用浏览器下载。

    5、如仍有其他下载问题,请看常见问题解答。

    下载地址:

    展开全文
  • 在这一个实验中,我将通过算符优先分析文法这一个工具,在语法分析的时候,顺便进行语义分析,也就是识别出语法单位,同时简要的将识别出的中间代码进行计算(目标代码的生成+运行),得到相应的结果,来检验自己...
  •  算符优先分析法(Operator Precedence Parse)是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。  优点:简单,有效,适合表达式...
  • 算符优先分析方法设计一个分析解释程序,对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中;若存在错误,提示错误相关信息。
  • 实验算符优先分析算法的设计与实现,郑州大学,昝红英,编译原理,源码,已通过
  • 完成一个交互式面向对象的算符优先分析程序,而一个交互式面向对象的算符优先分析程序基本功能是: (1) 输入文法规则 (2) 对文法进行转换 (3) 生成每个非终结符的FirstVT和LastVT (4) 生成算符优先分析表 ...
  • 概述 算符优先分析法(Operator Precedence Parse)是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。 优点:简单,有效,适合表达式...
  • 编译原理实验3-算符优先分析法

    千次阅读 2013-10-26 13:07:13
    #include #include #include #include ... //算符优先关系表数组 char input[SIZE]; //存放输入的要进行分析的句子 char remain[SIZE]; //存放剩余串 char AnalyseStack[SIZE]; //分析栈 void analyse
  • 词法分析器-算符优先

    2012-05-09 17:52:42
    编译原理实验词法分析器-算符优先的设计,实现对词法分析程序所提供的单词序列的语法检查和结构分析
  • ⑴ 选择算符优先分析方法; ⑵ 选择对各种常见程序语言都用的语法结构,如赋值语句或表达式或控制流语句等作为分析对象,并且与所选语法分析方法要比较贴切。 实验内容及要求 (1)根据给定文法,先求出FirstVt和...
  • 算符优先分析法-思路方法在这里

    千次阅读 多人点赞 2020-05-16 20:48:28
    编写一个算符优先分析程序,能实现以下功能: 1.输入文法,判断是否为算符文法; 2.构造并输出该文法的每个非终结符的 FIRSTVT 集和 LASTVT 集; 3.构造并输出算符优先分析表,判断是否为算符优先文法,若不是提示...
  • 算符优先分析法研究--附源程序目 录1 课程设计的目的和要求21.1 课程设计的目的21.2 课程设计的要求22 系统描述22.1 自底向上分析方法的描述:22.2 算符优先文法的描述:23)输入符号串,进行移进-规约分析。...
  • 算符优先分析法是一种简单且直观的自下而上分析方法,它特别适合于分析程序语言中的各类表达式,并且宜于手工实现。所谓算符优先分析,就是依照算术表达式的四则运算过程来进行语法分析,即这种分析方法要预先规定...
  • #include #include #include #include #include #include #include #include #include #include #include <map>
  • 算符优先分析法的简单实现

    千次阅读 2018-05-11 19:05:50
    算符优先分析法即是一种针对算符优先文法的分析方法。 二.如果一个文法的任一产生式的右部都不存在两个相邻的非终结符,则称这个文法为算符文法(OG)。 三.假定文法G是一个不含e的算符文法,a,b∈Vt,P,Q,R∈Vn,...
  • 算符优先语法分析程序

    热门讨论 2012-07-07 21:27:39
    实现算符优先分析算法,完成以下描述算术表达式的算符优先文法的算符优先分析过程。 G[E]:E→E+T∣E-T∣T T→T*F∣T/F∣F F→(E)∣i 说明:终结符号i为用户定义的简单变量,即标识符的定义。 要求: (1)构造该算符...
  • 先用代码占个坑,等期末结束了再补详细解释。。。 /* 2020-06-20 by 软件工程172 202171139 TDM-GCC 4.9.2 64-bit -std=C++11 */ #include #... cout 算符优先分析表\n4.检测输入串\n5.退出\n"; while(true) { cout...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 493
精华内容 197
关键字:

算符优先分析法实验