Home » forums » LtU Forum

Parsing and syntax reordering

I been doing some programming language design and I ran into something that I am sure as a name, and I thought I would ask too see if anybody could tell me what it is.

I found that the two syntaxes have the same effect (at least the way that I think of languages):

def x <-> x
defun x y z <-> x(y) z
set x 4 <-> x = 4
add x 4 <-> x += 4

ie. the first defines a variable x in the symbol table, the second defines a function x with an arguement y and a body z, etc.

Now the question is: what is the name of a parsing and reordering scheme for transforming the form on the right to the form on the left? I'm not sure if I am using the correct terminology, but basically I'm looking for the algorithm that could be used to convert tokens (or a parse tree maybe?) from the form on the right to the form on the left.

Any help appreciated.

--
kruhft
kruhft.blogspot.com

By kruhft at 2005-10-31 19:19 | LtU Forum | previous forum topic | next forum topic | other blogs | 5870 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Term Rewriting Systems? Refactoring?

Could it be one of Term Rewriting Systems, or maybe Refactoring?

By shapr at Mon, 2005-10-31 23:41 | login or register to post comments

Linearity

I think this is the right kind of intuition to pursue, and the nice property that makes the rewrites simple is that the rewrites involved are linear.

By Charles Stewart at Tue, 2005-11-01 17:40 | login or register to post comments

Might be a winner

It seems that Term Rewrite Systems looks to be it. I'm a bit more of an engineer than a PLT so some of the terms are a bit unknown to me. I'll read up on TRS and see what I can find.

--
kruhft

By kruhft at Tue, 2005-11-01 18:12 | login or register to post comments

Looks like a fairly trivial

syntactic transfomation - perhaps I'm missing something, but I'm not sure it's really interesting enough to be worthy of a special name?

I guess, on the left, you're using standard prefix-style syntax for your functions/operators/language constructs (def, defun, add, set), whereas on the right they're being expressed with a more custom infix-style syntax _(_)_, +=, =. The transformation could be expressed recursively over the syntax tree quite easily. And to get the syntax tree you'd just use standard parsing techniques (I presume that isn't the problem?)

So, not really sure what you're asking - perhaps I should leave it to those who might...

By Matthew Willson at Tue, 2005-11-01 08:49 | login or register to post comments

The examples you give suggest

The examples you give suggest you're talking about a language in which programs can be parsed according to two concrete syntax grammars yielding just the same abstract syntax tree since the differences will mainly be in the terminal symbols of the grammar.

If you have the right tools you could parse a program in syntax1 to an abstract syntax tree and pretty print that AST to syntax2. So you need a parser for syntax1 and a pretty printer for syntax2.

Since you don't say much about what language/tools you're talking about, I don't know if this really is an answer to your question. Otherwise, shapr's answer might be what you were looking for.

By Martijn Vermaat at Tue, 2005-11-01 12:17 | login or register to post comments