fork download 
  1. """
  2. KSTACK specification
  3.  
  4. KSTACK is a stack-based language. Program state is comprised of a single stack of unsigned integers of arbitrary size.
  5.  
  6. A program is comprised of some number of commands, macros, and control flow elements.
  7.  
  8. --- commands ---
  9.  
  10. commands manipulate the stack in various ways.
  11. pop - remove the top element of the stack.
  12. <number> - push the number onto the stack.
  13. '<string>' push the ordinal value of each character onto the stack, in reverse order. All strings end with an implicit null character.
  14. copy - add a duplicate of the top element of the stack to the stack.
  15. swap - swap the top two elements of the stack.
  16. gt - compare the top two elements of the stack, and push the result:
  17.     top > item_below_top : 1
  18.     top <= item_below_top: 0
  19. inc - increment top by one.
  20. dec - decrement top by one.
  21. add - pop the top element of the stack and increment the new top by that much.
  22. sub - pop the top element of the stack and decrement the new top by that much.
  23. print - convert the top element of the stack to a character and print it. If the number does not map to a character in the ASCII range, the result is undefined.
  24.  
  25. show_stack - print the contents of the stack.
  26.  
  27. If there are not enough elements on the stack to perform the given command, the result is undefined.
  28. When undefined behavior occurs, it is recommended (but not required) that the program terminate with an error message.
  29.  
  30. --- control flow elements ---
  31.  
  32. KSTACK has one native control flow element, `while`.
  33.  
  34. while{
  35.     <body>
  36. }
  37.  
  38. At the beginning of the while block, the top element of the stack is (non-destructively) compared to zero. If the top element is zero, the body is skipped. Otherwise, the body is executed repeatedly, until the top element is zero.
  39.  
  40. --- macros ---
  41. a macro is an identifier that can expand into one or more commands or control flow elements.
  42. a macro is defined using a definition block, with the syntax:
  43.  
  44. def <macro name> {
  45. <body>
  46. }
  47.  
  48. If a macro definition contains a macro definition, the result is undefined.
  49. A macro definition may contain other macros' identifiers.
  50. A macro cannot contain its own identifier, either directly or via other macros.
  51. If a macro is defined more than once, the result is undefined.
  52. If a macro's identifier matches the name of a built-in command, the result is undefined. Recommended behavior: the macro overrides the default behavior.
  53. Macro definitions may not appear within a while body or a macro body."""
  54.  
  55. import re
  56.  
  57. token_rules = [
  58.     ("while\s*{", "WHILE_START"),
  59.     ("def\s+(\w+)\s*{", "MACRO_START"),
  60.     (re.escape("}"), "BLOCK_END"), #can be while or def
  61.     (r"\d+", "NUMBER"),
  62.     (r"'([^']*)'", "STRING"),
  63.     (r"\w+", "IDENTIFIER"),
  64.     (r"\s+", "WHITESPACE")
  65. ]
  66. token_rules = [(re.compile(pattern), name) for pattern, name in token_rules]
  67.  
  68.  
  69. def tokenize(s, token_rules):
  70.     idx = 0
  71.     results = []
  72.     while idx < len(s):
  73.         for pattern, name in token_rules:
  74.             m = pattern.match(s, idx)
  75.             if m:
  76.                 results.append((m, name))
  77.                 idx = m.end()
  78.                 break
  79.         else:
  80.             raise Exception(f"Can't tokenize string at index {idx}")
  81.     results.append((None, "PROGRAM_END"))
  82.     return results
  83.  
  84. def expect(token_stream, expected_name):
  85.     value, name = token_stream[-1]
  86.     if name != expected_name:
  87.         raise Exception(f"Expected {expected_name}, got {name}")
  88.     return token_stream.pop()
  89.  
  90. def parse_macro(token_stream):
  91.     match, _ = expect(token_stream, "MACRO_START")
  92.     identifier = match.group(1)
  93.     body = parse_body(token_stream)
  94.     expect(token_stream, "BLOCK_END")
  95.     return {"name": "Macro", "identifier": identifier, "body": body}
  96.  
  97. def parse_command(token_stream):
  98.     value, name = token_stream[-1]
  99.     if name not in ("NUMBER", "IDENTIFIER"):
  100.         raise Exception(f"Expected NUMBER or IDENTIFIER, got {name}")
  101.     token_stream.pop()
  102.     return {"name": "Atom", "value": value.group()}
  103.  
  104. def parse_string(token_stream):
  105.     match, _ = expect(token_stream, "STRING")
  106.     value = match.group(1)
  107.     chars = "\0" + value[::-1]
  108.     return {"name": "Block", "children": [
  109.         {"name": "Atom", "value": str(ord(c))}
  110.         for c in chars
  111.     ]}
  112.  
  113. def parse_while(token_stream):
  114.     expect(token_stream, "WHILE_START")
  115.     body = parse_body(token_stream)
  116.     expect(token_stream, "BLOCK_END")
  117.     return {"name": "While", "body": body}
  118.  
  119. def parse_body(token_stream):
  120.     children = []
  121.     while True:
  122.         value, name = token_stream[-1]
  123.         if name == "WHILE_START":
  124.             children.append(parse_while(token_stream))
  125.         elif name == "MACRO_START":
  126.             children.append(parse_macro(token_stream))
  127.         elif name == "BLOCK_END":
  128.             break
  129.         elif name == "STRING":
  130.             children.append(parse_string(token_stream))
  131.         elif name in ("NUMBER", "IDENTIFIER"):
  132.             children.append(parse_command(token_stream))
  133.         elif name == "PROGRAM_END":
  134.             break
  135.         else:
  136.             raise Exception(f"Unrecognized token name {name}")
  137.     return {"name": "Block", "children": children}
  138.  
  139.  
  140. def parse(token_stream):
  141.     token_stream = [token for token in token_stream if token[1] != "WHITESPACE"]
  142.     token_stream.reverse()
  143.     result = parse_body(token_stream)
  144.     expect(token_stream, "PROGRAM_END")
  145.     assert len(token_stream) == 0, f"{len(token_steam)} tokens remained at end of parsing"
  146.     return result
  147.  
  148. def to_lines(node, indent=0):
  149.     INDENT = "    "
  150.     result = []
  151.     if node["name"] == "Block":
  152.         for child in node["children"]:
  153.             result.extend(to_lines(child, indent))
  154.     elif node["name"] == "While":
  155.         result.append("while {")
  156.         result.extend(to_lines(node["body"], 1))
  157.         result.extend("}")
  158.     elif node["name"] == "Macro":
  159.         result.append("def " + node["identifier"] + " {")
  160.         result.extend(to_lines(node["body"], 1))
  161.         result.extend("}")
  162.     elif node["name"] == "Atom":
  163.         result.append(node["value"])
  164.     else:
  165.         raise Exception(f"to_lines not implemented for node type {node['name']}")
  166.     return [INDENT*indent + line for line in result]
  167.  
  168. def execute(node, stack=None, macros=None):
  169.     if stack is None:
  170.         stack = []
  171.     if macros is None:
  172.         macros = {}
  173.     if node["name"] == "Block":
  174.         for child in node["children"]:
  175.             execute(child, stack, macros)
  176.     elif node["name"] == "Macro":
  177.         macros[node["identifier"]] = node["body"]
  178.     elif node["name"] == "While":
  179.         while stack[-1] != 0:
  180.             execute(node["body"], stack, macros)
  181.     elif node["name"] == "Atom":
  182.         value = node["value"]
  183.         if value.isdigit():
  184.             stack.append(int(value))
  185.         elif value in macros:
  186.             execute(macros[value], stack, macros)
  187.         elif value == "pop":
  188.             stack.pop()
  189.         elif value == "copy":
  190.             stack.append(stack[-1])
  191.         elif value == "swap":
  192.             a,b = stack.pop(), stack.pop()
  193.             stack.append(a)
  194.             stack.append(b)
  195.         elif value == "print":
  196.             print(chr(stack[-1]), end="")
  197.         elif value == "inc":
  198.             stack[-1] += 1
  199.         elif value == "dec":
  200.             stack[-1] -= 1
  201.             assert stack[-1] >= 0
  202.         elif value == "add":
  203.             stack.append(stack.pop() + stack.pop())
  204.         elif value == "sub":
  205.             stack.append(-stack.pop() + stack.pop())
  206.             assert stack[-1] >= 0
  207.         elif value == "gt":
  208.             x = 1 if stack[-1] > stack[-2] else 0
  209.             stack.append(x)
  210.         else:
  211.             raise Exception(f"command {value} not implemented yet")
  212.     else:
  213.         raise Exception(f"Can't execute node type {node['name']} yet.")
  214.  
  215. s = """
  216. def print_str{
  217.     while{
  218.         print
  219.         pop
  220.     }
  221.     pop
  222. }
  223.  
  224. def divmod_by_10{
  225.     0 swap
  226.     9 swap gt
  227.     while{
  228.         pop swap pop
  229.         10 sub
  230.         swap inc swap
  231.         9 swap gt
  232.     }
  233.     pop swap pop
  234. }
  235.  
  236. def print_digit{
  237.     48 add
  238.     print
  239.     48 sub
  240. }
  241.  
  242. def int_to_zero_terminated_char_sequence{
  243.     0
  244.     swap
  245.     divmod_by_10
  246.     48 add
  247.     swap
  248.     while{
  249.         divmod_by_10
  250.         48 add
  251.         swap
  252.     }
  253.     pop
  254. }
  255.  
  256. def print_number{
  257.     copy
  258.     int_to_zero_terminated_char_sequence
  259.     print_str
  260. }
  261.  
  262. 99
  263. while{
  264.     '\n' print_str
  265.     print_number
  266.     ' Bottles of beer on the wall, ' print_str
  267.     print_number
  268.     ' Bottles of beer. Take one down, pass it around, ' print_str
  269.     dec
  270.     print_number
  271.     ' Bottles of beer on the wall. ' print_str
  272. }
  273. """
  274.  
  275. token_stream = tokenize(s, token_rules)
  276. ast = parse(token_stream)
  277. execute(ast)
Success #stdin #stdout 0.1s 10908KB
comments (?)
stdin 
Standard input is empty
stdout 
99 Bottles of beer on the wall, 99 Bottles of beer. Take one down, pass it around, 98 Bottles of beer on the wall. 
98 Bottles of beer on the wall, 98 Bottles of beer. Take one down, pass it around, 97 Bottles of beer on the wall. 
97 Bottles of beer on the wall, 97 Bottles of beer. Take one down, pass it around, 96 Bottles of beer on the wall. 
96 Bottles of beer on the wall, 96 Bottles of beer. Take one down, pass it around, 95 Bottles of beer on the wall. 
95 Bottles of beer on the wall, 95 Bottles of beer. Take one down, pass it around, 94 Bottles of beer on the wall. 
94 Bottles of beer on the wall, 94 Bottles of beer. Take one down, pass it around, 93 Bottles of beer on the wall. 
93 Bottles of beer on the wall, 93 Bottles of beer. Take one down, pass it around, 92 Bottles of beer on the wall. 
92 Bottles of beer on the wall, 92 Bottles of beer. Take one down, pass it around, 91 Bottles of beer on the wall. 
91 Bottles of beer on the wall, 91 Bottles of beer. Take one down, pass it around, 90 Bottles of beer on the wall. 
90 Bottles of beer on the wall, 90 Bottles of beer. Take one down, pass it around, 89 Bottles of beer on the wall. 
89 Bottles of beer on the wall, 89 Bottles of beer. Take one down, pass it around, 88 Bottles of beer on the wall. 
88 Bottles of beer on the wall, 88 Bottles of beer. Take one down, pass it around, 87 Bottles of beer on the wall. 
87 Bottles of beer on the wall, 87 Bottles of beer. Take one down, pass it around, 86 Bottles of beer on the wall. 
86 Bottles of beer on the wall, 86 Bottles of beer. Take one down, pass it around, 85 Bottles of beer on the wall. 
85 Bottles of beer on the wall, 85 Bottles of beer. Take one down, pass it around, 84 Bottles of beer on the wall. 
84 Bottles of beer on the wall, 84 Bottles of beer. Take one down, pass it around, 83 Bottles of beer on the wall. 
83 Bottles of beer on the wall, 83 Bottles of beer. Take one down, pass it around, 82 Bottles of beer on the wall. 
82 Bottles of beer on the wall, 82 Bottles of beer. Take one down, pass it around, 81 Bottles of beer on the wall. 
81 Bottles of beer on the wall, 81 Bottles of beer. Take one down, pass it around, 80 Bottles of beer on the wall. 
80 Bottles of beer on the wall, 80 Bottles of beer. Take one down, pass it around, 79 Bottles of beer on the wall. 
79 Bottles of beer on the wall, 79 Bottles of beer. Take one down, pass it around, 78 Bottles of beer on the wall. 
78 Bottles of beer on the wall, 78 Bottles of beer. Take one down, pass it around, 77 Bottles of beer on the wall. 
77 Bottles of beer on the wall, 77 Bottles of beer. Take one down, pass it around, 76 Bottles of beer on the wall. 
76 Bottles of beer on the wall, 76 Bottles of beer. Take one down, pass it around, 75 Bottles of beer on the wall. 
75 Bottles of beer on the wall, 75 Bottles of beer. Take one down, pass it around, 74 Bottles of beer on the wall. 
74 Bottles of beer on the wall, 74 Bottles of beer. Take one down, pass it around, 73 Bottles of beer on the wall. 
73 Bottles of beer on the wall, 73 Bottles of beer. Take one down, pass it around, 72 Bottles of beer on the wall. 
72 Bottles of beer on the wall, 72 Bottles of beer. Take one down, pass it around, 71 Bottles of beer on the wall. 
71 Bottles of beer on the wall, 71 Bottles of beer. Take one down, pass it around, 70 Bottles of beer on the wall. 
70 Bottles of beer on the wall, 70 Bottles of beer. Take one down, pass it around, 69 Bottles of beer on the wall. 
69 Bottles of beer on the wall, 69 Bottles of beer. Take one down, pass it around, 68 Bottles of beer on the wall. 
68 Bottles of beer on the wall, 68 Bottles of beer. Take one down, pass it around, 67 Bottles of beer on the wall. 
67 Bottles of beer on the wall, 67 Bottles of beer. Take one down, pass it around, 66 Bottles of beer on the wall. 
66 Bottles of beer on the wall, 66 Bottles of beer. Take one down, pass it around, 65 Bottles of beer on the wall. 
65 Bottles of beer on the wall, 65 Bottles of beer. Take one down, pass it around, 64 Bottles of beer on the wall. 
64 Bottles of beer on the wall, 64 Bottles of beer. Take one down, pass it around, 63 Bottles of beer on the wall. 
63 Bottles of beer on the wall, 63 Bottles of beer. Take one down, pass it around, 62 Bottles of beer on the wall. 
62 Bottles of beer on the wall, 62 Bottles of beer. Take one down, pass it around, 61 Bottles of beer on the wall. 
61 Bottles of beer on the wall, 61 Bottles of beer. Take one down, pass it around, 60 Bottles of beer on the wall. 
60 Bottles of beer on the wall, 60 Bottles of beer. Take one down, pass it around, 59 Bottles of beer on the wall. 
59 Bottles of beer on the wall, 59 Bottles of beer. Take one down, pass it around, 58 Bottles of beer on the wall. 
58 Bottles of beer on the wall, 58 Bottles of beer. Take one down, pass it around, 57 Bottles of beer on the wall. 
57 Bottles of beer on the wall, 57 Bottles of beer. Take one down, pass it around, 56 Bottles of beer on the wall. 
56 Bottles of beer on the wall, 56 Bottles of beer. Take one down, pass it around, 55 Bottles of beer on the wall. 
55 Bottles of beer on the wall, 55 Bottles of beer. Take one down, pass it around, 54 Bottles of beer on the wall. 
54 Bottles of beer on the wall, 54 Bottles of beer. Take one down, pass it around, 53 Bottles of beer on the wall. 
53 Bottles of beer on the wall, 53 Bottles of beer. Take one down, pass it around, 52 Bottles of beer on the wall. 
52 Bottles of beer on the wall, 52 Bottles of beer. Take one down, pass it around, 51 Bottles of beer on the wall. 
51 Bottles of beer on the wall, 51 Bottles of beer. Take one down, pass it around, 50 Bottles of beer on the wall. 
50 Bottles of beer on the wall, 50 Bottles of beer. Take one down, pass it around, 49 Bottles of beer on the wall. 
49 Bottles of beer on the wall, 49 Bottles of beer. Take one down, pass it around, 48 Bottles of beer on the wall. 
48 Bottles of beer on the wall, 48 Bottles of beer. Take one down, pass it around, 47 Bottles of beer on the wall. 
47 Bottles of beer on the wall, 47 Bottles of beer. Take one down, pass it around, 46 Bottles of beer on the wall. 
46 Bottles of beer on the wall, 46 Bottles of beer. Take one down, pass it around, 45 Bottles of beer on the wall. 
45 Bottles of beer on the wall, 45 Bottles of beer. Take one down, pass it around, 44 Bottles of beer on the wall. 
44 Bottles of beer on the wall, 44 Bottles of beer. Take one down, pass it around, 43 Bottles of beer on the wall. 
43 Bottles of beer on the wall, 43 Bottles of beer. Take one down, pass it around, 42 Bottles of beer on the wall. 
42 Bottles of beer on the wall, 42 Bottles of beer. Take one down, pass it around, 41 Bottles of beer on the wall. 
41 Bottles of beer on the wall, 41 Bottles of beer. Take one down, pass it around, 40 Bottles of beer on the wall. 
40 Bottles of beer on the wall, 40 Bottles of beer. Take one down, pass it around, 39 Bottles of beer on the wall. 
39 Bottles of beer on the wall, 39 Bottles of beer. Take one down, pass it around, 38 Bottles of beer on the wall. 
38 Bottles of beer on the wall, 38 Bottles of beer. Take one down, pass it around, 37 Bottles of beer on the wall. 
37 Bottles of beer on the wall, 37 Bottles of beer. Take one down, pass it around, 36 Bottles of beer on the wall. 
36 Bottles of beer on the wall, 36 Bottles of beer. Take one down, pass it around, 35 Bottles of beer on the wall. 
35 Bottles of beer on the wall, 35 Bottles of beer. Take one down, pass it around, 34 Bottles of beer on the wall. 
34 Bottles of beer on the wall, 34 Bottles of beer. Take one down, pass it around, 33 Bottles of beer on the wall. 
33 Bottles of beer on the wall, 33 Bottles of beer. Take one down, pass it around, 32 Bottles of beer on the wall. 
32 Bottles of beer on the wall, 32 Bottles of beer. Take one down, pass it around, 31 Bottles of beer on the wall. 
31 Bottles of beer on the wall, 31 Bottles of beer. Take one down, pass it around, 30 Bottles of beer on the wall. 
30 Bottles of beer on the wall, 30 Bottles of beer. Take one down, pass it around, 29 Bottles of beer on the wall. 
29 Bottles of beer on the wall, 29 Bottles of beer. Take one down, pass it around, 28 Bottles of beer on the wall. 
28 Bottles of beer on the wall, 28 Bottles of beer. Take one down, pass it around, 27 Bottles of beer on the wall. 
27 Bottles of beer on the wall, 27 Bottles of beer. Take one down, pass it around, 26 Bottles of beer on the wall. 
26 Bottles of beer on the wall, 26 Bottles of beer. Take one down, pass it around, 25 Bottles of beer on the wall. 
25 Bottles of beer on the wall, 25 Bottles of beer. Take one down, pass it around, 24 Bottles of beer on the wall. 
24 Bottles of beer on the wall, 24 Bottles of beer. Take one down, pass it around, 23 Bottles of beer on the wall. 
23 Bottles of beer on the wall, 23 Bottles of beer. Take one down, pass it around, 22 Bottles of beer on the wall. 
22 Bottles of beer on the wall, 22 Bottles of beer. Take one down, pass it around, 21 Bottles of beer on the wall. 
21 Bottles of beer on the wall, 21 Bottles of beer. Take one down, pass it around, 20 Bottles of beer on the wall. 
20 Bottles of beer on the wall, 20 Bottles of beer. Take one down, pass it around, 19 Bottles of beer on the wall. 
19 Bottles of beer on the wall, 19 Bottles of beer. Take one down, pass it around, 18 Bottles of beer on the wall. 
18 Bottles of beer on the wall, 18 Bottles of beer. Take one down, pass it around, 17 Bottles of beer on the wall. 
17 Bottles of beer on the wall, 17 Bottles of beer. Take one down, pass it around, 16 Bottles of beer on the wall. 
16 Bottles of beer on the wall, 16 Bottles of beer. Take one down, pass it around, 15 Bottles of beer on the wall. 
15 Bottles of beer on the wall, 15 Bottles of beer. Take one down, pass it around, 14 Bottles of beer on the wall. 
14 Bottles of beer on the wall, 14 Bottles of beer. Take one down, pass it around, 13 Bottles of beer on the wall. 
13 Bottles of beer on the wall, 13 Bottles of beer. Take one down, pass it around, 12 Bottles of beer on the wall. 
12 Bottles of beer on the wall, 12 Bottles of beer. Take one down, pass it around, 11 Bottles of beer on the wall. 
11 Bottles of beer on the wall, 11 Bottles of beer. Take one down, pass it around, 10 Bottles of beer on the wall. 
10 Bottles of beer on the wall, 10 Bottles of beer. Take one down, pass it around, 9 Bottles of beer on the wall. 
9 Bottles of beer on the wall, 9 Bottles of beer. Take one down, pass it around, 8 Bottles of beer on the wall. 
8 Bottles of beer on the wall, 8 Bottles of beer. Take one down, pass it around, 7 Bottles of beer on the wall. 
7 Bottles of beer on the wall, 7 Bottles of beer. Take one down, pass it around, 6 Bottles of beer on the wall. 
6 Bottles of beer on the wall, 6 Bottles of beer. Take one down, pass it around, 5 Bottles of beer on the wall. 
5 Bottles of beer on the wall, 5 Bottles of beer. Take one down, pass it around, 4 Bottles of beer on the wall. 
4 Bottles of beer on the wall, 4 Bottles of beer. Take one down, pass it around, 3 Bottles of beer on the wall. 
3 Bottles of beer on the wall, 3 Bottles of beer. Take one down, pass it around, 2 Bottles of beer on the wall. 
2 Bottles of beer on the wall, 2 Bottles of beer. Take one down, pass it around, 1 Bottles of beer on the wall. 
1 Bottles of beer on the wall, 1 Bottles of beer. Take one down, pass it around, 0 Bottles of beer on the wall.
https://ideone.com/luyzrW
language:
Python 3 (python  3.12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!