grammar.rb in lrama-0.5.4

- old
+ new

@@ -1,24 +1,22 @@
+require "lrama/grammar/auxiliary"
 require "lrama/grammar/code"
 require "lrama/grammar/error_token"
 require "lrama/grammar/precedence"
 require "lrama/grammar/printer"
 require "lrama/grammar/reference"
 require "lrama/grammar/rule"
 require "lrama/grammar/symbol"
 require "lrama/grammar/union"
 require "lrama/lexer"
+require "lrama/type"
 
 module Lrama
-  Type = Struct.new(:id, :tag, keyword_init: true)
   Token = Lrama::Lexer::Token
 
   # Grammar is the result of parsing an input grammar file
   class Grammar
-    # Grammar file information not used by States but by Output
-    Aux = Struct.new(:prologue_first_lineno, :prologue, :epilogue_first_lineno, :epilogue, keyword_init: true)
-
     attr_reader :eof_symbol, :error_symbol, :undef_symbol, :accept_symbol, :aux
     attr_accessor :union, :expect,
                   :printers, :error_tokens,
                   :lex_param, :parse_param, :initial_action,
                   :symbols, :types,
@@ -36,21 +34,21 @@
       @empty_symbol = nil
       @eof_symbol = nil
       @error_symbol = nil
       @undef_symbol = nil
       @accept_symbol = nil
-      @aux = Aux.new
+      @aux = Auxiliary.new
 
       append_special_symbols
     end
 
     def add_printer(ident_or_tags:, code:, lineno:)
       @printers << Printer.new(ident_or_tags: ident_or_tags, code: code, lineno: lineno)
     end
 
     def add_error_token(ident_or_tags:, code:, lineno:)
-      @error_tokens << ErrorToken.new(ident_or_tags, code, lineno)
+      @error_tokens << ErrorToken.new(ident_or_tags: ident_or_tags, code: code, lineno: lineno)
     end
 
     def add_term(id:, alias_name: nil, tag: nil, token_id: nil, replace: false)
       if token_id && (sym = @symbols.find {|s| s.token_id == token_id })
         if replace
@@ -210,9 +208,44 @@
         rule.nullable = false
       end
 
       nterms.select {|r| r.nullable.nil? }.each do |nterm|
         nterm.nullable = false
+      end
+    end
+
+    def compute_first_set
+      terms.each do |term|
+        term.first_set = Set.new([term]).freeze
+        term.first_set_bitmap = Lrama::Bitmap.from_array([term.number])
+      end
+
+      nterms.each do |nterm|
+        nterm.first_set = Set.new([]).freeze
+        nterm.first_set_bitmap = Lrama::Bitmap.from_array([])
+      end
+
+      while true do
+        changed = false
+
+        @rules.each do |rule|
+          rule.rhs.each do |r|
+            if rule.lhs.first_set_bitmap | r.first_set_bitmap != rule.lhs.first_set_bitmap
+              changed = true
+              rule.lhs.first_set_bitmap = rule.lhs.first_set_bitmap | r.first_set_bitmap
+            end
+
+            break unless r.nullable
+          end
+        end
+
+        break unless changed
+      end
+
+      nterms.each do |nterm|
+        nterm.first_set = Lrama::Bitmap.to_array(nterm.first_set_bitmap).map do |number|
+          find_symbol_by_number!(number)
+        end.to_set
       end
     end
 
     def find_symbol_by_s_value(s_value)
       @symbols.find do |sym|