Ein EBNF Parser in Perl
EBNF-Grammatiken (erweiterte Backus-Naur-Form) dienen der Beschreibung
von Sprachen und werden im Compilerbau, aber auch in vielen anderen
Bereichen der Informatik eingesetzt. Beschreibt man eine Sprache
in EBNF, so kann quasi "automatisch" ein Parser konstruiert werden.
#!/usr/bin/perl -w
use strict;
# [expression] ::= [term] | [term] OR [expression]
# [term] ::= [factor] | [factor] AND [term]
# [factor] ::= ( [expression] ) | NOT [expression] | [string]
# [string] ::= ".*" | \w+
# [literal] ::= '(' | ')' | 'OR' | 'AND' | 'NOT'
sub literal($);
sub expression();
sub term();
sub factor();
sub string();
sub error($);
sub parse();
my $tab=0;
my $TAB=" ";
my $error;
parse;
exit 0;
sub literal ($) {
$tab++;
my $lit = $_[0];# The literal string to be consumed.
my $test = s/^\s*\Q$lit\E\s*//;
if ($test) {
#print $TAB x $tab,"literal $lit\n";
$tab--;
return 1;
} else {
$tab--;
return 0;
}
}
sub expression () {
$tab++;
term;
expression if literal 'OR';
print $TAB x $tab,"expression $_\n";
$tab--;
}
sub term () {
$tab++;
factor;
term if literal 'AND';
print $TAB x $tab,"term $_\n";
$tab--;
}
sub factor () {
$tab++;
if ( literal '(' ) {
expression;
error 'missing )' unless literal ')';
} elsif ( literal 'NOT' ) {
error 'empty negation' if $_ eq '';
expressionss00
} else {
string;
}
print $TAB x $tab,"factor $_\n";
$tab--;
}
sub string () {
if (s/^\s*(?:"([^"]+)"|(\w+))\s*//) {
$tab++;
if (defined $1) {
#print $TAB x $tab,"string $1\n";
$tab--;
return $1;
} elsif (defined $2) {
#print $TAB x $tab,"string $2\n";
$tab--;
return $2;
}
$tab--;
}
}
sub error ($) {
my $msg = $_[0];
warn "$msg: $_\n";
}
sub parse () {
while ( ) {
chomp;
expression;
error 'illegal input' if $_ ne '';
}
}