tests/linear

   1 #! /usr/bin/env ruby
   2
   3 # Build a grammar whose LALR(1) parser has a given number of states.
   4 # Useful to test edge cases (e.g., 256 and 257 states, etc.).
   5
   6 # Copyright (C) 2020-2021 Free Software Foundation, Inc.
   7 #
   8 # This program is free software: you can redistribute it and/or modify
   9 # it under the terms of the GNU General Public License as published by
  10 # the Free Software Foundation, either version 3 of the License, or
  11 # (at your option) any later version.
  12 #
  13 # This program is distributed in the hope that it will be useful,
  14 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 # GNU General Public License for more details.
  17 #
  18 # You should have received a copy of the GNU General Public License
  19 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
  20 #
  21 # Written by Akim Demaille.
  22
  23 class Linear
  24   def initialize(states)
  25     @states = states - 4
  26     @cols = Math.sqrt(@states).to_i
  27     @lines = @states / @cols
  28     @rest = @states % @cols
  29
  30     @n = @lines * (@cols - 1) + (@rest == 0 ? 1 : @rest == 1 ? 2 : @rest)
  31   end
  32
  33   def nterms
  34     last = @lines + ([0, 1].include?(@rest) ? 0 : 1)
  35     (0...last).map { |i| "t#{i}" }.join(' ')
  36   end
  37
  38   def rules
  39     res = (0...@lines).map { |i| "t#{i}:#{' N' * (@cols - 1)}" }.join("\n")
  40     case @rest
  41     when 0
  42       res += ' N'
  43     when 1
  44       res += ' N N'
  45     else
  46       res += "\nt#{@lines}:#{" N" * @rest}"
  47     end
  48     res
  49   end
  50
  51   def to_s
  52     puts <<~EOF
  53       // states: #{@states}
  54       // cols: #{@cols}
  55       // lines: #{@lines}
  56       // rest: #{@rest}
  57       // n: #{@n}
  58
  59       %code {
  60         #include <stdio.h>
  61         #include <stdlib.h>
  62
  63         static int yylex (void);
  64         static void yyerror (const char *msg);
  65        }
  66
  67       %debug
  68       %define api.value.type union
  69       %define parse.lac full
  70       %define parse.error verbose
  71       %printer { fprintf (yyo, "%ld", $$); } <long>
  72       %token <long> N
  73
  74       %%
  75
  76       exp: #{nterms}
  77
  78       #{rules}
  79
  80       %%
  81
  82       static
  83       int yylex (void)
  84       {
  85         static long count = 0;
  86         if (count++ < #{@n})
  87           {
  88             yylval.N = count;
  89             return N;
  90           }
  91         else
  92           return 0;
  93       }
  94
  95       static
  96       void yyerror (const char *msg)
  97       {
  98         fprintf (stderr, "%s\\n", msg);
  99       }
 100
 101       int
 102       main (void)
 103       {
 104         yydebug = !!getenv ("YYDEBUG");
 105         return yyparse ();
 106       }
 107       EOF
 108   end
 109 end
 110
 111 puts Linear.new(ARGV[0].to_i).to_s