VisualLangLab
Encyclopedia
VisualLangLab is an open source parser generator for JVM (Java Virtual Machine) languages. VisualLangLab allows users to create and edit graphical grammar-trees that represent grammar rules.
VisualLangLab was The Java Posse's Project of the Week for episode 364.
An introductory article, Grammar without Tears is available online.
). This interactive IDE (Integrated Development Environment
)-style interface differentiates it from other parser generators. The grammar-trees are executable, and can be test-run at the click of a GUI button. Parsers can be created and tested entirely within the user interface without additional tools or skills. Because of its ease of use, VisualLangLab is an effective prototyping and training environment. It also allows the use of semantic actions (written as Scala or Javascript
functions) embedded within the grammar where needed. A comment on lambda-the-ultimate in October 2004 describes VisualLangLab as a Yacc with a GUI.
(e.g. JavaCC
, ANTLR
) use a textual grammar specification in Extended Backus-Naur Form (EBNF) or Parsing expression grammar (PEG)
. However, unlike them, the VisualLangLab instead creates a visual grammar of the language, using its GUI.
VisualLangLab's grammar-trees are equivalent to PEGs; they support sequences, ordered choices, multiplicities (*, +, ?), as well as syntactic and semantic predicates
. These grammar-trees are turned directly into instances of Scala's Parser type at run-time. The grammar-trees and other GUI features are intuitive, and the user does not have to understand PEGs or Scala programming, but familiarity with Scala's standard data types is useful in understanding the abstract syntax tree (AST)
.
recursive descent
parsers based on Scala's parser combinator
library.
VisualLangLab's parsers successfully handle the LL(*)
class of grammars, and can also handle optional left-recursion
by using packrat parsers. These are possible because of the underlying Scala parser combinator support.
thatInternal Lexer VisualLangLab's internal lexical analyzer is an improvement over the mechanism used in Scala's native RegexParsers. VisualLangLab includes a mechanism that automatically defines and creates an AST for all grammars.
VisualLangLab is licensed under a GPL license.
(eXtensible Markup Language) files that can be reopened later for review, further editing or testing.
) enables host programs to open the XML files and regenerate the parser. Starting with version 6.01 (which optionally provides ASTs created with basic JVM types only), host programs may be written in any JVM language. This feature makes VisualLangLab's parsers available to all JVM languages (present and future).
The availability of Scala and its built-in parser-combinators prompted a re-write, and a Scala version was published at the current Official VisualLangLab website on 10th March 2010. Although all of the code was re-written in Scala, the essential character of the GUI remains the same. A news item on jaxenter featured this version in late March 2010.
The Grammar without Tears article was featured in the java.net Editor's blog on 14th September 2011.
In September 2011 VisualLangLab was The Java Posse's Project of the week
VisualLangLab was The Java Posse's Project of the Week for episode 364.
An introductory article, Grammar without Tears is available online.
Ease of Use
VisualLangLab provides a graphical user interface (GUIGraphical user interface
In computing, a graphical user interface is a type of user interface that allows users to interact with electronic devices with images rather than text commands. GUIs can be used in computers, hand-held devices such as MP3 players, portable media players or gaming devices, household appliances and...
). This interactive IDE (Integrated Development Environment
Integrated development environment
An integrated development environment is a software application that provides comprehensive facilities to computer programmers for software development...
)-style interface differentiates it from other parser generators. The grammar-trees are executable, and can be test-run at the click of a GUI button. Parsers can be created and tested entirely within the user interface without additional tools or skills. Because of its ease of use, VisualLangLab is an effective prototyping and training environment. It also allows the use of semantic actions (written as Scala or Javascript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
functions) embedded within the grammar where needed. A comment on lambda-the-ultimate in October 2004 describes VisualLangLab as a Yacc with a GUI.
Grammar as Visual Tree
Most other parser generators for JavaJava
Java is an island of Indonesia. With a population of 135 million , it is the world's most populous island, and one of the most densely populated regions in the world. It is home to 60% of Indonesia's population. The Indonesian capital city, Jakarta, is in west Java...
(e.g. JavaCC
JavaCC
JavaCC is an open source parser generator and lexical analyzer generator for the Java programming language. JavaCC is similar to yacc in that it generates a parser from a formal grammar written in EBNF notation, except the output is Java source code...
, ANTLR
ANTLR
In computer-based language recognition, ANTLR , or ANother Tool for Language Recognition, is a parser generator that uses LL parsing. ANTLR is the successor to the Purdue Compiler Construction Tool Set , first developed in 1989, and is under active development...
) use a textual grammar specification in Extended Backus-Naur Form (EBNF) or Parsing expression grammar (PEG)
Parsing expression grammar
A parsing expression grammar, or PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language...
. However, unlike them, the VisualLangLab instead creates a visual grammar of the language, using its GUI.
VisualLangLab's grammar-trees are equivalent to PEGs; they support sequences, ordered choices, multiplicities (*, +, ?), as well as syntactic and semantic predicates
Syntactic predicate
A syntactic predicate specifies the syntactic validity of applying a production in a formal grammar and is analogous to a semantic predicate that specifies the semantic validity of applying a production. It is a simple and effective means of dramatically improving the recognition strength of an LL...
. These grammar-trees are turned directly into instances of Scala's Parser type at run-time. The grammar-trees and other GUI features are intuitive, and the user does not have to understand PEGs or Scala programming, but familiarity with Scala's standard data types is useful in understanding the abstract syntax tree (AST)
Abstract syntax tree
In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...
.
Capabilities
VisualLangLab generates backtrackingBacktracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
recursive descent
Recursive descent parser
A recursive descent parser is a top-down parser built from a set of mutually-recursive procedures where each such procedure usually implements one of the production rules of the grammar...
parsers based on Scala's parser combinator
Parser Combinator
In functional programming, a parser combinator is a higher-order function which accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some structure as output, typically a parse tree or a set of...
library.
VisualLangLab's parsers successfully handle the LL(*)
LL parser
An LL parser is a top-down parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Leftmost derivation of the sentence...
class of grammars, and can also handle optional left-recursion
Left recursion
In computer science, left recursion is a special case of recursion.In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s ‘alternatives’ either immediately or through some other non-terminal definitions rewrites to r again.- Definition :"A...
by using packrat parsers. These are possible because of the underlying Scala parser combinator support.
Built-in Lexer
VisualLangLab uses an internal lexical analyzerLexical analysis
In computer science, lexical analysis is the process of converting a sequence of characters into a sequence of tokens. A program or function which performs lexical analysis is called a lexical analyzer, lexer or scanner...
thatInternal Lexer VisualLangLab's internal lexical analyzer is an improvement over the mechanism used in Scala's native RegexParsers. VisualLangLab includes a mechanism that automatically defines and creates an AST for all grammars.
VisualLangLab is licensed under a GPL license.
Grammar Reuse
Parsers created in VisualLangLab can be saved as XMLXML
Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....
(eXtensible Markup Language) files that can be reopened later for review, further editing or testing.
API
An API (Application Programming InterfaceApplication programming interface
An application programming interface is a source code based specification intended to be used as an interface by software components to communicate with each other...
) enables host programs to open the XML files and regenerate the parser. Starting with version 6.01 (which optionally provides ASTs created with basic JVM types only), host programs may be written in any JVM language. This feature makes VisualLangLab's parsers available to all JVM languages (present and future).
History
VisualLangLab was created on 5th March 2004 as A Visual LL(K) Parser Generator. This first version was written in Java, and can still be found at the Older version website. The software was usable by mid-2004, and an interesting application is described in this java.net article published in early October 2004. A comment on lambda-the-ultimate in October 2004 describes VisualLangLab as a Yacc with a GUI.The availability of Scala and its built-in parser-combinators prompted a re-write, and a Scala version was published at the current Official VisualLangLab website on 10th March 2010. Although all of the code was re-written in Scala, the essential character of the GUI remains the same. A news item on jaxenter featured this version in late March 2010.
The Grammar without Tears article was featured in the java.net Editor's blog on 14th September 2011.
In September 2011 VisualLangLab was The Java Posse's Project of the week
See also
- JavaCCJavaCCJavaCC is an open source parser generator and lexical analyzer generator for the Java programming language. JavaCC is similar to yacc in that it generates a parser from a formal grammar written in EBNF notation, except the output is Java source code...
- ANTLRANTLRIn computer-based language recognition, ANTLR , or ANother Tool for Language Recognition, is a parser generator that uses LL parsing. ANTLR is the successor to the Purdue Compiler Construction Tool Set , first developed in 1989, and is under active development...
- SableCCSableCCSableCC is an open source compiler generator in Java. Stable version is licensed under the GNU Lesser General Public License...
- Coco/RCoco/RCoco/R is a compiler generator that takes an L-attributed Extended Backus–Naur Form grammar of a source language and generates a scanner and a parser for that language....
- parboiledParboiled (Java)parboiled is an open-source Java library released under an Apache License. It provides support for defining PEG parsers directly in Java source code....