基于LL(1)的语法分析器

Feelme

发布日期: 2019-02-15 08:26:25 浏览量: 510
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

需求分析

构造一个自定义语法分析程序,实现语法分析器,基于LL(1)语法分析方法对输入语句进行分析,并输出结果。

内容描述

此程序用java编写。程序读取一个文本文件,并对其中的序列进行语法分析。使用LL(1)方法自顶向下进行分析,输出分析过程中的匹配情况和产生式序列。

思路方法

  • 自定义文法G

  • 对G进行预处理,消除左递归、二义性,形成文法G’

  • 计算所有非终结符的First、Follow

  • 构造Prediction Parsing Table

  • 根据输入队列和状态栈的栈顶元素进行分析,将终结符进行匹配或非终结符产生子项,循环处理至输入队列队尾

  • 输出匹配情况和产生式序列

假设

输入的序列仅含有i, +, -, *, /, (, )符号, 相关分析过程描述:

自定义文法

  1. G:
  2. E-> E+T | E-T | T
  3. T-> T*F | T/F | F
  4. F-> (E) | T

文法预处理

  1. G’:
  2. E-> TC
  3. C-> AC | ε
  4. a-> +T | -T
  5. T-> FD
  6. D-> BD | ε
  7. B-> *F | /F
  8. F-> (E) | i

计算非终结符的First、Follow集

First Follow
E {(,i } {+,-,ε}
T {(,i } {+,-,),$ }
F {(,i } {+,-,*,/,),$ }
A {+,- } {+,-,),$ }
B {+,-,*,/,),$ } {+,-,*,/,),$ }
C {+,-,ε} {+,-,*,/,),$ }
D {*,/,ε} {+,-,),$ }

构造PPT

+ - * / ( ) i $
E E->TC E->TC
C C->AC C->AC C->ε C->ε
A A->+T A->-T
T T->FD T->FD
D D->ε D->ε D->BD D->BD D->ε D->ε
B B->*F B->/F
F F->(E) F->i

程序实现

数据结构定义

PPT格式如下

  1. public class ParsingTable {
  2. static String[][] table= {{"null", "null", "null","null","E->TC","null","E->TC"},
  3. {"C->AC","C->AC","null","null","null","C->#","null"},
  4. {"A->+T","A->-T","null","null","null","null","null"},
  5. {"null","null","null","null","T->FD","null","T->FD"},
  6. {"D->#","D->#","D->BD","D->BD","null","D->#","null"},
  7. {"null","null","B->*F","B->/F","null","null","null"},
  8. {"null","null","null","null","F->(E)","null","F->i"}};
  9. public ParsingTable(){
  10. }
  11. public String getExpression(int i,int j){
  12. return table[i][j];
  13. }
  14. }

输出格式

List<String>

核心算法

  1. public LLParser(){
  2. output=new ArrayList<>();
  3. identifier=new Stack<>();
  4. identifier.push('E');
  5. table=new ParsingTable();
  6. }
  7. public void analyze(String input){
  8. int i=0;
  9. while (input.charAt(i)!='$'){
  10. char x=input.charAt(i);
  11. char y=identifier.peek();
  12. if (x==y){
  13. identifier.pop();
  14. output.add("match: "+x);
  15. i++;
  16. continue;
  17. }
  18. else if (table.getExpression(getIndex(y),getIndex(x)).equals("null")){
  19. output.add("error");
  20. break;
  21. }else{
  22. String expr=table.getExpression(getIndex(y),getIndex(x));
  23. output.add(expr);
  24. String id=expr.substring(expr.indexOf(">")+1);
  25. identifier.pop();
  26. for (int j=id.length()-1;j>=0;j--){
  27. if (id.charAt(j)!='#')
  28. identifier.push(id.charAt(j));
  29. }
  30. continue;
  31. }
  32. }
  33. }

程序有状态栈和输入队列,在输入字符序列最后加上终止符,放进队列,状态栈中压入非终结符。读取栈和队列的第一个元素分析,如果匹配成功,则弹出,如果不匹配,则查询PPT表的相关产生式,把新元素压栈,循环至队尾。如果过程中终结符不匹配,则输出error。

测试运行

输入内容如下:

输出内容如下:

上传的附件 cloud_download 基于LL(1)的语法分析器.zip ( 145.43kb, 12次下载 )
error_outline 下载需要3点积分

发送私信

去奋斗,去追求,去发现,但不要放弃

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