-
Notifications
You must be signed in to change notification settings - Fork 0
/
parse.py
141 lines (114 loc) · 3.99 KB
/
parse.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
from __future__ import annotations
import sys
import typing as t
class AST:
"""Representation of the constructed tree out of a list of token."""
def __init__(self, name: str, operands: t.Optional[t.List[AST]] = None) -> None:
self.name = name
self.operands = operands or []
def __contains__(self, name: str) -> bool:
if self.name == name:
return True
for ast in self.operands:
if name in ast:
return True
return False
def __str__(self) -> str:
if self.name in ("=", "?"):
return "{} {}".format(self.name, self.operands)
if self.name in ("=>", "<=>"):
return "{1} {0} {2}".format(self.name, *self.operands)
return ["{}", "({} {})", "({1} {0} {2})"][len(self.operands)].format(
self.name, *self.operands
)
def __repr__(self):
return str(self)
class RecursionHelper:
"""Helper class used to temporarily increase the
size of the stack for the recursive descent parser"""
def __init__(self, limit: int) -> None:
self.limit = limit
self.old = sys.getrecursionlimit()
def __enter__(self):
sys.setrecursionlimit(self.limit)
def __exit__(self, *_):
sys.setrecursionlimit(self.old)
def atom(stream: t.List[str]) -> t.Tuple[int, AST]:
"""[a-zA-Z] | \\( expr \\)"""
if stream[0].isalpha():
return 1, AST(stream[0])
if stream[0] == "(":
n, ast = expr(stream[1:])
if stream[n + 1] == ")":
return n + 2, ast
raise SyntaxError("Expected ')'")
raise SyntaxError("Unexpected token '{}'".format(stream[0]))
def notop(stream: t.List[str]) -> t.Tuple[int, AST]:
"""(!)* atom"""
if stream[0] == "!":
n, ast = notop(stream[1:])
if not n:
raise SyntaxError("Unexpected EOF.")
return n + 1, AST("!", [ast])
return atom(stream)
def andop(
stream: t.List[str], n: t.Optional[int] = None, last: t.Optional[AST] = None
) -> t.Tuple[int, AST]:
"""not (+ not)*"""
if n is None:
n, last = notop(stream)
if n == len(stream) or stream[n] != "+":
return n, last
m, rast = notop(stream[n + 1 :])
return andop(stream, n + m + 1, AST("+", [last, rast]))
def orop(
stream: t.List[str], n: t.Optional[int] = None, last: t.Optional[AST] = None
) -> t.Tuple[int, AST]:
"""and (\\| and)*"""
if n is None:
n, last = andop(stream)
if n == len(stream) or stream[n] != "|":
return n, last
m, rast = andop(stream[n + 1 :])
return orop(stream, n + m + 1, AST("|", [last, rast]))
def xorop(
stream: t.List[str], n: t.Optional[int] = None, last: t.Optional[AST] = None
) -> t.Tuple[int, AST]:
"""or (^ or)*"""
if n is None:
n, last = orop(stream)
if n == len(stream) or stream[n] != "^":
return n, last
m, rast = orop(stream[n + 1 :])
# x ^ y <=> (x + !y) | (!x + y)
return xorop(
stream,
n + m + 1,
AST(
"|",
[AST("+", [last, AST("!", [rast])]), AST("+", [AST("!", [last]), rast])],
),
)
def expr(stream: t.List[str]) -> t.Tuple[int, AST]:
"""Alias for xor."""
try:
with RecursionHelper(8000):
return xorop(stream)
except IndexError:
raise SyntaxError("Unexpected EOL.")
def ifop(stream: t.List[str]) -> AST:
"""expr (=> | <=>) expr"""
n, last = expr(stream)
if not stream[n:] or stream[n] not in ("=>", "<=>"):
raise SyntaxError("Expected => or <=>.")
if not stream[n + 1 :]:
raise SyntaxError("Expected expression.")
m, rast = expr(stream[n + 1 :])
if stream[n + 1 + m :]:
raise SyntaxError("Unexpected character '{}'.".format(stream[n + 1 + m]))
return AST(stream[n], [last, rast])
def ident_serie(stream: t.List[str]) -> t.List[AST]:
"""([a-zA-Z])+"""
if [*filter(lambda s: not s.isalpha(), stream)]:
raise SyntaxError("Unexpected character.")
return [*map(AST, stream)]