The language of languages
matt.might.net
matt.might.net
It can not only do the basic text->tree parsing from a file describing the grammar, but will also allow to specify additional grammars for traversing the generated tree and executing arbitrary code in your language of choice as particular nodes are recognized. I built a little compiler in it some years ago, I had a Xpl.g grammar file for parsing the program text and creating the abstract syntax tree, a SemanticAnalysis.g grammar file for doing a first pass through the tree, annotating it with additional information, filling the symbol table, checking semantic correctness and then finally CodeGeneration.g for emitting JVM bytecode using the annotated tree. The code for this is still on Github:
https://github.com/jaroslawr/xpl/tree/509120e66e23aac8493414...
There is a simpler example using the same functionalities described on the ANTLR wiki:
http://www.antlr.org/wiki/display/ANTLR3/Simple+tree-based+i...
I used the ANTLR reference book when learning it, but now there is also a real introductory manual:
http://pragprog.com/book/tpantlr2/the-definitive-antlr-4-ref... http://pragprog.com/book/tpdsl/language-implementation-patte...
I also used the Dragon Book and "Programming Language Pragmatics" for theory, both great books and PLP certainly deserves to be better known.
Grammars are only one part of understanding a language, hardly the "language of languages". In natural languages, grammars are one subset of linguistics. It would be just as valid to say vocabularies or phonology are the language of languages as it would be to say grammars are.
Other than these overly broad arguments and attempts to define natural languages in the same way that formal languages can be defined, this is a nice general introduction to some specific notation techniques for computer languages.
Of course, I might not have read it at all if it were titled "An Introduction to Backus-Naur Form, Extendend BNF, and Augmented BNF Notation Techniques".
Similarly, the 'language of languages' is also appropriate given that BNF is defined with a grammar, and is used to specify grammars.
Furthermore, formal grammars were originally invented for purposes of exploring natural languages.
Sorry if you didn't enjoy the article, but there's nothing wrong with it in the context of formal language theory :)
I'm not even sure if a XBNF is the best way to describe or reason about language syntax. Precedence grammars (with hacks to handle braces) are quite interesting for robust error tolerant parsing, and might more closely mirror how we internal grammars in our head.
(a|b)(x|y)
{"ax", "ay", "bx", "by"}
While it's true that these other languages have more to them than their syntax, they do define a "language" in the above initial sense: the set of all valid instances of it (i.e. without syntax errors), the set of sequences of symbols.
Programming languages generally include ways of extending their language (in the initial sense). Even java: a java program includes a syntax for extending its syntax (its "language"), in the sense that a program using a certain method invocation becomes valid, if that method is defined. Thus, it is itself both definitions of a grammar, and instances within that grammar - like XML and XSD combined in one (or XML and DTD).
BTW: this reply (and the two similar ones) will probably annoy you, because you know what a "formal language" is (at least, you use the term). I think your misinterpretation is that the article does not claim anything about "natural languages" - only the shape/structure of a language ("So, what shapes languages? Grammars do."/"Behind every language, there is a grammar that determines its structure.").
To be fair though, it then jumps straight into "A grammar defines a language.", without noting a shift in the meaning of the term "language". I think its meaning is clear from context, but it's certainly misleading to shift terminology as you go along!
I find it interesting that the parser generators are so closely bound up with code generation. I like the model where you can specify at runtime: when this non-terminal is parsed, execute that function.
[1] http://en.wikipedia.org/wiki/Parsing_expression_grammar [2] http://en.wikipedia.org/wiki/LALR_parser
Like a KR or some system that could read BNF or whatever and translate directly into another level, like operations defined by the operating system or something.
Why can't we describe a language declaratively and semantically so that its low level details wouldn't have to be specified manually and so that it could be related to other languages and reasoning could be done about its effects?
The lowest levels of the system would probably have to be described as part of the same representation system.
The grammar is here:
http://felix-lang.org/lib/grammar
Close examination reveals even the regexps for literals are defined in the grammar. The parser is built on top of the excellent extensible GLR+ parsing tool Dypgen.
In principle the Felix parsing system is independent of Felix. All you need to do is replace the s-expression to Felix AST translator with some kind of pretty printer for s-expressions, even XML, and you can target anything.
The other understanding you need to be able to put them to use is having a mental model of how a bottom up parser processes the tokens. You need to be able to insert actions for each grammar rule at appropriate places, which allows the information to flow bottom up too, and be processed appropriately at the same time. I have found this second bit to language processing is actually the harder bit, and its worth rewriting your grammar to make it simpler.
I (and many others) prefer to keep these passes relatively distinct. Parse tree -> AST -> Internal Representation -> (Generation of Output / Interpretation)