A few questions about making an interpreter

MTK358 · 01-20-2011, 03:11 PM

The first is about implementing function calls. The way I currently have it is that functions are called with a C++ std::vector of nodes as the parameters. How would I turn a comma-seperated list of expressions into a C++ vector in the grammar?

Second, how do you implement left-associative operators in a parser that does not allow left recursion?

And third, what would be the best internal representation of integers? A C++ int seems simplest, but limited. Using GMP seems more versatile, but I'm afraid it might seriously slow down the interpreter compared to C++ ints.

johnsfine · 01-20-2011, 04:43 PM

Quote:

Originally Posted by MTK358

How would I turn a comma-seperated list of expressions into a C++ vector in the grammar?

Second, how do you implement left-associative operators in a parser that does not allow left recursion?

If you are asking YACC questions, your thread title should say you are asking YACC questions, not questions about "making an interpreter".

I took the stupid formal grammar portion of a computer science course far too long ago to remember much beyond how unrealistic it all was. So maybe there are answers to your questions within the realm of grammar that don't assume the specific tool (YACC or some specific other). But even if so, I suspect it would be too abstract an answer to be useful.

When you just code a parser from scratch (no YACC, nor ANTLR nor whatever), none of those issues are ever problems. Having used YACC and ANTLR (and other tools) and coded from scratch, each multiple times, my own experience is that coding from scratch feels tedious and wasteful as you are doing it (lots of doing almost the same thing over and over) but none of it is ever hard and debugging the result (if that ever is necessary) is trivial.

VS. using a tool starts out quick and easy (after some delay for reading about the tool) but then one detail after another that ought to be trivial turns out to be hard. Then you need a lot of debugging and the debugging is a nightmare.

The best feature of YACC is that it isn't too hard to use for a good language, but becomes a nightmare for a bad language. That is a very positive feature in academic use where you typically invent the language and the parser together. If a language feature is hard to parse, must be a stupid language feature, so change the language spec, rather than struggle with the parser.

Outside of academia, YACC is garbage. In the real world the language is typically spec'ed by an idiot and that spec is forced onto the programmer (too often me) responsible for the parser with no path to push back against bad language design.

I assume you are inventing your own language. So I still don't like YACC, but I won't say you are absolutely wrong to choose it.

Just if you want to ask a YACC question, explicitly ask a YACC question. (and wait for someone other than me to answer it).

Quote:

And third, what would be the best internal representation of integers? A C++ int seems simplest, but limited. Using GMP seems more versatile, but I'm afraid it might seriously slow down the interpreter compared to C++ ints.

Don't ask that!

How do we know the design goals and tradeoffs of your project? Take some responsibility for your design.

That said, there is a serious amount of overhead to all but the most perfect interpreter designs. The higher the overhead is, the less noticeable the real work will be. In a compiled language unnecessarily using GMP when int or long long would have been enough would be outrageously inefficient. Percentage wise, the same choice in an interpreter isn't as important.

MTK358 · 01-20-2011, 07:14 PM

I was using leg, which generates a recursive descent parser.

And the basic structure of a function call would be like this:

Code:

Expr OPAREN (Expr (COMMA Expr)*)? CPAREN

The problem is how do I convert the parenthesized list of Exprs into a C++ vector? Note that the first item is an expression, not an identifier. This is because this language has first-class functions.

MTK358 · 01-21-2011, 03:45 PM

I have a partially completed leg grammar now:

Code:

%{
#include <string>
#define YYSTYPE union {Node *node; std::string &str; std::vector<Node*> &vector}
%}

Program = - b:Block !. { b.node->eval(); } ;

Block = l:StmtList { $$ = new ScopeNode(l.node); } ;

Stmt = e:Expr EOL  { $$ = e.node; } ;

StmtList = s:Stmt l:StmtList { $$ = new StmtListNode(s.node, l.node); }
         | s:Stmt            { $$ = s; }
         ;

Expr = n:NAME                                    { $$ = new VariableNode(n.str); }
     | e:Expr DOT n:NAME                         { $$ = new MemberAccessNode(e.node, n.str); }
     | n:NAME ASSIGN e:Expr                      { $$ = new AssignmentNode(n.str, e.node); }
     | e:Expr OPAREN l:CommaSeparatedList CPAREN { $$ = new FuncCallNode(e.node, l.vector); }
     | x:INTEGER                                 { $$ = x; }
     | OPAREN x:Expr CPAREN                      { $$ = x; }
     ;

CommaSeparatedList = expr:Expr COMMA list:CommaSeparatedList { list.vector.insert(0, expr.node); $$ = list; }
                   | expr:Expr { $$ = std::vector<Node*>(expr.node); }
                   ;

INTEGER = <([0-9]+ | 0b[01]+ | 0o[0-7]+ | 0x[0-9a-fA-F]+)([Ee][0-9]+)?> - { $$ = new IntegerNode(yytext); } ;

NAME    = <[A-Za-z_][A-Za-z_0-9]*> - { $$ = std::string(yytext); } ;

IF        = 'if'    - ;
ELSEIF    = 'ei'    - ;
ELSE      = 'else'  - ;
ENDIF     = 'endif' - ;
WHILE     = 'while' - ;
ENDWHILE  = 'loop'  - ;
DO        = 'do'    - ;
FUNC      = 'func'  - ;
ASSIGN    = '='     - ;
OPAREN    = '('     - ;
CPAREN    = ')'     - ;
DOT       = '.'     - ;
COMMA     = ','     - ;

EOL = '\n' | ';'    - ;

- = [ \t]* ;

But it shows an error:

Code:

$ leg parser.leg -o parser.cpp
parser.leg:28: syntax error before text "%{"

I have no idea what it could be.