递归下降法Java(递归下降法不允许任一非终极符是直接)
LL（1）分析法是什么?
LL分析方法—自顶向下分析
LL(1)是LL(k)的特例,其中的k则表示向前看k个符号.
LL(1)方法和递归下降法属于同一级别的自顶向下分析法,但有一些区别.
递归下降法对每个非终极符产生子程序,而LL(1)方法则产生LL分析表；
递归下降法能判断每个产生式的结束,而LL(1)方法则不能；
递归下降法分析法不用符号栈,而LL(1)方法则用符号栈.
为什么说递归效率低？
对于递归，有人提到了两点：
（1）对栈的容量的压力。
（2）个别问题的递归解法，其算法的低效性。
这两个因素我简短点评下，
（1）对栈的容量压力：
通常递归的深度很大造成的。对于这一点当然应该有程序员编码时，来衡量和把握。win32 中一个新建的线程，默认的栈通常在 1 MB 大小。那么如果你的递归函数，深度很大，显然程序员应该对这种情况有预估，和对风险的避免。
这就和你选择，把内存分配在栈上还是堆上，会考虑到分配的内存大小的因素一样。
当然，如果在函数内分配很大的栈上空间，在函数体内定义一个很大的数组，这样不需要很深的深度，也会让栈溢出。这当然也是程序员自己应该控制的。
（2）个别问题的递归解法，算法的低效。
这个低效主要在于这个问题的算法本身。而不是在递归这种方法上。比如说求斐波那契的某一项，子问题会大量重复出现，会产生很多重复计算，这个是很多算法书上，是用来引导出动态规划或者查表法的。
这主要是算法本身的效率问题，而不是递归的问题。这一点是必须应该明确的。
（3）我们可以看到，在和树有关的算法中，经常会有递归函数。
例如，遍历文件夹，删除注册表的某一个 key （及其所有子key）。
尤其对一般树的前序，后序遍历，二叉树的中序遍历。
这主要原因是因为树的定义，就是“递归性”的：
树就是，某一个节点有多个子节点，每个子节点是一个树。
我们再此可以看到，递归的显著优点，是对解的描述的直观性，代码的简洁性。
DO-WHILE循环语句的翻译程序设计（递归下降法、输出四元式）
///////////////////////////////////////////////////////////////////
////董超勋的for循环语句翻译 递归下降法 输出三地址码 /////////////
#define MAX 100
#includeiostream.h
#includestdio.h
#includestring.h
char str[MAX];
char ch;
int turn;
char strToken[MAX];
int kind;
int n=0;//存放strtoken[]元素的个数
struct Word//结构体 存放单词
{
int sort;
char word[MAX];//存放strtoken[]的内容
};
//record[x]=new Word;
Word *record[12];//放所有识别出来的单词，分别存放他们的编号以及字符串，x是其下标
////////////////////词法分析///////////////////////
int buffer()//载入
{
int i=0;
cout"输入程序，以“#”作为结束标志。"endl;
for(int n=0;n=MAX;n++)
{
for(;i=MAX;i++)
{
scanf("%c",str[i]);
/////////////cinstr[i]不可用，用C语言读入字符。
if(str[i]=='#')
break;///////如果尾数为识别码#,则表示程序读完,跳出循环.
}
break;
}
return(i);
}
bool IsLetter(char ch)///////////判断是否是字母
{
if(ch=65ch=90||ch=97ch=122)
return(true);
else
return(false);
}
bool IsDigit(char ch)//////////判断是否是数字
{
if(ch=48ch=57)
return(true);
else
return(false);
}
char GetChar(int i)///////读取字符
{
char ch;
ch=str[i];
return(ch);
}
char GetBC(char ch)////判断是不是空格或者换行，如果是，直接读取下一个字符直道不再空白为止
{
if(ch==32||ch==10)
{
turn++;
ch=GetChar(turn);
ch=GetBC(ch);/////////递归实现
return(ch);
}
else
return(ch);
}
void Concat()/////////////连接，即为strtoken[]赋值
{
strToken[n]=ch;
n++;
}
int Reserve()/////以单词为单位查找保留字，是则返回编码，不是则返回0，用来区分标志符和保留字
{
if(strcmp(strToken," DIM\0")==0)///////调用strcmp函数实现,
return(1);
else if(strcmp(strToken,"for\0")==0)
return(2);
else if(strcmp(strToken,"step\0")==0)
return(3);
else if(strcmp(strToken,"until\0")==0)
return(4);
else if(strcmp(strToken,"do\0")==0)
return(5);
else
return(6);
}
void clear()
{
n=0;
}
/////////////*语法递归分析*/////////////////
int A(int * c,int q)
{
if(c[q++]==3)
{
if(c[q]==7)
{ q++;
return 1;
}
else {cout"step右部出错"endl;return 0;}
}else {cout"error 'step'"endl;return 0;}
}
int B(int * b,int o)
{
if(b[o++]==4)
{
if(b[o]==7)
{ o++;
return 1;
}
else {cout"until右部出错"endl;return 0;}
}else {cout"error 'until'"endl;return 0;}
}
int S2(int * d,int h)
{
if(d[h++]==6)
{
if(d[h++]==8)
{
if((d[h]==6||d[h]==7)) {h++; return 1;}
else {cout"赋值语句右部出错 "endl;return 0;}
}else {cout"赋值语句缺少赋值运算符 "endl;return 0;}
}else {cout"赋值语句左部出错 "endl;return 0;}
}
int S1(int * m,int n)
{
if(S2(m,n))
{
if(A(m,n))
{
if(B(m,n)) return 1;
else return 0;
}else return 0;
}else return 0;
}
int S(int *a,int z)
{
if (a[z++]==2)
{
if (S1(a,z))
{
if(a[z++]==5)
{
if(S2(a,z))
{
cout"succeed!"endl;return 1;
}else return 0;
}else {cout"error 'do'"endl; return 0;}
}else return 0;
}else {cout"error 'for'"endl; return 0;}
}
void main()
{
cout"*************产生式***************"endl;// for step until do i j =
cout" S -for S1 do S2"endl; // 编号 2 3 4 5 6 7 8
cout" S1 -S2AB"endl;
cout" S2 -i=j"endl;
cout" A -stepj"endl;
cout" B -untilj"endl;
int num;
turn=0;
num=buffer()-1;
int x=0;//计识别的单词的个数
for(;turn=num;turn++)//总循环,ch存放刚读入的字符，strtoken[]存放已识别的标志付或保留字，turn是数组str[]的下标
{
ch=GetChar(turn);
ch=GetBC(ch);
if(IsLetter(ch))
{
while(IsLetter(ch)turn=num||IsDigit(ch)turn=num)
{
Concat();
ch=GetChar(++turn);
}
strToken[n]='\0';
ch=NULL;//此ch不是标志符中的符号
turn=turn-1;
kind=Reserve();
record[x]=new Word; record[x]-sort=kind;//12345或6
//coutkind; //测试
cout"(";
for(int i=0;in;i++)
{
record[x]-word[i]=strToken[i];
coutrecord[x]-word[i];//输出识别的标志符或保留字
}
cout","kind")"endl;
record[x]-word[i]='\0';
clear();
x++;
}
else if(IsDigit(ch))
{
while(IsDigit(ch)turn=num)
{
Concat();
ch=GetChar(++turn);
}
ch=NULL;
turn=turn-1;
kind=7;
//////////////
record[x]=new Word;
record[x]-sort=kind;
////////////////
cout"(";
for(int i=0;in;i++)
{
record[x]-word[i]=strToken[i];
coutrecord[x]-word[i];
}
cout","kind")"endl;
record[x]-word[i]='\0';
clear();x++;
}
else if(ch=='=')
{
kind=8;
///////
record[x]=new Word;
record[x]-word[0]='=';
record[x++]-sort=kind;
cout"(=,"kind")"endl;
}
else
cout"error input!"endl;
}
//////////////////////*语法分析*////////////////
//int y;
/*for(y=0;yx;y++)
{coutrecord[y]-sort" ";//打印单词的编号 。
}coutendl;*/
int ana[MAX];//存放词法分析得到的单词序列的编号的序列
int m;
for(m=0;mx;m++)
{
ana[m]=record[m]-sort;//将sort作为数组保存起来
}
/////////语法分析///////
int j=0;
///////////////////制导翻译//////////////////
if(!S(ana,j)) cout"语法出错!"endl;
else
{ cout"三地址码如下："endl;
cout"100 ";
int i=0;
while(record[1]-word[i]!='\0')
coutrecord[1]-word[i++];coutrecord[2]-word[0];
i=0;
while(record[3]-word[i]!='\0')
coutrecord[3]-word[i++];coutendl;
cout"101 goto 103"endl;
cout"102 ";
i=0;
while(record[1]-word[i]!='\0')
coutrecord[1]-word[i++];cout":=";
i=0;
while(record[1]-word[i]!='\0')
coutrecord[1]-word[i++];cout"+";
i=0;
while(record[5]-word[i]!='\0')
coutrecord[5]-word[i++];coutendl;
cout"103 if ";
i=0;
while(record[1]-word[i]!='\0')
coutrecord[1]-word[i++];cout"";
i=0;
while(record[7]-word[i]!='\0')
coutrecord[7]-word[i++];
cout" goto 105"endl;
cout"104 goto 107"endl;
cout"105 ";
i=0;
while(record[9]-word[i]!='\0')
coutrecord[9]-word[i++];cout":=";
i=0;
while(record[11]-word[i]!='\0')
coutrecord[11]-word[i++];coutendl;
cout"106 goto 102"endl;
cout"107 end"endl;
}
}
在从上到下的语法分析中,预测分析法与递归下降法各有什么优点和缺点
你说的应该是编译原理吧。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 所以，当有左递归出现时，递归下降分析程序就会出现回朔，将可能产生无限的循环，所以递归下降分析的前提条件之一就是消除左递归。
递归下降法属于
递归下降法属于自顶向下分析法。在高级语言编译程序常用的语法分析方法中，递归下降法属于自顶向下分析法。
如何通俗易懂地解释编译原理中语法分析的过程
分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间代码，代码生成，代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的，所以那本龙书的内容格式几乎成了现在编译原理教材的定式，包括国内的教材也是如此。一般来说，大学里面的本科教学是不可能把上面的所有部分都认真讲完的，而是比较偏重于前面几个部分。像代码优化那部分东西，就像个无底洞一样，如果要认真讲，就是单独开一个学期的课也不可能讲得清楚。所以，一般对于本科生，对词法分析和语法分析掌握要求就相对要高一点了。
词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。
语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。