What is Meta-S?
Meta-S is a visual grammar development system,
formerly known as PAISLEI, evolved from research in adaptive parsing. It allows for the controlled development and debugging of grammars written in either the Language for Pattern Matching or
A-BNF (Adaptive BNF), and for the automated creation of a C++ class that can be compiled once the grammar is completely
satisfactory. Meta-S grammars, since they can contain adaptive features, allow for the development and debugging of context-sensitive grammars
without a single line of developer-supplied C++
code.
Why
Meta-S?
Consider for a moment a classical example of a pair of ambiguous sentences:
Fruit flies like a banana. Time flies like
an arrow.
Imagine trying to parse the above with a standard parser, without writing any code to deal with the semantic shift that occurs as "flies" shifts from being a noun to a verb. Even a human reader may scratch his or her head trying to parse the above sentence pair. Such sentences are the stuff that party chat is made of amongst parsing theorists.
What about this, though?
Flies is a noun. Fruit flies like a banana. Flies is now a verb. Time flies like an arrow.
All ambiguity is now gone for the human reader—the punch line has been removed from the party chat. Can a parser developer write an
LALR(k) or LL(k) grammar, using available tools, that does not invoke ad hockery in the attached code? No. Why not? To parse the above four sentences, some form of context-sensitive grammar formalism is needed, since the context of the second and fourth sentences is dependent on the disambiguating antecedents provided by the first and third sentences.
One of the problems with ad hockery is that it interrupts the flow of grammar
development. As soon as even one line of C++ is necessary to correctly parse input, it becomes very difficult to get the full benefits of a visual grammar
development system. By providing a formalism that allows a grammar to change its rules during the parse itself—the need for
ad hockery is greatly reduced.
Meta-S can parse the fruit flies and more. Suppose we have a small markup language that works something like this:
<define-balanced-tag:document>
<define-tag:end>
<document>
This is the document.
</document>
<end>
With Meta-S, a grammar can be devised that causes <document> to have to be
balanced with </document> and accepts <end> on its own, even though the tags are defined within the input being parsed itself! What other parser
generator can do that without a single line of attached code, without a single hand-written symbol table?
There is no such thing as something for nothing, as we will shortly see in the "Brief
History" of adaptive grammar theory that follows, and adaptive grammar development is therefore for the solidly grounded parsing
expert— but Meta-S takes much of the toil and turns it into play. You may even find yourself writing grammars in ways that you didn't think possible. Like all "new" things, this exploration will surely bite once or twice until you tame it, but isn't that what innovation is about—being on the cutting edge? Meta-S is about taming the frontier of parsing.
Welcome to adaptive grammar theory in practice—welcome to Meta-S.
In the late 1960's, van Wijngaarden introduced a new grammar type known as the two-level grammar, and this type of grammar still bears his name. Although researchers such as Lutz Wegner followed up on two-level grammars,
such grammars never caught the popular imagination. They did, however, lead to a different way of viewing what was possible from grammars.
In the late 1980's and into the early 1990's, researchers such as Henning
Christiansen, Boris Burshteyn, John Shutt, and Pierre Boullier showed an interest in adaptive (or modifiable) grammars. Shutt formally semi-formally defined the adaptive grammar model as follows:
"A grammatical formalism that allows rule sets (a.k.a. sets of production rules) to be explicitly manipulated within a
grammar."
Shutt further divided adaptive grammars into two families: imperative (those
that adapt over time) and declarative (those that adapt over space). In what appears to be more or less be the last word at the time on this track of
research, Boullier declared in 1994:
"A lot of related problems should still be investigated. What is the compared
performance (for both a theoretical and practical point of view) of a dynamic parser versus a more usual method? What kind of error recovery and repair
strategies will work with dynamic grammars? [...] If it appears that dynamic grammars constitute a valuable practical concept, the way the rule engine is
actually written should be improved in a much more descriptive manner. [...] The same ideas have been used to implement a dynamic scanner but
its integration into a single system is not yet done. We suspect that this unifying
framework will facilitate the emergence of other applications."
The §-Calculus, the formalism behind Meta-S Grammars, took up that torch. Although adaptive features were implemented in the
Language for Pattern Matching (the engine behind Meta-S grammars) from a very early stage, they
were not made public knowledge until they had been studied
sufficiently. With the addition of a visual front-end to the Language for Pattern Matching (a
front-end inspired by the groundbreaking IDE of Visual Parse++), it became possible to test adaptive grammars experimentally and iteratively iron out
certain folds in the fabric of adaptive grammar theory.
Since adaptive grammars are Type 1 in the Chomsky Hierarchy (that is, they can be context-sensitive), it is possible to write a grammar
that is not known to terminate on arbitrary input. The Meta-S development environment,
however, provides a means of catching the potential danger spots in such grammars in the bud, during debugging and development, in much the same
way a programming language IDE allows programmers to write programs in C++ (a Turing Powerful language) that have decidable results on arbitrary
input.
Grammar Development under Win32 Operating Systems (95, 98, NT 4.0, 2000)
If your development environment supports 32-bit Microsoft operating system
Portable Executables for the Intel family of processors (or their clones), you
can develop an adaptive grammar using the Meta-S development environment.
Generated Parsers Deployable on Any System that has an ANSI/ISO C++
Compiler
If the platform has a standard C++ compiler, you can use your final grammar
class on that platform. Nothing simpler than that.
Classes may be Used for Simple Pattern Matching
If all you need is a regular expression window on a search dialog box, you can
simply do this:
#include <lpm_mm.hpp>
// .. your code here
CLpm rule = "<RE(" + UserSuppliedRegularExpression + ")>";
if(rule.Match(TextToBeSearched))
{
// the user supplied regular expression has found a match
}
Parsers can be Compiled to Accept UNICODE Input
Is the parser you've developed to be deployed in a system that uses UNICODE
strings? Simply make sure all literal strings are wrapped in the SHU_UT(string)
macro, define SHU_UNICODE before you compile, and everything else is taken
care of.
Multiple Parsers within One System
If your HTML parser must jump to parsing JavaScript, there is no problem,
since you can have multiple parsing classes within the same compile, and you
can even call one parser while in the middle of another parse, as long as all
the parsers are in the same thread.
Adaptive, Predicated, Backtracking, Recursive Descent
The engine behind Meta-S is a backtracking LL(k) recursive descent parser.
This comes with some caveats, but adaptive features and predication can often
smooth over some of the known issues of LL(k) grammars as compared to the
more general LALR(k) model. If linear time and generality are
necessary— Visual Parse++ is the answer. If you want to knock together a
grammar-only parser for a specialized scripting language and you know you are up to the
challenge of the cutting-edge technology of Meta-S, it may be the right tool. If
natural language or context-sensitive parsing is on your to-do list, Meta-S is
certainly the horse to carry the load.
Trees Automatically Produced During Parse
The C++ framework builds trees during a parse without your having to write a
single line of code. Turning this feature off is as simple as inserting one
statement. You can even fine-tune a grammar so that tree nodes are only
created for those productions that need them.
Multiple Parsing Events for Fine-Tuning of Parsing Behavior
With automatic trees and features that allow for context sensitivity, you may
find yourself relying on reduction-invoked code much less than with other tools, but Meta-S allows for code to be attached to more than just reductions.
When was the last time you had to use a Swiss army knife? Even so, some still carry one.
Grammars Can be Written in Extended BNF Form
Most grammar developers are familiar with EBNF, and Meta-S takes this into
account. If absolute fine-tuned control is necessary, there is always the
Language for Pattern Matching, the heart of Meta-S grammars. Productions can
be in either, or both. It's entirely up to the needs of the developer.
Color Syntax Highlighting
Compare:
to this:
Color syntax highlighting speaks for itself. In Meta-S, it is fully customizable to the preference of the logged-on Windows user.
Grammar Debugging
Profiler
Intuition about where the most time is spent in a grammar takes quite a while
to hone. The profiler in Meta-S takes away some of the guess work and lets you see if the optimization you want to try out really makes things parse more
quickly when applied against your typical case test data. No other visual parsing development system will tell you how quickly a grammar does its
work, or how many times each production hits and misses.
Tree, Stack, and Sequence Views
In the spirit of Visual Parse++, a tool that has made visual parsing a standard
in a development world that has grown accustomed to visual development tools, Meta-S will give you this:
instead of the numerous pages of trace logs needed to convey that information.
Single Stepping
Debugging a grammar, just as with debugging C++ code or any programming
language, takes time, effort, skill, and patience. Being able to single step through suspect portions of a grammar and examine the entire state of the
grammar one step at a time in order to isolate idiosyncrasies in a grammar saves time, reduces effort, puts skill to its best use, and is less trying on
one's patience than reading through a trace log.
Break Points
If you suspect the flaws in a grammar occur in a specific production, in a
specific clause of a production, or even if you know only that they show up when the grammar reaches the seventy-third line of an input document, why
waste time on what you know works when all you care about is that one portion of the grammar? Simply set a breakpoint, and skip what works.
Various Input Views
Marquee, line view, or flat ASCII—Meta-S presents the input data view that
suits the data best by presenting various views of the input that you can switch between—leaving you to decide.
C++ Reduction Action Code Simplified
Clean Access to Lexemes and other Reduction Instance Data
What happens when a production is changed so much that absolute position of
a lexeme in a production changes? In other parsers—this means changing C++. Meta-S grammars allow for named lexemes, and reference in the C++ by the
name, rather than position of the lexeme, however—so no code will be effected.
Synchronization of Grammar Project with Outside Changes to Generated Code
As you debug your parser, you may find that you wish to add, remove, or edit
productions. What about all those tweaks that were made while in your favorite C++ development environment? If you follow a few guidelines and don't insert
C++ code into the generated grammar class where it doesn't belong—Meta-S will allow you to synchronize those changes with the grammar
specification project, and no time will be lost keeping the two files in synch. An indicator on
the Meta-S program will flash whenever the two files need synchronization.
Pierre Boullier, "Dynamic Grammars and Semantic
Analysis," INRIA Research Report 2322, August 1994.
Quinn Tyler Jackson & Christopher Michael Langan, "Adaptive Predicates in Empty-Start Natural Language
Parsing," Noesis-E, Vol. 1
No. 6, Nov. 2001.
Quinn Tyler Jackson, "An Introduction to PAISLEI,"
Noesis-E, Vol. 1 No. 2, March 2001.
Quinn Tyler Jackson, "PAISLEI:
Towards Grammar-Only Parsing of C++."
