编写简单语言的语法分析器

Question

我正在尝试设计一种类似于lips、schema的简单语言。我已经写了它的lexer（tokenizer）。我可以分为运算符、标识符等。但我现在尝试编写解析器。对此，我只需要一个例子就足够了。有人能给我一个java代码的例子吗

• –EXP -> EXPI | EXPB
• –EXPI -> (+ EXPI EXPI) | (- EXPI EXPI) | (* EXPI EXPI) | (/ EXPI EXPI) | Id | IntegerValue | (Id EXPLIST)
• –EXPB -> (and EXPB EXPB)

如果我的输入是(+ 1 2)，我希望得到作为输出

 - START-> INPUT
 - -> EXP
 - -> EXPI
 - -> (+ EXPI EXPI)
 - -> (+ EXPI Id)
 - -> (+ Id Id)

这是关于LR（移位减少解析）。我有一个简单的例子，我不知道是否可以修改代码进行解析。但是，有一点引起了我的注意，栈的使用对于LR算法来说是合适的。不是吗？

import java.util.Stack;
public class SmallLisp {
    Stack<String> stack;
    public SmallLisp(){
        String[] tokens = new String[]{"(","+","2","(","+","3","2",")",")",};
        stack = new Stack<String>();
        for (int i=0;i<tokens.length;i++){
            stack.push(tokens[i]);
            if(tokens[i].equals(")")) Interprete();
        }
    }
    public void Interprete(){
        String tok;
        Stack<String> callStack = new Stack<String>();
        tok = stack.pop(); /* This is the ) character */
        while(!(tok=stack.pop()).equals("(")){
            callStack.push(tok);
        }
        Call(callStack);
    }
    public void Call(Stack<String> callStack){
        String func = callStack.pop(); /* This is the operator or function */
        if(func.equals("+")) {
            double result = Plus(callStack);
            stack.push(String.valueOf(result));
        }
        //if(func.equals("-")) Minus(callStack);
    }
    public double Plus(Stack<String> callStack){
        double a = Double.parseDouble(callStack.pop());
        double b = Double.parseDouble(callStack.pop());
        System.out.println("Answer is "+(a+b));
        return(a+b);
    }
    public static void main(String[] args) {
        new SmallLisp();
    }
}

Answer 1

如果你想避免编写自己的Parser，你可以使用ANTLR

这是一个解析器生成器，如果您使用有效的语法支持它，它将为您完成所有工作。

如果你仍然想自己写，你仍然可以使用ANTLR来查看他们是如何创建解析器/lexer的。