ยปCore Development>Code coverage>Lib/lib2to3/pgen2/pgen.py

Python code coverage for Lib/lib2to3/pgen2/pgen.py

#countcontent
1n/a# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved.
2n/a# Licensed to PSF under a Contributor Agreement.
3n/a
4n/a# Pgen imports
5n/afrom . import grammar, token, tokenize
6n/a
7n/aclass PgenGrammar(grammar.Grammar):
8n/a pass
9n/a
10n/aclass ParserGenerator(object):
11n/a
12n/a def __init__(self, filename, stream=None):
13n/a close_stream = None
14n/a if stream is None:
15n/a stream = open(filename)
16n/a close_stream = stream.close
17n/a self.filename = filename
18n/a self.stream = stream
19n/a self.generator = tokenize.generate_tokens(stream.readline)
20n/a self.gettoken() # Initialize lookahead
21n/a self.dfas, self.startsymbol = self.parse()
22n/a if close_stream is not None:
23n/a close_stream()
24n/a self.first = {} # map from symbol name to set of tokens
25n/a self.addfirstsets()
26n/a
27n/a def make_grammar(self):
28n/a c = PgenGrammar()
29n/a names = list(self.dfas.keys())
30n/a names.sort()
31n/a names.remove(self.startsymbol)
32n/a names.insert(0, self.startsymbol)
33n/a for name in names:
34n/a i = 256 + len(c.symbol2number)
35n/a c.symbol2number[name] = i
36n/a c.number2symbol[i] = name
37n/a for name in names:
38n/a dfa = self.dfas[name]
39n/a states = []
40n/a for state in dfa:
41n/a arcs = []
42n/a for label, next in sorted(state.arcs.items()):
43n/a arcs.append((self.make_label(c, label), dfa.index(next)))
44n/a if state.isfinal:
45n/a arcs.append((0, dfa.index(state)))
46n/a states.append(arcs)
47n/a c.states.append(states)
48n/a c.dfas[c.symbol2number[name]] = (states, self.make_first(c, name))
49n/a c.start = c.symbol2number[self.startsymbol]
50n/a return c
51n/a
52n/a def make_first(self, c, name):
53n/a rawfirst = self.first[name]
54n/a first = {}
55n/a for label in sorted(rawfirst):
56n/a ilabel = self.make_label(c, label)
57n/a ##assert ilabel not in first # XXX failed on <> ... !=
58n/a first[ilabel] = 1
59n/a return first
60n/a
61n/a def make_label(self, c, label):
62n/a # XXX Maybe this should be a method on a subclass of converter?
63n/a ilabel = len(c.labels)
64n/a if label[0].isalpha():
65n/a # Either a symbol name or a named token
66n/a if label in c.symbol2number:
67n/a # A symbol name (a non-terminal)
68n/a if label in c.symbol2label:
69n/a return c.symbol2label[label]
70n/a else:
71n/a c.labels.append((c.symbol2number[label], None))
72n/a c.symbol2label[label] = ilabel
73n/a return ilabel
74n/a else:
75n/a # A named token (NAME, NUMBER, STRING)
76n/a itoken = getattr(token, label, None)
77n/a assert isinstance(itoken, int), label
78n/a assert itoken in token.tok_name, label
79n/a if itoken in c.tokens:
80n/a return c.tokens[itoken]
81n/a else:
82n/a c.labels.append((itoken, None))
83n/a c.tokens[itoken] = ilabel
84n/a return ilabel
85n/a else:
86n/a # Either a keyword or an operator
87n/a assert label[0] in ('"', "'"), label
88n/a value = eval(label)
89n/a if value[0].isalpha():
90n/a # A keyword
91n/a if value in c.keywords:
92n/a return c.keywords[value]
93n/a else:
94n/a c.labels.append((token.NAME, value))
95n/a c.keywords[value] = ilabel
96n/a return ilabel
97n/a else:
98n/a # An operator (any non-numeric token)
99n/a itoken = grammar.opmap[value] # Fails if unknown token
100n/a if itoken in c.tokens:
101n/a return c.tokens[itoken]
102n/a else:
103n/a c.labels.append((itoken, None))
104n/a c.tokens[itoken] = ilabel
105n/a return ilabel
106n/a
107n/a def addfirstsets(self):
108n/a names = list(self.dfas.keys())
109n/a names.sort()
110n/a for name in names:
111n/a if name not in self.first:
112n/a self.calcfirst(name)
113n/a #print name, self.first[name].keys()
114n/a
115n/a def calcfirst(self, name):
116n/a dfa = self.dfas[name]
117n/a self.first[name] = None # dummy to detect left recursion
118n/a state = dfa[0]
119n/a totalset = {}
120n/a overlapcheck = {}
121n/a for label, next in state.arcs.items():
122n/a if label in self.dfas:
123n/a if label in self.first:
124n/a fset = self.first[label]
125n/a if fset is None:
126n/a raise ValueError("recursion for rule %r" % name)
127n/a else:
128n/a self.calcfirst(label)
129n/a fset = self.first[label]
130n/a totalset.update(fset)
131n/a overlapcheck[label] = fset
132n/a else:
133n/a totalset[label] = 1
134n/a overlapcheck[label] = {label: 1}
135n/a inverse = {}
136n/a for label, itsfirst in overlapcheck.items():
137n/a for symbol in itsfirst:
138n/a if symbol in inverse:
139n/a raise ValueError("rule %s is ambiguous; %s is in the"
140n/a " first sets of %s as well as %s" %
141n/a (name, symbol, label, inverse[symbol]))
142n/a inverse[symbol] = label
143n/a self.first[name] = totalset
144n/a
145n/a def parse(self):
146n/a dfas = {}
147n/a startsymbol = None
148n/a # MSTART: (NEWLINE | RULE)* ENDMARKER
149n/a while self.type != token.ENDMARKER:
150n/a while self.type == token.NEWLINE:
151n/a self.gettoken()
152n/a # RULE: NAME ':' RHS NEWLINE
153n/a name = self.expect(token.NAME)
154n/a self.expect(token.OP, ":")
155n/a a, z = self.parse_rhs()
156n/a self.expect(token.NEWLINE)
157n/a #self.dump_nfa(name, a, z)
158n/a dfa = self.make_dfa(a, z)
159n/a #self.dump_dfa(name, dfa)
160n/a oldlen = len(dfa)
161n/a self.simplify_dfa(dfa)
162n/a newlen = len(dfa)
163n/a dfas[name] = dfa
164n/a #print name, oldlen, newlen
165n/a if startsymbol is None:
166n/a startsymbol = name
167n/a return dfas, startsymbol
168n/a
169n/a def make_dfa(self, start, finish):
170n/a # To turn an NFA into a DFA, we define the states of the DFA
171n/a # to correspond to *sets* of states of the NFA. Then do some
172n/a # state reduction. Let's represent sets as dicts with 1 for
173n/a # values.
174n/a assert isinstance(start, NFAState)
175n/a assert isinstance(finish, NFAState)
176n/a def closure(state):
177n/a base = {}
178n/a addclosure(state, base)
179n/a return base
180n/a def addclosure(state, base):
181n/a assert isinstance(state, NFAState)
182n/a if state in base:
183n/a return
184n/a base[state] = 1
185n/a for label, next in state.arcs:
186n/a if label is None:
187n/a addclosure(next, base)
188n/a states = [DFAState(closure(start), finish)]
189n/a for state in states: # NB states grows while we're iterating
190n/a arcs = {}
191n/a for nfastate in state.nfaset:
192n/a for label, next in nfastate.arcs:
193n/a if label is not None:
194n/a addclosure(next, arcs.setdefault(label, {}))
195n/a for label, nfaset in sorted(arcs.items()):
196n/a for st in states:
197n/a if st.nfaset == nfaset:
198n/a break
199n/a else:
200n/a st = DFAState(nfaset, finish)
201n/a states.append(st)
202n/a state.addarc(st, label)
203n/a return states # List of DFAState instances; first one is start
204n/a
205n/a def dump_nfa(self, name, start, finish):
206n/a print("Dump of NFA for", name)
207n/a todo = [start]
208n/a for i, state in enumerate(todo):
209n/a print(" State", i, state is finish and "(final)" or "")
210n/a for label, next in state.arcs:
211n/a if next in todo:
212n/a j = todo.index(next)
213n/a else:
214n/a j = len(todo)
215n/a todo.append(next)
216n/a if label is None:
217n/a print(" -> %d" % j)
218n/a else:
219n/a print(" %s -> %d" % (label, j))
220n/a
221n/a def dump_dfa(self, name, dfa):
222n/a print("Dump of DFA for", name)
223n/a for i, state in enumerate(dfa):
224n/a print(" State", i, state.isfinal and "(final)" or "")
225n/a for label, next in sorted(state.arcs.items()):
226n/a print(" %s -> %d" % (label, dfa.index(next)))
227n/a
228n/a def simplify_dfa(self, dfa):
229n/a # This is not theoretically optimal, but works well enough.
230n/a # Algorithm: repeatedly look for two states that have the same
231n/a # set of arcs (same labels pointing to the same nodes) and
232n/a # unify them, until things stop changing.
233n/a
234n/a # dfa is a list of DFAState instances
235n/a changes = True
236n/a while changes:
237n/a changes = False
238n/a for i, state_i in enumerate(dfa):
239n/a for j in range(i+1, len(dfa)):
240n/a state_j = dfa[j]
241n/a if state_i == state_j:
242n/a #print " unify", i, j
243n/a del dfa[j]
244n/a for state in dfa:
245n/a state.unifystate(state_j, state_i)
246n/a changes = True
247n/a break
248n/a
249n/a def parse_rhs(self):
250n/a # RHS: ALT ('|' ALT)*
251n/a a, z = self.parse_alt()
252n/a if self.value != "|":
253n/a return a, z
254n/a else:
255n/a aa = NFAState()
256n/a zz = NFAState()
257n/a aa.addarc(a)
258n/a z.addarc(zz)
259n/a while self.value == "|":
260n/a self.gettoken()
261n/a a, z = self.parse_alt()
262n/a aa.addarc(a)
263n/a z.addarc(zz)
264n/a return aa, zz
265n/a
266n/a def parse_alt(self):
267n/a # ALT: ITEM+
268n/a a, b = self.parse_item()
269n/a while (self.value in ("(", "[") or
270n/a self.type in (token.NAME, token.STRING)):
271n/a c, d = self.parse_item()
272n/a b.addarc(c)
273n/a b = d
274n/a return a, b
275n/a
276n/a def parse_item(self):
277n/a # ITEM: '[' RHS ']' | ATOM ['+' | '*']
278n/a if self.value == "[":
279n/a self.gettoken()
280n/a a, z = self.parse_rhs()
281n/a self.expect(token.OP, "]")
282n/a a.addarc(z)
283n/a return a, z
284n/a else:
285n/a a, z = self.parse_atom()
286n/a value = self.value
287n/a if value not in ("+", "*"):
288n/a return a, z
289n/a self.gettoken()
290n/a z.addarc(a)
291n/a if value == "+":
292n/a return a, z
293n/a else:
294n/a return a, a
295n/a
296n/a def parse_atom(self):
297n/a # ATOM: '(' RHS ')' | NAME | STRING
298n/a if self.value == "(":
299n/a self.gettoken()
300n/a a, z = self.parse_rhs()
301n/a self.expect(token.OP, ")")
302n/a return a, z
303n/a elif self.type in (token.NAME, token.STRING):
304n/a a = NFAState()
305n/a z = NFAState()
306n/a a.addarc(z, self.value)
307n/a self.gettoken()
308n/a return a, z
309n/a else:
310n/a self.raise_error("expected (...) or NAME or STRING, got %s/%s",
311n/a self.type, self.value)
312n/a
313n/a def expect(self, type, value=None):
314n/a if self.type != type or (value is not None and self.value != value):
315n/a self.raise_error("expected %s/%s, got %s/%s",
316n/a type, value, self.type, self.value)
317n/a value = self.value
318n/a self.gettoken()
319n/a return value
320n/a
321n/a def gettoken(self):
322n/a tup = next(self.generator)
323n/a while tup[0] in (tokenize.COMMENT, tokenize.NL):
324n/a tup = next(self.generator)
325n/a self.type, self.value, self.begin, self.end, self.line = tup
326n/a #print token.tok_name[self.type], repr(self.value)
327n/a
328n/a def raise_error(self, msg, *args):
329n/a if args:
330n/a try:
331n/a msg = msg % args
332n/a except:
333n/a msg = " ".join([msg] + list(map(str, args)))
334n/a raise SyntaxError(msg, (self.filename, self.end[0],
335n/a self.end[1], self.line))
336n/a
337n/aclass NFAState(object):
338n/a
339n/a def __init__(self):
340n/a self.arcs = [] # list of (label, NFAState) pairs
341n/a
342n/a def addarc(self, next, label=None):
343n/a assert label is None or isinstance(label, str)
344n/a assert isinstance(next, NFAState)
345n/a self.arcs.append((label, next))
346n/a
347n/aclass DFAState(object):
348n/a
349n/a def __init__(self, nfaset, final):
350n/a assert isinstance(nfaset, dict)
351n/a assert isinstance(next(iter(nfaset)), NFAState)
352n/a assert isinstance(final, NFAState)
353n/a self.nfaset = nfaset
354n/a self.isfinal = final in nfaset
355n/a self.arcs = {} # map from label to DFAState
356n/a
357n/a def addarc(self, next, label):
358n/a assert isinstance(label, str)
359n/a assert label not in self.arcs
360n/a assert isinstance(next, DFAState)
361n/a self.arcs[label] = next
362n/a
363n/a def unifystate(self, old, new):
364n/a for label, next in self.arcs.items():
365n/a if next is old:
366n/a self.arcs[label] = new
367n/a
368n/a def __eq__(self, other):
369n/a # Equality test -- ignore the nfaset instance variable
370n/a assert isinstance(other, DFAState)
371n/a if self.isfinal != other.isfinal:
372n/a return False
373n/a # Can't just return self.arcs == other.arcs, because that
374n/a # would invoke this method recursively, with cycles...
375n/a if len(self.arcs) != len(other.arcs):
376n/a return False
377n/a for label, next in self.arcs.items():
378n/a if next is not other.arcs.get(label):
379n/a return False
380n/a return True
381n/a
382n/a __hash__ = None # For Py3 compatibility.
383n/a
384n/adef generate_grammar(filename="Grammar.txt"):
385n/a p = ParserGenerator(filename)
386n/a return p.make_grammar()