编译原理 递归下降分析实现

[实验项目]
完成以下描述赋值语句的 LL(1)文法的递归下降分析程序。
G[A]:
A->V=E
E->TX
X->ATX
X->$
T->FY
Y->MFY
Y->$
F->(E)
F->i
A->+
A->-
M->*
M->/
V->i
（为便于分析，这里将文法拆分为单个产生式，$表示空）
Ex: i=(i)+i*i#

[设计说明]
终结符号 i 为用户定义的简单变量，即标识符的定义。

[设计要求]
（1）输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的输出结果，输出为输入串是否为该文法定义的算术表达式的判断结果；
（2）递归下降分析程序应能发现简单的语法错误；
（3）设计两个测试用例（尽可能完备，正确和出错），并给出测试结果；

[实验过程]
由LL(1)文法判定定理可得，原文法G[A]是LL(1)文法，不存在左递归和回溯。为每个非终结符号定义一个对应的函数，函数内容由对应的产生式决定。通过各函数之间的递归调用从而实现递归下降语法分析的功能。具体算法为：
（1）当检索到终结符号a时，则读入输入串中的下一符号；
（2）当检索到非终结符号A时，若当前符号属于First(A)，则调用函数A()，否则报错；
（3）对于A->$（$表示空）规则，在函数A()内部通过判断当前检索的符号a是否属于Follow(A)来决定是否要执行A()；若属于，则跳过A()的执行（因为此处将A推导为空，不应继续对A递归下降分析），否则会出错。
（4）当主程序无退出地检索到输入结束标志”#”时，分析成功。

[实验代码]

#include "pch.h"
#define _CRT_SECURE_NO_WARNINGS
#include "iostream"
#include "stdio.h"
#include "string"
using namespace std;
char Token[50];
char sym;
static int index = 1;
void A();	//A → V=E | + | -
void E();	//E → TX
void T();	//T → FY
void X();	//X → ATX | ε
void Y();	//Y → MFY | ε
void F();	//F → (E) | i
void M();	//M → * | /
void V();	//V → i
void scan() {		//扫描下一字符sym = Token[index];index++;cout << sym <<" ";
}
void error(int a) { //表示出错并指出位置cout << " Error " <<a;cout << sym;exit(0);
}
//A → V=E | + | -
void A(){if (sym == '+' || sym == '-') {scan();}else if(sym == 'i'){V();if (sym == '=') {scan();E();}else {error(0);}}else {error(1);}return;
}
//E → TX
void E() { if (sym == '(' || sym == 'i') { //First(T)T(); X();}elseerror(2);
}//T → FY
void T() {if (sym == '(' || sym == 'i') { //First(F)F();Y();}elseerror(2);
}
//X → ATX | ε
void X() { if (sym == '+' || sym == '-' || sym == 'i') { //First(A)A(); T(); X();}else if (sym == ')' || sym == '#') { // Follow(X);//对于A->ε规则，检查当前符号sym是否在follow(A)中，若是，则执行空函数}elseerror(3);
}
//Y → MFY | ε
void Y() { if (sym == '*' || sym == '/') { //First(M)M(); F(); Y();}else if (sym == '+' || sym == '-' || sym == 'i' || sym == ')' || sym == '#') { //Follow(Y);}elseerror(4);
}
//F → (E) | i
void F() { if (sym == 'i') {scan();}else if (sym == '(') {scan();E();if (sym == ')') {scan(); }else {error(5);}}else {error(6);}return;
}
//M → * | /
void M() {if (sym == '*' || sym == '/')scan();else {error(7);}return;
}
//V → i
void V() { if (sym == 'i')scan();else {error(8);}return;
}
int main()
{cout << "请输入：" << endl;char s ;int i = 0; do{scanf("%c", &s); i++;Token[i] = s;} while (Token[i] != '#');scan();A(); //开始递归if (sym == '#')cout << "分析成功！" << endl;elsecout << "分析失败！" << endl;return 0;
}