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

Mr.E wrote:
> ... our fathers BASIC is different from todays BASIC.


Ah, I show my age again :-)


> I will study your example and make good use of it.
>
> Thank you very much for your input.


I'll readily admit I had much fun hacking it together, though I hope
you realize that this is not production ready code and the style is
aweful (to make it fit).


Our dear moderator be willing, I've made it a tad more realistic and
finish the 2nd half: a JIT binary code compiler (works on x86 Linux in
32-bit mode).


Do feel free to ask questions.


Enjoy,
Tommy


#include <ctype.h>
#include <stdio.h>


char *s;
int lookahead;
int intValue;
char *symbolValue;
unsigned symbolLength;


void nexttoken(void) {
                  while (isspace(*s)) ++s;
                  if (isdigit(*s)) {
                                  intValue = 0;
                                  lookahead = '0';
                                  while (isdigit(*s)) intValue = 10*intValue + *s++ - '0';
                  } else if (isalpha(*s)) {
                                  lookahead = 'a';
                                  symbolValue = s;
                                  while (isalnum(*s)) ++s;
                                  symbolLength = symbolValue - s;
                  } else lookahead = *s++; }
void match(unsigned expect) {
                  if (lookahead != expect) lookahead = -1;
                  nexttoken(); }


typedef struct node *ast_t;
struct node {
                  int kind;
                  ast_t l, r;
                  int intValue;
} nodes[9999];
int next = 0;
ast_t mk(int kind, ast_t l, ast_t r, int k) {
                  nodes[next].kind = kind;
                  nodes[next].l = l;
                  nodes[next].r = r;
                  nodes[next].intValue = k;
                  return &nodes[next++]; }


ast_t pExp(void);
ast_t pFactor(void) {
                  ast_t v;
                  switch (lookahead) {
                  case '(': match('('); v = pExp(); match(')'); break;
                  case 'a': v = mk('a', 0,0, symbolValue[0]); match('a'); break;
                  case '0': v = mk('0', 0,0, intValue); match('0'); break; }
                  return v;}
ast_t pTerm(void) {
                  ast_t v = pFactor();
                  while (lookahead == '*') match('*'),v=mk('*',v,pFactor(),0);
                  return v;}
ast_t pExp(void) {
                  ast_t v = pTerm();
                  while (lookahead == '+') match('+'),v=mk('+',v,pTerm(),0);
                  return v;}


void prast(ast_t t) {
                  if (t->kind == '0') printf("%d", t->intValue);
                  else if (t->kind == 'a') printf("%c", t->intValue);
                  else { printf("(");
                  prast(t->l); printf("%c", t->kind); prast(t->r); printf(")");}}


char code[9999], *cp = code;
int env[256] = { ['x'] = 2, ['y'] = 3 };


void gen(ast_t t) {
                  if (t->kind == '0') {
                                  *cp++ = 0x50; // push %eax
                                  *cp++ = 0xB8; // movl $<intValue>, %eax
                                  *(int *)cp = t->intValue;
                                  cp += 4;
                  } else if (t->kind == 'a') {
                                  *cp++ = 0x50; // push %eax
                                  *cp++ = 0xA1; // mov <env[..]>, %eax
                                  *(int **)cp = &env[t->intValue];
                                  cp += 4;
                  } else {
                                  gen(t->r);
                                  gen(t->l);
                                  *cp++ = 0x5B; // pop %ebx
                                  if (t->kind == '+') *cp++=1, *cp++=0xD8; // add %ebx,%eax
                                  else *cp++=0xF, *cp++=0xAF, *cp++=0xC3; // imul %ebx, %eax
}}


int main(int argc, char **argv) {
                  ast_t res;
                  s = "1 + x*3 + 4*(5 + y)";
                  if (argc > 1) s = argv[1];
                  nexttoken();
                  res = pExp();
                  if (lookahead != 0){printf("Syntax error at:%s\n", s); return -1;}
                  prast(res);
                  printf("\n");


                  gen(res);
                  *cp++=0x5B; // pop dummy
                  *cp++=0xC3; // ret
                  printf("%d\n", ((int(*)()) code)());
                  return 0;
}

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