On Mon, 08 Mar 2004 14:51:57 +0000, J French wrote:
> On Tue, 09 Mar 2004 01:35:52 +1100, Johnathan
> <zork_666@[EMAIL PROTECTED]
> wrote:
>
>>Hi,
>>
>>I'm looking for a BASIC grammar. Not necessarily the original BASIC
>>language - I'd be happy with a more modern dialect like QBasic. I can
>>infer a lot from Microsoft's QBASIC help file, but I'd really like to
>>get my hands on a LL(1) grammar. I could probably try to write my own,
>>but I don't know enough about compiler theory to do it. I'd like to
>>take a stab at writing a recursive descent parser. So bearing this in
>>mind, small is beautiful at this stage. :)
>
> And in what language would you write the recursive parser ?
If you've never tried it before, start with the smallest subset of BASIC
that you can write nontrivial programs in. I've never tried to analyze
it, but I suspect that QBasic's grammar isn't LL1. You can write a
recursive-descent parser in any language. It helps if the language
supports recursive functions, so you don't have to maintain your own
stack, but you could theoretically do it on a Turing machine, given a few
man-centuries of programming effort.
Seriously, it's been done in Pascal and QuickBasic. I worked through most
of Jack Crenshaw's "Let's Build A Compiler!" tutorial (see
http://compilers.iecc.com/crenshaw/),
translating his Pascal code into
QuickBasic as I went along. It wasn't that hard, given QB's Pascal - like
control structures and the trick of using strings to represent sets, so
that INSTR() can serve as the membership function. Crenshaw's "Tiny"
language is far smaller than any BASIC, but I wound up with a compiler
that actually worked (under real-mode DOS; *don't* try this in a
Windows environment).
Some caveats: Crenshaw never finished the series; it peters out after
introducing procedures. The target processor is the Motorola 68000 (a
much nicer architecture than the 8086; WHY did IBM have to bless Intel's
kluge?). One of his fans published an assembly-language runtime package
for the 8086, and I grabbed that and wrote my own code generator routines
to emit 8086 assembler code.
It would be a _lot_ of work to go from the end of Crenshaw's series to a
practical compiler, even in a DOS environment, but it's a good exercise.
Dogpile still shows the original link, along with some others for
"Crenshaw compiler tutorial."
|
