Created
January 23, 2021 03:25
-
-
Save darius/e2a068dbd7c17b5985c88f1c508d3ce8 to your computer and use it in GitHub Desktop.
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
| """ | |
| derived from Kragen Sitaker's http://canonical.org/~kragen/sw/dev3/caronte.py | |
| """ | |
| from __future__ import division, print_function | |
| import itertools | |
| import grammars | |
| from semantics import ast_semantics, ComboSemantics, DictSemantics | |
| grammar_text = r""" | |
| start : _ expr. | |
| expr : e10 ++ (';'_ [:drop]). | |
| e10 : lvalue ( ':='_ e10 [:put] | |
| | '='_ e10 [:init] ) | |
| | e40. | |
| lvalue : id ([:fetch] '['_ expr ']'_)*. | |
| e40 : lvalue '<-'_ e60 '|'_ [:mklabel] >AGAIN [:mklabel] >LOOP | |
| [@LOOP :each] | |
| @AGAIN | |
| e40 | |
| @LOOP [@AGAIN :loop] | |
| | e60. | |
| e60 : e65 ( '?'_ [:mklabel] >ELSE [:mklabel] >THEN | |
| [@ELSE :unless] | |
| e65 | |
| ':'_ [@THEN :jump] | |
| @ELSE | |
| e60 | |
| @THEN | |
| )?. | |
| e65 : e70 ('=='_ e70 [:eq])?. | |
| e70 : e110 ('+'_ e110 [:add])*. | |
| e110 : e120 ( '['_ expr ']'_ [:fetch] | |
| | '('_ actuals ')'_ [:call] | |
| )*. | |
| e120 : '('_ expr ')'_ | |
| | id [:fetch] | |
| | string :con | |
| | integer :con | |
| | '{'_ '}'_ [:newdict]. | |
| actuals : (e40 [:arg]) ** (','_). | |
| id : { /[A-Za-z_]/ /\w/* } _ :id. | |
| string : '"' { (/[^\\"]/ | '\\' /./)* } '"' _. | |
| integer : { /\d/+ } _ :int. | |
| _ : /\s/*. | |
| """ | |
| def Caronte(make_parsing): | |
| def caronte(s, rule=None): | |
| return caronte.grammar.parse(s, rule).interpret(caronte_actions) | |
| caronte.grammar = grammars.Grammar(grammar_text, make_parsing) | |
| return caronte | |
| gensym_counter = itertools.count() | |
| def mklabel(): return '_%d' % next(gensym_counter) | |
| caronte_actions = ComboSemantics(ast_semantics, DictSemantics(dict(int=int, mklabel=mklabel))) | |
| ## from nonincremental import Parsing | |
| ## parse = Caronte(Parsing) | |
| ## parse("a", rule='id') | |
| #. (('id', 'a'),) | |
| ## parse("a[42] := b") | |
| #. (('id', 'a'), ('fetch',), ('con', 42), ('id', 'b'), ('fetch',), ('put',)) | |
| def run(prog): | |
| insns = [] | |
| # Assembler pass 1 | |
| labels = {} | |
| for line in prog: | |
| if isinstance(line, str): # label | |
| assert line not in labels | |
| labels[line] = len(insns) | |
| else: | |
| insns.append(line) | |
| # Assembler pass 2 | |
| for i, line in enumerate(insns): | |
| if line[0] in ('each', 'loop', 'unless', 'jump'): | |
| insns[i] = (line[0], labels[line[1]]) | |
| pc = 0 | |
| ram = {'iota': lambda n: list(range(n)), 'say': lambda v: print(*v, end='')} | |
| stack = [] | |
| args = [] | |
| loops = [] | |
| # Now run it | |
| ninsns = len(insns) | |
| while pc < ninsns: | |
| insn = insns[pc] | |
| c = insn[0] | |
| if c == 'newdict': | |
| stack.append({}) | |
| elif c == 'drop': | |
| stack.pop() | |
| elif c == 'con': | |
| stack.append(insn[1]) | |
| elif c == 'add': | |
| x = stack.pop() | |
| stack.append(stack.pop() + x) | |
| elif c == 'eq': | |
| x = stack.pop() | |
| stack.append('true' if stack.pop() == x else 'false') | |
| elif c == 'arg': | |
| args.append(stack.pop()) | |
| elif c == 'call': | |
| f = stack.pop() | |
| stack.append(f(*args)) | |
| args = [] | |
| elif c == 'id': | |
| stack.append(ram) | |
| stack.append(insn[1]) | |
| elif c == 'fetch': | |
| idx = stack.pop() | |
| loc = stack.pop() | |
| stack.append(loc[idx]) | |
| elif c in ('init', 'put'): | |
| val = stack.pop() | |
| idx = stack.pop() | |
| loc = stack.pop() | |
| loc[idx] = val | |
| stack.append(val) | |
| elif c == 'each': | |
| seq = stack.pop() | |
| idx = stack.pop() | |
| loc = stack.pop() | |
| loops.append([loc, idx, seq, 0]) | |
| pc = insn[1] | |
| continue | |
| elif c == 'loop': | |
| loc, off, seq, idx = loops[-1] | |
| if idx >= len(seq): | |
| loops.pop() | |
| pc += 1 | |
| stack.append(seq) # was missing from Kragen's; I think it's the desired semantics? | |
| continue | |
| loc[off] = seq[idx] | |
| loops[-1][-1] += 1 | |
| pc = insn[1] | |
| continue | |
| elif c == 'unless': | |
| x = stack.pop() | |
| assert x in ('true', 'false') | |
| if x == 'false': | |
| pc = insn[1] | |
| continue | |
| elif c == 'jump': | |
| pc = insn[1] | |
| continue | |
| else: | |
| assert 0, "bad insn %r at %d" % (c, pc) | |
| pc += 1 | |
| # Smoke test | |
| sier = """ | |
| c = {}; | |
| x <- iota(128) | (c[x] = 0); | |
| c[0] := 1; | |
| y <- iota(128) | ( | |
| x <- iota(127) | (c[x+1] := (c[x] + c[x+1] == 1) ? 1 : 0); | |
| x <- iota(128) | say((c[x] == 0) ? " " : "#"); | |
| say("\n") | |
| ) | |
| """ | |
| def testme(): | |
| from nonincremental import Parsing | |
| parser = Caronte(Parsing) | |
| prog = parser(sier) | |
| for line in prog: print(line) | |
| print() | |
| run(prog) | |
| if __name__ == '__main__': | |
| testme() | |
| ## testme() | |
| #. ('id', 'c') | |
| #. ('newdict',) | |
| #. ('init',) | |
| #. ('drop',) | |
| #. ('id', 'x') | |
| #. ('id', 'iota') | |
| #. ('fetch',) | |
| #. ('con', 128) | |
| #. ('arg',) | |
| #. ('call',) | |
| #. ('each', '_1') | |
| #. _0 | |
| #. ('id', 'c') | |
| #. ('fetch',) | |
| #. ('id', 'x') | |
| #. ('fetch',) | |
| #. ('con', 0) | |
| #. ('init',) | |
| #. _1 | |
| #. ('loop', '_0') | |
| #. ('drop',) | |
| #. ('id', 'c') | |
| #. ('fetch',) | |
| #. ('con', 0) | |
| #. ('con', 1) | |
| #. ('put',) | |
| #. ('drop',) | |
| #. ('id', 'y') | |
| #. ('id', 'iota') | |
| #. ('fetch',) | |
| #. ('con', 128) | |
| #. ('arg',) | |
| #. ('call',) | |
| #. ('each', '_3') | |
| #. _2 | |
| #. ('id', 'x') | |
| #. ('id', 'iota') | |
| #. ('fetch',) | |
| #. ('con', 127) | |
| #. ('arg',) | |
| #. ('call',) | |
| #. ('each', '_5') | |
| #. _4 | |
| #. ('id', 'c') | |
| #. ('fetch',) | |
| #. ('id', 'x') | |
| #. ('fetch',) | |
| #. ('con', 1) | |
| #. ('add',) | |
| #. ('id', 'c') | |
| #. ('fetch',) | |
| #. ('id', 'x') | |
| #. ('fetch',) | |
| #. ('fetch',) | |
| #. ('id', 'c') | |
| #. ('fetch',) | |
| #. ('id', 'x') | |
| #. ('fetch',) | |
| #. ('con', 1) | |
| #. ('add',) | |
| #. ('fetch',) | |
| #. ('add',) | |
| #. ('con', 1) | |
| #. ('eq',) | |
| #. ('unless', '_6') | |
| #. ('con', 1) | |
| #. ('jump', '_7') | |
| #. _6 | |
| #. ('con', 0) | |
| #. _7 | |
| #. ('put',) | |
| #. _5 | |
| #. ('loop', '_4') | |
| #. ('drop',) | |
| #. ('id', 'x') | |
| #. ('id', 'iota') | |
| #. ('fetch',) | |
| #. ('con', 128) | |
| #. ('arg',) | |
| #. ('call',) | |
| #. ('each', '_9') | |
| #. _8 | |
| #. ('id', 'say') | |
| #. ('fetch',) | |
| #. ('id', 'c') | |
| #. ('fetch',) | |
| #. ('id', 'x') | |
| #. ('fetch',) | |
| #. ('fetch',) | |
| #. ('con', 0) | |
| #. ('eq',) | |
| #. ('unless', '_10') | |
| #. ('con', ' ') | |
| #. ('jump', '_11') | |
| #. _10 | |
| #. ('con', '#') | |
| #. _11 | |
| #. ('arg',) | |
| #. ('call',) | |
| #. _9 | |
| #. ('loop', '_8') | |
| #. ('drop',) | |
| #. ('id', 'say') | |
| #. ('fetch',) | |
| #. ('con', '\n') | |
| #. ('arg',) | |
| #. ('call',) | |
| #. _3 | |
| #. ('loop', '_2') | |
| #. | |
| #. ################################################################################################################################ | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. ######## ######## ######## ######## ######## ######## ######## ######## | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. ################ ################ ################ ################ | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. ######## ######## ######## ######## | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ################################ ################################ | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. ######## ######## ######## ######## | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ################ ################ | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ######## ######## | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. #### #### | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. ################################################################ | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. ######## ######## ######## ######## | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ################ ################ | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ######## ######## | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. #### #### | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. ################################ | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ######## ######## | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. #### #### | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. ################ | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. #### #### | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. ######## | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. #### | |
| #. # # | |
| #. ## | |
| #. # |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment