java实现消除文法的左递归

页面导航:首页 > 软件编程 > Java编程 > java实现消除文法的左递归

java实现消除文法的左递归

来源: 作者: 时间:2016-01-21 09:39 【

package com.siwanghu.syntaxanalyzer.bean;public class Grammar { private String left; private String right; private int id; private static int ID = 0; ...
package com.siwanghu.syntaxanalyzer.bean;

public class Grammar {
    private String left;
    private String right;
    private int id;
    private static int ID = 0;

    public Grammar() {
        super();
        id = ID++;
    }

    public Grammar(String left, String right) {
        super();
        this.left = left;
        this.right = right;
        id = ID++;
    }

    public String getLeft() {
        return left;
    }

    public void setLeft(String left) {
        this.left = left.replace(" ", "");
    }

    public String getRight() {
        return right;
    }

    public void setRight(String right) {
        this.right = right.replace(" ", "");
    }

    public int getId() {
        return id;
    }
     
     

    @Override
    public String toString() {
        return "Grammar [left=" + left + ", right=" + right + "]";
    }

}

 
 
package com.siwanghu.syntaxanalyzer.algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

import com.siwanghu.syntaxanalyzer.bean.Grammar;

public class Production {
    private List productions = new LinkedList();       //产生式
    private List symbols = new ArrayList();        //初始产生式非终结符
    private List nonTerminatingSymbol = new ArrayList(); //LL(1)文法非终结符
    private List terminatingSymbol = new ArrayList();    //LL(1)文法终结符

    public Production(List productions) {
        super();
        this.productions = productions;
        symbolProductions();
    }

    public List getProductions() {
        return productions;
    }

    public List getSymbols() {
        return symbols;
    }
     
    public List getNonTerminatingSymbol(){
        return nonTerminatingSymbol;
    }
     
    public List getTerminatingSymbol(){
        return terminatingSymbol;
    }
     
    public void removeLeftRecursion() {
        for (int i = 0; i < symbols.size(); i++) {
            for (int j = 0; j < i; j++) {
                iterativeReplacement(symbols.get(i), symbols.get(j));
            }
            removeLeftRecursion(symbols.get(i));
        }
        no_or_is_terminatingSymbol();
    }

    private void symbolProductions() {
        if (productions.size() != 0) {
            for (int i = 0; i < productions.size(); i++) {
                if (!((ArrayList) symbols).contains(productions
                        .get(i).getLeft().charAt(0))) {
                    symbols.add(productions.get(i).getLeft().charAt(0));
                }
            }
        }
    }

    private void no_or_is_terminatingSymbol() {
        for (int i = 0; i < productions.size(); i++) {
            if (!((ArrayList) nonTerminatingSymbol)
                    .contains(productions.get(i).getLeft())) {
                nonTerminatingSymbol.add(productions.get(i).getLeft());
            }
            if (productions.get(i).getLeft() == productions.get(i).getLeft()
                    .charAt(0)
                    + "'") {
                nonTerminatingSymbol.add(productions.get(i).getLeft());
            }
        }
        for (int i = 0; i < productions.size(); i++) {
            String temp = productions.get(i).getRight();
            temp = temp.replace("epsilon", "#");
            for (int j = 0; j < nonTerminatingSymbol.size(); j++) {
                temp = temp.replaceAll(nonTerminatingSymbol.get(j), "");
            }
            temp = temp.replaceAll("\\\\|", "");
            temp = temp.replaceAll("'", "");
            char[] chars = temp.toCharArray();
            for (int k = 0; k < chars.length; k++) {
                if (chars[k] == '#') {
                    if (!terminatingSymbol.contains("epsilon")) {
                        terminatingSymbol.add("epsilon");
                    }
                } else {
                    if (!terminatingSymbol.contains(String.valueOf(chars[k]))) {
                        terminatingSymbol.add(String.valueOf(chars[k]));
                    }
                }
            }
        }
    }

    private void iterativeReplacement(Character left, Character right) {
        ListIterator listIterator = productions.listIterator();
        while (listIterator.hasNext()) {
            String inRight = "";
            Grammar grammar = listIterator.next();
            if (grammar.getLeft().equals(left.toString())) {
                boolean isReplacement = false;
                String[] rights = grammar.getRight().split("\\\\|");
                for (int i = 0; i < rights.length; i++) {
                    if (rights[i].startsWith(right.toString())) {
                        isReplacement = true;
                    }
                }
                if (isReplacement) {
                    ListIterator _listIterator = productions
                            .listIterator();
                    while (_listIterator.hasNext()) {
                        Grammar _grammar = _listIterator.next();
                        if (_grammar.getLeft().equals(right.toString())) {
                            String[] _rights = _grammar.getRight().split("\\\\|");
                            for (int i = 0; i < rights.length; i++) {
                                boolean isCheck = false;
                                if (rights[i].startsWith(right.toString())) {
                                    isCheck = true;
                                    for (int j = 0; j < _rights.length; j++) {
                                        String temp = rights[i];
                                        inRight += (temp.replaceFirst(
                                                right.toString(), _rights[j]) + "|");
                                    }
                                }
                                if (!isCheck) {
                                    inRight += (rights[i] + "|");
                                }
                            }
                        }
                    }
                    if (inRight.length() != 0) {
                        listIterator.remove();
                        listIterator.add(new Grammar(left.toString(), inRight
                                .substring(0, inRight.length() - 1)));
                    }
                }
            }
        }
    }

    private void removeLeftRecursion(Character left) {
        ListIterator listIterator = productions.listIterator();
        while (listIterator.hasNext()) {
            Grammar grammar = listIterator.next();
            if (grammar.getLeft().equals(left.toString())) {
                String[] rights = grammar.getRight().split("\\\\|");
                boolean isLeftRecursion = false;
                for (int i = 0; i < rights.length; i++) {
                    if (rights[i].startsWith(left.toString())) {
                        isLeftRecursion = true;
                    }
                }
                if (isLeftRecursion) {
                    listIterator.remove();
                    String oneRight = "", twoRight = "";
                    for (int i = 0; i < rights.length; i++) {
                        if (!rights[i].startsWith(left.toString())) {
                            oneRight += (rights[i]
                                    .concat(left.toString() + "'") + "|");
                        } else {
                            twoRight += (rights[i].replaceFirst(
                                    left.toString(), "").concat(
                                    left.toString() + "'") + "|");
                        }
                    }
                    listIterator.add(new Grammar(left.toString(), oneRight
                            .substring(0, oneRight.length() - 1)));
                    listIterator.add(new Grammar(left.toString() + "'",
                            twoRight.concat("epsilon")));
                }
            }
        }
    }

    @Override
    public String toString() {
        String temp = "非终结符: ";
        for (int i = 0; i < nonTerminatingSymbol.size(); i++) {
            temp += nonTerminatingSymbol.get(i) + " ";
        }
        temp+="  共计:"+nonTerminatingSymbol.size();
        temp += "\\n终结符: ";
        for (int i = 0; i < terminatingSymbol.size(); i++) {
            temp += terminatingSymbol.get(i) + "  ";
        }
        temp+="  共计:"+terminatingSymbol.size();
        temp += "\\n消除左递归后的文法:\\n";
        for (int i = 0; i < productions.size(); i++) {
            temp += (productions.get(i) + "\\n");
        }
        return temp;
    }
}

 

 
 
 
package com.siwanghu.syntaxanalyzer.test;

import java.util.LinkedList;
import java.util.List;

import com.siwanghu.syntaxanalyzer.algorithm.Production;
import com.siwanghu.syntaxanalyzer.bean.Grammar;

public class Test {
    public static void main(String[] args) {
        System.out.println("The Productions of G");
        Grammar g1 = new Grammar("S", "Qc|c");
        Grammar g2 = new Grammar("Q", "Rb|b");
        Grammar g3 = new Grammar("R", "Sa|a");
        List g_productions = new LinkedList();
        g_productions.add(g3);
        g_productions.add(g2);
        g_productions.add(g1);
        Production g_production = new Production(g_productions);
        g_production.removeLeftRecursion();
        System.out.print(g_production);
        System.out.println("end G\\n");

        System.out.println("The Productions of H");
        Grammar h1 = new Grammar("E", "E+T|T");
        Grammar h2 = new Grammar("T", "T*F|F");
        Grammar h3 = new Grammar("F", "(E)|i");
        List h_productions = new LinkedList();
        h_productions.add(h1);
        h_productions.add(h2);
        h_productions.add(h3);
        Production h_production = new Production(h_productions);
        h_production.removeLeftRecursion();
        System.out.print(h_production);
        System.out.println("end H");

    }

 

}
 
Tags:

相关文章

    文章评论

    最 近 更 新
    热 点 排 行
    Js与CSS工具
    代码转换工具
    
    <