1

I'm trying to create a tiny interpreter for TI-BASIC syntax.

This is a snippet of TI-BASIC I'm trying to interpret

A->(2+(3*3))

I've tokenized the code above into this sequence of tokens:

Token{type=VARIABLE, content='A'}
Token{type=ASSIGN, content='null'}
Token{type=L_PAREN, content='null'}
Token{type=NUM, content='2'}
Token{type=ADD, content='null'}
Token{type=L_PAREN, content='null'}
Token{type=NUM, content='3'}
Token{type=MULT, content='null'}
Token{type=NUM, content='3'}
Token{type=R_PAREN, content='null'}
Token{type=R_PAREN, content='null'}
Token{type=EOS, content='null'} (end of statement)
Token{type=EOF, content='null'} (end of file)

If I'm not mistaken, I think the next step from here is to represent these tokens as a tree of statements (Abstract Syntax Tree?)

 Assignment (->)
    / \
   /   \
  A    Add
       /\
      /  \
     2  Multiply
           /\
          /  \
         3    3

I'm wondering how I should go about creating this tree, or if that's even the correct thing to do. Thanks!

August
  • 12,410
  • 3
  • 35
  • 51
  • Related: http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769 – Bart Kiers Jul 09 '14 at 19:27

1 Answers1

-2

The simple answer is that you need to write a parser for TI-Basic. You've already written your lexer (lexical analyzer) and now you need to write your syntax analyzer.

There are many ways of doing this, but the Wikipedia page on parsers is a good place to start: examples of parsers.

Jashaszun
  • 9,207
  • 3
  • 29
  • 57
  • @August If this is the answer, then please mark it as such. – Jashaszun Jul 09 '14 at 19:17
  • He needs more than a parser. He needs a parser that builds an AST. You get that by building a parser, and weaving AST fragment building operations into actions attached to matching on rules. See YACC/Bison/JavaCC/Antlr for various ways to do this. – Ira Baxter Aug 01 '14 at 08:36
  • @IraBaxter The most common output of parsers is ASTs. It is not a huge step from writing a parser to simply *verify* that code is syntactically correct to writing a parser that verifies *and* creates an AST. – Jashaszun Aug 01 '14 at 13:24
  • @jashaszun: "Parsing" is a funny term. It can mean as little as checking sytax (that's the narrow definition) and as much as "read the source code and determine the meaning of identifiers, how data flows from one point to another, ..." (that's a rare definition). But when building a "parser", one has to implement the narrow definition by necessity no matter where one is going. You can code a syntax checker by hand, or use as parser generator (the latter supporting the narrow definition well but not other aspects). ... – Ira Baxter Aug 01 '14 at 14:44
  • 1
    ... Having gotten past this step, *somebody* must build AST construction machinery. The parser generator typically doesn't do it (our DMS Software Reengineering Toolkit was one of the first to automate AST building from just the grammar, and the ANTLR guys have recently followed suit, but no others to my knowledge). That means OP must consider that *he* has to do it. You claim (here, hidden in the comments) that it isn't a huge step. But it is step that takes nonzero energy and some additional education on his part beyond just "parsing". Your answer didn't tell him that. – Ira Baxter Aug 01 '14 at 14:47
  • @IraBaxter I've written multiple parsers myself and, from experience, can say that it was natural to generate an AST. From what I remember (it was a while ago), it would have almost been harder for me *not* to generate an AST than to generate it. – Jashaszun Aug 01 '14 at 15:34
  • 1
    @IraBaxter Also, if you want to write your own answer, than please do so! Anybody in the future that looks at this question could benefit if you do so. – Jashaszun Aug 01 '14 at 15:34