Using adaptive grammars [closed]

Question

I'm trying to implement a language (or family of languages) whose grammar can be changed dynamically. I have found no examples that serve as study cases.

Can you give me some reference to any that are actually used in the real world (even from the academic world)?

Does it make sense to implement a Domain-Specific Languages with a dynamic grammar?

Chellman

You mean a language in which you can just define new control structures on the fly? That's kind of strange. Do you have an example of the kinds of things you want to do for which you think you need this kind of functionality? – Anjaanjali

Would Lisp fit your description? – Isoline

Since all compilers are built with tools (like Yacc and Lex and Bison) than all compiled languages are "adaptive" according to this definition. This question is too vague to answer. – Apocopate

@Starkey: It is often emphasized that Lisp barely has any syntax at all... @S.Lott: Quite a few language implementations use handwritten parsers (including gcc agaik). And methinks the OP is referring to parts of the program currently parsed changing how the rest of the program is parsed. – Owe

@delnan: How's that different from a script which includes lex, yacc and the resulting program built by yacc? It seems to vague to be answered except with a trivial "Yup, it can be done and is done all the time." – Apocopate

@S.Lott: I was exploring the option of using a script pipeline to represent an adaptive grammar, but I do not think that can be formalized as a grammar must be (web.cs.wpi.edu/~jshutt/adapt/adapt.html). The reference to OMeta (tinlizzie.org/ometa) is pretty much closer to what I'm looking for, which is the possibility that one's grammar evolve over time. It does not seem to me to be equal to rebuild again and again, at least not from the standpoint of object-oriented programming. – Chellman

Answer 1

The most famous current language that has a dynamic syntax is Perl6. The most famous example in general is probably Smalltalk-72.

You might also want to look into OMeta and the rest of the STEPS project from Alan Kay's Viewpoints Research Institute, as well as Val Schorre's original META II.

Also interesting: the π programming language.

XL (Extensible Language) also allows for powerful manipulation of the syntax itself.

Ascendant

EnglishScript also has a dynamic syntax, but it's still a work-in-progress. – Subdued

This answer needs some clarification. Why is the syntax of Perl 6 considered to be "dynamic"? – Subdued

Answer 2

The Katahdin programming language offers syntax and semantic changes at runtime. It's an unsupported thesis language so don't expect to use it in production. Still, Chris Seaton's thesis may be a good resource for implementing similar ideas in your own language.

Seaton is cited in this paper describing a macro system for the Fortress programming language. The authors' goal is to make syntactic extension indistinguishable from core syntax.

Moravia

How could I forget about Katahdin! There's also a related, similar one, whose name escapes me at the moment. – Favien

Answer 3

I really like the syntax of Agda, which is extremely flexible. It allows for arbitrary distfix operators which essentially allows for, what looks like new language features.

Although I haven't looked closely into her work I know Annika Aasa has done some work on letting programmers specify new syntax. You'll find her work on Google Scholar.

Fwiw, I think developing domain-specific languages as a library in a language with a very flexible syntax makes a lot of sense. It's sometimes referred to as an embedded domain-specific language, in case you didn't know.

Mopboard

Agda has syntax declarations, which allow user-defined syntax. This is similar to the syntax extensions in the Coq proof assistant. – Subdued

Answer 4

Katahdin is an obvious choice. There is also PFront, and good old parsing macros in Common Lisp as well.

Whiteheaded

The link to PFront appears to be broken now. – Subdued

@AndersonGreen, edited: a link to an article still works, not sure where is the download link now. – Whiteheaded

Answer 5

I'm working on the same thing.

I should have a couple extendable parser libraries that people can use soon. I've got the lexer done and I'm busy throwing together the parser.

The first library is being written in Ruby and I intend to translate it to Java when it's done. I tried a Java version first, but I got bogged down in stupid details so I switched to Ruby so the language won't get in my way while I'm still thinking.

I'm happy with my approach which allows switching between multiple lexers and multiple expression types with distfix operators. The lexers are just ordered series of regex expressions.

The parsing is simple operator precedence outside of the distfix parts of the productions and LL(1) inside. We'll see if I find I want anything stronger.

Acton

Answer 6

I have found relatively few implementations of adaptive grammars, though there is an adaptive parser generator called Dypgen. I also wrote an adaptive parser in Prolog that can "learn" new grammars from its input.

There is also a "self-modifying grammar interpreter" called OpenZZ, though it hasn't been updated in a few years.

It's also possible to write "self-modifying" parsers using Nearley, though this feature isn't documented yet.

Subdued