SLRParser.py

"""
	Author: Charanjit Singh
	Website: https://charanjit-singh.github.io

	Description: This module Parses grammar using LR Parsing: Simple LR (SLR).

"""
from utils.ParserUtils import *

class SLRParser():
	""" SLR Parser """

	class State(object):
		""" State contains set of items """
		def __init__(self, id, item_set = [] ):
			self.id = id
			self.item_set = item_set

		def contains_item(self, i):
			for item in self.item_set:
				if i.rule.equals(item.rule) and i.dot_index == item.dot_index:
					return True
			return False

		def equals(self, state):
			pass

		def contains_item_set(self, item_set):
			if not len(item_set) == len(self.item_set):
				return False 

			for item in item_set:
				if not self.contains_item(item):
					return True 
			return False

		def  __repr__(self):
			string = "{\nI[%d]: "%(self.id)
			for item in self.item_set:
				string+="\n\t%s"%(item)
			return string + "\n}"


	class Item(object):
		""" Item contains rule and dot at some index in it's body. """
		def __init__(self, rule = None, dot_index = -1):
			self.rule = rule
			self.dot_index = dot_index

		def make_copy(self):
			new_item = SLRParser.Item(self.rule, self.dot_index)
			return new_item

		def __repr__(self):
			string = "%s : "%(self.rule.lhs) 
			i = 0
			for grammar_symbol in self.rule.rhs:
				if i == self.dot_index:
					string += " [.] "
				string += " %s "%(grammar_symbol)
				i += 1 
			return string

	def __init__(self, grammar):
		self.grammar = grammar
		self.states = []
		self.states = []
		self.gotos = [] # gotos contains rules in form: { 'on': GrammarSymbol, 'at': State, 'to': State }
		self.start_rule = None
		self.augment_grammar()
		self.latest_id = 0
		self.construct_states()

	def augment_grammar(self):
		start_symbol = self.grammar.start_symbol
		augmented_symbol = GrammarSymbol(start_symbol.content + "_prime", start_symbol.type)
		augmented_rule = GrammarRule(augmented_symbol, [start_symbol])
		self.grammar.grammar_rules.append(augmented_rule)
		self.grammar.start_symbol = augmented_symbol
		self.start_rule = augmented_rule

	def get_goto_itemset(self, I, X):
		""" Returns ItemSet that is generated by going to grammarSymbol X on itemSet I. """
		item_set = []
		for item in I.item_set:
			if item.rule.rhs[item.dot_index].equals(X):
				item_set.append(item.make_copy())

		if len(item_set) > 0:
			while True:
				restart_loop = False
				for item in item_set:
					B = item.rule.rhs[item.dot_index]
					if B.type == GrammarSymbol.TYPE_NON_TERMINAL:
						B_rules = self.grammar.get_deltas(B)
						for grammar_rule in B_rules:
							new_item = SLRParser.Item(grammar_rule, 0)
							# if not state.contains_item(new_item):
							contains_item = False

							for inner_item in item_set:
								if inner_item.rule.equals(new_item.rule) and inner_item.dot_index == new_item.dot_index:
									contains_item = True
									break

							if not contains_item:
								# Check if item is complete
								if not item.dot_index >= len(grammar_rule.rhs) - 1  : 
									item.dot_index = item.dot_index + 1
								item_set.append(new_item)
								restart_loop = True
								break
					if restart_loop:
						break

				if not restart_loop:
					break

		return item_set

	def get_closure(self, state):
		while True:
			restart_loop = False
			for item in state.item_set:
				B = item.rule.rhs[item.dot_index]
				if B.type == GrammarSymbol.TYPE_NON_TERMINAL:
					B_rules = self.grammar.get_deltas(B)
					for grammar_rule in B_rules:
						new_item = SLRParser.Item(grammar_rule, 0)
						if not state.contains_item(new_item):
							state.item_set.append(new_item)
							restart_loop = True
							break
				if restart_loop:
					break
			if not restart_loop:
				break
		return state

	def construct_states(self):
		I0_item = SLRParser.Item( self.start_rule, 0)
		C = { self.get_closure( SLRParser.State(self.latest_id, [I0_item]) ) }
		for state in C:
			for grammar_symbol in self.grammar.get_all_grammar_symbols():
				print("GrammarSymbol: ", grammar_symbol, "I:", state)
				print("GOTO:", self.get_goto_itemset(state, grammar_symbol))