www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Compile time lex + parse + semantic = 300 lines of code

reply Don Clugston <dac nospam.com.au> writes:
I've finally released the compile-time parser I mentioned in my conference 
presentation.

http://www.dsource.org/projects/mathextra/browser/trunk/blade/SyntaxTree.d

contains one publicly usable function:

char [] syntaxtreeof(char [] expression).

When mixed in, this lexes and parses the expression, determines precedence and 
associativity, creating an object of type AbstractSyntaxTree, which contains a 
standardized 'placeholder expression' (eg "A+=(B*C)")
and a symbol table for the variables, constants and functions A,B,C,...
The symbol table includes the type and value for each symbol.
All aliases and compile-time constants are resolved and converted to a standard 
form.
All symbols must be reachable from the scope where syntaxtreeof() is mixed into.

The created AbstractSyntaxTree is a compile-time constant, so it can be used
for 
  further compile-time operations and code generation.

Works for almost any expression (templates, functions, strings, slicing, struct 
literals,...); the biggest omission is relational operators.
Less than 300 lines of code in D1.020.
Probably could simplified using __traits in D2.0.
Enjoy.


Return type:
-----
struct Symbol {
     char [] type; // the name of the type, as text
     char [] value; // the value, as text. Either the symbol name, or a literal
}

// The result of semantic analysis of the original expression
struct AbstractSyntaxTree {
     char [] expression; // syntax tree in Placeholder format, eg A+=(B*C)
     Symbol[] symbolTable; // The types and values of A,B,C,...
}
------

Example:
-----
import SyntaxTree;

const foo = "abc";
int bar(real x, char [] s) { return 0; }
struct Duck{};
Duck duck;

AbstractSyntaxTree a = mixin(syntaxtreeof(`foo*   bar(2.18_3242e+45L, "xyz") in 
duck`));
Sep 11 2007
next sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Don Clugston wrote:
 I've finally released the compile-time parser I mentioned in my
 conference presentation.
 
 http://www.dsource.org/projects/mathextra/browser/trunk/blade/SyntaxTree.d
 
 contains one publicly usable function:
 
 char [] syntaxtreeof(char [] expression).
 
 When mixed in, this lexes and parses the expression, determines
 precedence and associativity, creating an object of type
 AbstractSyntaxTree, which contains a standardized 'placeholder
 expression' (eg "A+=(B*C)")
 and a symbol table for the variables, constants and functions A,B,C,...
 The symbol table includes the type and value for each symbol.
 All aliases and compile-time constants are resolved and converted to a
 standard form.
 All symbols must be reachable from the scope where syntaxtreeof() is
 mixed into.
 
 The created AbstractSyntaxTree is a compile-time constant, so it can be
 used for  further compile-time operations and code generation.
 
 Works for almost any expression (templates, functions, strings, slicing,
 struct literals,...); the biggest omission is relational operators.
 Less than 300 lines of code in D1.020.
 Probably could simplified using __traits in D2.0.
 Enjoy.
 
 
 Return type:
 -----
 struct Symbol {
     char [] type; // the name of the type, as text
     char [] value; // the value, as text. Either the symbol name, or a
 literal
 }
 
 // The result of semantic analysis of the original expression
 struct AbstractSyntaxTree {
     char [] expression; // syntax tree in Placeholder format, eg A+=(B*C)
     Symbol[] symbolTable; // The types and values of A,B,C,...
 }
 ------
 
 Example:
 -----
 import SyntaxTree;
 
 const foo = "abc";
 int bar(real x, char [] s) { return 0; }
 struct Duck{};
 Duck duck;
 
 AbstractSyntaxTree a = mixin(syntaxtreeof(`foo*   bar(2.18_3242e+45L,
 "xyz") in duck`));

Words fail me; I'm going to have to borrow some from Dave Grossman: Sweet mother of double-jeopardy back-stroking in butterscotch with a holy cap-wearing catfish flopping a crime-beat past sweet suffering St. Sebastian on a sousaphone in a short story by Susan Sontag with the great grinning head of John the Baptist in a pork-pie hat stuffed in a rhinestone bowling bag by the Greek goddess Celine in a chariot with dual overhead cams and Silver Fox mudflaps... ...that's impressive. -- Daniel
Sep 12 2007
parent reply Regan Heath <regan netmail.co.nz> writes:
Daniel Keep wrote:
 
 Don Clugston wrote:
 I've finally released the compile-time parser I mentioned in my
 conference presentation.

 http://www.dsource.org/projects/mathextra/browser/trunk/blade/SyntaxTree.d

 contains one publicly usable function:

 char [] syntaxtreeof(char [] expression).

 When mixed in, this lexes and parses the expression, determines
 precedence and associativity, creating an object of type
 AbstractSyntaxTree, which contains a standardized 'placeholder
 expression' (eg "A+=(B*C)")
 and a symbol table for the variables, constants and functions A,B,C,...
 The symbol table includes the type and value for each symbol.
 All aliases and compile-time constants are resolved and converted to a
 standard form.
 All symbols must be reachable from the scope where syntaxtreeof() is
 mixed into.

 The created AbstractSyntaxTree is a compile-time constant, so it can be
 used for  further compile-time operations and code generation.

 Works for almost any expression (templates, functions, strings, slicing,
 struct literals,...); the biggest omission is relational operators.
 Less than 300 lines of code in D1.020.
 Probably could simplified using __traits in D2.0.
 Enjoy.


 Return type:
 -----
 struct Symbol {
     char [] type; // the name of the type, as text
     char [] value; // the value, as text. Either the symbol name, or a
 literal
 }

 // The result of semantic analysis of the original expression
 struct AbstractSyntaxTree {
     char [] expression; // syntax tree in Placeholder format, eg A+=(B*C)
     Symbol[] symbolTable; // The types and values of A,B,C,...
 }
 ------

 Example:
 -----
 import SyntaxTree;

 const foo = "abc";
 int bar(real x, char [] s) { return 0; }
 struct Duck{};
 Duck duck;

 AbstractSyntaxTree a = mixin(syntaxtreeof(`foo*   bar(2.18_3242e+45L,
 "xyz") in duck`));

Words fail me; I'm going to have to borrow some from Dave Grossman: Sweet mother of double-jeopardy back-stroking in butterscotch with a holy cap-wearing catfish flopping a crime-beat past sweet suffering St. Sebastian on a sousaphone in a short story by Susan Sontag with the great grinning head of John the Baptist in a pork-pie hat stuffed in a rhinestone bowling bag by the Greek goddess Celine in a chariot with dual overhead cams and Silver Fox mudflaps... ...that's impressive.

This is the sort of thing that needs to be published in a "Check out the crazy sh!t we can do with D" article :D Regan
Sep 12 2007
parent Regan Heath <regan netmail.co.nz> writes:
Regan Heath wrote:
 Daniel Keep wrote:
 Don Clugston wrote:
 I've finally released the compile-time parser I mentioned in my
 conference presentation.

 http://www.dsource.org/projects/mathextra/browser/trunk/blade/SyntaxTree.d 


 contains one publicly usable function:

 char [] syntaxtreeof(char [] expression).

 When mixed in, this lexes and parses the expression, determines
 precedence and associativity, creating an object of type
 AbstractSyntaxTree, which contains a standardized 'placeholder
 expression' (eg "A+=(B*C)")
 and a symbol table for the variables, constants and functions A,B,C,...
 The symbol table includes the type and value for each symbol.
 All aliases and compile-time constants are resolved and converted to a
 standard form.
 All symbols must be reachable from the scope where syntaxtreeof() is
 mixed into.

 The created AbstractSyntaxTree is a compile-time constant, so it can be
 used for  further compile-time operations and code generation.

 Works for almost any expression (templates, functions, strings, slicing,
 struct literals,...); the biggest omission is relational operators.
 Less than 300 lines of code in D1.020.
 Probably could simplified using __traits in D2.0.
 Enjoy.


 Return type:
 -----
 struct Symbol {
     char [] type; // the name of the type, as text
     char [] value; // the value, as text. Either the symbol name, or a
 literal
 }

 // The result of semantic analysis of the original expression
 struct AbstractSyntaxTree {
     char [] expression; // syntax tree in Placeholder format, eg 
 A+=(B*C)
     Symbol[] symbolTable; // The types and values of A,B,C,...
 }
 ------

 Example:
 -----
 import SyntaxTree;

 const foo = "abc";
 int bar(real x, char [] s) { return 0; }
 struct Duck{};
 Duck duck;

 AbstractSyntaxTree a = mixin(syntaxtreeof(`foo*   bar(2.18_3242e+45L,
 "xyz") in duck`));

Words fail me; I'm going to have to borrow some from Dave Grossman: Sweet mother of double-jeopardy back-stroking in butterscotch with a holy cap-wearing catfish flopping a crime-beat past sweet suffering St. Sebastian on a sousaphone in a short story by Susan Sontag with the great grinning head of John the Baptist in a pork-pie hat stuffed in a rhinestone bowling bag by the Greek goddess Celine in a chariot with dual overhead cams and Silver Fox mudflaps... ...that's impressive.

This is the sort of thing that needs to be published in a "Check out the crazy sh!t we can do with D" article :D

Clarification; "crazy" as in "crazy cool" :P Regan
Sep 12 2007
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Don Clugston wrote:
 I've finally released the compile-time parser I mentioned in my 
 conference presentation.
 
 http://www.dsource.org/projects/mathextra/browser/trunk/blade/SyntaxTree.d

Don, you are incredible.
Sep 12 2007
parent Don Clugston <dac nospam.com.au> writes:
Walter Bright wrote:
 Don Clugston wrote:
 I've finally released the compile-time parser I mentioned in my 
 conference presentation.

 http://www.dsource.org/projects/mathextra/browser/trunk/blade/SyntaxTree.d 

Don, you are incredible.

Well, you wrote the incredible compiler that makes it all possible... <g>. It would really help if bug #1373 was fixed. It looks like a very simple bug to fix, but I have to go through a lot of contortions to work around it.
Sep 18 2007
prev sibling next sibling parent Alexander Panek <a.panek brainsware.org> writes:
Don Clugston wrote:
 I've finally released the compile-time parser I mentioned in my 
 conference presentation.
 
 http://www.dsource.org/projects/mathextra/browser/trunk/blade/SyntaxTree.d

I think this fits pretty well here: This is madness. :) Best regards, Alex
Sep 12 2007
prev sibling parent Sean Kelly <sean f4.ca> writes:
That's incredible!  And the best part is that the code is really quite 
understandable.  It just happens to contain some extremely clever ideas 
put together in an elegant manner :-)


Sean
Sep 13 2007