util.pm.svn-base

这是一个DFA简化和生成LL(1)分析表的程序,自动生成表格及图形

# t/Util.pm

package t::Util;

use strict;
use warnings;

#use Data::Dumper::Simple;
use base 'Exporter';
use LL1;

our @EXPORT_OK = qw(
    parse_grammar
    dump_fsets
    dump_LL1_table
);

sub parse_grammar ($) {
    my $grammar = shift;
    $grammar =~ s/^[\n\s]+|[\n\s]+$//gso;
    my @rules = split /\s*\n+\s*/, $grammar;
    my ($startrule, %rules);
    for (@rules) {
        if (/^(\w+)\s*:\s*(.*)/) {
            my ($rulename, $choices) = ($1, $2);
            $startrule = $rulename if !$startrule;
            my @list = split /\s*\|\s*/, $choices ;
            #warn Dumper(@list);
            if (@list) {
                map { $_ = [ split /\s+/, $_ ]; } @list;
            } else {
                @list = [];
            }
            if ($choices =~ /\|\s*$/) {
                push @list, [];
            }
            $rules{$rulename} = \@list;
        } else {
            die "Syntax error in grammar: $_";
        }
    }
    { startrule => $startrule, rules => \%rules };
}

# dump out First/Follow sets returned by subs first_sets, follow_sets, and etc.
sub dump_fsets ($) {
    my $fsets = $_[0];
    my $out = '';
    for my $symbol (sort keys %$fsets) {
        my $set = $fsets->{$symbol};
        my @elems = $set->elements;
        map { if ($_ eq '/\Z/') { $_ = '$'; } } @elems;
        @elems = sort @elems;
        $out .= "$symbol: @elems\n";
    }
    $out;
}

# dump out the LL(1) parsing table generated by &LL1::Table::LL1_table
sub dump_LL1_table ($) {
    my $table = shift;
    my $str = '';
    my $eof = LL1::eof;
    for my $N (sort keys %$table) {
        $str .= "$N\n";
        my $line = $table->{$N};
        my @tokens = keys %$line;
        map { if ($_ eq $eof) { $_ = '$' } } @tokens;
        $line->{'$'} = $line->{$eof};
        for my $T (sort @tokens) {
            if ($T eq $eof) { $T = '$' }
            $str .= "  $T: $N -> @{$line->{$T}}\n";
        }
    }
    $str =~ s/->\s+\n/->\n/gs;
    $str;
}

1;