--- /dev/null
+++ b/t/reproducibility.t
@@ -0,0 +1,412 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use Parse::Yapp;
+use Text::Diff;
+
+BEGIN { $| = 1; print "1..1\n"; }
+
+open( my $inp, 'Calc.yp' );
+my $grammar = join '', <$inp>;
+close $inp;
+
+my $parser = new Parse::Yapp( input => $grammar );
+
+my $output_new = $parser->Output( classname => 'Calc' );
+$output_new =~ s/(Parse::Yapp version )\d+\.\d+/$1<version>/;
+$output_new =~ s/(yyversion => ')[^']+'/$1<version>'/;
+
+my $output_old = join '', <DATA>;
+close DATA;
+
+my $diff = diff \$output_old, \$output_new;
+if( $diff ) {
+ print "not ok 1\n";
+ print "Non-zero diff:\n" . $diff;
+ exit(1);
+} else {
+ print "ok 1\n";
+}
+
+__DATA__
+####################################################################
+#
+# This file was generated using Parse::Yapp version <version>.
+#
+# Don't edit this file, use source file instead.
+#
+# ANY CHANGE MADE HERE WILL BE LOST !
+#
+####################################################################
+package Calc;
+use vars qw ( @ISA );
+use strict;
+
+@ISA= qw ( Parse::Yapp::Driver );
+use Parse::Yapp::Driver;
+
+
+
+sub new {
+ my($class)=shift;
+ ref($class)
+ and $class=ref($class);
+
+ my($self)=$class->SUPER::new( yyversion => '<version>',
+ yystates =>
+[
+ {#State 0
+ DEFAULT => -1,
+ GOTOS => {
+ 'input' => 1
+ }
+ },
+ {#State 1
+ ACTIONS => {
+ '' => 2,
+ "(" => 3,
+ "-" => 4,
+ "\n" => 5,
+ 'NUM' => 6,
+ 'VAR' => 7,
+ 'error' => 8
+ },
+ GOTOS => {
+ 'exp' => 9,
+ 'line' => 10
+ }
+ },
+ {#State 2
+ DEFAULT => 0
+ },
+ {#State 3
+ ACTIONS => {
+ "(" => 3,
+ "-" => 4,
+ 'NUM' => 6,
+ 'VAR' => 7
+ },
+ GOTOS => {
+ 'exp' => 11
+ }
+ },
+ {#State 4
+ ACTIONS => {
+ "(" => 3,
+ "-" => 4,
+ 'NUM' => 6,
+ 'VAR' => 7
+ },
+ GOTOS => {
+ 'exp' => 12
+ }
+ },
+ {#State 5
+ DEFAULT => -3
+ },
+ {#State 6
+ DEFAULT => -6
+ },
+ {#State 7
+ ACTIONS => {
+ "=" => 13
+ },
+ DEFAULT => -7
+ },
+ {#State 8
+ ACTIONS => {
+ "\n" => 14
+ }
+ },
+ {#State 9
+ ACTIONS => {
+ "*" => 15,
+ "+" => 16,
+ "-" => 17,
+ "/" => 18,
+ "\n" => 19,
+ "^" => 20
+ }
+ },
+ {#State 10
+ DEFAULT => -2
+ },
+ {#State 11
+ ACTIONS => {
+ ")" => 21,
+ "*" => 15,
+ "+" => 16,
+ "-" => 17,
+ "/" => 18,
+ "^" => 20
+ }
+ },
+ {#State 12
+ ACTIONS => {
+ "^" => 20
+ },
+ DEFAULT => -13
+ },
+ {#State 13
+ ACTIONS => {
+ "(" => 3,
+ "-" => 4,
+ 'NUM' => 6,
+ 'VAR' => 7
+ },
+ GOTOS => {
+ 'exp' => 22
+ }
+ },
+ {#State 14
+ DEFAULT => -5
+ },
+ {#State 15
+ ACTIONS => {
+ "(" => 3,
+ "-" => 4,
+ 'NUM' => 6,
+ 'VAR' => 7
+ },
+ GOTOS => {
+ 'exp' => 23
+ }
+ },
+ {#State 16
+ ACTIONS => {
+ "(" => 3,
+ "-" => 4,
+ 'NUM' => 6,
+ 'VAR' => 7
+ },
+ GOTOS => {
+ 'exp' => 24
+ }
+ },
+ {#State 17
+ ACTIONS => {
+ "(" => 3,
+ "-" => 4,
+ 'NUM' => 6,
+ 'VAR' => 7
+ },
+ GOTOS => {
+ 'exp' => 25
+ }
+ },
+ {#State 18
+ ACTIONS => {
+ "(" => 3,
+ "-" => 4,
+ 'NUM' => 6,
+ 'VAR' => 7
+ },
+ GOTOS => {
+ 'exp' => 26
+ }
+ },
+ {#State 19
+ DEFAULT => -4
+ },
+ {#State 20
+ ACTIONS => {
+ "(" => 3,
+ "-" => 4,
+ 'NUM' => 6,
+ 'VAR' => 7
+ },
+ GOTOS => {
+ 'exp' => 27
+ }
+ },
+ {#State 21
+ DEFAULT => -15
+ },
+ {#State 22
+ ACTIONS => {
+ "*" => 15,
+ "+" => 16,
+ "-" => 17,
+ "/" => 18,
+ "^" => 20
+ },
+ DEFAULT => -8
+ },
+ {#State 23
+ ACTIONS => {
+ "^" => 20
+ },
+ DEFAULT => -11
+ },
+ {#State 24
+ ACTIONS => {
+ "*" => 15,
+ "/" => 18,
+ "^" => 20
+ },
+ DEFAULT => -9
+ },
+ {#State 25
+ ACTIONS => {
+ "*" => 15,
+ "/" => 18,
+ "^" => 20
+ },
+ DEFAULT => -10
+ },
+ {#State 26
+ ACTIONS => {
+ "^" => 20
+ },
+ DEFAULT => -12
+ },
+ {#State 27
+ ACTIONS => {
+ "^" => 20
+ },
+ DEFAULT => -14
+ }
+],
+ yyrules =>
+[
+ [#Rule 0
+ '$start', 2, undef
+ ],
+ [#Rule 1
+ 'input', 0, undef
+ ],
+ [#Rule 2
+ 'input', 2,
+sub
+#line 17 "unkown"
+{ push(@{$_[1]},$_[2]); $_[1] }
+ ],
+ [#Rule 3
+ 'line', 1,
+sub
+#line 20 "unkown"
+{ $_[1] }
+ ],
+ [#Rule 4
+ 'line', 2,
+sub
+#line 21 "unkown"
+{ print "$_[1]\n" }
+ ],
+ [#Rule 5
+ 'line', 2,
+sub
+#line 22 "unkown"
+{ $_[0]->YYErrok }
+ ],
+ [#Rule 6
+ 'exp', 1, undef
+ ],
+ [#Rule 7
+ 'exp', 1,
+sub
+#line 26 "unkown"
+{ $_[0]->YYData->{VARS}{$_[1]} }
+ ],
+ [#Rule 8
+ 'exp', 3,
+sub
+#line 27 "unkown"
+{ $_[0]->YYData->{VARS}{$_[1]}=$_[3] }
+ ],
+ [#Rule 9
+ 'exp', 3,
+sub
+#line 28 "unkown"
+{ $_[1] + $_[3] }
+ ],
+ [#Rule 10
+ 'exp', 3,
+sub
+#line 29 "unkown"
+{ $_[1] - $_[3] }
+ ],
+ [#Rule 11
+ 'exp', 3,
+sub
+#line 30 "unkown"
+{ $_[1] * $_[3] }
+ ],
+ [#Rule 12
+ 'exp', 3,
+sub
+#line 31 "unkown"
+{
+ $_[3]
+ and return($_[1] / $_[3]);
+ $_[0]->YYData->{ERRMSG}
+ = "Illegal division by zero.\n";
+ $_[0]->YYError;
+ undef
+ }
+ ],
+ [#Rule 13
+ 'exp', 2,
+sub
+#line 39 "unkown"
+{ -$_[2] }
+ ],
+ [#Rule 14
+ 'exp', 3,
+sub
+#line 40 "unkown"
+{ $_[1] ** $_[3] }
+ ],
+ [#Rule 15
+ 'exp', 3,
+sub
+#line 41 "unkown"
+{ $_[2] }
+ ]
+],
+ @_);
+ bless($self,$class);
+}
+
+#line 44 "unkown"
+
+
+sub _Error {
+ exists $_[0]->YYData->{ERRMSG}
+ and do {
+ print $_[0]->YYData->{ERRMSG};
+ delete $_[0]->YYData->{ERRMSG};
+ return;
+ };
+ print "Syntax error.\n";
+}
+
+sub _Lexer {
+ my($parser)=shift;
+
+ $parser->YYData->{INPUT}
+ or $parser->YYData->{INPUT} = <STDIN>
+ or return('',undef);
+
+ $parser->YYData->{INPUT}=~s/^[ \t]//;
+
+ for ($parser->YYData->{INPUT}) {
+ s/^([0-9]+(?:\.[0-9]+)?)//
+ and return('NUM',$1);
+ s/^([A-Za-z][A-Za-z0-9_]*)//
+ and return('VAR',$1);
+ s/^(.)//s
+ and return($1,$1);
+ }
+}
+
+sub Run {
+ my($self)=shift;
+ $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
+}
+
+my($calc)=new Calc;
+$calc->Run;
+
+1;
Description: sorting hash keys to remove non-determinism from the generated
parsers.
Bug:
https://rt.cpan.org/Public/Bug/Display.html?id=122977
Bug-Debian:
http://bugs.debian.org/903979
Forwarded: no
Author: Andrius Merkys <andrius.merkys@gmail.com>
Last-Update: 2018-07-19
--- a/lib/Parse/Yapp/Driver.pm
+++ b/lib/Parse/Yapp/Driver.pm
@@ -159,7 +159,7 @@
sub YYExpect {
my($self)=shift;
- keys %{$self->{STATES}[$self->{STACK}[-1][0]]{ACTIONS}}
+ sort keys %{$self->{STATES}[$self->{STACK}[-1][0]]{ACTIONS}}
}
sub YYLexer {
--- a/lib/Parse/Yapp/Grammar.pm
+++ b/lib/Parse/Yapp/Grammar.pm
@@ -340,7 +340,7 @@
$reachable = _Reachable($rules,$nterm,$term,$ufrules,$ufnterm);
$$grammar{TERM}{chr(0)}=undef;
- for my $sym (keys %$term) {
+ for my $sym (sort keys %$term) {
( exists($$reachable{$sym})
or exists($values->{PREC}{$sym}) )
and do {
@@ -352,7 +352,7 @@
}
$$grammar{NTERM}{'$start'}=[];
- for my $sym (keys %$nterm) {
+ for my $sym (sort keys %$nterm) {
exists($$reachable{$sym})
and do {
exists($values->{NULL}{$sym})
--- a/lib/Parse/Yapp/Lalr.pm
+++ b/lib/Parse/Yapp/Lalr.pm
@@ -132,7 +132,7 @@
}
#Prepare Actions
- for (keys(%{$$states[$stateno]{ACTIONS}})) {
+ for (sort keys(%{$$states[$stateno]{ACTIONS}})) {
my($term,$action)=($_,$$states[$stateno]{ACTIONS}{$_});
$term eq chr(0)
@@ -220,7 +220,7 @@
exists($$states[$stateno]{GOTOS})
and do {
$text.= "\n";
- for (keys(%{$$states[$stateno]{GOTOS}})) {
+ for (sort keys(%{$$states[$stateno]{GOTOS}})) {
$text.= "\t$_\tgo to state $$states[$stateno]{GOTOS}{$_}\n";
}
};
@@ -336,7 +336,7 @@
"$term => $action";
- } grep { $_ } keys(%{$$state{ACTIONS}}));
+ } grep { $_ } sort keys(%{$$state{ACTIONS}}));
$text.="\n\t\t}";
};
@@ -359,7 +359,7 @@
"'$nterm' => $stateno";
- } keys(%{$$state{GOTOS}}));
+ } sort keys(%{$$state{GOTOS}}));
$text.="\n\t\t}";
};
@@ -412,7 +412,7 @@
exists($$rel{$x})
and do {
- for $y (keys(%{$$rel{$x}})) {
+ for $y (sort keys(%{$$rel{$x}})) {
exists($N{$y})
or &$Traverse($y,$d+1);
@@ -435,7 +435,7 @@
};
};
- for (keys(%$rel)) {
+ for (sort keys(%$rel)) {
exists($N{$_})
or &$Traverse($_,1);
}
@@ -459,7 +459,7 @@
my($grammar)=@_;
my($rel,$closures);
- for my $symbol (keys(%{$$grammar{NTERM}})) {
+ for my $symbol (sort keys(%{$$grammar{NTERM}})) {
$closures->{$symbol}=pack('b'.@{$$grammar{RULES}});
for my $ruleno (@{$$grammar{NTERM}{$symbol}}) {
@@ -511,7 +511,7 @@
push(@{$transitions{$$rhs[$pos]}},[ $ruleno, $pos+1 ]);
}
- for (keys(%transitions)) {
+ for (sort keys(%transitions)) {
my($symbol,$core)=($_,$transitions{$_});
my($corekey)=join(',',map { join('.',@$_) }
sort { $$a[0] <=> $$b[0]
@@ -573,7 +573,7 @@
my($grammar,$termlst,$terminx)=@_;
my($rel,$first)=( {}, {} );
- for my $symbol (keys(%{$$grammar{NTERM}})) {
+ for my $symbol (sort keys(%{$$grammar{NTERM}})) {
$first->{$symbol}=pack('b'.@$termlst);
RULE:
@@ -621,7 +621,7 @@
}
# Pass @$preds through a hash to ensure unicity
- [ keys( %{ +{ map { ($_,1) } @$preds } } ) ];
+ [ sort keys( %{ +{ map { ($_,1) } @$preds } } ) ];
}
sub _FirstSfx {
@@ -694,7 +694,7 @@
exists($$state{GOTOS})
or next;
- for my $symbol (keys(%{$$state{GOTOS}})) {
+ for my $symbol (sort keys(%{$$state{GOTOS}})) {
my($tostate)=$$states[$$state{GOTOS}{$symbol}];
my($goto)="$stateno.$symbol";
@@ -731,11 +731,11 @@
sub _ComputeLA {
my($grammar,$states)=@_;
- my($termlst)= [ '',keys(%{$$grammar{TERM}}) ];
+ my($termlst)= [ '',sort keys(%{$$grammar{TERM}}) ];
my($follows,$inconsistent) = _ComputeFollows($grammar,$states,$termlst);
- for my $stateno ( keys(%$inconsistent ) ) {
+ for my $stateno ( sort keys(%$inconsistent ) ) {
my($state)=$$states[$stateno];
my($conflict);
@@ -794,12 +794,12 @@
undef;
};
- for my $stateno (keys(%$inconsistent)) {
+ for my $stateno (sort keys(%$inconsistent)) {
my($state)=$$states[$stateno];
my($actions)=$$state{ACTIONS};
my($nbsr,$nbrr);
- for my $term ( keys(%$actions) ) {
+ for my $term ( sort keys(%$actions) ) {
my($act)=$$actions{$term};
@$act > 1
@@ -899,7 +899,7 @@
and $$actions{error}[0] > 0
and ++$nodefault;
- for my $term (keys(%$actions)) {
+ for my $term (sort keys(%$actions)) {
$$actions{$term}=$$actions{$term}[0];
@@ -917,7 +917,7 @@
$default=( map { $$_[0] }
sort { $$b[1] <=> $$a[1] or $$b[0] <=> $$a[0] }
map { [ $_, scalar(@{$reduces{$_}}) ] }
- keys(%reduces))[0];
+ sort(keys(%reduces)))[0];
delete(@$actions{ @{$reduces{$default}} });
$$state{ACTIONS}{''}=$default;
