🔒 Locked

Syntax tree flattening

Started by ToohrVyk Sep 1, 2006 at 9:50 AM 8 replies 1.1k views

Original Post

Sep 1, 2006 at 9:50 AM

I have a small-ish problem when converting a small script language to C++. Most operations are transparent (function calls, operators, etc...) so they can be converted simply by copying them over. My problem occurs when I manipulate variables. I want to convert code as follows:


a + b                    return a+b;

let a = b                T a(b);
in c(a)                  return c(a);

let a =                  U b(c);
  let b = c              V a(d(b));
  in d(b)                return e(a);
in e(a)

How can I unroll the syntax tree on the left into the sequence of variable initializations on the right? I have no problem with getting the type of any expression, or with generating unique variable names, what I'm stuck on is the actual unrolling of the statements. And I'm pretty sure it can be described easily.

deffer

Sep 1, 2006 at 11:10 AM

How complicated can it get?

let a =  let b =    if (c < 2)      let d = (c - 1)      in f1(d)    else      let d = (c - 2)      in f2(d)  in f3(b)in f4(a)

Such mess is possible?

ToohrVyk

Sep 1, 2006 at 12:14 PM

Quote:
Original post by deffer
How complicated can it get?
let a =  let b =    if (c < 2)      let d = (c - 1)      in f1(d)    else      let d = (c - 2)      in f2(d)  in f3(b)in f4(a)
Such mess is possible?

Yes, it is.

deffer

Sep 1, 2006 at 12:37 PM

Hm. Sounds tough.
While I'm thinking about it... are you familiar with those:
The implementation of anonymous methods in C# and its consequences (part 1)
And part 2
Might give you some ideas.

deffer

Sep 1, 2006 at 1:47 PM

Quote:
Original post by ToohrVyk
U b(c);
V a(d(b));
return e(a);

Does it have to be through copy-construction?
How about: default constructor + assignment operator?

V a{  U b;  {    b = c;  };  a = d(b);};return e(a);

Is this version acceptable?

ToohrVyk

Sep 1, 2006 at 2:21 PM

It would work, since my objects are boxed (so I manipulate pointers).

deffer

Sep 1, 2006 at 2:55 PM

Then I'd see it work like that:

struct expr_let : public expr_t{  type_t t;  var_t  v;  expr_t *eVar;  expr_t *eIn;  virtual std::string GenCode(const std::string & retCode) const; // "someVar = " or "return "};// Generated code:t->GenName() v->GenName() ";""{"  eVar->GenCode(v->GenName() + " = ") ";""};"eIn->GenCode(retCode) ";"

ToohrVyk

Sep 1, 2006 at 3:09 PM

Excellent! Thank you for your help.

KulSeran

Sep 2, 2006 at 1:31 AM

ToohrVyk, just wondering. I'm taking a compilers class this semester. And that code looks a lot like
TIGER. Are you making a croscompiler for a compiler class? Even if your answer is no
you should look into flex and bison if you aren't using that already. You'd end up with a few more
statments than that in C, but it would do what you want.

something like
let a = U b(c);

let b = c V a(d(b));

in d(b)

in e(a)

would easily be translated to
Q c;
U b(c);
V d(b);
W a(d);
return e(a);

ToohrVyk

Sep 2, 2006 at 2:25 AM

Quote:
Original post by KulSeran
ToohrVyk, just wondering. I'm taking a compilers class this semester. And that code looks a lot like
TIGER. Are you making a croscompiler for a compiler class? Even if your answer is no
you should look into flex and bison if you aren't using that already.

The answer is no, I'm not making a crosscompiler for a compiler class, although I did take a compilers class two years ago. The language is designed to look like ML (which is the case for TIGER, too). I'm currently using ocamlyacc for parsing the tree and determining types and other similar details.

Quote:

Would easily be translated to
Q c;
U b(c);
V d(b);
W a(d);
return e(a);

There's a small problem here: d is not a variable, it's a function. I think you meant W a(d(b));

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.