牛骨文教育服务平台(让学习变的简单)
前言
编译原理(一) Chomsky文法的判断方法及C++代码实现
编译原理(二) NFA的确定化及DFA的最小化的算法及C++
编译原理(三) 消除文法的左递归
编译原理(四) 提取左因子法消除回溯
编译原理(五) LL(1)文法分析法(预测分析表的构造算法C
编译原理(六) LL(1)文法分析法(分析过程的C++实现)
编译原理(七) 算符优先分析法(构造算符优先关系表算法及C+
编译原理(八) 算符优先分析法(分析过程的算法和C++实现)
编译原理(九) LR(0)文法分析法(算法描述和C++代码实
编译原理(十) SLR文法分析法(算法原理和C++实现)
当前位置:牛骨文教育服务平台 》开发手册 》 学习手册 》 编译原理算法实现 》 编译原理(一) Chomsky文法的判断方法及C++代码实现

一、明确定义

  • 0型文法：对任一产生式α→β，都有α∈(VN∪VT)+， β∈(VN∪VT)*
  • 1型文法：对任一产生式α→β，都有|β|≥|α|， 仅仅 α→ε除外
  • 2型文法：对任一产生式α→β，都有α∈VN ， β∈(VN∪VT)*
  • 3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN,B∈VN,a∈VT。上述叫做右线性文法，另有左线性文法，二者等价。

二、基本思路

  • 0型文法

  • 首先字符串α的是(Vn⋃Vt)+，是全符号集的一个正闭包，那么包含符号集中所有符号的一个任一组合，但不包含ε元素。

  • 字符串β的是(Vn⋃Vt)∗，是全符号集的一个闭包，那么它比α会多一个ε元素。
  • 那么我们想要判断一个文法是否为0型文法，只需要判断左侧非空即可

  • 任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集

  • 1型文法

  • 首先1型文法必须是0型文法

  • 1型文法除了α→ε这一个特例外，其他情况都满足β的长度大于α的长度

  • 1型文法也叫作上下文相关文法

  • 2型文法

  • 首先2型文法必须是1型文法

  • 2型文法左边必须是一个非终结字符

  • 2型文法也叫做上下文无关文法

  • 3型文法

  • 首先3型文法必须是2型文法

  • 3型文法必须是线性文法

  • 也就是在A,B为非终结符，a是终结符的情况下，产生式只满足如下两种形式(如下为右线性的例子)：

  • A→aB

  • A→a

三、代码实现：

  • 提供两个实现方案：

  • 根据产生式，自己判断Vn,Vt，然后判断文法的类型，支持产生式的缩写版本，是最早实现的版本，可能代码的安排上有些混乱，冗余代码也比较多

#include<iostream>
#include<string>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <vector>
#include <cctype>

using namespace std;

typedef struct CSS
{
    string left;
    string right;//定义产生式的右部 
}CSS;
bool Zero (CSS *p, int n)
{
    int i,j;
    for(i=0;i<n;i++)//循环n次，即遍历所有产生式 
    {
        for(j=0;j<p[i].left.length();j++)//遍历产生式左部每一个字符    
        {
            if(p[i].left[j]>="A"&&p[i].left[j]<="Z")//判断字符是否是非终结符    
            break;
        }
        if(j==p[i].left.length())
        {
            cout<<"该文法不是0型文法"<<endl;
            return 0;
            break;
        }
    }
    if(i==n)
        return 1;//如果每个产生时都能找到非终结符 
}
bool First(CSS *p , int n )//判断1型文法 
{
    int i;
    if(Zero(p,n)) //先判断是否是0型文法 
    {
        for(i=0;i<n;i++)
        {
            if((p[i].left.length()>p[i].right.length())&&p[i].right.length()!=NULL)//判断产生式左部长度是否大于右部 
                break;
        }
        if (i == n )
            return 1;
        else
        {
            cout<<"该文法是0型文法"<<endl;
            return 0;
            }
    }
    else
        return 0;
}
bool Second( CSS*p,int n)//判断2型文法 
{
    int i;
    if(First(p,n))//同上，先判断低级文法是否成立 
    {
        for(i=0;i<n;i++)//同上，遍历所有文法产生式     
        {
            if((p[i].left.length()!=1)||!(p[i].left[0]>="A"&&p[i].left[0]<="Z"))
                break;
        }
        if(i==n)
            return 1;
        else
        {
            cout<<"该文法是1型文法"<<endl;
            return 0;
        }
    }
    else
    return 0;
}

void Third(CSS *p,int n)//判断3型文法 
{
    int i;
    if(Second(p,n))//同上，先判断是否是2型文法 
    {
        for(i=0;i<n;i++)//同上，遍历文法所有的产生式    
        {
            if((p[i].right.length()==0)||(p[i].right.length()>=3)||(p[i].right[0]>="A"&&p[i].right[0]<="Z"))//判断产生式右部字符个数是否在12之间，判断右部第一个字符是否是非终结符 
                break;
        }
            if(i==n)
        {
            for(i=0;i<n;i++)
            {
                if(p[i].right.length()==2)
                {
                    if(!(p[i].right[1]>="A"&&p[i].right[1]<="Z"))
                        break;
                }
            }
            if(i==n)
            {
                cout<<"该文法属于3型文法"<<endl;
            }
            else
                cout<<"该文法属于2型文法"<<endl;
        }
        else
            cout<<"该文法属于2型文法"<<endl;
    }
    else
        cout<<"结束"<<endl;
}

int main ( )
{
    CSS *p = new CSS[100];
    map<char,bool> dic;
    map<char,bool> dic2;
    vector<char> VN;
    vector<char> VT;
    string input1,input2,input3;    
    cout <<"请输入文法："<<endl;
    cin >> input1;
    cout << "请输入VN: "<<endl; 
    cin >> input2;
    for ( int i = 0 ; i < input2.length() ; i++ )
        if ( isalnum ( input2[i] ) )
        {
            VN.push_back ( input2[i] );
            dic[input2[i]]=true;
        }
    cout <<"请输入产生式规则的个数:"<<endl;
    int n;
    cin >> n;
    cout <<"请输入产生式规则："<<endl;
    int cnt = 0;
    for ( int i = 0 ; i < n ; i++ )
    {
        input3.erase ();
        cin >> input3;
        bool flag = false;
        for ( int j = 0 ; j < input3.length() ; j++ )
            if ( input3[j] =="|" ) flag = true;
        if ( flag )
        {
            string temp;
            int j;
            for ( j = 0 ; j < input3.length(); j++ )
            {
                if ( input3[j] ==":" )
                {
                    temp = input3.substr(0,j);
                    j = j+3;
                    break;
                }
            }
            for ( int k =j ; k < input3.length() ; k++ )
            {
                if ( isalnum ( input3[k] ) )
                {
                    p[cnt].left = temp;
                    int tt = k;
                    for ( ;tt < input3.length(); tt++ )
                        if ( input3[tt]=="|" ) break;
                    if ( input3[tt] == "|" ) tt--;
                    p[cnt].right = input3.substr( k , tt-k+1 );
                    if ( dic[input3[k]] == false )
                    {
                        VT.push_back ( input3[k] );
                        dic[input3[k]] = true;
                    } 
                    cnt++;
                    k = tt;
                }
            }
            continue;
        }
        for ( int j = 0 ; j < input3.length() ; j++ )
        {
            if ( input3[j]== ":" )
            {
                p[cnt].left=input3.substr(0,j);
                p[cnt].right=input3.substr(j+3,input3.length());
                cnt++;
                break;
            }
        }   
        for ( int j = 0 ; j < input3.length() ; j++ )
        {
            if ( isalnum( input3[j] ) )
            {
                if ( dic[input3[j]] ) continue;
                VT.push_back ( input3[j] );
                dic[input3[j]] = true;
            }
        }
    }
    cout << input1 << " = ( {";
    for ( int i = 0 ; i < VN.size()-1 ; i++ )
        cout << VN[i] << ",";
    cout << VN[VN.size()-1] <<"},{";
    for ( int i = 0 ; i < VT.size()-1 ; i++ )
        cout << VT[i] << ",";
    cout << VT[VT.size()-1] << "},";
    cout << "P," << input1[2] << " )"<<endl;
    cout << "P : " << endl;
    vector<string> output;
    vector<string> head[500];
    string pre[500];
    for ( int i = 0 ; i < cnt ; i++ )
    {
        int x = p[i].left[0];
        head[x].push_back ( p[i].right );
        pre[x] = p[i].left;
    }
    for ( int i = 0 ; i < 500 ; i++ )
    {
        if ( head[i].size() == 0 ) continue;
        string temp = pre[i]+" ::= ";
        for ( int j = 0 ; j < head[i].size() ; j++ )
        {
            temp += head[i][j];
            if ( j != head[i].size() - 1 ) temp += " | ";
        }
        output.push_back ( temp );
    }
    for ( int i = 0 ; i < output.size() ; i ++ )
        cout << output[i] << endl;
    Third ( p , cnt );
}
  • 第二个版本则是代码和注释风格比较清楚的实现版本，是周末整理之后的一个缩减的版本，不支持缩写，需要提前设定字符集，但是给出了一个更良好的实现方案，适合理解这4种文法类型。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>

using namespace std;
const int VSIZE= 300;

class Principle
{
    public:
        string left;
        string right;
        Principle ( const char* , const char* ); 
};
//只考虑不包含varepsilon的情况，且所有元素均只包含一个字母
vector<char> VN;//非终结符集
vector<char> VT;//终结符集
vector<Principle> principle;//产生式的集合
int type[VSIZE];//每个字符的类型

void init();//清理工作
int get_type(char);//1代表是非终结符，2代表是终结符
bool set_type(char,int);//设置一个字符的类型
int get_result ( );//获得输入的文法的类型

int main ( )
{
    char buf[1000];
    char ** elements;
    while ( true )
    {
        puts("输入VN:");
        gets( buf );
        for ( int i = 0 ; i < strlen(buf); i++ )
        {
            char ch = buf[i];
            if ( !isupper(ch) ) continue;
            if ( get_type(ch) ) continue; 
            VN.push_back ( ch );
            set_type(ch,1);
        }
        puts("输入VT:");
        gets( buf );
        for ( int i = 0 ; i < strlen(buf); i++ )
        {
            char ch = buf[i];
            if ( !islower(ch) ) continue;
            if ( get_type(ch) ) continue;
            VT.push_back ( ch );
            set_type(ch,2);
        } 
        puts("输入产生式：（格式为[A::=...a...]）, 输入"exit"作为结束");
        while ( true )
        {
            gets ( buf );
            if ( !strcmp(buf , "exit" ) ) break;
            int i;
            for ( i = 0 ; i < strlen(buf) ; i++ )
                if ( buf[i] == ":" )
                {
                    buf[i] = 0;
                    i = i+3;
                    break;
                }
            principle.push_back ( Principle( buf , buf+i ) );
            printf ( "%s|%s|
" , buf , buf+i );
        }
        int flag = get_result();
        switch ( flag )
        {
            case -1:
                puts("产生式中出现未知字符");
                break;
            case 0:
                puts("该文法为0型文法");
                break;
            case 1:
                puts("该文法为1型文法");
                break;
            case 2:
                puts("该文法为2型文法");
                break;
            case 3:
                puts("该文法为左线性型文法");
                break;
            case 4:
                puts("该文法为右线性型文法");
                break;
        }
    }
    return 0;
}

Principle::Principle ( const char*l , const char* r )
{
    left = l;
    right = r;
}

//判断字符串是否包含未知字符
bool hasError ( const string& s )
{
    for ( int i = 0 ; i < s.length() ; i++ )
        if ( !get_type(s[i]) ) return true;
    return false;
}

//判断是否为0型文法
bool isZero ( )
{
    for ( int i = 0 ; i < principle.size() ; i++ )
        if ( hasError(principle[i].left) ) return false;
        else if ( hasError(principle[i].right)) return false;
    return true;
}

//判断一个0型文法是否为1型文法
bool isOne ( )
{
    for ( int i = 0 ; i < principle.size(); i++ )
        if ( principle[i].left.length() > principle[i].right.length() )
            return false;
    return true;
}

//判断一个1型文法是否为2型文法
bool isTwo ( )
{
    for ( int i = 0 ; i < principle.size() ; i++ )
    {
        string left = principle[i].left;
        if ( left.size() != 1 ) return false;
        if ( get_type(left[0]) != 1 ) return false;
    }
    return true;
}

//判断一个2型文法是否为左线性文法
bool isLeftThree ()
{
    for ( int i = 0 ; i < principle.size() ; i++ )
    {
        string right = principle[i].right;
        for ( int j = 1; j < right.length() ; j++ )
            if ( get_type(right[j]) != 2 ) return false; 
    }
    return true;
}

//判断一个2型文法是否为右线性文法
bool isRightThree ()
{
    for ( int i = 0 ; i < principle.size() ; i++ )
    {
        string right = principle[i].right;
        for ( int j = 0 ; j < right.length()-1; j++ )
            if ( get_type(right[j]) != 2 ) 
                return false; 
    }
    return true;
}

int get_result ( )
{
    if ( !isZero() ) return -1;
    if ( !isOne() ) return 0;
    if ( !isTwo() ) return 1;
    if ( isLeftThree() ) return 3;
    if ( isRightThree() ) return 4;
    return 2;
}

void init ( )
{
    VN.clear();
    VT.clear();
    principle.clear();
    memset ( type , 0 , sizeof ( type ) );
}

int get_type ( char ch )
{
    return type[ch];
}

bool set_type ( char ch , int x )
{
    type[ch] = x;
    return true;
}
copyright © 2008-2019 亿联网络 版权所有 备案号：粤ICP备14031511号-2