package CompilerGenerator.lex; /**
* Created by natalia on 05.04.14.
*/
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.io.*;
import java.util.ArrayList;
class Reader {
private File openedFile_;
private BufferedReader reader_;
private ArrayList<String> readedText_;
public Reader(String path) {
openedFile_ = new File(path);
try {
reader_ = new BufferedReader(new InputStreamReader(new FileInputStream(openedFile_), "UTF-8"));
} catch (UnsupportedEncodingException exc) {
System.out.println(" UTF-8 exception. " + exc.getMessage());
} catch (FileNotFoundException exc) {
System.out.println("File Not Found. " + exc.getMessage());
}
readedText_ = new ArrayList<String>();
}
public ArrayList<String> Read() {
String currentString;
try {
while((currentString = reader_.readLine()) != null) {
readedText_.add(currentString);
}
} catch (IOException exc) {
System.out.println("IOException while reading file. " + exc.getMessage());
}
return new ArrayList<String>(readedText_);
}
}
class Parse {
private String axiom;
private List<String> nTerm;
private List<String> Term;
HashMap<String, List<String[]>> lRule_rRule;// = new HashMap<String, List<String>>();
public Parse() {
nTerm = new LinkedList<String>();
Term = new LinkedList<String>();
lRule_rRule = new HashMap<String, List<String[]>>();
String s = "bla";
//if(s.equals("bla"))
// System.out.println("yeee ! start with bla");
//else
// System.out.println("oop");
}
public void addNTerm(String Nterms) {
Nterms = Nterms.substring(0, Nterms.length()-1);
String [] terms = Nterms.split(" ") ;
for(int i = 1; i < terms.length; i++) {
nTerm.add(terms[i]);
// System.out.println("nterms: " + terms[i]);
}
//nTerm.add(Nterm);
}
public void addTerm(String T) {
T = T.substring(0, T.length()-1);
String [] terms = T.split(" ") ;
for(int i = 1; i < terms.length; i++) {
Term.add(terms[i].split("\"")[1]);
System.out.println("terms: " + terms[i].split("\"")[1]);
}
//System.out.println("!!! " + F("*hhh"));
}
public void addAxiom(String a) {
a = a.substring(0,a.length()-1);
String toAdd = a.split(" ")[1];
axiom = toAdd;
nTerm.add(toAdd);
System.out.println("axiom: " + axiom);
}
public void addRule(String lr, String rr) {
String []rRules = rr.split("\n");
System.out.println("rules: " + lr + " - " + rr);
lRule_rRule.put(lr, new LinkedList<String[]>());
for(int i = 0; i < rRules.length; i++) {
String [] s = rRules[i].split(" ");
String [] news = new String[s.length-1];
for(int j = 1; j < s.length; j++) {
if(s[j].charAt(0) == '\"')
s[j] = s[j].split("\"")[1];
news[j - 1] = s[j];
}
//System.out.println(" !"+s[j]+"! ");
lRule_rRule.get(lr).add(news);
//System.out.println("part_of_rule: " + news[0]);
}
}
//----------creating--FIRST--&--FOLLOW------------------------------------
private List<String> F(String s) {
if(s.length() < 1)
return null;
List<String> result = new LinkedList<String>();
boolean notTerm = true;
for(String t: Term)
if (s.startsWith(t)) {
result.add(t);
notTerm = false;
}
if(notTerm) {
if(s.equals("$EPS"))
result.add("$EPS");
else {
String nt = "";
for(String t: nTerm) {
String f = s.substring(0, t.length());
if(t.equals(f))
nt = f;
}
if(FIRST.get(nt) != null) {
if (!FIRST.get(nt).contains("$EPS") || s.equals(nt)) {
return FIRST.get(nt);
} else {
List<String> copy = new LinkedList<String>();
for(String l: FIRST.get(nt))
copy.add(l);
copy.remove("$EPS");
return Union(copy, F(s.substring(nt.length(), s.length())));
}
} else
return null;
}
}
return result;
}
HashMap<String, List<String>> FIRST = new HashMap<String, List<String>>();
public void createFirst() {
System.out.println("StartFirst");
for(String nt: nTerm)
FIRST.put(nt, new LinkedList<String>());
boolean isChanging = true;
while (isChanging) {
isChanging = false;
for (String lR : nTerm)
for (String[] rR : lRule_rRule.get(lR)) {
String Fu = "";
for (String a : rR)
Fu += a;
List<String> cF = F(Fu);
//System.out.println("FU: " + cF + "for: " + Fu);
if (cF != null)
if (!cF.isEmpty()) {
//isChanging = true;
List<String> oldF = FIRST.get(lR);
List<String> newF = Union(oldF, cF);
for(String l: newF) {
if(!oldF.contains(l)) {
FIRST.put(lR, newF);
isChanging = true;
}
}
}
}
}
for(String l: nTerm)
System.out.println("nt: "+l + " f: " + FIRST.get(l));
}
private List<String> Union(List<String> a, List<String> b) {
List<String> union = new LinkedList<String>();
if(a != null)
for(String l: a) {
union.add(l);
}
if(b != null)
for(String l: b) {
if(!union.contains(l))
union.add(l);
}
return union;
}
private boolean ifContainsNewElements(List<String> before, List<String> after) {
for(String a: after)
if(!before.contains(a))
return true;
return false;
}
HashMap<String, List<String>> FOLLOW = new HashMap<String, List<String>>();
public void countFollow() {
for(String nt: nTerm)
FOLLOW.put(nt, new LinkedList<String>());
FOLLOW.get(axiom).add("$");
for(String nt: nTerm) {
for(String []rR: lRule_rRule.get(nt)) {
for (int i = 0; i < rR.length; i++) {
if(nTerm.contains(rR[i])) {
String tail = "";
for(int j = i + 1; j < rR.length; j++)
tail += rR[j];
List<String> oldF = FOLLOW.get(rR[i]);
List<String> f = new LinkedList<String>();
List<String> ff = F(tail);
if(ff != null)
f.addAll(F(tail));
if(f != null)
if(f.contains("$EPS"))
f.remove("$EPS");
FOLLOW.put(rR[i], Union(oldF, f));//???
}
}
}
}
boolean isChanged = true;
while(isChanged) {
isChanged = false;
for (String X: nTerm) {
for (String []oneRule: lRule_rRule.get(X)){
for(int i = 0; i < oneRule.length; i++) {
if(nTerm.contains(oneRule[i])) {//contains Y
String Y = oneRule[i];
boolean add = false;
if(i + 1 == oneRule.length) {
add = true;
} else {
String tail = "";
for(int j = i + 1; j < oneRule.length; j++)
tail += oneRule[j];
List<String> f = F(tail);//new LinkedList<String>();
if(f.contains("$EPS"))
add = true;
}
if(add && FOLLOW.get(X) != null)
if(!FOLLOW.get(X).isEmpty()) {
List<String> uToCompare = Union(FOLLOW.get(X), FOLLOW.get(Y));
if(ifContainsNewElements(FOLLOW.get(Y), uToCompare)) {
FOLLOW.put(Y, uToCompare);
isChanged = true;
}
}
}
}
}
}
}
for(String l: nTerm)
System.out.println("folnt: "+l + " f: " + FOLLOW.get(l));
}
//-----------creating--TABLE---------------------------
String[][][] delta;
public void createTable() {
//int nsize = nTerm.size(), tsize = Term.size();
delta = new String[nTerm.size()][Term.size()+1][];
for(String nt: nTerm) {
for(String t: Term)
delta[nTerm.indexOf(nt)][Term.indexOf(t)] = new String[]{"ERROR"};
delta[nTerm.indexOf(nt)][Term.size()] = new String[]{"ERROR"};
}
for(String nt: nTerm)
for(String[] r: lRule_rRule.get(nt)) {
String rule = "";
for(int i = 0; i < r.length; i++)
rule += r[i];
for(String e: F(rule)) {
if(!e.equals("$EPS")) {
System.out.println("e=" + e+ " i=" + Term.indexOf(e));
if(!delta[nTerm.indexOf(nt)][Term.indexOf(e)][0].equals("ERROR"))
System.out.println("error: not LL1");
else
delta[nTerm.indexOf(nt)][Term.indexOf(e)] = r;
} else {
for(String b: FOLLOW.get(nt)) {
int tind = 0;
if(Term.indexOf(b) == -1)
tind = Term.size();
else
tind = Term.indexOf(b);
if(!delta[nTerm.indexOf(nt)][tind][0].equals("ERROR"))
System.out.println("error: not LL1");
else
delta[nTerm.indexOf(nt)][tind] = r;
}
}
}
}
}
String [][][] tryM = new String[][][] {
new String[][] { //nTerm
new String[]{"a", "b", "c",}, //rule, used for term
new String[]{"c"},
},
new String[][] {
new String[]{"ff"},
new String[]{"kk"},
},
};
//List<String> tryL = new LinkedList<String>(){"a", "b"};
public void printTableDeclaration() {
String termDec = "\t\tTerm = new LinkedList<String>();\n";
for(String t: Term)
termDec += ("\t\tTerm.add(\"" + t + "\");\n");
termDec += ("\t\tTerm.add(\"$\");\n");
String nTermDec = "\t\tnTerm = new LinkedList<String>();\n";
for(String t: nTerm)
nTermDec += ("\t\tnTerm.add(\"" + t + "\");\n");
String axiomDec = "\t\taxiom = \"" + axiom + "\";\n";
String initFunc = "\tstatic void init() {\n";
initFunc += axiomDec+ "\n" +termDec + "\n" + nTermDec + "\n\t}\n";
String tableDec = "";
tableDec += "\tstatic String [][][] delta = new String[][][] {\n";
for(String nt: nTerm) {
tableDec += "\t\tnew String[][] {\n";
for(String t: Term) {
tableDec += "\t\t\tnew String[] {";
for(String d: delta[nTerm.indexOf(nt)][Term.indexOf(t)])
tableDec += ("\"" + d + "\", ");
tableDec += "},\n";
}
tableDec += "\t\t},\n";
}
tableDec += ("\n" + "\t};");
System.out.println(initFunc+"\n"+tableDec);
}
public void print() {
System.out.println("terms: ");
for(String l: Term)
System.out.println("-"+l+"-");
System.out.println("nterms: ");
for(String l: nTerm)
System.out.println("-"+l+"-");
System.out.println("rules: ");
for(String l: lRule_rRule.keySet()) {
System.out.println("="+l+"=");
for(String []e: lRule_rRule.get(l)) {
System.out.println("[");
for (String a: e)
System.out.println("-"+a+"-");
System.out.println("]");
}
}
}
}
public class lex {
static private int strNum = 0;
static private Parse parse = new Parse();
private void print(String s, int pos, int mend) {
// System.out.println("IDENT ("+strNum+","+pos+")-("+strNum+","+(pos+mend)+"): "+s);
}
private static void findLex2(String s, Pattern p) {
int pos = 0;
Matcher m;
while(s.length() != 0){
m = p.matcher(s);
if(m.find()) {
if (m.group(1) != null) {
// System.out.println("RULE II ("+strNum+","+pos+")-("+strNum+","+
// (pos+m.end())+"): "+m.group(1));
parse.addRule(m.group(2), m.group(3));
}
/*for(int i = 0; i < 5; i++) {
if(m.group(i) != null)
System.out.println(i+ " g: " + m.group(i));
}*/
pos += m.end();
s = s.substring(m.end());
//System.out.println(s);
//for(int i = 1; i< 7;i++)
// System.out.println("g: " +m.group(i));
} else {
pos++;
if(s.charAt(0) != ' ') {
System.out.println("ERROR at (" + strNum + "," + pos + ")");
}
s = s.substring(1);
}
}
strNum++;
}
private static void findLex(String s, Pattern p) {
int pos = 0;
Matcher m;
while(s.length() != 0){
m = p.matcher(s);
if(m.find()) {
if (m.group(1) != null) {
// System.out.println("AXIOM ("+strNum+","+pos+")-("+strNum+","+
// (pos+m.end())+"): "+m.group(1));
parse.addAxiom(m.group(1));
} else if(m.group(5) != null) {
// System.out.println("TERM ("+strNum+","+pos+")-("+strNum+","+
// (pos+m.end())+"): "+m.group(5));
parse.addTerm(m.group(5));
} else if(m.group(3) != null) {
// System.out.println("NTERM ("+strNum+","+pos+")-("+strNum+","+
// (pos+m.end())+"): "+m.group(3));
parse.addNTerm(m.group(3));
} else {
// System.out.println("RULES-to-be-continued ("+strNum+","+pos+")-("+strNum+","+
// (pos+m.end())+"): "+m.group(7));
findLex2(m.group(7), Pattern.compile("\\$RULE (([A-Z]\\'{0,1}) =(([( [A-Z]\\'{0,1})( \"[a-z]\"| \"\\*\"| \"\\+\"| \"\\(\"| \"\\)\")]+\\n| \\$EPS\\n)+))"));
}
pos += m.end();
s = s.substring(m.end());
//System.out.println(s);
//for(int i = 1; i< 7;i++)
// System.out.println("g: " +m.group(i));
} else {
pos++;
if(s.charAt(0) != ' ') {
System.out.println("ERROR at (" + strNum + "," + pos + ")");
}
s = s.substring(1);
}
}
strNum++;
}
public static void splitLexems(String rules) {
}
public static void main(String args[])
{
// Текст для сопоставления
String text = "$AXIOM E\n" +
"$TERM";
// Регулярные выражения
String ident = "^\\p{L}.{0,8}\\p{L}";//"^[A-Za-z]+|^[(][0-9]+[)]";+";//
//String number = //"^0|^[1-9][0-9]*";
//String oper = //"^[(][)]|^[:][=]|^[:]";
String strlit = "^\'([^\\\\]|\\\\n|\\\\\'|\\\\[0-9A-Fa-f]{4,4}|\\p{L})*\'";//|[[\\][n]]*|[[\\][0-9A-Fa-f]{,4}]*|[.]*][\']\'";
String keyword = "^z|^forward|^for";
String pattern = "("+keyword+")|("+strlit+")|("+ident+")";
String nt = "[A-Z]\\'{0,1}";
String t = "\"[a-z]\"| \"\\*\"| \"\\+\"| \"\\(\"| \"\\)\"";
String axiom = "\\$AXIOM ([A-Z]\\\'{0,1})\\n";
String nterm = "\\$NTERM( [A-Z]\\'{0,1})+\\n";
String term = "\\$TERM( \"[a-z]\"| \"\\*\"| \"\\+\"| \"\\(\"| \"\\)\")+\\n";
String rule = "\\$RULE ([A-Z]\\'{0,1} =([( [A-Z]\\'{0,1})( \"[a-z]\"| \"\\*\"| \"\\+\"| \"\\(\"| \"\\)\")]+\\n| \\$EPS\\n)+)";
pattern = "("+axiom+")|("+nterm+")|("+term+")|(("+rule+")+)";
//String
// Компиляция регулярного выражения
Pattern p = Pattern.compile(pattern);
Reader reader = new Reader("test.txt");
ArrayList<String> mas = reader.Read();
//System.out.println(reader1.Read());
// Сопоставление текста с регулярным выражением
String program = "";
for(String s: mas)
program += (s+'\n');
findLex(program, p);
parse.print();
parse.createFirst();
parse.countFollow();
parse.createTable();
parse.printTableDeclaration();
for (String s : mas) {
//System.out.println();
//findLex(s+'\n', p);
}
}
}