LLg 1.07 Alpha

LLg is a recursive descent parser generator.

SYNOPSIS

use LLg;
@tokens = (
ADDOP => [-+],
LEFTP => [(],
RIGHTP => [)],
INTEGER => 0|[1-9][0-9]*,
);
$reader = Lex->new(@tokens);
$ADDOP->debug;

$expr = And->new(($factor, Any->new($ADDOP, $factor)),
sub {
shift(@_);
my $result = shift(@_);
my ($op, $integer);
while ($#_ >= 0) {
($op, $integer) = (shift(@_), shift(@_));
if ($op eq +) {
$result += $integer;
} else {
$result -= $integer;
}
}
$result;
});
$factor = Or->new($INTEGER, $parexp);
$parexp = And->new($LEFTP, $expr, $RIGHTP,
sub { $_[2] });

print STDERR "Type your arithmetic expression: ";
print "Result: ", $expr->next, "n";

Creating parsers by hand is tedious even for simple languages. This activity can be automated by parser-generators - yacc is a well-known example. But using such tools is quite demanding and requires a reasonable knowlege of the principles of syntactic analysis.

LLg is a set of Perl5 packages which allow the generation of recursive descent parsers for context-free grammars.

LLg is provided with the packages Lex and Token which are object-based. The use of these packages presupposes that you know how to write a BNF grammar and that you know (just a little) about programming in Perl.

Specifying the parser does not require any extension to Perl syntax. The specification is carried out entirely in standard Perl, be it definition of tokens, syntactic rules or associated semantic actions. LLg allows the easy specification of translation schemes, that is parsers for which the semantic action is given by actions directly associated with each production.

The packages Token and LLg allow respectively the definition of objects corresponding to terminals (tokens) and non-terminals of the grammar. Lex handles the reading and "eating" of tokens in the input stream.

Before using these packages you need to define a BNF grammar without left recursion (an LL(1) grammar). Given this, making the parser consists in:

1. create a lexical analyser by specifying the terminals,
2. create a parser (syntactic analyser) by creating a LLg object (or, more precisely, one of the packages which inherits from LLg) for each non-terminal.
3. define the semantics by associating an anonymous function with each LLg object.

Take as an example arithmetic expressions having only + and - as operators. In the Camel book we find the following grammar:

expr ::= factor { ADDOP factor }
ADDOP ::= + | -
factor ::= NUMBER | ( expr )

Creating the parser for this language involves defining a lexical analyser and a syntactic analyser.

The lexical analyser is defined thusly:

@tokens = (
ADDOP => [-+],
LEFTP => [(],
RIGHTP => [)],
INTEGER => [1-9][0-9]*,
);
$reader = Lex->new(@tokens);

The argument of the method new() is a list of pairs: the identity of the terminal and the corresponding regular expression. Each such pair leads to the creation of a terminal of type Token.

The package LLg is the base package of a set : And, Any, Do, Hook, Opt, Or. These packages allow the creation of the different types of rules normally found in context-free grammars. We use a prefix notation with the following equivalences.

A | B Or->new($A, $B) symbol A or symbol B


A B And->new($A, $B) symbol A followed by symbol B


{ A } Any->new($A) arbitrary number of A


[ A ] Opt->new($A) zero or one occurrence of A

The rules in our example are given by creating the following objects:

$expr = And->new(($factor, Any->new($ADDOP, $factor));
$factor = Or->new($NUMBER, $parexp);
$parexp = And->new($LEFTP, $expr, $RIGHTP);

The arguments of the method new() are references to LLg or Token objects. (The written order of the rule has no significance, since scalars can be references before they are assigned a value. These references are resolved when each object is used. As the example shows, references can be obtained to the objects returned by a rule.)

The semantics is defined by putting an anonymous function at the end of the list of object references. The anonymous function uses information associated with the objects. This information is transmitted by positional parameters (the array @_). The nth argument designates the result of the nth parameter of the method new(). Information returned by the function is associated with the object and is transmitted by means of positional parameters wherever the object is used. In our example we will have:

$expr = And->new(($factor, Any->new($ADDOP, $factor)),
sub {
shift(@_);
my $result = shift(@_);
my ($op, $integer);
while ($#_ >= 0) {
($op, $integer) = (shift(@_), shift(@_));
if ($op eq +) {
$result += $integer;
} else {
$result -= $integer;
}
}
$result;
});
$factor = Or->new($INTEGER, $parexp);
$parexp = And->new($LEFTP, $expr, $RIGHTP,
sub { $_[2] });

print STDERR "Type your arithmetic expression: ";
print "Result: ", $expr->next, "n";

When an integer is recognised it is returned by the anonymous function associated with the object $factor. This returned information (or, more precisely, synthesised, since it comes from a a terminal and is transmitted to non-terminals) is also available in the anonymous function associated with the object $expr. The information returned by the following object is used to calculate the value of the arithmetical expression.

The analyser is started up by applying the method next() to the axiom of the grammar:

$expr->next;

By default the input for analysis is read from the standard input. The example parser analyses and interprets individual expressions typed in at the terminal. The example calculator.pl delivered with the LLg package shows how to create an input loop allowing reading and interpretation of arbitrary many expressions.
The parser generator can be used for other purposes than the analysis of a character stream. Given that the packages Lex, LLg and Token, it is perfectly possible to define terminals which are objects i.e. instances of a class other than Token. Each new package defining terminals ought at least to have the methods status() and next() - see vonkoch.pl as an example.