import com.sun.org.apache.xpath.internal.operations.Or;
import java.io.*;
import java.util.*;
public class SFYXFXF {
private Scanner scanner = null;
private BufferedReader reader = null;
//文法
private List<String> wf = new ArrayList<String>();
//非终结符
private List<String> N = new ArrayList<String>();
//终结符
private List<String> V = new ArrayList<String>();
//first集和
private Map<String,List<String>> firstVt = new HashMap<String, List<String>>();
//follow集和
private Map<String,List<String>> lastVt = new HashMap<String, List<String>>();
//等待计算完成后添加的集和（辅助计算follow集合）
private Map<String,String> waitAdd = new HashMap<String, String>();
public SFYXFXF() throws FileNotFoundException {
scanner = new Scanner(System.in);
reader = new BufferedReader(
new InputStreamReader(new FileInputStream(new File("F:\Workplace\IDEA_Workplace\SchoolProect\软件构造实验5\wf.txt")))
);
}
public void getWf() throws IOException {
System.out.println("所有的文法:");
String temp;
while (!(temp = reader.readLine()).equals("#")){
wf.add(temp);
System.out.println(temp);
}
String s = wf.get(0);
String[] strings = s.split("->");
wf.add(0, strings[0] + "`->#" + strings[0] + "#");
}
public void getN() throws IOException {
System.out.println("所有的非终结符:");
String temp;
while (!(temp = reader.readLine()).equals("#")){
N.add(temp);
System.out.println(temp);
}
}
public void getV() throws IOException {
System.out.println("所有的终结符:");
String temp;
while (!(temp = reader.readLine()).equals("#")){
V.add(temp);
System.out.println(temp);
}
}
public void getFirstVt(){
String wfStr;
//转置一下，从后往前推
Collections.reverse(wf);
for (int i = 0; i < wf.size(); i++) {
List<String> wfFirst = new ArrayList<String>();
wfStr = wf.get(i);
//前后分割
String[] strings = wfStr.split("->");
//文法产生的式子
String[] split = strings[1].split("\|");
//计算first集合
for (int j = 0; j < split.length; j++) {
String firstChar = String.valueOf(split[j].charAt(0));
String secondChar = null;
if (split[j].length()>1){
secondChar = String.valueOf(split[j].charAt(1));
}
if (N.contains(firstChar)){
if (secondChar != null && V.contains(secondChar)){
wfFirst.add(secondChar);
}else {
wfFirst.addAll(firstVt.get(firstChar));
}
}else {
wfFirst.add(firstChar);
}
}
firstVt.put(strings[0],wfFirst);
}
Collections.reverse(wf);
}
//获取follow集和
public void getLastVt(){
String wfStr;
//转置一下，从后往前推
Collections.reverse(wf);
for (int i = 0; i < wf.size(); i++) {
List<String> wfLastVt = new ArrayList<String>();
wfStr = wf.get(i);
//前后分割
String[] strings = wfStr.split("->");
//文法产生的式子
String[] split = strings[1].split("\|");
//计算first集合
for (int j = 0; j < split.length; j++) {
String lastChar = String.valueOf(split[j].charAt(split[j].length()-1));
String lastTwoChar = null;
if (split[j].length()>1){
lastTwoChar = String.valueOf(split[j].charAt(split[j].length()-2));
}
if (N.contains(lastChar)){
if (lastTwoChar != null && V.contains(lastTwoChar)){
wfLastVt.add(lastTwoChar);
}else {
wfLastVt.addAll(lastVt.get(lastChar));
}
}else {
wfLastVt.add(lastChar);
}
}
lastVt.put(strings[0],wfLastVt);
}
Collections.reverse(wf);
}
//判断该文法是否有空
private boolean haveK(String c) {
boolean haveK = false;
List<String> strings = firstVt.get(c);
if (strings.contains("^")){
haveK = true;
}
return haveK;
}
//显示firstVt集
public void showFirst(){
System.out.println("FirstVt集合:");
Set<String> strings = firstVt.keySet();
for (String key : strings) {
System.out.println(key + ":" + firstVt.get(key));
}
}
//显示lastVt集
public void showFollow(){
System.out.println("LastVt集合:");
Set<String> strings = lastVt.keySet();
for (String key : strings) {
System.out.println(key + ":" + lastVt.get(key));
}
}
//构建预测分析表
public String[][] buildTable(){
String[][] table = new String[V.size()+1][V.size()+1];
for (int i = 0; i < (V.size() + 1); i++) {
for (int j = 0; j < (V.size() + 1); j++) {
table[i][j] = "";
}
}
//将#加入到非终结符中
V.add("#");
for (int i = 0; i < wf.size(); i++) {
//当前的文法
String wfStr = wf.get(i);
String[] split = wfStr.split("->");
//当前的非终结符
String NStr = split[0];
//当前的产生式
String tuidaoStr = split[1];
//分割多个产生式
String[] tuidao = tuidaoStr.split("\|");
for (int j = 0; j < tuidao.length; j++) {
//遍历每个产生式
String s = tuidao[j];
for (int k = 0; k < s.length()-1; k++) {
String s1 = String.valueOf(s.charAt(k));
String s2 = String.valueOf(s.charAt(k + 1));
//前终结符，后非终结符
if (V.contains(s1) && N.contains(s2)){
int s1Index = getCharIndex(s1);
List<String> firstList = firstVt.get(s2);
for (String s3 : firstList) {
int charIndex = getCharIndex(s3);
table[s1Index][charIndex] = "<";
}
}else if (N.contains(s1) && V.contains(s2)){
//前非终结符，后终结符
int s2Index = getCharIndex(s2);
List<String> lastList = lastVt.get(s1);
for (String s3 : lastList) {
int index = getCharIndex(s3);
table[index][s2Index] = ">";
}
}
try {
//前终结，中非，后终结
String s3 = String.valueOf(s.charAt(k + 2));
if (V.contains(s1) && N.contains(s2) && V.contains(s3)){
int index = getCharIndex(s3);
int s1Index = getCharIndex(s1);
table[s1Index][index] = "=";
}
}catch (Exception e){
}
}
}
}
System.out.println("预测分析表：");
System.out.print(" ");
for (int i = 0; i < V.size(); i++) {
System.out.print(V.get(i) + " ");
}
System.out.println();
for (int i = 0; i < V.size(); i++) {
System.out.printf(V.get(i)+" ");
for (int j = 0; j < V.size(); j++) {
System.out.print(table[i][j] + " ");
}
System.out.println();
}
System.out.println();
return table;
}
//获取终结符在预测表中的位置
public int getCharIndex(String c){
return V.indexOf(c);
}
public void fx(String[][] table, String s) {
Stack<String> stack = new Stack<String>();
List<String> stackStr = new ArrayList<String>();
stack.push("#");
stackStr.add("#");
String sy = s;
System.out.println("符号栈 输入符号串 动作");
while (!sy.equals("")){
String firstChar = String.valueOf(sy.charAt(0));
//顶部非终结符号
List<String> tempStack = new ArrayList<String>();
String peek = stack.pop();
tempStack.add(peek);
stackStr.remove(stackStr.size()-1);
while (N.contains(peek)){
peek = stack.pop();
stackStr.remove(stackStr.size()-1);
tempStack.add(peek);
}
//获取比较的结果(栈顶元素和第一个字符比)
int charIndex = getCharIndex(firstChar);
int peekIndex = getCharIndex(peek);
String bj = table[peekIndex][charIndex];
if (bj.equals("<") || bj.equals("=")){
//再将取出来的符号放回栈中
Collections.reverse(tempStack);
for (String s1 : tempStack) {
stack.push(s1);
stackStr.add(s1);
}
System.out.println(stackStr.toString()
+ " " + sy + " "
+ peek + bj + firstChar + ",移进");
//小于则移进
stack.push(firstChar);
stackStr.add(firstChar);
sy = deleteFirstChar(sy);
}else if (bj.equals(">")){
//大于则规约
List<String> realStackStr = new ArrayList<String>();
realStackStr.addAll(stackStr);
Collections.reverse(tempStack);
realStackStr.addAll(tempStack);
Collections.reverse(tempStack);
System.out.println(realStackStr.toString() + " " +
sy + " " + peek + bj + firstChar + ",规约");
String pop = stack.pop();
stackStr.remove(stackStr.size()-1);
while (N.contains(pop) || table[getCharIndex(pop)][peekIndex].equals("=")){
pop = stack.pop();
stackStr.remove(stackStr.size()-1);
}
stack.push(pop);
stack.push(N.get(0));
stackStr.add(pop);
stackStr.add(N.get(0));
}else {
System.out.println("分析出错!");
System.exit(-1);
}
}
System.out.println("分析成功!");
}
private String deleteFirstChar(String str){
String[] strings = str.split("||");
String newStr = "";
for (int i = 1; i < strings.length; i++) {
newStr += strings[i];
}
return newStr;
}
public void useYcfxf() throws IOException {
getWf();
getN();
getV();
getFirstVt();
showFirst();
getLastVt();
showFollow();
String[][] table = buildTable();
System.out.println("请输入要分析的符号串:");
fx(table,scanner.next());
}
}
测试代码
import java.io.IOException;
public class TestY {
public static void main(String[] args) throws IOException {
SFYXFXF SFYXFXF = new SFYXFXF();
SFYXFXF.useYcfxf();
}
}
文法
E->E+T|T
T->T*P|P
P->(E)|i
#
E
T
P
#
+
*
(
)
i
#