基于C++实现的语法分析之LL(1)分析法实现

Renaissance

发布日期: 2018-11-05 09:29:56 浏览量: 1129
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

一、设计目的

根据某一文法编制调试LL(1)分析程序,以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL(1)分析法的理解。

二、设计要求

程序输入/输出示例:

对下列文法,用LL(1)分析法对任意输入的符号串进行分析:

原文法

  1. E->E+T|E-T|T
  2. T->T*F|T/F|F
  3. F->id|(E)|num
  4. 其中: id: a-f, A-Fnum:0-9

消左递归

  1. E->TA A->+TA A->-TA A->e
  2. T->FB B->*FB B->/FB B->e
  3. F->i F->(E) F->n
  4. 其中:i:id, n:num, e:epsilonE->TG

FIRST集和FOLLOW集

TA +TA -TA e FB *FB /FB e i (E) n
FIRST i,(,n + - e i,(,n * / e i ( n
E A T B F
FOLLOW $,) $,) +,-,$,) +,-,$,) *,/,+,-,$,)

输出的格式如下

  • 输入一以#结束的符号串(包括+—*/()i#):

  • 输出过程如下:

输入 输出
$E (a-1)*(3+4/2)+((8*2))$ E->TA
  • 输入符号串为非法符号串(或者为合法符号串)

注意

  • 表达式中允许使用运算符(+-*/)、分割符(括号)、字符i,结束符#

  • 如果遇到错误的表达式,应输出错误提示信息(该信息越详细越好)

  • 测试用的表达式可以事先放在文本文件中,一行存放一个表达式,同时以分号分割。同时将预期的输出结果写在另一个文本文件中,以便和输出进行对照

三、设计说明

3.1 需求分析

3.1.1 输入及其范围

输入为文法,表达式中允许使用运算符(+-*/)、分割符(括号)、字符a。

3.1.2 输出形式

输入 输出
$E (a-1)*(3+4/2)+((8*2))$ E->TA

3.1.3 程序功能

根据输入的文法进行分析,利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表,对输入符号串自上而下的分析过程。

3.1.4 测试数据

  • 输入:文件“fin.txt”输入待分析串

  • 输出:命令行界面输出预测分析表,LL(1)分析过程输出至“fout.txt”

3.2 概要设计

3.2.1 数据类型的定义

  1. // 预测分析表
  2. vector<vector<string>> table(5,vector<string>(9));
  3. // 消除左递归后的文法产生式
  4. vector<string> G;
  5. // 文法符号到下标的转换字典
  6. map<char, int> index;
  7. // 终结符
  8. string terminal("in+-*/()$");
  9. // 非终结符
  10. string nonTerminal("EATBF");
  11. // 产生式右部符号串的first集
  12. vector<string> First;
  13. // 非终结符的follow集
  14. vector<string> Follow;

3.2.2 主程序流程

3.3 详细设计

  1. int main()
  2. {
  3. for(文法G每个产生式itGitFirst为其右部符号串的first集)
  4. {
  5. x = itG左部非终结符号的下标;
  6. for(itFirst中的每个终结符号first)
  7. {
  8. y = 终结符号first的下标;
  9. itG加入分析表表G[x][y];
  10. }
  11. if(终结符号first == epsilon)
  12. for(Follow集中的每个符号follow)
  13. {
  14. y = follow的下标;
  15. itG加入分析表G[x][y];
  16. }
  17. }
  18. for(所有非终结符号的Follow集)
  19. if(对应表项为空)
  20. 写入synch
  21. 将分析表输出到命令行界面;
  22. return analysis();
  23. }
  1. int analysis(void)
  2. {
  3. 从文件fin.txt读取待分析串到s
  4. s末尾加‘$’;
  5. 分析栈vector<char> analyStack;
  6. 向栈压入‘$’、‘E’;
  7. ip指向s的第一个字符;
  8. do
  9. {
  10. top是栈顶符号;
  11. curip所指向的输入符号;
  12. ifcur是字母) cur = i’;
  13. ifcur是数字) cur = n’;
  14. iftop是终结符号或‘$’)
  15. {
  16. iftop == cur
  17. {
  18. 从栈顶弹出cur
  19. ip前移一个位置;
  20. }
  21. else
  22. error
  23. }
  24. else
  25. {
  26. x = top对应下标;
  27. y = cur对应下标;
  28. 产生式production = table[x][y];
  29. ifproduction非空)
  30. {
  31. 栈顶弹出cur
  32. production右部逆序压栈;
  33. 输出production
  34. }
  35. else
  36. error
  37. }while(top != $’);
  38. }

四、运行结果及分析

4.1 测试数据

fin.txt文件入字符串:(a-1)*(3+4/2)+((8*2))

4.2 测试输出的结果

4.3 输出文件

4.4 设计和思考

主要的难点在于对LL(1)的理解部分,消除二义性、消除左递归、提取左因子,判断是否为LL(1)文法,然后开始整理思路进行编码阶段。开始要对错误的文法进行分析,并提示详细的错误信息。思考之后实现了表达式中允许使用运算符(+-*/)、分割符(括号)、字符a。

五、总结

本次课程设计是本周实验来难点最大的一次作业,首先需要温习LL(1)的知识,如何消除左递归,区别二义性文法,以及对文法的分析。在实验的过程中,最重要的还是要理顺思路,想好解决办法,这也是我经过不断实验总结出的自我思考的方法。然后就进入了编码阶段,此次编码也有一定的难度,在代码量以及代码的整体设计上都有了提升,也是最值得思考的地方。最后,通过实验报告的书写,以及参考资料的查找,对今后的学习和工作都有很大的帮助。

上传的附件 cloud_download 语法分析之 LL1分析法实现.7z ( 359.60kb, 99次下载 )
error_outline 下载需要4点积分

发送私信

聪明但不自以为是,有趣但不哗众取宠,黑暗但不深不见底

8
文章数
11
评论数
最近文章
eject