Commits

Steven! Ragnarök committed 4d24230

Implements first function.

Comments (0)

Files changed (1)

 class TopDowner
-	attr_accessor :tree
+	attr_reader :token
+
 	def initialize grammar, token_types
 		@grammar = grammar
 		@token_types = token_types
 		@r_cache = Hash.new
-		@tree = Hash.new
+		@first = Hash.new
 	end
 
 	def parse string
 		@tree = Hash.new
 		@enumerator = tokenize(string).each
-		recognize [:Program]
 	end
 
 	private
 	## A Token Type Detector ##
-	def detect(token)
+	def detect token
 		@token_types.each do |type, matcher|
 			if token =~ matcher
 				return { :token => token, :type => type }
 			end
 		end
-		raise ArgumentError.new "Unknown token type for #{token}"
+		raise ArgumentError.new "Unrecognizeable token: #{token}"
 	end
 
 	## String Tokenizer ##
 		tokens.map do |token|
 			detect(token)
 		end
+		tokens << {:token => :'$', :type => :eof}
+	end
+
+	## Strips meta-grammar from symbol
+	def strip_meta symbol
+		symbol.to_s.gsub!(/[\|\*]/,'').to_sym
+	end
+
+	# First algorithm
+	# returns a set of all valid first token types for a rule.
+	# Memoizes return values for better performance.
+	def first rule
+		@first[rule] ||=
+			if @grammar.has_key? rule
+				case @grammar[rule][0][0]
+				when '*'
+					[first(strip_meta(@grammar[rule][0])),
+						first(@grammar[rule][1])].flatten
+				when '|'
+					@grammar[rule].find_all{|s| s[0] =='|'}.map do |s|
+						first(strip_meta(s))
+					end.flatten
+				else
+					[first(@grammar[rule][0])].flatten
+				end
+			else
+				[rule]
+			end
+	end
+
+	def match t
+		if @token[:type] == t
+			tkn, @token, @peek = @token, @enumerator.next, @enumerator.peek
+			return tkn[:token]
+		else
+			raise ArgumentError.new "SYNTAX ERROR expected #{t}, got #{@token[:token]}"
+		end
 	end
 
 	# After we get a tokenized string, what should we do. The logic of the topdown
 	# First we need to build some functions which recognize the first two
 	# symbols for each rule so that we can accurately consume our language.
 	# Now that we have a plan. Let's fuck some shit up!!!!
-	
-	## returns a set of all possible [:first, :second] tokens for a given rule.
-	def first_two rule
-		# Check that rule is a nonterminal.
-		if @grammar.has_key? rule
-			# implement :* behavior
-			if @grammar[rule].include? :*
-				(@grammar)
-			end
-		end
-	end
-
 end