Lambda the Ultimate

...let me highly recommend Spirit and its dynamic parser support.

I mean, when an extension is in your code but the actual definition is in another place. The code may have already been parsed... Just to know whether Spirit allows it or there is any paper/document speaking about this.

It sounds like you might be talking about what is sometimes called a "Syntax Directed Compiler" or a "Syntax Directed Language". Google it and see if that's the sort of thing you're looking for. I've compiled some links at:

http://www.peerbox.com:8668/space/start/2005-11-14/1

I understand that this was something of a hot topic in the 1960's and that there were even conferences on the subject.

This sounds similar to Objective Caml's preprocessor, camlp4. It implements the core grammar as a recursive descent parser. User code can extend the grammar by adding rules to the parser (albeit via a more heavyweight syntax than yours). All rules added within the same precedence level have common prefixes factored out so that the parser can operate with only one lookahead token and no backtracking. Because these rules can be stored as a tree rather than as a state table this simplifies runtime extension. A better description can be found here in the camlp4 manual.

It seems to support what you want out-of-the-box:
http://nemerle.org/Macros_tutorial#Adding_new_syntax_to_the_compiler

Maybe you can get some ideas there.

Felix supports limited user defined on-the-fly syntax extensions, in a way similar to camlp4. The grammar extension is more lightweight, however the semantic rules are more convoluted. The technology used to implement this is written Ocaml and quite tricky because the core grammar and semantic rules use a standard Ocamlyacc LALR1 parser, but the extensions are table driven and provide recursive descent parsing.

As an example, the standard library contains the following definition of the whilst statement:

#statement#
  whilst expr do statements done ; =>#
  macro {
    macro lab1 is new;
    macro lab2 is new;
    lab1:>
      if not _1 goto lab2;
      _3;
      goto lab1;
    lab2:>
  };
#

The grammar production couldn't be simpler: whilst is made into a keyword, do and done are already keywords, and expr and statements are magic keywords which invoke the core LALR1 parser recursively for statements and an expression, respectively. The recursion is open in the sense that it includes user added grammar entries .. including the one currently being defined.

The action rule is to emit the parsed user code following the =># symbol, replacing symbols _1, _2 etc with the parse trees of the corresponding nonterminals in the grammar.

As you can see in the example, the resultant parse tree usually involves macro terms, which invoke the syntax macro processor in the subsequent processing phase. The macro processor is programmed to reduce the syntax tree to pre-defined terms which the following stages of compilation are programmed to handle.

Felix also supports user defined binary infix operators and unary bracket operators.

The implementation is interesting because it does not compromise the high performance of the underlying LR parser engine, and also because of the extreme 'hackery' required to provide the Ocamlyacc parser with state data, without using any global variables.

Luckily, the Ocamllex lexer does allow state variables. So what happens is the lexer, which also handles preprocessor directives such as the #statement directive above, keeps track of of keywords in a symbol table. The table is augmented whilst lexing by user defined keywords, and the entire content of the user defined syntax extension is embedded as an attribute in the keyword table entry. In order to capture the correct environment, it is stored as an executable closure inside the corresponding token, when the keyword is lexed.

Each file is lexed entirely before parsing. Then the parser is fed the token stream via a custom lex buffer object. When the parser sees a statement starting with a user defined keyword, it invokes the embedded closure, and returns the resultant parse tree.

Under the hood, the closure parses the text interpretively, using the user's grammar production, in the process or which the Ocamlyacc parser can be invoked recursively on seeing the magic statements or expr symbols.

There is a hack here: Ocamlyacc, like all LR1 parsers, can 'overshoot' by one token before doing a reduction. To fix this problem, the Ocamlyacc grammar defines special terms for terminated expressions, which never overshoot (well actually they always overshoot expressions by one exactly one token). The terminator is pushed back into the token stream so it can be rescanned by the parent parsing process. This is a hack because it relies on experimentally observed but undocumented Ocamlyacc behaviour.

I comment that the biggest problem here is that recursive descent executable parsers have NO error handling capabilities. Any failure propagates back to the last choice point and the parser simply tries the next alternative. Consquently, the only possible error you can get is a Syntax Error, and it always occurs right at the beginning of the token stream.

LR parsers, on the other hand, always pinpoint precisely the first token causing an error.

To solve this problem, at least partially, Felix keeps track of whether there actually is an earlier choice point, and fails immediately if there is not. Although this is still theoretically a very weak diagnostic, in practice it is miles better than simply knowing that your whilst statement has an error in it .. somewhere! In particular, errors reported by recursive calls to the Ocamlyacc engine throw exceptions which carry precise error locations and perhaps other diagnostic information, and the RD parser can propagate this error if there is no prior choice point.

Consequently it is best if user defined statements all start with distinct keywords, otherwise only errors parsing the last tried alternative can carry sensible diagnostics .. which is unfortunate if the programmer intended one of the other grammar productions to apply.

All in all, this feature allows both ordinary programmers and the Felix developers to easily add pleasing syntactic sugar to the language without rebuilding the compiler. It is intended as the precursor of a more ambitious feature: the ability to program arbitrary Domain Specific Sub Languages (DSSLs) directly in library code.

You might like to take a look at Common Lisp's reader macros. Whenever the Lisp reader encounters a certain character or sequence of certain characters (such as "#c" or "{") the reader calls a specified function which is to read the next expression. That way you could write "#c(1 2)" and have it be read as "(complex 1 2)", or set curly braces to act like parentheses.

It's not as general and powerful as what you describe, but it is simple and pretty flexible.

You can check out http://jparsec.codehaus.org

Parsec is implemented in Java, C# and Ruby so far.

Thanks to Java's syntax, jparsec is the most verbose among all. Nothing prevents you from writing dynamic grammar if you don't mind the ugly anonymous classes everywhere.

C#'s version is much better using anonymous delegate.

Ruby Parsec is the most pleasant one. I find it even easier to use than Haskell Parsec pragmatically.

From another current LtU discussion: Good Ideas, Through the Looking Glass, here's what Niklaus Wirth has to say on the subject:

5.2. Extensible languages
The phantasies of computer scientists in the 1960s knew no bounds. Spurned by the success of automatic syntax analysis and parser generation, some proposed the idea of the flexible, or at least extensible language. The notion was that a program would be preceded by syntactic rules which would then guide the general parser while parsing the subsequent program. A step further: The syntax rules would not only precede the program, but they could be interspersed anywhere throughout the text. For example, if someone wished to use a particularly fancy private form of for statement, he could do so elegantly, even specifying different variants for the same concept in different sections of the same program. The concept that languages serve to communicate between humans had been completely blended out, as apparently everyone could now define his own language on the fly. The high hopes, however, were soon damped by the difficulties encountered when trying to specify, what these private constructions should mean. As a consequence, the intreaguing idea of extensible languages faded away rather quickly.

D allows lazy parameters in function declarations.

The expression in that position is wrapped up in a delegate and called whenever the parameter is evaluated.

http://www.digitalmars.com/d/function.html

void While( lazy bool cond, lazy void code )
{
for( ; cond() ; ) code();
}

D-Expressions claim to bring Lisp-style macros to languages with more conventional syntax. The basic idea is to extend Lisp's simple syntax

sexpr ::= atom | (atom*)

with a bit more variation, however ensuring that there always is a defined tree structure. I.e., instead of just matching pairs of "(" and ")" you also allow matching pairs of "[", "]" (as Reader macros do in Lisp) but also "define", "end" or "macro-name", "end".

The last rule has quite some implications, namely that the parser must maintain an environment of macro names, introducing some staging problems (i.e., the code of the macro-function must be available, so usually be in a different module).

Dylan has those kind of macros as a pattern-matching facility and I think you can get quite far with it. D-Expressions allow for even more.

I have had a go at this kind of thing myself, where I wanted macro definitions to be part of the main language grammar, rather than being pre-processor instructions, as in C macros. This would allow macro definitions to be syntax-checked at the point of definition, rather than at the point of expansion.

The basic problem, as I see it, is that no worthwhile grammar will allow arbitrary sequences of tokens. There has to be some structure. Jorend described a two-phase parser above, where the first phase is just a list of tokens. But that is just a lexer, not a parser.

Languages of the Lisp family solve the macro-in-grammar problem by having a minimalist and permissive grammar that describes the structure of the AST, without special keyword constructs. Special forms, e.g. conditionals, are merely instances of a general structure, with a particular symbol at the head of the list.

In a language that has keywords and special constructs, one can still define new constructs, provided that the grammar is permissive about what counts as an expression. For an extensible imperative language, one could allow blocks as expressions, i.e. you can pass { statement; ... } as an argument to a function. It is quite possible to define this sort of thing in Yacc or a similar parser generator.

Please, I need some help—someone to review a paper I'm working on, called The Ameba Paradigm. I'm a retired programmer with no one among my friends and family who can review it.

Among other things, the paper features a method for designing an imperative language with an adaptable syntax. It avoids “the difficulties encountered when trying to specify, what these private constructions should mean,” (Niklaus Wirth). Furthermore, this adaptable syntax solution requires a persistent object-base/runtime data structure.

I've searched the Internet for a similar solution, and found none. Thus, I believe my paper describes a novel method of implementing an imperative programming language with adaptable syntax and a persistent object base. That means, some intellectual property is at risk. Being retired with a modest, fixed income means no money for patents. What options do I have?

A draft of the abstract is ready for review, but I will limit the number of reviewers. After reviewing the abstract, a reviewer may request the paper for review. However, before sending my paper to anyone, I need to find out a little about intellectual property protection and prospective reviewers. I am not looking for private information. I will read blog posts, a personal web page, a resume, publications by the reviewer, and whatever a prospective reviewer offers.

I hope no one is offended by my trying to get to know a prospective reviewer, just a little.

To anyone who offers to review my paper: Thank you! Thank you! Thank you!