实验4 递归下降语法分析
[实验目的]：
1.了解语法分析的主要任务。
2.熟悉编译程序的编制。
[实验内容]： 根据某文法，构造一基本递归下降语法分析程序。给出分析过程中所用的产生式序列。
[实验要求]：
1.构造一个小语言的文法，例如，Pascal语言子集的文法，考虑其中的算术表达式文法：
G[<表达式>]： G[E]：
<表达式>→<表达式>+<项>|<表达式>-<项>|<项> E→E+T|T
<项>→<项><因式>|<项>/<因式>|<因式> T→TF|F
<因式>→<标识符>|<无符号整数>|(<表达式>) F→i|(E)
2.设计语法树的输出形式，例如：
产生式
……
3.编写递归下降语法分析程序
实现基本的递归下降分析器，能够分析任给的符号串是否为该文法所定义的合法算术表达式。实验报告中要说明分析使用的方法。
4.生成并输出分析过程中所用的产生式序列：
1 产生式1
2 产生式2
……
[实验步骤]：
1.写出一个小语言的算术表达式文法。
G[E]:
E->E+T|T
T->T*F|F
F->(E)|i
2.写出该小语言的算术表达式等价的LL(1)文法。例如：
G[E]： 其中
E→TG G为E’
E→+TG|^ ^为ε
T→FS S为T’
T→*FS|^
F→i|(E)
消除左递归：
E->TG 其中
G->+TG|^ G为E’
T->FS ^为ε
S->*FS|^ S为T’
F->(E)|i
3.编写递归下降语法分析程序。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
char str[10];
int index = 0; //输入串分析字符的索引
void E(); // E->TG
void G(); // G->+TG | ^
void T(); // T->FS
void S(); // S->*FS | ^
void F(); // F->(E) | i
int mycount;
void myrank(); //计数器（步骤数）
void latter(); //当前分析字符
int m, n; //每次匹配终结符(除了^)成功后+1，用来获取分析串和剩余串的下标的结束和开始索引
int len; //输入串长度
void analyze(); //求分析串（i=0~m）
void remain(); //求剩余串 （j=n+1~len)
int main() {int T;printf("请输入要测试的次数：");scanf_s("%d", &T);while (T--) {mycount = 0; m = -1, n = -1; index = 0;printf("请输入算数表达式：");scanf_s("%s", str,sizeof(str));len = strlen(str);str[len] = '#';printf("步骤\t 文法\t\t 分析串\t\t\t分析字符\t\t剩余串\n");E();if (str[index] == '#') printf("正确语句！\n");elseprintf("分析失败!\n");}return 0;
}
void E() { // E->TG myrank(); printf("E -> TX\t\t"); analyze(); latter(); remain();T();G();
}
void G() { // G->+TG | ^if (str[index] == '+') {myrank(); printf("G->+TX\t\t"); m++; n++; analyze(); latter(); remain();index++;T();G();}else {myrank(); printf("G -> ^\t\t"); analyze(); latter(); remain();}
}
void T() { // T->FSmyrank(); printf("T -> FS\t\t"); analyze(); latter(); remain();F();S();
}
void S() { // S->*FS | ^if (str[index] == '*') {myrank(); printf("S->*FS\t\t"); m++; n++; analyze();latter(); remain(); index++;F();S();}else {myrank(); printf("S -> ^\t\t"); analyze(); latter(); remain();}}
void F() { // F->(E) | iif (str[index] == 'i'){myrank(); printf("F ->i\t\t"); m++; n++; analyze(); latter(); remain();index++;}else if (str[index] == '('){myrank(); printf("F ->(E)\t\t"); m++; n++; analyze(); latter(); remain();index++;E();if (str[index] == ')') {myrank(); printf("F ->(E)\t\t"); m++; n++; analyze(); latter(); remain();index++;}else {printf("分析失败!\n");exit(0);}}else{printf("分析失败!\n");exit(0);}
}
void myrank() //计数步骤
{printf("%d\t", mycount);mycount++;
}void analyze() //求分析串
{if (m < 0) cout << ' ';else{for (int i = 0; i <= m; i++) cout << str[i];}cout << '\t' << '\t' << '\t';
}void latter() //打印当前分析字符
{printf("%c", str[index]);cout << '\t' << '\t' << '\t';
}void remain() //获取剩余串
{for (int j = n + 1; j <= len; j++) cout << str[j];cout << '\n';
}
4.调试运行程序。
5.结果分析。
从开始符号开始，使用预测分析表和输入符号串来逐步推导句子，直到接受或拒绝输入。
6.撰写实验报告。
[实验报告]：
1.写出实现的算法。
void E() { // E->TG myrank(); printf("E -> TX\t\t"); analyze(); latter(); remain();T();G();
}
void G() { // G->+TG | ^if (str[index] == '+') {myrank(); printf("G->+TX\t\t"); m++; n++; analyze(); latter(); remain();index++;T();G();}else {myrank(); printf("G -> ^\t\t"); analyze(); latter(); remain();}
}
void T() { // T->FSmyrank(); printf("T -> FS\t\t"); analyze(); latter(); remain();F();S();
}
void S() { // S->*FS | ^if (str[index] == '*') {myrank(); printf("S->*FS\t\t"); m++; n++; analyze();latter(); remain(); index++;F();S();}else {myrank(); printf("S -> ^\t\t"); analyze(); latter(); remain();}}
void F() { // F->(E) | iif (str[index] == 'i'){myrank(); printf("F ->i\t\t"); m++; n++; analyze(); latter(); remain();index++;}else if (str[index] == '('){myrank(); printf("F ->(E)\t\t"); m++; n++; analyze(); latter(); remain();index++;E();if (str[index] == ')') {myrank(); printf("F ->(E)\t\t"); m++; n++; analyze(); latter(); remain();index++;}else {printf("分析失败!\n");exit(0);}}else{printf("分析失败!\n");exit(0);}
}
void myrank() //计数步骤
{printf("%d\t", mycount);mycount++;
}void analyze() //求分析串
{if (m < 0) cout << ' ';else{for (int i = 0; i <= m; i++) cout << str[i];}cout << '\t' << '\t' << '\t';
}void latter() //打印当前分析字符
{printf("%c", str[index]);cout << '\t' << '\t' << '\t';
}void remain() //获取剩余串
{for (int j = n + 1; j <= len; j++) cout << str[j];cout << '\n';
}
2.画出流程图。
3.实验设计过程中出现的问题及解决的方法。
问题：文法不满足递归下降分析法的要求：递归下降分析法要求文法是LL(1)文法，即对于文法中的每个非终结符，其所有候选式的首符号集合（First集合）必须两两不相交，且不存在左递归。
方法：对文法进行变换以满足递归下降分析法的要求：如果文法不是LL(1)文法，可以通过消除左递归、提取公因子等方法对文法进行变换，使其满足递归下降分析法的要求。在变换过程中，需要仔细计算每个产生式的First集合和Follow集合，以确保变换后的文法仍然是正确的。
4.实验设计过程中的体会。
对递归下降分析法的原理和实际应用有了更深入的理解。
5.给出程序清单。
6.给出测试结果。
7.心得收获的总结
对编译原理中的语法分析部分有了更深入的理解。通过实际操作，我掌握了递归下降分析法的核心原理，以及如何构造递归下降分析器。
