About Me

I am a computer programmer. I do programming professionally and for a laugh.

Technical stuff on programming, java, DSLs, etc...

Tuesday, 30 March 2010

Another DSL Framework - tutorial 1

Lets start with a simple arithmetic language;

An arithmetic language, a fancy name for a simple calculator, is the simplest DSL to define. The task in hand is to take an arbitrary text of numbers and operators, parse the text and calculate the result watching the precedence of *|/ over +|-. Sounds simple, it is not. If you keep reading, the last bit of the tutorial shows how to define a bit of the Lisp language. But you get the idea, with a Language Framework you can define any language.

E -> E + T | E - T | T
T -> T * n | T / n | n

An expression is either a number or (*|/|+|-) of 2 expressions.
We define 2 different kinds of expressions (E and T) to enforce precedence of *|/ over +|-
This language requires 5 terminals. The number terminal and 4 operation terminals.
We define a terminal in java regexp; so a digit is \\p{Digit}+ and 4 operation terminals are "\\+", "\\-", "\\*", "\\/"

The semantic is the simplest possible; a digit is the value of the identifier and an any of +|-|*|/ is the corresponding operation.

The way you define the semantic is an inlined semantic class where you over-ride the method evaluate. By the time your evaluate method is called, the children parameters are already calculated, so for addition all you have to do is get the first and the third child and add them up. The second child is the + sign. For terminals like digit, you should get the lexeme and convert it to a type meaningful for your language. A BigInteger in our case.

The way you run the calculator is as below:-

            assertEquals(new BigInteger("3"), language.getTargetLanguage().evaluate("2 * 3 - 5 - 7 / 7 * 3 + 2 * 2 + 2 / 2"));

The complete listing of the calculator language is as below;


            BNFLanguage language = new BNFLanguage(); 
            language.addLanguageTerminal("digit", "\\p{Digit}+", new TerminalSemantic() {
                  public Object evaluate(String lexeme){
                        return new BigInteger(lexeme);
                  }
            });
            language.addLanguageTerminal("add", "\\+");
            language.addLanguageTerminal("sub", "\\-");
            language.addLanguageTerminal("mult", "\\*");
            language.addLanguageTerminal("div", "\\/");
            language.addLanguageTerminal(new WhiteSpace());
            language.addProduction("E -> E add T ", new Semantic(){
                  @Override
                  public Object evaluate(List<Object>childEvals) {
                        return ((BigInteger) childEvals.get(0)).add((BigInteger) childEvals.get(2));
                  }
            });
            language.addProduction("E -> E sub T ", new Semantic(){
                  @Override
                  public Object evaluate(List<Object>childEvals) {
                        return ((BigInteger)childEvals.get(0)).subtract((BigInteger) childEvals.get(2));
                  }
            });
            language.addProduction("E -> T ");
            language.addProduction("T -> T mult digit ", new Semantic(){
                  @Override
                  public Object evaluate(List<Object>childEvals) {
                        return ((BigInteger)childEvals.get(0)).multiply((BigInteger) childEvals.get(2));
                  }
            });
            language.addProduction("T -> T div digit ", new Semantic(){
                  @Override
                  public Object evaluate(List<Object>childEvals) {
                        return ((BigInteger)childEvals.get(0)).divide((BigInteger) childEvals.get(2));
                  }
            });
            language.addProduction("T -> digit");
            language.resolveRecursion();

No comments:

Post a Comment

Followers