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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
# ruff: noqa: PLW2901
# pyright: reportGeneralTypeIssues=false
# ty: ignore
# type: ignore
from __future__ import annotations
from collections import defaultdict
from collections.abc import Callable
from . import grammars
# Based on https://github.com/ncellar/autumn_v1/
# Returns the correct Rule instance for a RuleRef
def follow(node, rule_dict):
if isinstance(node, grammars.RuleRef):
return rule_dict.get(node.name, node)
else:
return node
class Nullable:
def __init__(self, children, resolved=False, nullable=False):
self.resolved = resolved
self.nullable = nullable
self.children = children
def resolve(self, node, rule_dict):
pass
def resolve_with(self, n):
self.resolved = True
self.nullable = n
self.children = None # No longer needed
all: Callable
any: Callable
of: Callable
no: Callable
yes: Callable
class _All(Nullable):
def resolve(self, node, rule_dict):
unresolved = []
for c in self.children:
c = follow(c, rule_dict)
n = c._nullability
if n.resolved:
if not n.nullable:
# Not nullable if any is not nullable
self.resolve_with(False)
return
else:
unresolved.append(c)
if not unresolved:
# Nullable if all are nullable
self.resolve_with(True)
else:
# Otherwise still unresolved
self.children = unresolved
class _Any(Nullable):
def resolve(self, node, rule_dict):
# Inverse of All
unresolved = []
for c in self.children:
c = follow(c, rule_dict)
n = c._nullability
if n.resolved:
if n.nullable:
self.resolve_with(True)
return
else:
unresolved.append(c)
if not unresolved:
self.resolve_with(False)
else:
self.children = unresolved
class _Single(Nullable):
def resolve(self, node, rule_dict):
n = follow(self.children[0], rule_dict)._nullability
if not n.resolved:
return
self.resolve_with(n.nullable)
Nullable.all = _All # Nullable if all children are nullable
Nullable.any = _Any # Nullable if one child is nullable
Nullable.of = lambda child: _Single(
[child],
) # Nullable if the only child is nullable
Nullable.no = lambda: Nullable(None, True, False) # Not nullable
Nullable.yes = lambda: Nullable(None, True, True) # Nullable
def resolve_nullability(grammar, rule_dict):
dependants = defaultdict(list)
visited = set() # To prevent infinite recursion
def walk(model): # TODO Write a walker for this?
if model in visited:
return
visited.add(model)
for child in model.children_list():
child = follow(child, rule_dict)
walk(child)
resolve(model)
def resolve(model):
nullability = model._nullability
if not nullability.resolved:
nullability.resolve(model, rule_dict)
if nullability.resolved:
for dependant in dependants[model]:
n = dependant._nullability
if not n.resolved:
resolve(
dependant,
) # Resolve nodes that depend on this one
else:
for n in nullability.children:
dependants[n].append(model)
walk(grammar)
# This breaks left recursive cycles by tagging
# left recursive rules
def find_left_recursion(grammar):
rule_dict = {
rule.name: rule for rule in grammar.rules
} # Required to resolve rule references
# First we need to resolve nullable rules
resolve_nullability(grammar, rule_dict)
# Traversable state
FIRST = 0
CUTOFF = 1
VISITED = 2
state = defaultdict(lambda: FIRST)
stack_depth = [0] # nonlocal workaround 2.7
stack_positions = {}
lr_stack_positions = [-1]
def walk(model):
if state[model] == FIRST:
state[model] = CUTOFF
else:
return
# beforeNode
leftrec = isinstance(model, grammars.Rule) and model.is_leftrec
if leftrec:
lr_stack_positions.append(stack_depth[0])
stack_positions[model] = stack_depth[0]
stack_depth[0] += 1
for child in model.at_same_pos(rule_dict):
child = follow(child, rule_dict)
walk(child)
# afterEdge
if (
state[child] == CUTOFF
and stack_positions[child] > lr_stack_positions[-1]
):
# turn off memoization for all rules that were involved in this cycle
for rule in stack_positions:
if isinstance(rule, grammars.Rule):
rule.is_memoizable = False
child.is_leftrec = True
# afterNode
if leftrec:
lr_stack_positions.pop()
del stack_positions[model]
stack_depth[0] -= 1
state[model] = VISITED
for rule in grammar.children_list():
walk(rule)
# print()
# for rule in grammar.children_list():
# print(rule)
# if rule.is_leftrec: print("-> Leftrec")
# if rule.is_nullable(): print("-> Nullable")
|
