Has anyone implemented BASIC in Python?

[Andrea Griffini]

On Sun, 22 Aug 2004 22:30:55 -0400, Leif K-Brooks
<eurleif at ecritters.biz> wrote:

>Andrea Griffini wrote:
>> I've no idea why you think that an unstructured language would
>> be a good starting point.
>
>There's no stack to deal with, and generally less possible expressions 
>to worry about. You're probably right about doing an expression parser 
>first, though; I will. Thanks for the advice.

I resorted to use two explicit stacks; one for FORs and one
for GOSUBs. There is no stack for expression evaluation because
python stack is used indirectly instead (expressions are evaluated
directly from the parse tree). Both of the explicit stacks
could have been dropped by considering a structured approach
with functions instead of the concept of just GOSUB-RETURN.
GOSUB-RETURN requires an explicit stack because it's a runtime
concept; not a parse-time concept. So it's not only uglier to
use... it's also harder to write.

Writing an interpreter that executes directly a parse tree of
a structured language program is IMO *easier* than writing an
interpreter for an unstructured language program.
That's why I think that starting from BASIC is not a good idea.

Things are different if we're talking about the VM approach,
but that's IMO something that should come later.

>> Anyway I found the idea of a BASIC interpreter in python intriguing,
>> so I wrote one this weekend. I wrote it for my egoistic fun, so
>> I'm not sure if it would be useful for you (or anyone else).
>
>Whoa, that's your idea of a weekend project? I'm speechless.

Writing parsers, interpreters and compilers is a lot simpler than
many do think. Of course the evil is in the details and getting
something that comes even just close to (just for example ;-) )
python is a *LOT* harder.

I have "The dragon" book, and I saw that the part dedicated
to recursive descent parsers is incredibly small.
No wonder that writing compilers and interpreters is considered
such a difficult task... IMO the shift-reduce approach is just
*too* abstract (at least too abstract for *ME*, that is ;-) ).

Note also that working without any requirement (i.e. creating
requirements on the fly) and without any timeline (i.e. doing
whatever you think it would be nice to do) and without any
(pointy-haired) boss or (annoying) user is a lot easier.

I actually even think that the percentage of time I spent coding
the tic-tac-toe example in BASIC is not so small...

>I really appreciate the example, and I'll try my best to understand it. 
>Did you use a parser generator or anything like that, or is it purely 
>hand-coded?

I never use yacc/lex, I just prefer hand-coding the parsers.

I never felt as pressing the problem of the speed of parsing
(I've read that this is one main superiority of shift-reduce
parsers). An hand-coded recursive descent parser is in my
opinion very easy to write... and very easy to maintain.
In the years I just found myself using tables for binary
operators to avoid repeating annoying code for just different
precedence levels or grouping; so I normally end up have just
one function for parsing "terms" (literals, varables, function
calls, parenthesized expressions and unary operators calls)
and one for parsing "expressions" that handles all binary
operators and that accepts the precedence level as a parameter.
Statements normally get their separate handcoded parsing
function (and this implies a lot of freedom about the syntax,
including making parsing dependent on the *meaning* of a symbol).
Also it's very easy to provide meaningful error messages.

For starting I would suggest however coding a separate
function at least for every precedence level (i.e. one for
mul/div, one for add/sub etc.... with lower precedence
ones that call higher precedence ones and with the highest
"term" one that calls the lowest "expr" for example for
parenthesized subexpressions).

Andrea