递归下降算法
自上而下文法的递归下降的预测分析。
从根节点出发逐步构造分析树,所以被称作自上而下文法,在文法中有递归的函数,例如:E’->+TE’|&。所以叫做递归下降算法。
使用的文法如下:
E -> TE ’
E ¢ -> + TE ’ | e
T ->FT ’
T ’ -> * FT ¢’| e
F -> (E) | id
使用的测试字符串为"id+id*id#"
#& 在这里表示空串#
上机题随便写的,使用的c语言,直接参考的文法分析表
总的设计就是遍历字符串,将当前字符与非终结符在表中对应的产生式输出出来
/*
第三次上机-语法分析1-递归下降
2018/10/9
*/
#include<stdio.h>
#include<string.h>
int location=0; //遍历字符串的当前位置
char arr[20]="id+id*id#";
void error(); //错误提示函数
/*
每一个非终结符都构造一个函数
*/
void E(char t);
void Ep(char t);
void T(char t);
void Tp(char t);
void F(char t);
void E(char t){
if(t=='('){
printf("E->TE'");
printf("\n");
T(arr[location]);
Ep(arr[location]);
}else if(t=='i'){
printf("E->TE'");
printf("\n");
T(arr[location]);
Ep(arr[location]);
}
else{
error();
location++;
E(arr[location]);
}
}
void T(char t){
if(t=='i'){
printf("T->FT'");
printf("\n");
F(arr[location]);
Tp(arr[location]);
}else if(t=='('){
printf("T->FT'");
printf("\n");
F(arr[location]);
Tp(arr[location]);
}else{
error();
location++;
T(arr[location]);
}
}
void Ep(char t){
if(t=='+'){
printf("E'->+TE'");
printf("\n");
location++;
T(arr[location]);
Ep(arr[location]);
}else if(t==')'){
printf("E'->&");
printf("\n");
}else if(t=='#'){
}
else{
error();
if(t=='i')
location+=2;
else
location++;
Ep(arr[location]);
}
}
void Tp(char t){
switch(t){
case '+':
printf("T'->&");
printf("\n");
break;
case '*':
printf("T'->*FT'");
printf("\n");
location++;
F(arr[location]);
Tp(arr[location]);
break;
case ')':
printf("T'->&");
printf("\n");
break;
case '#':
printf("T'->&");
printf("\n");
break;
default:
error();
if(t=='i')
location+=2;
else
location++;
Tp(arr[location]);
break;
}
}
void F(char t){
if(t=='i'){
printf("F->id");
printf("\n");
location+=2;
}else if(t=='('){
printf("F->(E)");
printf("\n");
}else{
error();
location++;
F(arr[location]);
}
}
void error(){
printf("有一个错误,略过当前词法记号");
printf("\n");
}
int main(){
E(arr[location]);
}
``