爱华网递归下降分析程序构造
实验任务
完成以下描述算术表达式的LL(1)文法的递归下降分析程序构造
G[E]:
E→TE′
E′→+TE′|ε
T→FT′
T′→*FT′|ε
F→(E)|i
说明：终结符号i为用户定义的简单变量,即标识符的定义。
要求具有如下功能：
1)从文件读入算术表达式/或者从终端输入
2)总控函数分析算术表达式；
3)根据分析结果正误，分别给出不同信息
实验目的和要求
通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标：(1) 掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。
(2)、掌握语法分析的实现方法。
(3)、上机调试编出的语法分析程序。
实验学时
2学时
实验背景知识
递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。
递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。
每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。
自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，可根据输入串的当前符号以及各产生式右部首符，选择某非终结符的产生式，效率高，且不易出错。
无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。即：假设A的全部产生式为Aàα1|α2|……|αn，则必须满足如下条件才能保证可以唯一的选择合适的产生式
First(Aàαi)∩First(Aàαj)=Φ,当i≠j.
无左递归：既没有直接左递归，也没有间接左递归。
无回溯：对于人以非中介符号U的产生式右部 ，其对应的字的首终结符号两两不相交。
如果一个文法不含回路（形如 的推导），也不含以 为右部的产生式，那么可以通过执行消除左递归的算法消除文法的一切左递归。
实验步骤
1．根据First集合的定义求文法中每个产生式的First集合，判断是否满足递归下降法分析条件，若不满足用消除左递归和消除公共前缀等文法等价变化算法对文法进行变换，使其满足递归下降法的要求。
2. 构造递归下降语法分析程序
采用递归子程序方法进行语法分析,对文法中的每个非终结符号按其产生式结构产生相应的语法分析子程序,完成相应的识别任务。其中终结符产生匹配命令，非终结符则产生调用命令。每次进入子程序之前都预先读入一个单词。因为使用了递归下降方法,所以程序结构和层次清晰明了,易于手工实现,且时空效率较高。实际的语法分析工作,从调用总程序的分析子程序开始，根据产生式进行递归调用各个分析子程序。
实验目的原理：只是单纯地分析文法，递归地遍历右部分过程，有两个程序，一个是根据非终结符的FIRST集合来编写，另一个则是直接很据非终结符做的，无需计算first集合。关键的地方是要判断输入的字符串最后一个字符为‘ ’..
程序如下：
#include "Stdio.h"
#include "stdlib.h"
#include "string.h"
int i=0;char *s;
void error()
{
printf("errorn");
}
void match(char t)
{
if (s[i] == t)
i++;
else
error();
}
void E()
{
if ((s[i] == '(') || (s[i] == 'i'))
{
printf("E->TE'n");
T();
E1();
}
else
error();
}
int E1()
{
if(s[i]=='+')
{
printf("E'->+TE'n");
match('+');
T();
E1();
}
else if ((s[i] == '(') || (s[i] == 'i') || (s[i] == '*') || (s[i]== ' ') || (s[i] == ')'))
printf("E'->&n");
else
error();
return 0;
}
int T()
{
if ((s[i] == '(') || (s[i] == 'i'))
{
printf( "T->FT'n");
F();
T1();
}
else
error();
return 0;
}
int T1()
{
if (s[i] == '*')
{
printf( "T'->*FT'n");
match('*');
F();
T1();
}
else if ((s[i] == '(') || (s[i] == 'i') || (s[i] == '+') || (s[i]== ' ') || (s[i] == ')'))
printf("T'->&n");
else
error();
return 0;
}
int F()
{
if (s[i] == '(')
{
printf("F->(E)n");
match('(');
E();
match(')');
}
else if (s[i] == 'i')
{
printf("F->in");
match('i');
}
else
error();
return 0;
}
void main()
{
gets(s);
E();
getch();
}
输入结果显示：
这是根据first集合来做的，自顶向下分析文法。
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
int i=0,flag=1;
char *s;
int E()
{
if(T())
{
if (E_prime())
{
printf("E->TE'n");
return 1;
}
}
printf("error_%dn",i);
flag=0;
return 0;
}
int E_prime()
{
if(A())
{
if (T())
{
if (E_prime())
{
printf("E'->ATE'n");
return 1;
}
else {printf("error_%dn",i); flag=0;return 0;}
}
else {printf("error_%dn",i); flag=0;return 0;}
}
return1;
}
int T()
{
if (F())
{
if (T_prime())
{
printf("T->FT'n");
return 1;
}
}
flag=0;
printf("error_%dn",i);
return 0;
}
int T_prime()
{
if (M())
{
if (F())
{
if (T_prime())
{
printf("T'->MFT'n");
return 1;
}
else {printf("error_%dn",i);flag=0;return 0;}
}
else {printf("error_%dn",i); flag=0;return 0;}
}
return 1;
}
int F()
{
if (s[i] == '(')
{
advance();
if (E())
{
if (s[i] == ')')
{
advance();
printf("F->(E)n");
return 1;
}
}
}
else if (s[i] == 'i')
{
advance();
printf("F->in");
return 1;
}
flag=0;
prin--tf("error_%dn",i);
return 0;
}
int A()
{
if (s[i] == '+')
{
advance();
printf("A->+n");
return 1;
}
else if (s[i] == '-')
{
advance();
printf("A->-n");
return 1;
}
return 0;
}
int M()
{
if (s[i] == '*')
{
advance();
printf("M->*n");
return 1;
}
else if (s[i] == '/')
{
advance();
printf("M->/n");
return 1;
}
return 0;
}
int advance()
{
i=i+1;
return0;
}
int main()
{
gets(s);
E();
if(flag==0)
printf("is error!");
else
printf("is ok!");
getch();
return0;
}
结果如下图：
结果是从下至上的分析。。出错时会提示具体错误的位置。。。
