Last active
March 13, 2018 10:11
-
-
Save vigack/3af136ccf85723717050ee0b745e83dc to your computer and use it in GitHub Desktop.
lr(0) algo implements by python. Based on <Modern Compiler Implemention in C> in ch03
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| cfg = [] | |
| ht = {} | |
| class Token: | |
| def __init__(self, val, is_term): | |
| self.val = val | |
| self.is_term = is_term | |
| def __eq__(self, other): | |
| return (self.val, self.is_term) == (other.val, other.is_term) | |
| def __hash__(self): | |
| return hash((self.val, self.is_term)) | |
| class Production: | |
| def __init__(self, left, right): | |
| self.left = left | |
| self.right = right | |
| class Item: | |
| def __init__(self, pid, pos=0): | |
| self.pid = pid | |
| self.pos = pos | |
| def next_token(self): | |
| prod = cfg[self.pid] | |
| if self.pos < len(prod.right): | |
| return prod.right[self.pos] | |
| else: | |
| return None | |
| def __hash__(self): | |
| return hash((self.pid, self.pos)) | |
| def __eq__(self, other): | |
| return (self.pid, self.pos) == (other.pid, other.pos) | |
| def __ne__(self, other): | |
| return not(self == other) | |
| class State: | |
| def __init__(self, root): | |
| # root should be tuple | |
| self.root = root | |
| self.items = self.closure() | |
| def go_to(self, token): | |
| j = set() | |
| for item in self.items: | |
| if item.next_token() and item.next_token() == token: | |
| j.add(Item(item.pid, item.pos + 1)) | |
| if not j: | |
| return None | |
| return State(tuple(j)) | |
| def closure(self): | |
| res = set() | |
| res |= set(self.root) | |
| while True: | |
| addon = set() | |
| for item in res: | |
| if item.next_token() and not item.next_token().is_term: | |
| for p in ht[item.next_token()]: | |
| if Item(p) not in res: | |
| addon.add(Item(p)) | |
| if not addon: | |
| break | |
| else: | |
| res |= addon | |
| return res | |
| def __hash__(self): | |
| return hash(self.root) | |
| def __eq__(self, other): | |
| return True | |
| def __ne__(self, other): | |
| return False | |
| def generate(): | |
| states = {State((Item(0),))} | |
| while True: | |
| addon = set() | |
| for state in states: | |
| for item in state.items: | |
| new_state = state.go_to(item.next_token()) | |
| if new_state and new_state not in states: | |
| addon.add(new_state) | |
| if not addon: | |
| break | |
| else: | |
| states |= addon | |
| print(len(states)) | |
| def main(): | |
| fs = Token('S\'', False) | |
| s = Token('S', False) | |
| d = Token('$', True) | |
| lp = Token('(', True) | |
| rp = Token(')', True) | |
| l = Token('L', False) | |
| x = Token('x', True) | |
| colon = Token(',', True) | |
| cfg.append(Production(fs, [s, d])) | |
| cfg.append(Production(s, [lp,l,rp])) | |
| cfg.append(Production(s, [x])) | |
| cfg.append(Production(l, [s])) | |
| cfg.append(Production(l, [l, colon, s])) | |
| ht[fs] = [0] | |
| ht[s] = [1,2] | |
| ht[l] = [3,4] | |
| generate() | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment