Writing an interpreter

Who am I?

Roses red
rust_prank

How do they work!?

  • programming languages?
  • DSLs (Domain Specific Lang.)?
  • linters, prettyprinters?
  • interpreters/evals?
  • trolling recruiters? (see RockstarLang)

1. Parsing

options, in preferred order:
  1. use existing library
  2. use regex
  3. use parser generator (e.g. ANTLR/Fastparse)
  4. make your own parser
  5. quit your job

Y no regexes?

  • coz they wack (for complex structures)
  • can't handle nested syntax, e.g. properly nested/matched parentheses (()()(()())),
    nested HTML/BBcode tags, nested blocks etc...

ANTLR

To the rescue!


  1. specify lex rules
  2. specify parse rules (or steal from Github)
  3. generate Lexer, Parser, Visitor (java, js, c#...)
  4. implement your logic in a custom Visitor
  5. drink coffee, celebrate

ANTLR grammar


                        grammar Calculator;

                        /* parse rules -> AST */
                        expr
                            : NUMBER ('*'|'/') NUMBER
                            | NUMBER ('+'|'-') NUMBER
                            | NUMBER
                        ;

                        /* lex rules -> tokens */
                        NUMBER
                            : [1-9][0-9]* ( '.' [0-9]+ )?
                        ;

                        WS : [ \t]+ -> skip;
                    
E.g for "2 + 3":
  • tokens: [NUMBER(2), OP(+), NUMBER(3)]
  • AST: [Sum(Literal(2), Literal(3))]

Test your grammar

Test grammar

Generate lexer, parser, visitor...

gen code

2. Interpret, do something?

interpret meaning
visitor

                        var is = new FileInputStream(str);
                        var input = new ANTLRInputStream(is);
                        var lexer = new LabeledExprLexer(input);
                        var tokens = new CommonTokenStream(lexer);
                        var parser = new LabeledExprParser(tokens);
                        var tree = parser.prog(); // parse

                        var eval = new EvalVisitor();
                        eval.visit(tree);
                    
Yes, this is Java. It has vars now...

That's all folks!


See also:


Questions?