编译原理实验二递归下降语法分析器的构建

86 阅读 0 评论 57 点赞

我是靠谱客的博主正直时光，最近开发中收集的这篇文章主要介绍编译原理实验二递归下降语法分析器的构建，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

实验二递归下降语法分析器的构建

一、实验要求
运用递归下降法，针对给定的上下文无关文法，给出实验方案。预估实验中可能出现的问题。

二、实验方案

构造LL(1),通过设计、编制、调试递归下降语法分析程序，对输入的符号串进行分析匹配，观察输入符号串是否为给定文法的句子。
根据LL(1)写函数和程序
三、预估问题
应确保LL（1）构造成功，不然程序会出错
四、内容和步骤
1、针对4.8习题输入和输出的设计及代码

2、针对现场给定语法的设计和处理
（1）输入字符串，后并加上$符号
（2）匹配字符，若成功，输出并换行，若遇到非终结符，输出空格，若遇到错误，输出字符和位置。

3、实验具体步骤
代码：
#include
#include
#include
using namespace std;
string str;
int pos;
bool flag;
void lexp_seq();
void lexp_seq1();
char judge(char ch)
{
if(ch >= ‘0’ && ch <= ‘9’) return ‘n’;
else if((ch >= ‘A’ && ch <= ‘Z’) || (ch >= ‘a’ && ch <= ‘z’)) return ‘a’;
else return ch;
}
void error(char ch)
{
if (!flag) return;
else flag = false;
cout<<endl<<“error：”<<ch<<",position："<<pos;
}

void match(char kind, char ch)
{
cout<<kind<<": "<<ch<<endl;
pos++;
}

void atom()
{
if(!flag) return;
char ch= judge(str[pos]);
if(ch==‘n’) match(‘n’, str[pos]);
else if(ch==‘a’) match(‘a’, str[pos]);
else if(ch==’$’) cout<<“accept”<<endl;
else error(ch);
}
void list()
{
if(!flag) return;
match(‘l’, ‘(’);
cout<<" ";
lexp_seq();
if(str[pos] == ‘)’) match(‘r’,’)’);
else error(str[pos]);
}

void lexp()
{
if(!flag) return;
char ch= judge(str[pos]);
if(ch == ‘n’ || ch == ‘a’){cout<<" “;atom();}
else if(ch == ‘(’){cout<<” ";list();}
else if(ch == ‘ $KaTeX parse error: Expected 'EOF', got '}' at position 46: \dotslse error(ch); }̲ void lexp_seq(\dots$ ’) cout<<“accept”<<endl;
else error(ch);
}

void lexp_seq1()
{
if(!flag) return;
char ch= judge(str[pos]);
if(ch == ‘n’ || ch == ‘a’ || ch == ‘(’) {cout<<" “;lexp();cout<<” ";lexp_seq1();}
else if(ch == ‘)’) match(‘r’, ‘)’);
else if(ch == ‘$’) cout<<“accept”<<endl;
else error(ch);
}

int main()
{
pos = 0;
flag = true;
cin>>str;
str +=’$’;
lexp_seq();
return 0;
}

针对给定语法进行设计：
E->E+T|T
T->TF|F
F->(E)|id
E->TE’
E’->+TE’|ε
T->FT’
T’->FT’|ε
F->(E)|id
First(E)={(,id}
First(E’)={+, ε}
First(T)={(,id}
First(T’)={, ε}
First(F)={(,id}
Follow(E)={ $KaTeX parse error: Expected 'EOF', got '}' at position 3: ,)}̲ Follow(E’)={$ ,)}
Follow(T)={+, $KaTeX parse error: Expected 'EOF', got '}' at position 3: ,)}̲ Follow(T’)={+,$ ,)}
Follow(F)={*,+,$,)}

五、实验结果:
1、截图

在这里插入图片描述
六、实验结论:
1 、实验结论
通过设计、编制、调试递归下降语法分析程序，对输入的符号串进行分析匹
配，观察输入符号串是否为给定文法的句子，输出其语法树。
2、分析和总结
1）对输入设计的结论
按照4.8的输入
2）对输出设计的结论
输出一个语法树，不受界面尺寸限制
3）对递归下降法的算法的结论
递归下降分析法是一种自顶向下的分析方法，文法的每个非终结符对应一个递归过程（函数）。分析过程就是从文法开始符出发执行一组递归过程（函数），
这样向下推导直到推出句子；或者说从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一棵语法树。