LL(1)语法分析程序

代码基于词法分析程序,并且只实现了根据分析表分析字符串操作,分析表是静态创建的。

import java.io.IOException;
import java.util.Stack;

/**
 * 语法分析程序
 * @author 霍淇滨
 *
 */
public class Analysis {
	private Stack<Character> ans;		//分析栈
	private Stack<Character> aim;		//余留字符串栈
	private String[][] table;		//分析表
	private int count = 1;
	/**
	 * 构造函数,初始化栈和表
	 * @param str
	 */
	public Analysis(String str) {
		ans = new Stack<Character>();
		aim = new Stack<Character>();
		table = new String[5][6];		
		System.out.println(str);
		
		aim.push('#');
		for(int i = str.length()-1;i>=0;i--)		//初始化余留字符串栈
			aim.push(str.charAt(i));
		ans.push('#');		//初始化分析栈
		
		construct();		//构建分析表
	}
	
	/**
	 * 构建分析表
	 */
	private void construct() {
		table[0][0] = "TS";table[0][1] = "error";table[0][2] = "error";table[0][3] = "TS";table[0][4] = "error";table[0][5] = "error";
		table[1][0] = "error";table[1][1] = "+TS";table[1][2] = "error";table[1][3] = "error";table[1][4] = "0";table[1][5] = "0";
		table[2][0] = "FZ";table[2][1] = "error";table[2][2] = "error";table[2][3] = "FZ";table[2][4] = "error";table[2][5] = "error";
		table[3][0] = "error";table[3][1] = "0";table[3][2] = "*FZ";table[3][3] = "error";table[3][4] = "0";table[3][5] = "0";
		table[4][0] = "i";table[4][1] = "error";table[4][2] = "error";table[4][3] = "(E)";table[4][4] = "error";table[4][5] = "error";
	}
	
	/**
	 * 从分析表中获取字符串
	 * @param A
	 * @param a
	 * @return
	 */
	public String getString(char A,char a) {
		int i=0,j=0;
		switch(A) {		//匹配非终结符
		case 'E':	i = 0;break;
		case 'S':	i = 1;break;
		case 'T':	i = 2;break;
		case 'Z':	i = 3;break;
		case 'F':	i = 4;break;
		}
		switch(a) {		//匹配终结符
		case 'i':	j = 0;break;
		case '+':	j = 1;break;
		case '*':	j = 2;break;
		case '(':	j = 3;break;
		case ')':	j = 4;break;
		case '#':	j = 5;break;
		}
		return table[i][j];
	}
	
	/**
	 * 语法分析方法
	 */
	public void analyzer() {
		char N,n;
		ans.push('E');
		PrintHead();
		n = aim.pop();
		aim.push(n);
		Print('E',n);
		
		while(!ans.isEmpty()) {		//终结条件:分析栈为空
			char A = ans.pop();		//分析栈出栈
			char a = aim.pop();		//余留栈出栈
			
			if(A == a) {
				Print('$','$');
				continue;	//相同,双方都需要出栈,继续循环
			}
			aim.push(a);	//否则余留字符重新入栈
			String st = getString(A,a);		//查询分析表
			if(st.equals("error")) {		//为空,算法结束,匹配不成功
				Print(A,a);
				break;
			}
			else if(st.equals("0")) {
				Print(A,a);
				continue;		//0表示空,不需要入分析栈直接进行下一次循环
			}
			else {
				for(int i = st.length()-1;i>=0;i--) {		//逆序入栈
					ans.push(st.charAt(i));
				}
				Print(A,a);
			}
		}
		if(aim.isEmpty() && ans.isEmpty()) 	System.out.println("success");
		else System.out.println("failture");
	}
	
	/**
	 * 打印栈
	 * @param stack
	 */
	public void printStack(Stack<Character> stack) {
		for(Character s : stack)
			System.out.print(s);
		System.out.print("\t");
	}
	/**
	 * 打印分析过程
	 * @param A
	 * @param a
	 */
	public void Print(char A, char a) {
		if(ans.isEmpty()) return;
		System.out.print("步骤" + count++ +"\t");
		printStack(ans);
		printStack(aim);
		if(count==2) {
			System.out.println();
			return;
		}
		if(A == '$' && a == '$') {
			System.out.println();
			return;
		}
		else {
			if(A == '#') System.out.println("success");
			else {
				System.out.print("" + A + "->" + getString(A,a));
				System.out.println();
			}
		}
		
	}
	/**
	 * 打印头部
	 */
	public void PrintHead() {
		System.out.println("步骤\t"+"分析栈\t"+"余留栈\t"+"上个步骤所用产生式");
	}
	/**
	 * 测试方法
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		Analyzer ans = new Analyzer("./src/success.txt");//成功样例
		//Analyzer ans = new Analyzer("./src/failture.txt");//失败样例
		ans.readFile();	
		ans.analyse();	
		String str = ans.reStr();

		Analysis run = new Analysis(str);
		run.analyzer();
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GreenLeaves

C# 通过IEnumberable接口和IEnumerator接口实现自定义集合类型foreach功能

1、IEnumerator和IEnumerable的作用 其实IEnumerator和IEnumerable的作用很简单,就是让除数组和集合之外的类型也能支持f...

20710
来自专栏IT进修之路

原 分分钟看懂java用引用传递与值传递在

1925
来自专栏小工匠技术圈

【小工匠聊密码学】-- Base64算法

1453
来自专栏Java架构

Java 8简明教程

2385
来自专栏软件开发

JavaSE学习总结(八)—— 异常处理(Exception)

一、理解异常及异常处理的概念 异常就是在程序的运行过程中所发生的不正常的事件,它会中断正在运行的程序。 异常不是错误 程序中关键的位置有异常处理,提高程序的稳定...

2339
来自专栏函数式编程语言及工具

Scalaz(18)- Monad: ReaderWriterState-可以是一种简单的编程语言

  说道FP,我们马上会联想到Monad。我们说过Monad的代表函数flatMap可以把两个运算F[A],F[B]连续起来,这样就可以从程序的意义上形成一种串...

2037
来自专栏大内老A

从yield关键字看IEnumerable和Collection的区别

C#的yield关键字由来以久,如果我没有记错的话,应该是在C# 2.0中被引入的。相信大家此关键字的用法已经了然于胸,很多人也了解yield背后的“延迟赋值”...

2247
来自专栏每日一篇技术文章

Swift3.0 - 真的很简单

中文翻译文档 https://github.com/numbbbbb/the-swift-programming-language-in-chinese

1671
来自专栏机器学习入门

POJ 刷题系列:2739. Sum of Consecutive Prime Numbers

POJ 刷题系列:2739. Sum of Consecutive Prime Numbers 传送门:POJ 2739. Sum of Consecutive...

2137
来自专栏海说

17、Map接口及其常用子类(Hashtable、HashMap、WeakHashMap)

17、Map接口   Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个val...

2090

扫码关注云+社区

领取腾讯云代金券