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

Tommy Thorn <tommy.thorn@gmail.com>
10 Sep 2006 23:44:00 -0400

          From comp.compilers

Related articles
[4 earlier articles]
Re: Generating a simple hand-coded like recursive descent parser pjb@informatimago.com (Pascal Bourguignon) (2006-09-10)
Re: Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-10)
Re: Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-10)
Re: Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-10)
Re: Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-10)
Re: Generating a simple hand-coded like recursive descent parser pjb@informatimago.com (Pascal Bourguignon) (2006-09-10)
Re: Generating a simple hand-coded like recursive descent parser tommy.thorn@gmail.com (Tommy Thorn) (2006-09-10)
Re: Generating a simple hand-coded like recursive descent parser ArarghMail609@Arargh.com (2006-09-11)
Re: Generating a simple hand-coded like recursive descent parser DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-09-11)
Re: Generating a simple hand-coded like recursive descent parser mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-09-11)
Re: Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-11)
Re: Generating a simple hand-coded like recursive descent parser ArarghMail609@Arargh.com (2006-09-11)
Re: Generating a simple hand-coded like recursive descent parser mr.waverlye@verizon.net (Mr.E) (2006-09-11)
[41 later articles]
| List of all articles for this month |

From: Tommy Thorn <tommy.thorn@gmail.com>
Newsgroups: comp.compilers
Date: 10 Sep 2006 23:44:00 -0400
Organization: Sonic.Net
References: 06-09-02906-09-035 06-09-039
Keywords: Basic, parse

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;}


Post a followup to this message

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