Я строю простой грамматический парсер с регулярным выражением. Это работает, но теперь я хочу добавить абстрактное синтаксическое дерево. Но я все еще не понимаю, как его настроить. я включил парсер. Парсер получает строку и токенизирует ее с помощью лексера.
Токены включают значение и тип. Любая идея, как настроить узлы для построения AST?
public class Parser {
lexer lex;
Hashtable<String, Integer> data = new Hashtable<String, Integer>();
public Parser( String str){
ArrayList<Token> token = new ArrayList<Token>();
String[] strpatt = { "[0-9]*\\.[0-9]+", //0
"[a-zA-Z_][a-zA-Z0-9_]*",//1
"[0-9]+",//2
"\\+",//3
"\\-",//4
"\\*",//5
"\\/",//6
"\\=",// 7
"\\)",// 8
"\\("//9
};
lex = new lexer(strpatt, "[\\ \t\r\n]+");
lex.set_data(str);
}
public int peek() {
//System.out.println(lex.peek().type);
return lex.peek().type;
}
public boolean peek( String[] regex) {
return lex.peek(regex);
}
public void set_data( String s) {
lex.set_data(s);
}
public Token scan() {
return lex.scan();
}
public int goal() {
int ret = 0;
while(peek() != -1) {
ret = expr();
}
return ret;
}
public int expr() {
int ret = factor();
while(peek(new String[]{"\\+", "\\-"}) ) {
if (peek(new String[]{"\\+"})) {
scan();
ret = ret + factor();
}
else {
scan();
ret = ret - factor();
}
}
return ret;
}
public int factor(){
int ret = term();
while(peek(new String[]{"\\*", "\\/"})) {
if (peek(new String[]{"\\/"})) {
scan();
ret = ret / term();
}
else {
scan();
ret = ret * term();
}
}
return ret;
}
public int term() {
if (peek(new String[] { "[0-9]+" })) {
return Integer.parseInt(scan().value);
} else if (peek(new String[] { "\\(" })) {
scan();
int var = expr();
scan();
return var;
} else if (peek(new String[] { "[a-zA-Z_][a-zA-Z0-9_]*" })) {
Token name = scan();
if (peek(new String[] { "\\=" })) {
scan();
int var2 = expr();
data.put(name.value, var2);
return var2;
}
return data.get(name.value);
}
else {
throw new RuntimeException("smh");
}
}
public static void main( String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String str = "B = 3*2+2";
Parser pars = new Parser(str);
//System.out.println(pars.lex.peek());
int var = pars.goal();
while (true) {
String input = in.readLine();
pars.set_data(input);
System.out.println(pars.goal());
}
}
}
Хорошо, вот моя вторая попытка построить AST. Я построил класс ASTNodes. ASTNodes расширяется другими узлами ASTExpr, et c.
/*
ASTExpr(ASTExpr left, int operator, ASTExpr right)
*/
public ASTNodes.ASTExpr expr() {
ASTNodes.ASTExpr ret = new ASTNodes.ASTExpr();
ret.left = factor();
// int ret = factor();
while(peek(new String[]{"\\+", "\\-"}) ) {
if (peek(new String[]{"\\+"})) {
scan();
// ret = ret + factor();
ret.operator = 3; // 3 = +
ret.right = factor();
}
else {
scan();
// ret = ret - factor();
ret.operator = 4; // 4 = -
ret.right = factor();
}
}
return ret;
}
// ASTFactor(ASTFactor left, int operator, ASTFactor right)
public ASTNodes.ASTFactor factor(){
ASTNodes.ASTFactor ret = new ASTNodes.ASTFactor();
ret.left = term();
// int ret = term();
while(peek(new String[]{"\\*", "\\/"})) {
if (peek(new String[]{"\\/"})) {
scan();
// ret = ret / term();
ret.operator = 6;
ret.right = term();
}
else {
scan();
// ret = ret * term();
ret.operator = 5;
ret.right = term();
}
}
return ret;
}
// ASTTerm(int left, ASTExpr assign, ASTExpr right)
public ASTNodes.ASTTerm term() {
ASTNodes.ASTTerm ret = new ASTNodes.ASTTerm();
if (peek(new String[] { "[0-9]+" })) {
ret.left = Integer.parseInt(scan().value);
return ret;
} else if (peek(new String[] { "\\(" })) {
scan();
ASTNodes.ASTExpr var = expr();
scan();
ret.right = var;
return ret;
} else if (peek(new String[] { "[a-zA-Z_][a-zA-Z0-9_]*" })) {
Token name = scan();
if (peek(new String[] { "\\=" })) {
scan();
ASTNodes.ASTExpr var2 = expr();
data.put(name.value, var2);
ret.assign = data.get(name.value);
}
return ret;
}
else {
throw new RuntimeException("bla");
}
}
public static void main( String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// Parser pars = new Parser(String str);
String str = "B = 3*2+2";
Parser pars = new Parser(str);
//System.out.println(pars.lex.peek());
ASTNodes.ASTGoal var = pars.goal();
while (true) {
String input = in.readLine();
pars.set_data(input);
System.out.println(pars.goal());
}
}
}