如果对于某文法G,P中的每个规则具有下列形式:
U :: = T 或 U :: = WT
其中T∈VT;U,W∈VN,则称该文法G为左线性文法。
如果对于某文法G,P中的每个规则具有下列形式:
U :: = T 或 U :: = TW
其中T∈VT;U, W∈VN,则称该文法G为右线性文法。
左线性文法和右线性文法通称为3型文法或正则文法,有时又称为有穷状态文法,简写为RG。
按照定义,对于正则文法应用规则时,单个非终结符号只能被替换为单个终结符号,或被替换为单个非终结符号加上单个终结符号,或者被替换为单个终结符号加上单个非终结符号。
3型文法所确定的语言为3型语言L3,3型语言可由确定的有限状态自动机来识别。
程序设计语言的单词可由正则文法产生,例如,标识符的定义可由正则文法描述如下:
<标识符>::=<字母>/<标识符><字母>/<标识符><数字>
显然,该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法——正则表达式。正则表达式又称为正则式,每个正则表达式描述的集合称为正则集。
之所以采用正则表达式来描述,主要基于以下几点原因:
设有字母表∑。∑上的正则表达式和它所表示的正则集递归地定义如下:
定义中(1)和(2)定义了原子正则表达式,而(3)则表明字母表∑上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。
如果两个正则表达式e1和e2表示的正则集相同,即值相等,则称它们是等价的。记为e1=e2。
一个正则表达式的值是正则集,它是正则语言的另一种表示法。不难看出,除了符号Φ外,一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如,对于<数字> ::= 0/1/2/…/9,由非终结符数字所产生的字符串集合与正则表达式0/1/2/…/9所定义的字符串集合是相同的。正则集Φ,它对应一个不包含任何句子的语言,引进的目的主要是为了理论上的完备性。
规则的数据结构:包含两个string对象,一个是left即文法的产生式左边部分,另一个是right即文法产生式的右半部分。
C++
struct Principle{
string left;
string right;
};
文法的数据结构:考虑到文法是一个四元组,包含Vn为非终结符,Vt为终结符,P为文法的规则,S为识别符或开始符,flag为文法的类型,因此下面使用C++中的类来为文法定义,并且使用set集合来保存每个文法的某些属性(不会重复)。
C++
class Grammar{
public:
set<char> Vn;
set<char> Vt;
set<Principle> P;
char S;
int flag = -1;
};
ALL:
//
// main.cpp
// demo
//
// Created by 徐奕 on 2018/11/2.
// Copyright © 2018 Reacubeth. All rights reserved.
//
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#define MAX_LENGTH 10
using namespace std;
struct Principle{
string left;
string right;
};
struct Grammar{
set<char> Vn;
set<char> Vt;
vector<Principle> P;
set<Principle> R;
char S;
int flag = -1;
};
void input(vector<Principle> &principleSet,int time)
{
char tempLeft[MAX_LENGTH];
char tempRight[MAX_LENGTH];
int temp2=0;
while(scanf("%[^-]->%s",tempLeft,tempRight)!=EOF){
getchar();
Principle temp;
temp.left = tempLeft;
temp.right = tempRight;
principleSet.push_back(temp);
temp2++;
if(temp2==time)break;
}
}
void analyseGram(Grammar &G)
{
G.S = G.P.front().left[0];
for(int i=0;i<G.P.size();++i){
Principle &temp = G.P[i];
for(int j = 0;j<temp.left.size();++j){
char v = temp.left[j];
if(!isupper(v)){
G.Vt.insert(v);
}else{
G.Vn.insert(v);
}
}
for(int j = 0;j<temp.right.size();++j){
char v = temp.right[j];
if(!isupper(v)){
G.Vt.insert(v);
}else{
G.Vn.insert(v);
}
}
}
}
bool existVNT(string s)
{
for(int i=0;i<s.size();i++){
if(isupper(s[i])){
return true;
}
}
return false;
}
void judgeGram(Grammar &G)
{
for(int i=0;i<G.P.size();++i){
if(existVNT(G.P[i].left)){
G.flag = 0;
break;
}
}
int temp = 0;
for(int i=0;i<G.P.size()&&G.flag==0;++i){
if(G.P[i].left.size()<=G.P[i].right.size()){
temp++;
}
}
if(temp==G.P.size()){
G.flag=1;
}
temp = 0;
for(int i=0;i<G.P.size()&&G.flag==1;++i){
if(1==G.P[i].left.size()&&isupper(G.P[i].left[0])){
temp++;
}
}
if(temp==G.P.size()){
G.flag=2;
}
temp = 0;
for(int i=0;i<G.P.size()&&G.flag==2;++i){
if(1==G.P[i].left.size()&&isupper(G.P[i].left[0])&&
(1==G.P[i].right.size()&&!isupper(G.P[i].right[0])||2==G.P[i].right.size()&&!isupper(G.P[i].right[0])&&
isupper(G.P[i].right[G.P[i].right.size()-1]))){temp++;}
}
if(temp==G.P.size()){
G.flag=3;
}
}
void printResult(Grammar &G)
{
cout<<"G=(Vn,Vt,P,S):"<<G.flag<<"型文法"<<endl<<endl;
cout<<"非终结符Vn:";
for(set<char>::iterator i = G.Vn.begin();i!=G.Vn.end();++i){
cout<<*i<<" ";
}
cout<<endl;
cout<<"终结符Vt:";
for(set<char>::iterator i = G.Vt.begin();i!=G.Vt.end();++i){
cout<<*i<<" ";
}
cout<<endl;
cout<<"起始符为:"<<G.S<<endl;
cout<<"规则P如输入所示"<<endl;
cout<<endl;
}
void clearP(Principle &P){
P.left="";
P.right="";
}
void transfer2R(Grammar &G){
int i,j;
for(int i=0;i<G.P.size();i++){
for(int j=i+1;j<G.P.size();j++){
if(G.P[i].left == G.P[j].left && G.P[i].right[1]==G.P[j].right[1]&&G.P[i].right.length()>1){
//cout<<"xxxx"<<endl;
G.P[i].right=G.P[i].right+"|"+G.P[j].right;
clearP(G.P[j]);
}
/////////////
//规则3
//cout<<"!"<<G.P[i].left<<G.P[i].right<<G.P[j].left<<G.P[j].right<<endl;
if(G.P[i].right.length()==1&&G.P[j].right.length()==1&&G.P[i].left==G.P[j].left){
G.P[i].right = G.P[i].right+"|"+G.P[j].right;
clearP(G.P[j]);
//cout<<"!!"<<G.P[i].right<<endl;
}
}
}
int flag,m;
for(int i=0;i<G.P.size();i++){// S->aA|bA 2 S->(a|b)A
flag=G.P[i].right.length();
if(G.P[i].right.length()>2&&'A'<=G.P[i].right[1]&&G.P[i].right[1]<='Z'&&G.P[i].right[2]=='|'){
//cout<<"!"<<G.P[0].right<<endl;
int j=0;
for(j=1; j<flag-1;j=j+3){
G.P[i].right[j]=' ';
}
if(j == flag-1){
G.P[i].right="("+G.P[i].right.substr(0,G.P[i].right.length()-1)+")"+G.P[i].right.substr(G.P[i].right.length()-1);
}
}
}
//cout<<G.P[0].right<<endl;
/*
for(int i=0;i<G.P.size();i++){// S->aA|bA 2 S->(a|b)A
flag=G.P[i].right.length();
int k=0,m,t=0;
for(j=0;j<flag;j++){
for(k=j+1;k<flag;k++){
//cout<<G.P[i].right[j]<<G.P[i].right[k]<<endl;
if(G.P[i].right[j]==G.P[i].right[k]&&G.P[i].right[j]>='A'&&G.P[i].right[j]<='Z'){t=1;break;}
}
if(t==1)break;
}
G.P[i].right[j]=' ';
string temp = G.P[i].right;
G.P[i].right="(";
for(m=0;m<k;m++){
G.P[i].right=G.P[i].right+temp[m];
}
G.P[i].right = G.P[i].right+")";
for(m=k;m<flag;m++){
G.P[i].right=G.P[i].right+temp[m];
}
}
*///
for(int i=0;i<G.P.size();i++){
if(G.P[i].left[0]==G.P[i].right[G.P[i].right.length()-1]&&G.P[i].right.length()>1){
for(int j=0; j<G.P.size();j++){
if(G.P[i].left==G.P[j].left&&j!=i){
for(m=0;m<=G.P[j].right.length();m++){
if('A'<=G.P[j].right[m]&&G.P[j].right[m]<='Z'){
break;}
if(m==G.P[j].right.length()){
G.P[i].right=G.P[i].right.substr(0,G.P[i].right.length()-1)+"*"+"("+G.P[j].right+")";
clearP(G.P[j]);
}
}
}
}
}
}
for(int i=0;i<G.P.size();i++){
if(G.P[i].right.length()>1&&G.P[i].left[0]!=G.P[i].right[G.P[i].right.length()-1]){
for(int j=0;j<G.P.size();j++){
if(G.P[j].right.length()>1 && G.P[i].right[G.P[i].right.length()-1]==G.P[j].left[0]&&G.P[j].left[0]==G.P[j].right[G.P[j].right.length()-1]){
G.P[i].right=G.P[i].right.substr(0,G.P[i].right.length()-1)+G.P[j].right.substr(0,G.P[j].right.length()-1)+"*"+G.P[j].right[G.P[j].right.length()-1];
clearP(G.P[j]);
}
}
}
}
flag = G.P.size();
for(int k=0;k<flag;k++){
for(int i=0;i<G.P.size();i++,flag--){
int j;
//cout<<i<<" "<<flag<<endl;
for(j=0;j<G.P[i].right.length();j++){
if('A'<=G.P[i].right[j]&&G.P[i].right[j]<='Z'){
for(m=0;m<G.P.size();m++){
if(G.P[m].left[0]==G.P[i].right[j]&&m!=i){
G.P[i].right=G.P[i].right.substr(0,j)+G.P[m].right+G.P[i].right.substr(j+1);
clearP(G.P[m]);
break;
}
}
}
}
}
}
for(i=0;i<G.P.size();i++){
for(j=0;j<G.P.size();j++){
if(G.P[i].left[0]==G.P[j].left[0]&&i!=j){
if(G.P[j].right.length()>1){
G.P[i].right=G.P[i].right+"|"+"("+G.P[j].right+")";
clearP(G.P[j]);
}else{
G.P[i].right=G.P[i].right+"|"+G.P[j].right;
clearP(G.P[j]);
}
}
}
}
}
int main(){
Grammar G;
G.Vn.clear();
G.Vt.clear();
int time;
cout<<"input:";
cin>>time;
getchar();
input(G.P,time);
G.flag = 3;
analyseGram(G);
judgeGram(G);
//printResult(G);
transfer2R(G);
//cout<<"正则表达式: ";
for(int i=0;i<G.P.size();i++){
if(G.P[i].left.length()!=0){
cout<<G.P[i].left<<"=";
for(int j=0;j<G.P[i].right.length();j++){
if(G.P[i].right[j]!=' ')cout<<G.P[i].right[j];
}
cout<<endl;
}
}
}
1:
S->aA
S->a
A->aA
A->dA
A->a
A->d
2:
S->aB
S->c
B->bB
B->d
①通常如果只有两个相同的非终结符的规则S->a,S->b那么可以直接化简为S->a|b,如果存在多个目标结果为S->a|b|c,那么,需要进行特殊处理,可以使用栈或者递归调用来生成多个或式。
②闭包*的识别,即规则2也是本次实验的难点,需要同时识别文法规则的左右两边。
③有时经过规则1、2和3后所得的结果仍然不正确,这就需要使用集成开发环境的调试工具。增强调试技巧也是非常重要的。
④最后阅读相关文献,发现将正规文法转为正规式可以用解联立方程组的思想进行实现,因此可以用MATLAB解符号函数的方法来写代码。