本文档是做一个编译原理有关递归法的程序
题目：
已知文法G： 试编写一个程序， 判断文法G所能接受的串。
Z->aAcB | Bd
A->cD
D->aBD | d
B->bC
C->BcA | e
解答：
（1）、消除二义性：
判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。从直观上看，此文法没有二义性。
（2）、消除左递归：
依据消除文法一切左递归的算法，可知此文法没有左递归。
（3）、FIRST集：
FIRST (Z) = {a, b}
FIRST (A) = {c}
FIRST (B) = {b}
FIRST (C) = {ε, b}
FIRST (D) = {a, d}
（4）、FOLLOW集：
FOLLOW (Z) = {#}
FOLLOW (A) = {#, a, c, d}
FOLLOW (B) = {#, a, c, d }
FOLLOW (C) = {#, a, c, d }
FOLLOW (D) = {#, a, c, d }
（5）、产生式的SELECT集：
SELECT (Z->aAcB) = {a}
SELECT (Z->Bd) = {b}
SELECT (A->cD) = {c}
SELECT (B->bC) = {b}
SELECT (C->BcA) = {b}
SELECT (C->e) = {#, a, c, d}
SELECT (D->aBD) = {a}
SELECT (D->d) = {d}
因为SELECT (Z->aAcB) ∩SELECT (Z->Bd) 为空集
SELECT (C->BcA) ∩SELECT (C->e) 为空集
SELECT (D->aBD) ∩SELECT (D->d) 为空集
所以此文法为LL(1)文法。
（6）、LL(1)文法分析表：
a
b
c
d
#
S
aAcB
Bd
A
cD
B
bC
C
e
BcA
e
e
e
D
aBD
d
以下为Recursion.h的内容：
#include<iostream>
#include<cstdlib>
using namespace std;
class Recursion //此语法的递归实现。
{
private:
int i; //此处用于指出要读的字符的位置，相当于语法意义上的单词的位置。
char lookhead; //读出的字符，相当于语法意义上的特殊单词即保留字。
char temp[80]; //用于存放要识别的串即语法单位。
char nexttoken();//调词法分析程序
bool isTrue; //用于判断串是否为本语法识别。
void match(char t);//用于处理单词及出错登记。
void A(); //识别语法单位A
void B(); //识别语法单位B
void C(); //识别语法单位C
void D(); //识别语法单位D
void error(); //出错处理。
void Z(); //识别语法单位Z
public:
void isTrueString(); //判断串是否为本语法识别。
Recursion(char *temp);
};
以下为Recursion.cpp的内容：
#include "Recursion.h"
Recursion::Recursion(char *temp)
{
strcpy(this->temp, temp);
i = 0;
isTrue = true;
lookhead = nexttoken();
}
void Recursion::isTrueString()
{
Z();
if(isTrue == false)
printf("此串不能为此文法接受。\n\n");
else
printf("此串能为此文法接受。\n\n");
}
void Recursion::error()
{
isTrue = false;
}
char Recursion::nexttoken()
{
if(i<strlen(temp))
{
return(temp[i++]);
}
return('\0');
}
void Recursion::match(char t)
{
if (lookhead==t)
lookhead=nexttoken();
else
error(); // 出错处理程序
}
void Recursion::Z() // Z->aAcB | Bd
{
if(lookhead=='a')
{
match('a');
A();
match('c');
B();
}
else
{
B();
match('d');
}
}
void Recursion::A() // A->cD
{
if (lookhead=='c')
{
match('c');
D();
}
else
error();
}
void Recursion::D() // D->aBD | d
{
if(lookhead=='a')
{
match('a');
B();
D();
}
else if(lookhead=='d')
{
match('d');
}
else
error();
}
void Recursion::B() // B->bC
{
if(lookhead=='b')
{
match('b');
C();
}
else
error();
}
void Recursion::C() //C->BcA | !
{
if(lookhead=='\0' || lookhead=='a' || lookhead=='c' || lookhead=='d')
{
}
else
{
B();
match('c');
A();
}
}
以下为testRecursion.cpp的内容：
#include "Recursion.cpp"
void main()
{
char temp[80];
char ch;
do
{
printf("请输入要识别的串:\n");
scanf("%s",temp);
Recursion recursion(temp);
recursion.isTrueString();
printf("是否继续识别:[y,n]? ");
ch=getchar();
while (ch!='y' && ch!='n') ch=getchar();
}while(ch == 'y');
}
