VisualLangLab - Grammar without Tears

In the world of computing a grammar is a somewhat different thing
from the object implied in
grammar without tears.
But in terms of the misery caused to those
who have to deal with them, the two grammars appear to be closely related.
This article describes a no tears approach to parser development
using the free, open-source parser-generator VisualLangLab.
It has an
IDE that represents grammar rules
(or productions)
as intuitive trees, like those in Figure 1 below,
without code or scripts of any kind.

Figure 1. VisualLangLab's grammar-trees

The grammar-trees are also executable, and can be run directly
at the click of a button.
This encourages the use of tight
iterative-incremental
development cycles, and improves the pace of development manyfold.
These features also make it an effective prototyping environment and a training tool.

VisualLangLab is itself written in
Scala, a
JVM language that supports object orientation as well as
functional programming,
but you don't have to know much Scala to use VisualLangLab.

Parsing techniques and parser-generator tools are a great addition
to any developer's arsenal,
and VisualLangLab provides a convenient, gentle introduction to those topics.
A later article will describe the use of VisualLangLab to produce
a domain specific language or
DSL
for testing Java-Swing programs.

A periodically
revised version of this article that stays compatible with the current version of

VisualLangLab can be seen here.

Can I see the Generated Code?

As a now-famous panda discovered, powerful recipes sometimes have
no secret ingredient.
And there is no generated code.

VisualLangLab uses Scala's parser
combinator
functions to turn grammar-trees (or XML from a
saved grammar-file) directly into a
parser
at run-time without producing or compiling source-code.
But users of the GUI and the API
do not have to know anything about combinators to use these capabilities.

Download and Run VisualLangLab

The VisualLangLab web site has a
zip file
that includes everything you need. The only prerequisite is a 1.6+ JDK or JRE.
To run the tool, proceed as follows.

No Scala Installation

A Scala installation is not a mandatory prerequisite.
If you do not have Scala (or just want to avoid version issues),
download the executable JAR file
VLLS-All.jar
(which bundles the required Scala libraries).
VisualLangLab is started by double-clicking VLLS-All.jar
in a file browser, or by issuing the following command at a system prompt:

    java -jar VLL-All.jar

Linux or UNIX users will, of course, have to enable execution (chmod +x ...)
to have it start by double-clicking.

Have a Scala Installation

To run VisualLangLab with your installed version of Scala
use one of the launchers included in the zip file
(vlls.bat for Windows, vlls for Linux).
Linux or UNIX users will need to enable execution (chmod +x ...)
of the launcher script.

The GUI

When started, VisualLangLab displays the GUI shown in Figure 2 below.
The article explains the menus and buttons as needed, but a full
description can also be found online at
The GUI and in the download zip.
All toolbar buttons have tool-tip texts that explain their use.

Figure 2. The VisualLangLab GUI

The graphical and text panels are used as described below.

• A is used for the grammar-tree as described in
  Managing Rules below
• B displays the Abstract Syntax Tree (AST) structure
  of the selected grammar-tree node
• C is where the selected node's action code
  is displayed and edited. If this appears to break the
  no code, no script promise, rest assured that action-code
  is always optional
• D and E are used for testing the parser
  as described below

The following sections are a tutorial introduction that lead you through the
steps of creating a simple parser.

Managing Tokens

There are two kinds of token, literal and regex, that
the following discussion and examples will help you differentiate.
We create 2 literals and 1 regex that are
used in a rule later.

Literal Token Creation

To create a literal token select Tokens -> New literal from the main
menu as in Figure 3 below. Enter the literal's name (PLUS),
a comma, and the pattern (+) into the popped up dialog box and click
the OK button.
A token's name is used to refer to it from
rules, while the pattern describes its contents.
All instances of a particular literal token (during the parser's run)
have the same fixed content.

Now create another literal token
named MINUS with a - pattern (as in the second dialog box
in Figure 3).

Figure 3. Creating a literal token

Regex Token Creation

Figure 4 below shows how you can create a regex token.
Select Tokens -> New regex from the main menu,
and enter the token's name (NUMBER), a comma, and the
pattern (\\d+) into the dialog box and click OK.
You probably recognize the pattern as a Java
regular-expression
that matches numbers.

Figure 4. Creating a regex token

Observe that the pattern part in the dialogs above (for literal as well as regex tokens)
should be written exactly as if they were inside a String in a Java program
(without the surrounding quote marks).

There is not a great deal more to tokens, but if you would like to read the
fine print, check out the last part of
Editing the Grammar Tree.

Miscellaneous Token Operations

The main menu and toolbar also support several other operations. You can find which
rules use any particular token (Tokens -> Find token),
edit tokens (Tokens -> Edit token), and delete unused tokens (Tokens -> Delete token).

Token Libraries

Tokens tend to be reused within application domains, so VisualLangLab allows you to
create and use token libraries. These operations are invoked from the main menu
by selecting Tokens -> Import tokens and Tokens -> Export tokens,
or by using corresponding toolbar buttons.

Whitespace and Comments

You can specify the character patterns that separate adjacent tokens by invoking
Globals -> Whitespace from the main menu, and entering a regular expression
into the popped up dialog box. The default whitespace specification is "\\s+".

You can also provide a regular expression for recognizing comments in the input text.
Select Globals -> Comment from the main menu, and enter a regular expression
into the dialog box. There is no default value for this parameter.

Managing Rules

VisualLangLab represents rules as grammar-trees with distinctive icons
(as in Figure 1 above) and
a context-sensitive popup-menu.
This graphical depiction makes grammars comprehensible to a wider range of users.
The icons and textual annotations used in the grammar-trees are described below.

Node Icons

The table below lists the icons from which grammar-trees are constructed.

Non-terminals
	Root - used for the root node of every grammar tree
	Choice - used as the parent of a group of alternative items (any one of which occurs in the input)
	Sequence - used as the parent of a sequence of items which occur in the order specified
	RepSep - parent of a sequence of similar items that also uses a specified separator
	Reference - invokes another named parser
	Semantic predicate - succeeds or fails depending on the run-time value of an expression
Terminals
	Literal - matches a specified literal token
	Regexp - matches a specified regex token
Icon overlays
	Commit - displayed on top of a node that has the commit annotation
	Error: indicates an error in the associated node or rule

Node Annotations

Each grammar-tree node has characteristics (such as multiplicity) that are
represented as the node's annotations, and
are displayed as text beside each node's icon. You can change a node's
annotations by right-clicking the node and choosing the required settings
from the context-menu as in Figure 5 below.

Figure 5. Setting node annotations

The first annotation is a 1-character flag that indicates the node's multiplicity
-- the number of times the corresponding entity may occur in the parser's input.
You can see examples of its use everywhere in the built-in
Sample Grammars.
Multiplicity has one of the following values:

• 1 - exactly one occurrence
• ? - 0 or 1 occurrence
• * - 0 or more occurrences
• + - 1 or more occurrences
• 0 - the associated entity must not occur in the input (but see note below)
• = - the associated entity must occur in the input (but see note below)

Note: Observe that the last two values ("0" and "=") are actually commonly required
syntactic predicates
and have no influence on the structure of the
AST. The names not and guard are inspired
by functions of the same name and function in Scala's
Parsers.

The second annotation is the name of the entity. The value displayed depends on the
type of the node as described below.

• Root - the name of the parser rule itself
• Literal - the name of the literal token
• Regexp - the name of the regular-expression token
• Reference - the name of referred-to parser-rule
• Choice - the description (see below) if defined
• Sequence - the description (see below) if defined
• RepSep - the description (see below) if defined
• Semantic predicate - the description (see below) if defined

All icons have at least the two annotations described above. All other annotations,
described below, are optional. If any of the optional annotations are present, they are
enclosed within square brackets.

• commit - backtracking to optional parser clauses (at an upper level) will be
  prevented if this node is successfully parsed
• description - an optional user-assigned string (see below) that can be assigned
  to certain types of node
• drop - the node will not be entered into the AST. You can see examples of
  its use in the built-in ArithExpr Sample Grammars
• message - the node's associated error-message
• packrat - the parser-rule is a
  packrat parser
  (applicable only to a root-node)
• trace - the parser's use of the node will be logged at run-time

All node attributes can be reviewed and changed via the context-menu as shown in
Figure 5 above.

Creating Rules

The grammar-tree popup menu is the tool used for creating and editing grammar trees,
and is described fully in
Editing the Grammar Tree.
In the following example we get our feet just a little wet by composing a simple rule
with the tokens we created above.

First, add a Sequence node to the grammar-tree by right-clicking the root node
() and selecting
Add -> Sequence from the popup menu as shown on the left side of Figure 6 below.
A sequence icon
() is added to the root,
as on the right of the figure.

Figure 6. Adding a sequence node

Then perform the following steps:

• right-click the newly added sequence node
  () and select Add -> Token.
  This will bring up a dialog containing a list of token names.
  Select NUMBER and click the dialog's OK button.
  A regex icon () is added
  to the sequence node
• right-click the sequence node again and select Add -> Choice from the popup menu.
  This should add a Choice node icon
  ()
  to the sequence node
• right-click the newly created choice node ()
  and select Add -> Token.
  Select PLUS in the dialog box and click OK.
  A literal icon ()
  is added to the choice node.
  Repeat this action once more, and add the MUNUS token to the choice node
• repeat the first step above to add another NUMBER to the sequence node

You're done! If your parser does not look like the one in Figure 7 below,
use Edit from the grammar-tree's context menu to make the required changes.

Figure 7. Your first visual parser

The text displayed in the panel to the right of the grammar-tree is the
AST of the selected node,
and so depends on which icon you clicked last.

Miscellaneous Rule Operations

The main menu and toolbar also support several other operations. You can find which
other rules refer any particular rule (Rules -> Find rule),
rename rules (Rules -> Rename rule), and delete unused rules (Rules -> Delete rule).

Saving the Grammar

A grammar can be saved to a file by invoking File -> Save from the main menu.
Grammars are stored in XML files with a .vll suffix.
The contained XML captures the structure of the rules, the token definitions, and
other details, but no generated code of any kind.
The XML is quite intuitive and you can use XSLT or a similar technology to
transform it into another format
(a grammar for another tool, or code of some sort, for example) if required.

A saved grammar can be read back into the GUI by invoking File -> Open from
the main menu. This is useful for review, further editing, or testing.
The API can also load a saved grammar,
and regenerate the parser for use from a client program.

Testing your Parser

Testing is really simple. Key in the test input under
Parser Test Input (as at "A" in Figure 8 below),
click the Parse input button (under the red rectangle),
and validate the output that appears under Parser Log
(at "C" in the figure).
You don't have to write any code, use any other tools, or do anything else.

Figure 8. Testing your parser

The figure shows the result of testing the parser with "3 + 5"
as the input.
The Parser Log are should contain the following text:

    Generating parsers ... (10 ms)
    Parsing ... (3 chars in 0 ms), result follows:
    <u>Array(3, Pair(0, +), 5)</u>

The first two lines contain performance information that is safely ignored.
The last line (underlined) is the parser's result. The result is an
AST
with a predefined structure shown under Parse Tree (AST) Structure.
Since the test input entered was "3 + 5", we know that the result is correct.
However, real-life parsers are too complex for manual testing, so VisualLangLab supports
several approaches to automated testing that are described online in
Testing Parsers.

That brings us to the end of this quick example. If you feel that the result of
parsing "3 + 5" should be 8 instead of Array(3,Pair(0,+),5) check out
the section ArithExpr with action-code in
Sample Grammars.

The Parse-Tree (or AST)

The terms parse-tree and
Abstract Syntax Tree
(or just AST) are used interchangeably to mean the

structure of information gathered during the parsing process.
VisualLangLab displays the AST of the selected grammar-tree node in the text area
under Parse Tree (AST) Structure as seen in Figure 7 above.
ASTs are constructed from mutually nested instances of certain standard Scala types,
so a rudimentary understanding of their main features is useful.
Examples and more details can be found online at
AST and Action Code or
in the downloaded zip.

Action Code

Action-code (or just actions) are Scala or Javascript

functions associated with grammar-tree nodes, and entered into the text
area under Action Code ("C" in Figure 2 above).
It is never necessary to have action code embedded in the
grammar — you can always remove all code into an application program that invokes
the parser via the API, and then processes the
AST returned by it.
You can see examples of action-code in the ArithExpr with action-code
sample grammar, and more details can be found online at
AST and Action Code
or in the downloaded zip.

Using the API

The VisualLangLab API enables applications written in Scala (and Java with
some awkwardness) to use parsers created with the GUI. The API is very small,
and contains the types and functions required to perform the following
operations.

• load a parser from a saved grammar-file
• parse a string using the parser
• test the result, and retrieve the AST or error information

More details and examples can be found online at
Using the API.

Sample Grammars

To enable users to quickly gain hands-on experience with VisualLangLab grammars,
the tool contains some built-in sample grammars. These samples can be reviewed,
tested, modified, and saved just like any other grammar created from scratch.
To open a sample grammar select Help -> Sample grammars from the main
menu, and choose one of the samples shown as in Figure 9 below.

Figure 9. Sample grammars available

More information about these samples can be found online at
Sample Grammars or
in the downloaded zip file.

Differences from Scala's Combinators

The class diagram
in Figure 10 below shows VisualLangLab's relationship with Scala's parser combinators.

Figure 10. Relationship With Scala parser combinators

However, the tool's classes override and augment a few key functionalities of the
underlying Scala classes, so the behavior and AST of VisualLangLab's parsers
is significantly different in certain ways.

• The Literal and Regex node types use an internal
  lexical analyzer,
  and do not match input text in the same way
  as RegexParsers's
  literal() and regex() methods
• The Sequence and Choice node types use
  Parsers's
  ~ and | combinators internally, but have different return types

More details can be found online
at Relationship with Scala Parser Combinators,
or in the downloaded zip.

Conclusion

The article introduces readers to parser development using the completely visual
tool VisualLangLab.
Its features make it an effective prototyping environment and a training tool,
and will hopefully be a useful addition to any developer's skills.

Resources (or References)

• VisualLangLab - The VisualLangLab web-site

Attachment	Size
VLL_add-sequence.png	12.26 KB
VLL_GrammarIconCommitMark.gif	174 bytes
VLL_first-parser.png	19.76 KB
VLL_GrammarIconChoice.gif	500 bytes
VLL_GrammarIconErrorMark.gif	174 bytes
VLL_GrammarIconLiteral.gif	881 bytes
VLL_GrammarIconReference.gif	872 bytes
VLL_GrammarIconRegex.gif	893 bytes
VLL_GrammarIconRepSep.gif	870 bytes
VLL_GrammarIconRoot.gif	282 bytes
VLL_GrammarIconSemPred.gif	95 bytes
VLL_GrammarIconSequence.gif	202 bytes
VLL_grammar-tree-examples.png	9.61 KB
VLL_literal-creation.png	22.63 KB
VLL_regex-creation.png	22.21 KB
VLL_RelationshipWithScalaParserCombinators.png	29.51 KB
VLL_SampleGrammar1.png	9.21 KB
VLL_setting-annotations.png	25.52 KB
VLL_testing-parser.png	23.79 KB
VLL_vll-gui.png	17.06 KB