Debian Codegraph @

ptk/grammar.py

raw
1 # -*- coding: utf-8 -*-
2
3 # (c) Jérôme Laheurte 2015-2026
4 # See LICENSE.txt
5
6 """
7 Context-free grammars objects. To define a grammar, inherit the
8 Grammar class and define a method decorated with 'production' for each
9 production.
10 """
11
12 import copy
13 import functools
14 import inspect
15 import logging
16 import warnings
17
18 from ptk.lexer import EOF, _LexerMeta
19 from ptk.utils import Singleton
20
21
22 class Epsilon(metaclass=Singleton): # pylint: disable=too-few-public-methods
23 """
24 Empty production
25 """
26 __reprval__ = '\u03B5'
27
28
29 class GrammarError(Exception):
30 """
31 Generic grammar error, like duplicate production.
32 """
33
34
35 class GrammarParseError(GrammarError):
36 """
37 Syntax error in a production specification.
38 """
39
40
41 @functools.total_ordering
42 class Production:
43 """
44 Production object
45 """
46 def __init__(self, name, callback, priority=None, attributes=None):
47 self.name = name
48 self.posarg = None
49 self.callback = callback
50 self.right = []
51 self.attributes = attributes or {}
52 self.__priority = priority
53 # position => id
54 self.__ids = {} # pylint: disable=unused-private-member
55
56 def add_symbol(self, identifier, name=None):
57 """
58 Append a symbol to the production's right side.
59 """
60 if name is not None:
61 if name in self.__ids.values():
62 raise GrammarParseError(f'Duplicate identifier name "{name}"')
63 self.__ids[len(self.right)] = name
64 self.right.append(identifier)
65
66 def addSymbol(self, identifier, name=None): # pylint: disable=invalid-name
67 warnings.warn('addSymbol is deprecated in favor of add_symbol', DeprecationWarning)
68 self.add_symbol(identifier, name=name)
69
70 def cloned(self):
71 prod = Production(self.name, self.callback, self.__priority)
72 prod.right = list(self.right)
73 prod.__ids = dict(self.__ids) # pylint: disable=protected-access,unused-private-member
74 return prod
75
76 def apply(self, args, position):
77 kwargs = {name: args[index] for index, name in self.__ids.items()}
78 if self.posarg is not None:
79 kwargs[self.posarg] = position
80 return self.callback, kwargs
81
82 def rightmost_terminal(self, grammar):
83 """
84 Returns the rightmost terminal, or None if there is none
85 """
86 for symbol in reversed(self.right):
87 if symbol in grammar.token_types():
88 return symbol
89 return None
90
91 def rightmostTerminal(self, grammar): # pylint: disable=invalid-name
92 warnings.warn('rightmostTerminal is deprecated in favor of rightmost_terminal', DeprecationWarning)
93 return self.rightmost_terminal(grammar)
94
95 def precedence(self, grammar):
96 """
97 Returns the production's priority (specified through the
98 'priority' keyword argument to the 'production' decorator), or
99 if there is none, the priority for the rightmost terminal.
100 """
101 if self.__priority is not None:
102 return grammar.terminal_precedence(self.__priority)
103 symbol = self.rightmost_terminal(grammar)
104 if symbol is not None:
105 return grammar.terminal_precedence(symbol)
106 return None
107
108 def __eq__(self, other):
109 return (self.name, self.right) == (other.name, other.right)
110
111 def __lt__(self, other):
112 return (self.name, self.right) < (other.name, other.right)
113
114 def __repr__(self): # pragma: no cover
115 return '%s -> %s' % (self.name, ' '.join([repr(p) for p in self.right]) if self.right else repr(Epsilon)) # pylint: disable=consider-using-f-string
116
117 def __hash__(self):
118 return hash((self.name, tuple(self.right)))
119
120
121 # Same remark as in lexer.py.
122 _PRODREGISTER = []
123
124
125 class _GrammarMeta(_LexerMeta):
126 def __new__(mcs, name, bases, attrs):
127 global _PRODREGISTER # pylint: disable=W0603
128 try:
129 attrs['__productions__'] = []
130 attrs['__precedence__'] = []
131 attrs['__prepared__'] = False
132 attrs['__lrstates__'] = []
133 klass = super().__new__(mcs, name, bases, attrs)
134 for func, string, priority, attributes in _PRODREGISTER:
135 parser = klass._create_production_parser(func.__name__, priority, attributes) # pylint: disable=W0212
136 parser.parse(string)
137 return klass
138 finally:
139 _PRODREGISTER = []
140
141
142 def production(prod, priority=None, **kwargs):
143 def _wrap(func):
144 if any(func.__name__ == aFunc.__name__ and func != aFunc for aFunc, _, _, _ in _PRODREGISTER):
145 raise TypeError(f'Duplicate production method name "{func.__name__}"')
146 _PRODREGISTER.append((func, prod, priority, kwargs))
147 return func
148 return _wrap
149
150
151 class Grammar(metaclass=_GrammarMeta):
152 """
153 Base class for a context-free grammar
154 """
155
156 __productions__ = [] # Make pylint happy
157 __precedence__ = []
158 __prepared__ = False
159
160 startSymbol = None
161
162 def __init__(self):
163 # pylint: disable=R0912
164 super().__init__()
165 if not self.__prepared__:
166 self.prepare()
167
168 @classmethod
169 def prepare(cls):
170 cls.startSymbol = cls._default_start_symbol() if cls.startSymbol is None else cls.startSymbol
171
172 productions = set()
173 for prod in cls.productions():
174 if prod in productions:
175 raise GrammarError(f'Duplicate production "{prod}"')
176 productions.add(prod)
177
178 cls.__all_firsts__ = cls.__compute_firsts()
179
180 logger = logging.getLogger('Grammar')
181 productions = cls.productions()
182 max_width = max(len(prod.name) for prod in productions)
183 for prod in productions:
184 logger.debug('%%- %ds -> %%s' % max_width, prod.name, ' '.join([repr(name) for name in prod.right]) if prod.right else Epsilon) # pylint: disable=consider-using-f-string,logging-not-lazy
185
186 cls.__prepared__ = True
187
188 @classmethod
189 def __compute_firsts(cls):
190 # pylint: disable=too-many-nested-blocks
191 all_firsts = {symbol: set([symbol]) for symbol in cls.token_types()|set([EOF])} # pylint: disable=no-member
192 while True:
193 prev = copy.deepcopy(all_firsts)
194 for nonterminal in cls.nonterminals():
195 for prod in cls.productions():
196 if prod.name == nonterminal:
197 if prod.right:
198 for symbol in prod.right:
199 first = all_firsts.get(symbol, set())
200 all_firsts.setdefault(nonterminal, set()).update(first)
201 if Epsilon not in first:
202 break
203 else:
204 all_firsts.setdefault(nonterminal, set()).add(Epsilon)
205 else:
206 all_firsts.setdefault(nonterminal, set()).add(Epsilon)
207 if prev == all_firsts:
208 break
209 return all_firsts
210
211 @classmethod
212 def _default_start_symbol(cls):
213 return cls.productions()[0].name
214
215 @classmethod
216 def productions(cls):
217 """
218 Returns all productions
219 """
220 productions = []
221 for base in inspect.getmro(cls):
222 if issubclass(base, Grammar):
223 productions.extend(base.__productions__)
224 return productions
225
226 @classmethod
227 def nonterminals(cls):
228 """
229 Return all non-terminal symbols
230 """
231 result = set()
232 for prod in cls.productions():
233 result.add(prod.name)
234 for symbol in prod.right:
235 if symbol not in cls.token_types(): # pylint: disable=no-member
236 result.add(symbol)
237 return result
238
239 @classmethod
240 def precedences(cls):
241 precedences = []
242 for base in inspect.getmro(cls):
243 if issubclass(base, Grammar):
244 precedences.extend(base.__precedence__)
245 return precedences
246
247 @classmethod
248 def terminal_precedence(cls, symbol):
249 for index, (associativity, terminals) in enumerate(cls.precedences()):
250 if symbol in terminals:
251 return associativity, index
252 return None
253
254 @classmethod
255 def terminalPrecedence(cls, symbol): # pylint: disable=invalid-name
256 warnings.warn('terminalPrecedence is deprecated in favor of terminal_precedence', DeprecationWarning)
257 return cls.terminal_precedence(symbol)
258
259 @classmethod
260 @functools.cache
261 def first(cls, *symbols):
262 """
263 Returns the first set for a group of symbols
264 """
265 first = set()
266 for symbol in symbols:
267 rfirst = cls.__all_firsts__[symbol]
268 first |= {a for a in rfirst if a is not Epsilon}
269 if Epsilon not in rfirst:
270 break
271 else:
272 first.add(Epsilon)
273 return first