编译语法递归下降分析法
⑴ 编译原理语法分析有哪几种方法
语法分析有自上而下和自下而上两种分析方法
其中
自上而下：递归下降，LL(1)
自下而上：LR(0),SLR(1),LR(1),LALR(1)
⑵ 高分求编译原理递归下降语法分析设计原理
lz，最好改成这种形式，不要直接消左递归：
E -> TAE
T -> FMT
F -> (E) | i
A-> +|- M->*|/
⑶ 编译原理，递归下降子程序语法分析
没学过编译原理，看描述，是让写一个脚本执行软件。
终结符我查了下，就是不可再分的。比如iε。
输入是EGTSFI*/ε组成的字符串。
规则需要预处理。注意转意符在字符串中的效果。因为有/字符。
不会c或c++，只会c#。你可以到贴吧发帖。强人工智能吧 就挺好。算法吧有点乱。
最重要的，不要钱。
⑷ 编译原理 递归下降分析器
自顶向下分析法(递归下降分析程序构造)
E-->T/E+T
T-->F/T*F
F-->i/(E)
步骤 栈 输入字符串 状态
0 #E i1*(i2+i3)# 初始化
1 #T i1*(i2+i3)# E-->T
2 #T*F i1*(i2+i3)# T-->T*F
3 #T*i i1*(i2+i3)# F-->i
4 #F* *(i2+i3)# 匹配
5 #F (i2+i3)# 匹配
6 #(E) (i2+i3)# E-->(E)
7 #(E i2+i3)# 匹配
8 #(E+T i2+i3)# E-->E+T
9 #(E+F i2+i3)# T-->F
10 #(E+i i2+i3)# F-->i
11 #(E+ +i3)# 匹配
12 #(E i3)# 匹配
13 #(T i3)# E-->T
14 #(F i3)# T-->F
15 #(i i3)# F-->i
16 #( )# 匹配
17 # # 接受
所以可以写出
PROCEDURE E
BEGIN
T;
WHILE SYM='+' THEN ADVANCE;T END
END;
PROCEDURE T
BEGIN
F;
WHILE SYM='*' THEN ADVANCE;F END
END;
PROCEDURE F
BEGIN
IF SYM='i' THEN ADVANCE END
ELSE
IF SYM='(' THEN
BEGIN ADVANCE;E;
IF SYM=')' THEN ADVANCE;
ELSE ERROR;END
END;
⑸ 求解编译原理题 构造递归下降分析程序
兄弟，其实这个问题不难，只是我感觉你给的问题不完全，不知道怎么给你解决，要不我给你个递归下降分析方法分析文法的例子吧，你先看看。我估计你看了这个后绝对就明白整体的分析思想了～
文法如下:
S->do s1 begin s2 end while s2
s1->s2mB
s2->AmB
A->B
B->VAL //VAL是所有非关键字的字符字符组和数字
m->+｜-｜*｜/｜>｜<｜=
/////////////*语法递归分析*/////////////////
int B(int * c,int & q)
{
if(c[q]==13)
{ q++;
return 1;
}
else if(c[q]==5)
{ q++;
return 1;
}
else {cout<<"error 'B'"<<endl;return 0;}
}
int A(int * b,int & o)
{
if(B(b,o))
{
return 1;
}
else {cout<<"error 'A'"<<endl;return 0;}
}
int OP(int *r,int & v)
{
if(r[v]==6)
{
v++;
return 1;
}
else if(r[v]==7)
{
v++;
return 1;
}
else if(r[v]==8)
{
v++;
return 1;
}
else if(r[v]==9)
{
v++;
return 1;
}
else if(r[v]==10)
{
v++;
return 1;
}
else if(r[v]==11)
{
v++;
return 1;
}
else if(r[v]==12)
{
v++;
return 1;
}
else {cout<<"error 'OP'"<<endl;return 0;}
}
int S2(int * d,int & h)
{
if(A(d,h))
{
if(OP(d,h))
{
if(B(d,h))
return 1;
else {cout<<"条件语句右部出错 "<<endl;return 0;}
}
else {cout<<"条件语句缺少运算符 "<<endl;return 0;}
}
else {cout<<"条件语句左部出错 "<<endl;return 0;}
}
int S1(int * d,int & h)
{
if(S2(d,h))
{
if(OP(d,h))
{
if(B(d,h))
return 1;
else {cout<<"循环语句右部出错 "<<endl;return 0;}
}
else {cout<<"循环语句缺少运算符 "<<endl;return 0;}
}
else {cout<<"循环语句左部出错 "<<endl;return 0;}
}
int S(int *a,int & z)
{
if (a[z++]==1)
{
if (S1(a,z))
{
if (a[z++]==2)
{
if (S2(a,z))
{
if(a[z++]==3)
{
if(a[z++]==4)
{
if(S2(a,z))
{
cout<<"语法分析成功!"<<endl;
return 1;
}
else return 0;
}
else {cout<<"error 'while'"<<endl; return 0;}
}
else {cout<<"error 'end'"<<endl; return 0;}
}
else return 0;
}
else {cout<<"error 'begin'"<<endl; return 0;}
}
else return 0;
}
else {cout<<"error 'do'"<<endl; return 0;}
}
/////////////////////// 语法分析结束 ////////////////////////
词法分析中单词代号 词法分析中可识别到的所有单词
1 do
2 begin
3 end
4 while
5 除关键字以外的所有字符或字符串
6 +
7 -
8 *
9 /
10 =
11 >
12 <
13 数字
14 结束标识符“#”
自己好好琢磨琢磨吧，其实思想挺简单的～
⑹ 编译递归下降分析法
#include <stdio.h>
#include<dos.h>
#include<stdlib.h>
#include<string.h>
char a[50] ,b[50],d[200],e[10];
char ch;
int n1,i1=0,flag=1,n=5;
int E();
int E1();
int T();
int G();
int S();
int F();
void input();
void input1();
void output();
void main() /*递归分析*/
{
int f,p,j=0;
char x;
d[0]='E';
d[1]='=';
d[2]='';
d[3]='T';
d[4]='G';
d[5]='#';
printf("请输入字符串(长度<50,以#号结束）\n");
do{
scanf("%c",&ch);
a[j]=ch;
j++;
}while(ch!='#');
n1=j;
ch=b[0]=a[0];
printf("文法\t分析串\t\t分析字符\t剩余串\n");
f=E1();
if (f==0) return;
if (ch=='#')
{ printf("accept\n");
p=0;
x=d[p];
while(x!='#') {
printf("%c",x);p=p+1;x=d[p]; /*输出推导式*/
}
}
else {
printf("error\n");
printf("回车返回\n");
getchar();getchar();
return;
}
printf("\n");
printf("回车返回\n");
getchar();
getchar();
}
int E1()
{ int f,t;
printf("E--TG\t");
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
int E()
{ int f,t;
printf("E--TG\t");
e[0]='E';e[1]='=';e[2]='';e[3]='T';e[4]='G';e[5]='#';
output();
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
int T()
{ int f,t;
printf("T--FS\t");
e[0]='T';e[1]='=';e[2]='';e[3]='F';e[4]='S';e[5]='#';
output();
flag=1;
input();
input1();
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);
}
int G()
{ int f;
if(ch=='+') {
b[i1]=ch;
printf("G--+TG\t");
e[0]='G';e[1]='=';e[2]='';e[3]='+';e[4]='T';e[5]='G';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=T();
if (f==0) return(0);
G();
return(1);
}
printf("G--^\t");
e[0]='G';e[1]='=';e[2]='';e[3]='^';e[4]='#';
output();
flag=1;
input();input1();
return(1);
}
int S()
{
int f,t;
if(ch=='*') {
b[i1]=ch;printf("S--*FS\t");
e[0]='S';e[1]='=';e[2]='';e[3]='*';e[4]='F';e[5]='S';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);}
printf("S--^\t");
e[0]='S';e[1]='=';e[2]='';e[3]='^';e[4]='#';
output();
flag=1;
a[i1]=ch;
input();input1();
return(1);
}
int F()
{ int f;
if(ch=='(') {
b[i1]=ch;printf("F--(E)\t");
e[0]='F';e[1]='=';e[2]='';e[3]='(';e[4]='E';e[5]=')';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=E();
if (f==0) return(0);
if(ch==')') {
b[i1]=ch;printf("F--(E)\t");
flag=0;input();input1();
ch=a[++i1];
}
else {
printf("error\n");
return(0);
}
}
else if(ch=='i') {
b[i1]=ch;printf("F--i\t");
e[0]='F';e[1]='=';e[2]='';e[3]='i';e[4]='#';
output();
flag=0;input();input1();
ch=a[++i1];
}
else {printf("error\n");return(0);}
return(1);
}
void input()
{
int j=0;
for (;j<=i1-flag;j++)
printf("%c",b[j]); /*输出分析串*/
printf("\t\t");
printf("%c\t\t",ch); /*输出分析字符*/
}
void input1()
{
int j;
for (j=i1+1-flag;j<n1;j++)
printf("%c",a[j]); /*输出剩余字符*/
printf("\n");
}
void output(){ /*推导式计算*/
int m,k,j,q;
int i=0;
m=0;k=0;q=0;
i=n;
d[n]='=';d[n+1]='';d[n+2]='#';n=n+2;i=n;
i=i-2;
while(d[i]!=''&&i!=0) i=i-1;
i=i+1;
while(d[i]!=e[0]) i=i+1;
q=i;
m=q;k=q;
while(d[m]!='') m=m-1;
m=m+1;
while(m!=q) {
d[n]=d[m];m=m+1;n=n+1;
}
d[n]='#';
for(j=3;e[j]!='#';j++){
d[n]=e[j];
n=n+1;
}
k=k+1;
while(d[k]!='=') {
d[n]=d[k];n=n+1;k=k+1;
}
d[n]='#';
}
这是我们用到的程序，看看对你有没有帮助。
至于下面的两个问题，很简单，可以容易做出来吧！
不会可以和我交流！
祝 进步！
⑺ 在从上到下的语法分析中,预测分析法与递归下降法各有什么优点和缺点
你说的应该是编译原理吧。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 所以，当有左递归出现时，递归下降分析程序就会出现回朔，将可能产生无限的循环，所以递归下降分析的前提条件之一就是消除左递归。
⑻ 递归下降分析法
# include <iostream>
# include <cstdlib>
# include <cctype>
# include <csetjmp>
// Error jmp_buf buffer
static std::jmp_buf errjb;
// Function prototypes.
int addsubt();
int multdiv();
int number();
void error();
// Global expression buffer.
static char expr[81];
static int pos;
////////////////////////////
// The main() function. //
///////////////////////////
int main()
{
int ans;
do
{
// Mark the top of the parsing descent.
if(setjmp(errjb) == 0)
{
// Initialize the string subscript.
pos = 0
// Read an expression.
std::cout << "Enter expression(0 to quit):" << std::endl;
std::cin >>expr;
// Evaluate the expression.
ans = addsubt();
if(expr[pos] != '\0')
error();
if(ans != 0)
std::cout << ans << std:endl;
}
else
{
// An error occurred.
std::cout << "Try again" << std::endl;
ans = 1;
}
}
while(ans != 0);
return 0;
}
///////////////////////////////////////////////////
// Top of recursive descent: add/subtract. //
//////////////////////////////////////////////
int addsubt()
{
int rtn = multdiv();
while(expr[pos] == '+' || expr[pos] == '-')
{
int op = expr[pos++];
int opr2 = multdiv();
if(op == '+')
rtn += opr2;
else
rtn -= opr2;
}
return rtn;
}
////////////////////////////////////////////
// Highest precedence: multiply/divide. //
///////////////////////////////////////////
int multdiv()
{
int rtn = number();
while(expr[pos] == '*' || expr[pos] == '/')
{
int op = expr[pos++];
int opr2 = number();
if(op == '*')
rtn *= opr2;
else
rtn /= opr2;
}
return rtn;
}
/////////////////////////
// Extract a number //
///////////////////////
int number()
{
int rtn;
if(expr[pos] == '(')
{
// Parenthetical expression.
pos++;
rtn = addsubt(); // Back to top.
if(expr[pos++] != ')') // Must have ')'
error();
return rtn;
}
// Extract the number.
if(!isdigit(expr[pos]))
error;
rtn = atoi(expr + pos);
while(isdigit(expr[pos]))
pos++;
return rtn;
}
////////////////////////
// Syntax error. //
//////////////////////
void error()
{
std::cout << '\r';
while(pos--) // Position error pointer.
std::cout << ' ';
std::cout << "A syntax error" << std::endl << '\a';
// Return to the top of the program.
std::longjmp(errjb,1);
}
}
⑼ 编译原理-LL1文法详细讲解
我们知道2型文法( CFG )，它的每个产生式类型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。
例如, 一个表达式的文法:
最终推导出 id + (id + id) 的句子，那么它的推导过程就会构成一颗树，即 CFG 分析树：
从分析树可以看出，我们从文法开始符号起，不断地利用产生式的右部替换产生式左部的非终结符，最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。
从文法开始符号起，不断用非终结符的候选式(即产生式)替换当前句型中的非终结符，最终得到相应的句子。
在每一步推导过程中，我们需要做两个选择:
因为一个句型中，可能存在多个非终结符，我们就不确定选择那一个非终结符进行替换。
对于这种情况，我们就需要做强制规定，每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。
自顶向下的语法分析采用最左推导方式，即总是选择每个句型的最左非终结符进行替换。
最终的结果是要推导出一个特定句子(例如 id + (id + id) )。
我们将特定句子看成一个输入字符串，而每一个非终结符对应一个处理方法，这个处理方法用来匹配输入字符串的部分，算法如下:
方法解析:
这种方式称为递归下降分析( Recursive-Descent Parsing )：
当选择的候选式不正确，就需要回溯( backtracking )，重新选择候选式，进行下一次尝试匹配。因为要不断的回溯，导致分析效率比较低。
这种方式叫做预测分析( Predictive Parsing )：
要实现预测分析，我们必须保证从文法开始符号起，每一个推导过程中，当前句型最左非终结符 A 对于当前输入字符 a ,只能得到唯一的 A 候选式。
根据上面的解决方法，我们首先想到，如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。
进而我们可以得出，如果一个非终结符 A ，它的候选式都是以终结符开头，并且这些终结符都各不相同，那么本身就符合预测分析了。
这就是S_文法，满足下面两个条件:
例子:
这就是一个典型的S_文法，它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S -> aA | bAB , 只有遇到终结符 a 和 b 的时候，才能返回 S 的候选式，遇到其他终结符时，直接报错，匹配不成功。
虽然S_文法可以实现预测分析，但是从它的定义上看，S_文法不支持空产生式(ε产生式)，极大地限制了它的应用。
什么是空产生式(ε产生式)？
例子
这里 A 有了空产生式，那么 S 的产生式组 S -> aA | bAB ，就可以是 a | bB ,这样 a , bb , bc 就变成这个文法 G 的新句子了。
根据预测分析的定义，非终结符对于任一终结符得到的产生式是确定的，要么能获取唯一的产生式，要么不匹配直接报错。
那么空产生式何时被选择呢？
由此可以引入非终结符 A 的后继符号集的概念:
定义: 由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符 a 的集合，就是这个非终结符 A 的后继符号集，记为 FOLLOW(A) 。
因此对于 A -> ε 空产生式，只要遇到非终结符 A 的后继符号集中的字符，可以选择这个空产生式。
那么对于 A -> a 这样的产生式，只要遇到终结符 a 就可以选择了。
由此我们引入的产生式可选集概念:
定义: 在进行推导时，选用非终结符 A 一个产生式 A→β 对应的输入符号的集合，记为 SELECT(A→β)
因为预测分析要求非终结符 A 对于输入字符 a ,只能得到唯一的 A 候选式。
那么对于一个文法 G 的所有产生式组，要求有相同左部的产生式，它们的可选集不相交。
在 S_文法基础上，我们允许有空产生式，但是要做限制:
将上面例子中的文法改造:
但是q_文法的产生式不能是非终结符打头，这就限制了其应用，因此引入LL(1)文法。
LL(1)文法允许产生式的右部首字符是非终结符，那么怎么得到这个产生式可选集。
我们知道对于产生式:
定义: 给定一个文法符号串 α ， α 的 串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。
定义已经了解清楚了，那么该如何求呢？
例如一个文法符号串 BCDe , 其中 B C D 都是非终结符， e 是终结符。
因此对于一个文法符号串 X1X2 … Xn ，求解 串首终结符集 FIRST(X1X2 … Xn) 算法:
但是这里有一个关键点，如何求非终结符的串首终结符集？
因此对于一个非终结符 A , 求解 串首终结符集 FIRST(A) 算法:
这里大家可能有个疑惑，怎么能将 FIRST(Bβ) 添加到 FIRST(A) 中，如果问文法符号串 Bβ 中包含非终结符 A ，就产生了循环调用的情况，该怎么办?
对于 串首终结符集 ，我想大家疑惑的点就是，串首终结符集到底是针对 文法符号串 的，还是针对 非终结符 的，这个容易弄混。
其实我们应该知道， 非终结符 本身就属于一个特殊的 文法符号串 。
而求解 文法符号串 的串首终结符集，其实就是要知道文法符号串中每个字符的串首终结符集:
上面章节我们知道了，对于非终结符 A 的 后继符号集 :
就是由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符的集合，记为 FOLLOW(A) 。
仔细想一下，什么样的终结符可以出现在非终结符 A 后面，应该是在产生式中就位于 A 后面的终结符。例如 S -> Aa ，那么终结符 a 肯定属于 FOLLOW(A) 。
因此求非终结符 A 的 后继符号集 算法：
如果非终结符 A 是产生式结尾，那么说明这个产生式左部非终结符后面能出现的终结符，也都可以出现在非终结符 A 后面。
我们可以求出 LL(1) 文法中每个产生式可选集:
根据产生式可选集，我们可以构建一个预测分析表，表中的每一行都是一个非终结符，表中的每一列都是一个终结符，包括结束符号 $ ，而表中的值就是产生式。
这样进行语法推导的时候，非终结符遇到当前输入字符，就可以从预测分析表中获取对应的产生式了。
有了预测分析表，我们就可以进行预测分析了，具体流程:
可以这么理解：
我们知道要实现预测分析，要求相同左部的产生式，它们的可选集是不相交。
但是有的文法结构不符合这个要求，要进行改造。
如果相同左部的多个产生式有共同前缀，那么它们的可选集必然相交。
例如:
那么如何进行改造呢？
其实很简单，进行如下转换:
如此文法的相同左部的产生式，它们的可选集是不相交，符合现预测分析。
这种改造方法称为 提取公因子算法 。
当我们自顶向下的语法分析时，就需要采用最左推导方式。
而这个时候，如果产生式左部和产生式右部首字符一样(即A→Aα)，那么推导就可能陷入无限循环。
例如:
因此对于:
文法中不能包含这两种形式，不然最左推导就没办法进行。
例如:
它能够推导出如下:
你会惊奇的发现，它能推导出 b 和 (a)* (即由 0 个 a 或者无数个 a 生成的文法符号串)。其实就可以改造成:
因此消除 直接左递归 算法的一般形式：
例如:
消除间接左递归的方法就是直接带入消除，即
消除间接左递归算法：
这个算法看起来描述很多，其实理解起来很简单：
思考 : 我们通过 Ai -> Ajβ 来判断是不是间接左递归，那如果有产生式 Ai -> BAjβ 且 B -> ε ,那么它是不是间接左递归呢？
间接地我们可以推出如果一个产生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那么这个产生式是不是间接左递归。
⑽ 递归下降法属于
递归下降法属于自顶向下分析法。在高级语言编译程序常用的语法分析方法中，递归下降法属于自顶向下分析法。