[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
tests: check symbol/token renumbering
|
From: |
Akim Demaille |
|
Subject: |
tests: check symbol/token renumbering |
|
Date: |
Wed, 11 Aug 2021 18:03:42 +0200 |
commit e4e3cbce774af6c407e5cb699a8227ef213d54a1
Author: Akim Demaille <akim.demaille@gmail.com>
Date: Mon Aug 9 08:25:37 2021 +0200
tests: check symbol/token renumbering
In some extreme situations, with lots of useless tokens, Bison was
numbering them incorrectly, which resulted in a broken grammar.
<https://lists.gnu.org/r/bison-patches/2021-03/msg00001.html>
commit a774839ca873d1082f79ba3c4eecc1e242a28ce1.
* tests/regression.at (Useless Tokens): New.
diff --git a/TODO b/TODO
index b4557991..d9277255 100644
--- a/TODO
+++ b/TODO
@@ -8,14 +8,6 @@ The default case is scanning char-per-char.
make it more eager?
** Missing tests
-commit c22902e360e0fbbe9fd5657dcf107e03166da309
-Author: Akim Demaille <akim.demaille@gmail.com>
-Date: Sat Jan 23 18:40:15 2021 +0100
-
- tables: fix handling for useless tokens
-
-See https://github.com/akimd/bison/issues/72#issuecomment-766153154
-
commit 2c294c132528ede23d8ae4959783a67e9ff05ac5
Author: Vincent Imbimbo <vmi6@cornell.edu>
Date: Sat Jan 23 13:25:18 2021 -0500
diff --git a/tests/regression.at b/tests/regression.at
index a64da9ab..1a796a92 100644
--- a/tests/regression.at
+++ b/tests/regression.at
@@ -674,7 +674,7 @@ AT_SETUP([Web2c Actions])
AT_BISON_CHECK([-v -o input.c input.y])
# Check only the tables.
-[sed -n 's/ *$//;/^static const.*\[\] =/,/^}/p' input.c >tables.c]
+[sed -n 's/ *$//;/^static const.*\[\] =/,/^}/p;/#define YY.*NINF/p' input.c
>tables.c]
AT_CHECK([[cat tables.c]], 0,
[[static const yytype_int8 yytranslate[] =
@@ -717,6 +717,8 @@ AT_SETUP([Web2c Actions])
"\"then\"", "\"else\"", "$accept", "statement", "struct_stat", "if",
"else", YY_NULLPTR
};
+#define YYPACT_NINF (-8)
+#define YYTABLE_NINF (-1)
static const yytype_int8 yypact[] =
{
-2, -1, 4, -8, 0, 2, -8, -2, -8, -2,
@@ -761,6 +763,300 @@ AT_SETUP([Web2c Actions])
AT_CLEANUP
+## ---------------- ##
+## Useless Tokens. ##
+## ---------------- ##
+
+# In some extreme situations, with lots of useless tokens, Bison was
+# numbering them incorrectly, which resulted in a broken grammar.
+# <https://lists.gnu.org/r/bison-patches/2021-03/msg00001.html>
+# commit a774839ca873d1082f79ba3c4eecc1e242a28ce1.
+#
+# To track this failure, compare the tables between an incorrect
+# version of Bison (e.g., 3.7.5), and a correct one:
+#
+# LC_ALL=C /usr/local/stow/bison-3.7.5/bin/bison input.y -o old.c &&
+# LC_ALL=C bison input.y -o new.c &&
+# sed -n 's/ *$//;/^static const.*\[\] =/,/^}/p' old.c >old.tables &&
+# sed -n 's/ *$//;/^static const.*\[\] =/,/^}/p' new.c >new.tables &&
+# diff old.tables new.tables
+#
+# The following Ruby script normalizes token and nterm names.
+#
+# #! /usr/bin/env ruby
+#
+# require 'strscan'
+#
+# tokens = {}
+# nterms = {}
+#
+# ARGV.each do |file|
+# s = StringScanner.new File.read(file)
+# while !s.eos?
+# $stdout <<
+# case
+# when s.scan(/%\w+/)
+# s.matched
+# when s.scan(/[A-Z_0-9]+/)
+# tokens[s.matched] ||= 'T%02d' % tokens.size
+# when s.scan(/[a-z_0-9]+/)
+# nterms[s.matched] ||= 'n%02d' % nterms.size
+# when s.scan(/.|\n/)
+# s.matched
+# else
+# raise "error: #{s.rest}"
+# end
+# end
+# end
+
+AT_SETUP([Useless Tokens])
+
+AT_DATA([input.y],
+[[%token
+ T00 T01 T02 T03 T04 T05 T06 T07 T08 T09 T10 T11 T12 T13 T14 T15 T16
+ T17 T18 T19 T20 T21 T22 T23 T24 T25 T26 T27 T28 T29 T30 T31 T32 T33
+ T34 T35 T36 T37 T38 T39 T40 T41 T42 T43 T44 T45 T46 T47 T48 T49 T50
+ T51 T52 T53 T54 T55 T56 T57 T58 T59 T60 T61 T62 T63 T64 T65 T66 T67
+ T68 T69 T70 T71 T72 T73 T74 T75 T76 T77 T78 T79 T80 T81 T82 T83 T84
+ T85 T86 T87 T88 T89 T90
+
+%%
+
+n00: T00 n01;
+n01: T77 T88 n02 T89;
+n02: n03 n02 | %empty;
+n03: T16 T88 n04 T89 | T79 T88 n05 T89 | T78 T88 n06 T89 | T81 T88 n07 T89 |
T82 T88 n05 T89 | T83 T88 n05 T89 | T84 T88 n05 T89 | T80 T88 n08 T89 | n09;
+n04: n10 n04 | %empty;
+n05: T58 | T61;
+n06: n10
+n07: n05 | n11;
+n08: n12;
+n09: T30 T88 n05 T89;
+n11: n13 n11 | %empty;
+n13: T85 T88 n05 T89 | T86 T88 n08 T89;
+n10: n05;
+n14: %empty;
+n15: n16 T90 n15;
+n16: n17;
+n18: T58;
+n17: T07 T88 n19 T89;
+n19: n20;
+n20: n21 n20;
+n21: T13 T88 n22 T89;
+n22: n23;
+n24: n25;
+n25: n26 T90 n25 | n27 T90 n25;
+n26: n28;
+n28: T58;
+n29: n30 T90 n29;
+n30: T02 T88 n05 T89;
+n31: T04 T88 n32 T89;
+n33: n32;
+n32: n27 T90 n32;
+n27: T03 T88 n34 T89;
+n35: n36;
+n36: T05 T88 n34 T89 | n36 T06 T88 n34 T89;
+n34: n29 n33 n37;
+n37: T16 T88 n38 T89 T90;
+n38: n10 n38;
+n39: n05 | T58 T88 n05 T89;
+n40: n39;
+n41: n40 n41;
+n42: T48;
+n43: n42;
+n44: T59;
+n45: n44;
+n23: T59;
+n46: T60;
+n47: T60;
+n48: n05;
+n49: n05;
+n50: n49;
+n51: n49;
+n52: n05;
+n12: n05 n12 | %empty;
+n53: n05;
+n54: n05;
+n55: T15 T88 n05 T89;
+n56: T58;
+n57: n56;
+n58: T58;
+n59: T13 T88 n22 T89;
+n60: T75 T88 n22 T89;
+n61: T18 T88 n05 T89;
+n62: T76 T88 n46 T89;
+n63: n05 n63;
+n64: T14 T88 n22 T89;
+n65: T10 T88 n42 T89;
+n66: n05 n66;
+n67: T08 T88 n05 T89;
+n68: T11 T88 n42 T89;
+n69: T17 T88 n05 T89;
+n70: n71 n70;
+n71: T16 T88 n72 T89;
+n72: n10 n72;
+n73: T24 T88 n48 T89;
+n74: T12 T88 n05 T89;
+n75: T09 T88 n05 T89;
+n76: n05 n76;
+n77: T64 T88 n78 T89;
+n78: n79 n78;
+n79: T66 T88 n05 n40 T89;
+n80: n05 n80;
+n81: n82 n81;
+n82: T69 T88 n22 T89;
+n83: T47 T88 n05 T89;
+n84: T46 T88 T89;
+]])
+
+AT_BISON_CHECK([-Wno-other -o input.c input.y])
+
+# Check only the tables.
+[sed -n 's/ *$//;/^static const.*\[\] =/,/^}/p;/#define YY.*NINF/p' input.c
>tables.c]
+
+AT_CHECK([[cat tables.c]], 0,
+[[static const yytype_int8 yytranslate[] =
+{
+ 0, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 1, 2, 3, 4,
+ 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
+ 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
+ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
+ 35, 36, 37, 38, 39, 40, 41, 42, 43, 44,
+ 45, 46, 47, 48, 49, 50, 51, 52, 53, 54,
+ 55, 56, 57, 58, 59, 60, 61, 62, 63, 64,
+ 65, 66, 67, 68, 69, 70, 71, 72, 73, 74,
+ 75, 76, 77, 78, 79, 80, 81, 82, 83, 84,
+ 85, 86, 87, 88, 89, 90, 91, 92, 93
+};
+static const yytype_int8 yyrline[] =
+{
+ 0, 11, 11, 12, 13, 13, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 15, 15, 16, 16, 17,
+ 18, 18, 19, 20, 21, 21, 22, 22, 23, 63,
+ 63
+};
+static const char *const yytname[] =
+{
+ "\"end of file\"", "error", "\"invalid token\"", "T00", "T01", "T02",
+ "T03", "T04", "T05", "T06", "T07", "T08", "T09", "T10", "T11", "T12",
+ "T13", "T14", "T15", "T16", "T17", "T18", "T19", "T20", "T21", "T22",
+ "T23", "T24", "T25", "T26", "T27", "T28", "T29", "T30", "T31", "T32",
+ "T33", "T34", "T35", "T36", "T37", "T38", "T39", "T40", "T41", "T42",
+ "T43", "T44", "T45", "T46", "T47", "T48", "T49", "T50", "T51", "T52",
+ "T53", "T54", "T55", "T56", "T57", "T58", "T59", "T60", "T61", "T62",
+ "T63", "T64", "T65", "T66", "T67", "T68", "T69", "T70", "T71", "T72",
+ "T73", "T74", "T75", "T76", "T77", "T78", "T79", "T80", "T81", "T82",
+ "T83", "T84", "T85", "T86", "T87", "T88", "T89", "T90", "$accept", "n00",
+ "n01", "n02", "n03", "n04", "n05", "n06", "n07", "n08", "n09", "n11",
+ "n13", "n10", "n12", YY_NULLPTR
+};
+#define YYPACT_NINF (-78)
+#define YYTABLE_NINF (-1)
+static const yytype_int8 yypact[] =
+{
+ -2, -77, 11, -73, -78, -78, -19, -71, -69, -68,
+ -67, -66, -65, -64, -63, -62, -61, -19, -78, -49,
+ -49, -49, -49, -49, -51, -49, -49, -49, -78, -78,
+ -78, -78, -60, -78, -49, -59, -58, -78, -57, -49,
+ -56, -78, -52, -48, -78, -50, -78, -72, -47, -46,
+ -45, -78, -78, -78, -78, -78, -78, -78, -49, -49,
+ -78, -78, -78, -78, -78, -44, -43, -78, -78
+};
+static const yytype_int8 yydefact[] =
+{
+ 0, 0, 0, 0, 2, 1, 5, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 5, 14, 16,
+ 0, 0, 0, 30, 25, 0, 0, 0, 3, 4,
+ 17, 18, 0, 28, 16, 0, 0, 19, 0, 30,
+ 0, 22, 0, 0, 20, 0, 21, 25, 0, 0,
+ 0, 6, 15, 23, 8, 7, 29, 13, 0, 30,
+ 9, 24, 10, 11, 12, 0, 0, 26, 27
+};
+static const yytype_int8 yypgoto[] =
+{
+ -78, -78, -78, 2, -78, -4, -18, -78, -78, -15,
+ -78, 3, -78, 30, 13
+};
+static const yytype_int8 yydefgoto[] =
+{
+ 0, 2, 4, 16, 17, 32, 33, 36, 45, 40,
+ 18, 46, 47, 34, 41
+};
+static const yytype_int8 yytable[] =
+{
+ 7, 1, 35, 3, 38, 39, 44, 48, 49, 50,
+ 30, 5, 30, 31, 8, 31, 42, 43, 6, 29,
+ 19, 39, 20, 21, 22, 23, 24, 25, 26, 27,
+ 52, 28, 51, 53, 54, 55, 57, 42, 43, 58,
+ 65, 39, 60, 59, 66, 62, 63, 64, 67, 68,
+ 61, 37, 56, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 9, 10, 11, 12, 13, 14, 15
+};
+static const yytype_int8 yycheck[] =
+{
+ 19, 3, 20, 80, 22, 23, 24, 25, 26, 27,
+ 61, 0, 61, 64, 33, 64, 88, 89, 91, 17,
+ 91, 39, 91, 91, 91, 91, 91, 91, 91, 91,
+ 34, 92, 92, 92, 92, 92, 92, 88, 89, 91,
+ 58, 59, 92, 91, 59, 92, 92, 92, 92, 92,
+ 47, 21, 39, -1, -1, -1, -1, -1, -1, -1,
+ -1, -1, 81, 82, 83, 84, 85, 86, 87
+};
+static const yytype_int8 yystos[] =
+{
+ 0, 3, 95, 80, 96, 0, 91, 19, 33, 81,
+ 82, 83, 84, 85, 86, 87, 97, 98, 104, 91,
+ 91, 91, 91, 91, 91, 91, 91, 91, 92, 97,
+ 61, 64, 99, 100, 107, 100, 101, 107, 100, 100,
+ 103, 108, 88, 89, 100, 102, 105, 106, 100, 100,
+ 100, 92, 99, 92, 92, 92, 108, 92, 91, 91,
+ 92, 105, 92, 92, 92, 100, 103, 92, 92
+};
+static const yytype_int8 yyr1[] =
+{
+ 0, 94, 95, 96, 97, 97, 98, 98, 98, 98,
+ 98, 98, 98, 98, 98, 99, 99, 100, 100, 101,
+ 102, 102, 103, 104, 105, 105, 106, 106, 107, 108,
+ 108
+};
+static const yytype_int8 yyr2[] =
+{
+ 0, 2, 2, 4, 2, 0, 4, 4, 4, 4,
+ 4, 4, 4, 4, 1, 2, 0, 1, 1, 1,
+ 1, 1, 1, 4, 2, 0, 4, 4, 1, 2,
+ 0
+};
+]])
+
+AT_CLEANUP
+
+
+
## ------------------------- ##
## yycheck Bound Violation. ##
## ------------------------- ##
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- tests: check symbol/token renumbering,
Akim Demaille <=