[antlr-interest] Graph grammars

Ludwig Maes ludwig.maes at gmail.com
Wed May 9 13:02:26 PDT 2012


Playing with ANTLR and ANTLRworks is a very educative experience.
I was wondering if what ANTLR does to parse sentences (strings) from a
language (set of strings), could be generalized to parsing graphs from
graph languages. Then I recently found

What holds me back the most from using parsers or compiler middle
ends, is the huge hidden complexity in application specific
representation of information: there is much more than the parse tree
or abstract syntax tree, every applications stores specific kinds of
information in specialized structures.
In general I view (intended) information to be graphlike, where people
have agreed to linearize/tree-ify for purpouse of communication
(between humans, or humans and software, i.e. a compiler). Compilers
do not store everything it knows about code it is compiling in one big
graph for multiple (performance?) reasons. For example scopes and
other information are stored in specific structures. When I want to
automate a kind of transformation (or even mere visualization) of
code, I really just want this single graph vs a parse tree or AST.
This may necessitate some ontology for the information at hand (i.e.
the ontology would be an implicit part of the API agreement between
parser/compiler middle end and the user). It would then be up to the
user to only use the subgraph it is interested in (this way the user
only needs to learn 1) the specific "ontology" and 2) how to perform
manipulations on the graph) as opposed to learning the applications
multiple specialized data structures, and finding out how to gain
access to them, let alone use them correctly.

Are there any (open source) tools similar too ANTLR (in terms of
cleanness and functionality) which output graphs instead of parse
trees or AST's, or which can parse graphs as in the mentioned paper?


More information about the antlr-interest mailing list