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 class Linear
   7   def initialize(states)
   8     @states = states - 4
   9     @cols = Math.sqrt(@states).to_i
  10     @lines = @states / @cols
  11     @rest = @states % @cols
  12
  13     @n = @lines * (@cols - 1) + (@rest == 0 ? 1 : @rest == 1 ? 2 : @rest)
  14   end
  15
  16   def nterms
  17     last = @lines + ([0, 1].include?(@rest) ? 0 : 1)
  18     (0...last).map { |i| "t#{i}" }.join(' ')
  19   end
  20
  21   def rules
  22     res = (0...@lines).map { |i| "t#{i}:#{' N' * (@cols - 1)}" }.join("\n")
  23     case @rest
  24     when 0
  25       res += ' N'
  26     when 1
  27       res += ' N N'
  28     else
  29       res += "\nt#{@lines}:#{" N" * @rest}"
  30     end
  31     res
  32   end
  33
  34   def to_s
  35     puts <<~EOF
  36       // states: #{@states}
  37       // cols: #{@cols}
  38       // lines: #{@lines}
  39       // rest: #{@rest}
  40       // n: #{@n}
  41
  42       %code {
  43         #include <stdio.h>
  44         #include <stdlib.h>
  45
  46         static int yylex (void);
  47         static void yyerror (const char *msg);
  48        }
  49
  50       %debug
  51       %define api.value.type union
  52       %define parse.lac full
  53       %define parse.error verbose
  54       %printer { fprintf (yyo, "%ld", $$); } <long>
  55       %token <long> N
  56
  57       %%
  58
  59       exp: #{nterms}
  60
  61       #{rules}
  62
  63       %%
  64
  65       static
  66       int yylex (void)
  67       {
  68         static long count = 0;
  69         if (count++ < #{@n})
  70           {
  71             yylval.N = count;
  72             return N;
  73           }
  74         else
  75           return 0;
  76       }
  77
  78       static
  79       void yyerror (const char *msg)
  80       {
  81         fprintf (stderr, "%s\\n", msg);
  82       }
  83
  84       int
  85       main (void)
  86       {
  87         yydebug = !!getenv ("YYDEBUG");
  88         return yyparse ();
  89       }
  90       EOF
  91   end
  92 end
  93
  94 puts Linear.new(ARGV[0].to_i).to_s