本文共 1992 字,大约阅读时间需要 6 分钟。
运用递归下降法,针对给定的上下文无关文法,给出实验方案。预估实验中可能出现的问题。
1、构造LL(1),通过设计、编制、调试递归下降语法分析程序,对输入的符号串进行分析匹配,观察输入符号串是否为给定文法的句子。
2、根据LL(1)写函数和程序
应确保LL(1)构造成功,不然程序会出错
理论基础
递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理,添加语义加工工作比较方便。
递归下降分析程序的实现思想是:识别程序由一组子程序组成。每个子程序对应于一个非终结符号。
每一个子程序的功能是:选择正确的右部,扫描完相应的字。在右部中有非终结符号时,调用该非终结符号对应的子程序来完成。
自上向下分析过程中,如果带回溯,则分析过程是穷举所有可能的推导,看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术,当选择某非终结符的产生时,可根据输入串的当前符号以及各产生式右部首符号而进行,效率高,且不易出错。
无回溯的自上向下分析技术可用的先决条件是:无左递归和无回溯。
无左递归:既没有直接左递归,也没有间接左递归。
无回溯:对于任一非终结符号U的产生式右部x1|x2|…|xn,其对应的字的首终结符号两两不相交。
如果一个文法不含回路(形如P⇒+ P的推导),也不含以ε为右部的产生式,那么可以通过执行消除文法左递归的算法消除文法的一切左递归(改写后的文法可能含有以ε为右部的产生式)。
1、针对4.8习题输入和输出的设计及代码
2、针对现场给定语法的设计和处理
【考虑简单算术表达式文法G:
E→E + T | T
T→T * F | F
F→(E) | id
试设计递归下降分析程序,以对任意输入的符号串进行语法分析。】
3、实验具体步骤
(1)输入字符串,后并加上$符号
(2)匹配字符,若成功,输出并换行,若遇到非终结符,输出空格,若遇到错误,输出字符和位置。
针对给定语法进行设计:
E->E+T|TT->TF|FF->(E)|idE->TE’E’->+TE’|εT->FT’T’->FT’|εF->(E)|idFirst(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)={*,+,$,)}
代码
#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< <<"error:"< <<",position:"< >str; str +='$'; lexp_seq1(); return 0;}
截图
1 、实验结论
通过设计、编制、调试递归下降语法分析程序,对输入的符号串进行分析匹配,观察输入符号串是否为给定文法的句子,输出其语法树。
2、分析和总结
1)对输入设计的结论
按照4.8的输入
2)对输出设计的结论
输出一个语法树,不受界面尺寸限制
3)对递归下降法的算法的结论
递归下降分析法是一种自顶向下的分析方法,文法的每个非终结符对应一个递归过程(函数)。分析过程就是从文法开始符出发执行一组递归过程(函数),
这样向下推导直到推出句子;或者说从根节点出发,自顶向下为输入串寻找一个最左匹配序列,建立一棵语法树。
3、对预估问题的结论
预估问题未发生
转载地址:http://tiwof.baihongyu.com/