Re: Generating a simple hand-coded like recursive descent parser

Mr.E wrote:
> From what I've read, many compilers are grown and extended by using
> their own language, I like that idea.


Using the right language will teach you concepts that makes doing this
so much easier. At the very minimum you need product (~ "struct") and
sum (~ "union") types. In (classic) BASIC you'd have to simulate those
making it a very unnatural and messy implementation.


Consider starting with a much simpler example, say an expression
_interpreter_ to handle this language


      e := e + e | e * e | ( e ) | k | v


(where * binds stronger than +, k is an integer constant, and v a
variable of some value).


If you manage this in BASIC, then next make a compiler for it.


This exercise will likely teach you much that will be useful for a full
compiler for BASIC.




(building ASTs)
> Oh darn, an algorithm would give a standard to work with and compare
> to.


There isn't any "algorithm" to be had. Building AST nodes is trivial, or
if it isn't, you can bet writing a compiler won't be.




Tommy
PS: Here's a slightly compressed solution in C for the first half.


#include <ctype.h>
#include <stdio.h>
char *s = "1+x*3+4*(5+y)";
int pExp(void), env[256] = { ['x'] = 2, ['y'] = 3 };
int pFactor(void) {
                  int v = 0;
                  if (*s == '(')
                                  ++s, v = pExp(), ++s;
                  else if (isdigit(*s))
                                  while (isdigit(*s))
                                                  v = 10*v + *s++ - '0';
                  else if (isalpha(*s))
                                  v = env[(unsigned)*s++];
                  return v;}
int pTerm(void) {
                  int v = pFactor();
                  while (*s == '*') ++s, v *= pFactor();
                  return v;}
int pExp(void) {
                  int v = pTerm();
                  while (*s == '+') ++s, v += pTerm();
                  return v;}
int main(int argc, char **argv) {printf("%d\n", pExp()); return 0;}

Return to the comp.compilers page.
Search the comp.compilers archives again.