编译原理头歌实验：实验3《递归下降分析法设计与实现》（C语言版）

任务描述

本关任务：根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。

相关知识

为了完成本关任务，你需要掌握：递归下降分析程序设计与实现。

递归分析法

递归下降分析法，顾名思义就是使用递归的思想去分析。对于一个文法G，对其每一个非终结符U构造一个递归过程，一般的，以非终结符的名字来命名这个子过程。所有子程序构造完成后，对指定文法，运行文法开始符号对应的子程序，返回匹配结果。

递归下降分析法是一种简洁的分析方法，对于给定的文法G。

1. S -> N V N
2. N -> s
3. | t
4. | g
5. | w
6. V -> e
7. | d

可以根据S的产生式，得到 N,V,N 三个非终结符的子程序，在子程序中，可以分别对 N,V,N 进行相关的定义：

1. parse_S()
2. parse_N()
3. parse_V()
4. parse_N()
6. parse_N()
7. token = tokens[i++]
8. if(token == s || token == t || token == g || token == w)
9. return;
10. error("...")
12. parse_V()
13. token = tokens[i++]
14. ... //

同样的，如果N，V的产生式中还具有非终结符，我们便可以继续递归，完成文法的G的分析。

实验步骤

根据上述可知，在使用递归分析法完成语法分析时，需要做到：

• 对语法规则有明确的定义；
  在递归分析法中，文法由程序之间的相互调用形成递归而构成，我们需要在每个子程序中给出该符号的相关选择就可以了，例如，对于某一符号X，可以给出如下的定义：
  1. void X()
  2. {

  3. if (str[index] == '+')
  4. {

  5. index++;
  6. T();
  7. X();
  8. }
  9. }
• 编写的分析程序能够进行正确的语法分析；
• 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；

编程要求

根据提示，在右侧编辑器补充代码，运行程序，进行结果对比。 根据下列文法完成程序设计，并给出相应提示：

1. （1）E- TG
2. （2）G- +TG|—TG
3. （3）G- ε
4. （4）T- FS
5. （5）S- *FS|/FS
6. （6）S- ε
7. （7）F- (E)
8. （8）F- i

输出的格式如下： (1) 输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2) 输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。

测试说明

开始你的任务吧，祝你成功！

代码：

#include <iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
char str[10];
int index_a = 0;
void E();			//E->TG;
void X();			//G->+TG | e
void T();			//T->FS
void Y();			//S->*FS | e
void F();			//F->(E) | i
int main()
{
	int len;
	cin >> str;
	len = strlen(str);
	str[len + 1] = '\0';
	E();
	cout << str;
	cout << "为合法符号串" << endl;
	index_a = 0;
	return 0;
}
/*******Beign*******/
/*构造递归关系及子程序*/
void E()//E->TG;
{
    T();
    X();
}
void X()//G->+TG | e
{
    if(str[index_a] == '+'){
        index_a++;
        T();
        X();
    }
}
void T()//T->FS
{
    F();
    Y();
}
void Y()//S->*FS | e
{
    if(str[index_a] == '*' || str[index_a] == '/'){
        index_a++;
        F();
        Y();
    }
}
void F()//F->(E) | i
{
    if(str[index_a] == '('){
        index_a++;
        E();
        if(str[index_a] == ')'){
            index_a++;
        }
        else{
            cout << "非法的符号串!";
            exit(0);
        }
    }else if(str[index_a] == 'i'){
        index_a++;
    }
    else{
        cout << "非法的符号串!";
        exit(0);
    }
}
/*******End*******/