Untitled
unknown
plain_text
5 months ago
6.0 kB
5
Indexable
class Grammar: def __init__(self): self.rules = [] self.terminals = set() self.non_terminals = set() self.start_symbol = None self.symbols = set() def add_rule(self, left, right): self.rules.append((left, right)) self.non_terminals.add(left) self.symbols.add(left) for symbol in right: if symbol.isupper(): # Non-terminal symbols self.non_terminals.add(symbol) else: # Terminal symbols self.terminals.add(symbol) self.symbols.add(symbol) def set_start_symbol(self, start): self.start_symbol = start def get_start_symbol(self): return self.start_symbol class LR1Item: def __init__(self, left, right, dot_position, lookahead): self.left = left self.right = right self.dot_position = dot_position self.lookahead = lookahead def __str__(self): return f"{self.left} -> {''.join(self.right[:self.dot_position])}.{''.join(self.right[self.dot_position:])}, {self.lookahead}" def __eq__(self, other): return (self.left == other.left and self.right == other.right and self.dot_position == other.dot_position and self.lookahead == other.lookahead) def __hash__(self): return hash((self.left, tuple(self.right), self.dot_position, self.lookahead)) def construct_lr1_items(grammar): items = set() # Augmented start symbol rule items.add(LR1Item(grammar.start_symbol, ['.'], 0, '$')) for left, right in grammar.rules: for i in range(len(right) + 1): # Including position after the last symbol lookahead = '$' # Placeholder for simplicity; real lookahead computation needed items.add(LR1Item(left, right, i, lookahead)) return items def display_lr1_items(lr1_items): print("LR(1) Items:") for item in lr1_items: print(item) def merge_lr1_items(lr1_items): merged_items = set() for item in lr1_items: core = (item.left, item.right, item.dot_position) matching_items = {i for i in merged_items if (i.left, i.right, i.dot_position) == core} if matching_items: # Merge lookaheads from matching items lookaheads = {item.lookahead for item in matching_items} | {item.lookahead} for match in matching_items: merged_items.remove(match) for new_item in matching_items: merged_items.add(LR1Item(new_item.left, new_item.right, new_item.dot_position, list(lookaheads))) else: merged_items.add(item) return merged_items # Construct LALR parsing table (simplified) def construct_lalr_table(grammar, merged_items): action_table = {} goto_table = {} states = list(merged_items) # Each item represents a state for simplicity for item in states: if item.dot_position == len(item.right): # If dot is at the end of the rule if item.left == grammar.start_symbol: action_table[(item.left, item.lookahead)] = 'accept' # Accepting the input else: action_table[(item.left, item.lookahead)] = 'reduce' # Reduce operation else: next_symbol = item.right[item.dot_position] if next_symbol.isupper(): # Non-terminal, goto operation goto_table[(item.left, next_symbol)] = 'goto' else: # Terminal, shift operation action_table[(item.left, item.lookahead)] = 'shift' return action_table, goto_table def display_parse_table(action_table, goto_table): print("\nParse Table:") print("\nAction Table:") for (state, lookahead), action in action_table.items(): print(f"State {state}, Lookahead {lookahead}: {action}") print("\nGoto Table:") for (state, non_terminal), action in goto_table.items(): print(f"State {state}, Non-terminal {non_terminal}: {action}") # Perform LALR parsing (simplified) def lalr_parse(input_string, start_symbol, action_table, goto_table): stack = [start_symbol] input_tokens = list(input_string) + ['$'] # Add end-of-input symbol index = 0 while stack: current_symbol = input_tokens[index] current_state = stack[-1] # Check the action table action = action_table.get((current_state, current_symbol), None) if action == 'shift': stack.append(current_symbol) index += 1 elif action == 'reduce': # Example: Reduction based on a rule rule = current_state stack = stack[:-len(rule)] # pop the right side of the rule stack.append(rule[0]) # push the left side (non-terminal) elif action == 'accept': return True else: return False # Error in parsing return False # If no action was taken # Example grammar for arithmetic expressions grammar = Grammar() grammar.add_rule('S', ['E']) grammar.add_rule('E', ['E', '+', 'T']) grammar.add_rule('E', ['T']) grammar.add_rule('T', ['T', '*', 'F']) grammar.add_rule('T', ['F']) grammar.add_rule('F', ['(', 'E', ')']) grammar.add_rule('F', ['id']) grammar.set_start_symbol('S') # Construct LR(1) items lr1_items = construct_lr1_items(grammar) display_lr1_items(lr1_items) # Merge LR(1) items into LALR items merged_items = merge_lr1_items(lr1_items) # Display merged LALR items print("\nMerged LALR Items:") display_lr1_items(merged_items) # Construct the LALR parsing table action_table, goto_table = construct_lalr_table(grammar, merged_items) # Display the parse table (action and goto tables) display_parse_table(action_table, goto_table) # Example parsing input: 'id+id*id' input_string = 'id+id*id' result = lalr_parse(input_string, grammar.get_start_symbol(), action_table, goto_table) print(f"Parse result for '{input_string}': {result}")
Editor is loading...
Leave a Comment