writing parser of a simple language

Question

I'm trying to design a simple language is similar to lips, schema. I have written its lexer(tokenizer). I can seperate into operators, identifiers etc. But I try now writing parser. For this, just one example is enough for me. Can someone give me an example in java code just for the example? Besides, everyone mentions of usage antlr. Can someone who attempts to use antlr show an example using my example in this question?

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

if my input is (+ 1 2), I hope to get as output

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

It is about LR(shift-reduce parsing). I have a simple example that I don't know whether I can modify the code or not for the parsing. But, a point catches my attention, stack usage is proper for LR algorithm. Doesn't it ?

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();
    }
}

The answer you seek is complicated to explain. Here are the basic principles. First, you need to write down (enumerate) all of the states that the parser will encounter. Then, you need to write a transition table that allows the parser to shift from one state to another as it encounters tokens and parses rules. You're on the right track about using a stack: each time you shift, you push a state onto that stack. When you reduce, you pop multiple states off the stack. (You're missing two critical arrays in your code that would make your parser work.) — scooter me fecit
– scooter me fecit, Commented Dec 23, 2015 at 17:37
You could also use a switch statement instead of a transition table (array). But you still need to know all of the parser states and how to transition between them (hint: the top of the stack is the parser's current state that you switch on.) — scooter me fecit
– scooter me fecit, Commented Dec 23, 2015 at 17:43
a simple language is similar to lips, schema. based on the tags, do you mean Lisp and Scheme? — Joshua Taylor
– Joshua Taylor, Commented Dec 23, 2015 at 18:45
You'll have an easier time of parsing if you don't specially case the arithmetic operators. Just have your grammar be: exp ::= id | number | (exp exp exp). Then, when you're evaluating expressions (after you've parsed them), you can complain semantic errors like a number in the function position. — Joshua Taylor
– Joshua Taylor, Commented Dec 23, 2015 at 18:47
@JoshuaTaylor: Shouldn't that be (oper exp exp), with an oper rule oper -> '+' | '-' | '*' | '/'? — scooter me fecit
– scooter me fecit, Commented Dec 23, 2015 at 19:38

ChristophE · Accepted Answer · 2015-12-23 09:28:40Z

1

If you want to avoid to write your own Parser you could use ANTLR

This is a parser generator that does all the work for you if you support it with a valid grammar.

If you still want to write it yourself you could still use ANTLR to see how they create their parser/lexers.

answered Dec 23, 2015 at 9:28

ChristophE

8731 gold badge10 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

askque Over a year ago

can you show an example according to my question using antlr?

Collectives™ on Stack Overflow

writing parser of a simple language

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related