]> git.madduck.net Git - etc/vim.git/blob - blib2to3/pgen2/conv.py

madduck's git repository

Every one of the projects in this repository is available at the canonical URL git://git.madduck.net/madduck/pub/<projectpath> — see each project's metadata for the exact URL.

All patches and comments are welcome. Please squash your changes to logical commits before using git-format-patch and git-send-email to patches@git.madduck.net. If you'd read over the Git project's submission guidelines and adhered to them, I'd be especially grateful.

SSH access, as well as push access can be individually arranged.

If you use my repositories frequently, consider adding the following snippet to ~/.gitconfig and using the third clone URL listed for each project:

[url "git://git.madduck.net/madduck/"]
  insteadOf = madduck:

add instructions to Readme for installing vim plugin using vim native package loading...
[etc/vim.git] / blib2to3 / pgen2 / conv.py
1 # Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved.
2 # Licensed to PSF under a Contributor Agreement.
3
4 """Convert graminit.[ch] spit out by pgen to Python code.
5
6 Pgen is the Python parser generator.  It is useful to quickly create a
7 parser from a grammar file in Python's grammar notation.  But I don't
8 want my parsers to be written in C (yet), so I'm translating the
9 parsing tables to Python data structures and writing a Python parse
10 engine.
11
12 Note that the token numbers are constants determined by the standard
13 Python tokenizer.  The standard token module defines these numbers and
14 their names (the names are not used much).  The token numbers are
15 hardcoded into the Python tokenizer and into pgen.  A Python
16 implementation of the Python tokenizer is also available, in the
17 standard tokenize module.
18
19 On the other hand, symbol numbers (representing the grammar's
20 non-terminals) are assigned by pgen based on the actual grammar
21 input.
22
23 Note: this module is pretty much obsolete; the pgen module generates
24 equivalent grammar tables directly from the Grammar.txt input file
25 without having to invoke the Python pgen C program.
26
27 """
28
29 # Python imports
30 import regex as re
31
32 # Local imports
33 from pgen2 import grammar, token
34
35
36 class Converter(grammar.Grammar):
37     """Grammar subclass that reads classic pgen output files.
38
39     The run() method reads the tables as produced by the pgen parser
40     generator, typically contained in two C files, graminit.h and
41     graminit.c.  The other methods are for internal use only.
42
43     See the base class for more documentation.
44
45     """
46
47     def run(self, graminit_h, graminit_c):
48         """Load the grammar tables from the text files written by pgen."""
49         self.parse_graminit_h(graminit_h)
50         self.parse_graminit_c(graminit_c)
51         self.finish_off()
52
53     def parse_graminit_h(self, filename):
54         """Parse the .h file written by pgen.  (Internal)
55
56         This file is a sequence of #define statements defining the
57         nonterminals of the grammar as numbers.  We build two tables
58         mapping the numbers to names and back.
59
60         """
61         try:
62             f = open(filename)
63         except OSError as err:
64             print("Can't open %s: %s" % (filename, err))
65             return False
66         self.symbol2number = {}
67         self.number2symbol = {}
68         lineno = 0
69         for line in f:
70             lineno += 1
71             mo = re.match(r"^#define\s+(\w+)\s+(\d+)$", line)
72             if not mo and line.strip():
73                 print("%s(%s): can't parse %s" % (filename, lineno, line.strip()))
74             else:
75                 symbol, number = mo.groups()
76                 number = int(number)
77                 assert symbol not in self.symbol2number
78                 assert number not in self.number2symbol
79                 self.symbol2number[symbol] = number
80                 self.number2symbol[number] = symbol
81         return True
82
83     def parse_graminit_c(self, filename):
84         """Parse the .c file written by pgen.  (Internal)
85
86         The file looks as follows.  The first two lines are always this:
87
88         #include "pgenheaders.h"
89         #include "grammar.h"
90
91         After that come four blocks:
92
93         1) one or more state definitions
94         2) a table defining dfas
95         3) a table defining labels
96         4) a struct defining the grammar
97
98         A state definition has the following form:
99         - one or more arc arrays, each of the form:
100           static arc arcs_<n>_<m>[<k>] = {
101                   {<i>, <j>},
102                   ...
103           };
104         - followed by a state array, of the form:
105           static state states_<s>[<t>] = {
106                   {<k>, arcs_<n>_<m>},
107                   ...
108           };
109
110         """
111         try:
112             f = open(filename)
113         except OSError as err:
114             print("Can't open %s: %s" % (filename, err))
115             return False
116         # The code below essentially uses f's iterator-ness!
117         lineno = 0
118
119         # Expect the two #include lines
120         lineno, line = lineno + 1, next(f)
121         assert line == '#include "pgenheaders.h"\n', (lineno, line)
122         lineno, line = lineno + 1, next(f)
123         assert line == '#include "grammar.h"\n', (lineno, line)
124
125         # Parse the state definitions
126         lineno, line = lineno + 1, next(f)
127         allarcs = {}
128         states = []
129         while line.startswith("static arc "):
130             while line.startswith("static arc "):
131                 mo = re.match(r"static arc arcs_(\d+)_(\d+)\[(\d+)\] = {$", line)
132                 assert mo, (lineno, line)
133                 n, m, k = list(map(int, mo.groups()))
134                 arcs = []
135                 for _ in range(k):
136                     lineno, line = lineno + 1, next(f)
137                     mo = re.match(r"\s+{(\d+), (\d+)},$", line)
138                     assert mo, (lineno, line)
139                     i, j = list(map(int, mo.groups()))
140                     arcs.append((i, j))
141                 lineno, line = lineno + 1, next(f)
142                 assert line == "};\n", (lineno, line)
143                 allarcs[(n, m)] = arcs
144                 lineno, line = lineno + 1, next(f)
145             mo = re.match(r"static state states_(\d+)\[(\d+)\] = {$", line)
146             assert mo, (lineno, line)
147             s, t = list(map(int, mo.groups()))
148             assert s == len(states), (lineno, line)
149             state = []
150             for _ in range(t):
151                 lineno, line = lineno + 1, next(f)
152                 mo = re.match(r"\s+{(\d+), arcs_(\d+)_(\d+)},$", line)
153                 assert mo, (lineno, line)
154                 k, n, m = list(map(int, mo.groups()))
155                 arcs = allarcs[n, m]
156                 assert k == len(arcs), (lineno, line)
157                 state.append(arcs)
158             states.append(state)
159             lineno, line = lineno + 1, next(f)
160             assert line == "};\n", (lineno, line)
161             lineno, line = lineno + 1, next(f)
162         self.states = states
163
164         # Parse the dfas
165         dfas = {}
166         mo = re.match(r"static dfa dfas\[(\d+)\] = {$", line)
167         assert mo, (lineno, line)
168         ndfas = int(mo.group(1))
169         for i in range(ndfas):
170             lineno, line = lineno + 1, next(f)
171             mo = re.match(r'\s+{(\d+), "(\w+)", (\d+), (\d+), states_(\d+),$', line)
172             assert mo, (lineno, line)
173             symbol = mo.group(2)
174             number, x, y, z = list(map(int, mo.group(1, 3, 4, 5)))
175             assert self.symbol2number[symbol] == number, (lineno, line)
176             assert self.number2symbol[number] == symbol, (lineno, line)
177             assert x == 0, (lineno, line)
178             state = states[z]
179             assert y == len(state), (lineno, line)
180             lineno, line = lineno + 1, next(f)
181             mo = re.match(r'\s+("(?:\\\d\d\d)*")},$', line)
182             assert mo, (lineno, line)
183             first = {}
184             rawbitset = eval(mo.group(1))
185             for i, c in enumerate(rawbitset):
186                 byte = ord(c)
187                 for j in range(8):
188                     if byte & (1 << j):
189                         first[i * 8 + j] = 1
190             dfas[number] = (state, first)
191         lineno, line = lineno + 1, next(f)
192         assert line == "};\n", (lineno, line)
193         self.dfas = dfas
194
195         # Parse the labels
196         labels = []
197         lineno, line = lineno + 1, next(f)
198         mo = re.match(r"static label labels\[(\d+)\] = {$", line)
199         assert mo, (lineno, line)
200         nlabels = int(mo.group(1))
201         for i in range(nlabels):
202             lineno, line = lineno + 1, next(f)
203             mo = re.match(r'\s+{(\d+), (0|"\w+")},$', line)
204             assert mo, (lineno, line)
205             x, y = mo.groups()
206             x = int(x)
207             if y == "0":
208                 y = None
209             else:
210                 y = eval(y)
211             labels.append((x, y))
212         lineno, line = lineno + 1, next(f)
213         assert line == "};\n", (lineno, line)
214         self.labels = labels
215
216         # Parse the grammar struct
217         lineno, line = lineno + 1, next(f)
218         assert line == "grammar _PyParser_Grammar = {\n", (lineno, line)
219         lineno, line = lineno + 1, next(f)
220         mo = re.match(r"\s+(\d+),$", line)
221         assert mo, (lineno, line)
222         ndfas = int(mo.group(1))
223         assert ndfas == len(self.dfas)
224         lineno, line = lineno + 1, next(f)
225         assert line == "\tdfas,\n", (lineno, line)
226         lineno, line = lineno + 1, next(f)
227         mo = re.match(r"\s+{(\d+), labels},$", line)
228         assert mo, (lineno, line)
229         nlabels = int(mo.group(1))
230         assert nlabels == len(self.labels), (lineno, line)
231         lineno, line = lineno + 1, next(f)
232         mo = re.match(r"\s+(\d+)$", line)
233         assert mo, (lineno, line)
234         start = int(mo.group(1))
235         assert start in self.number2symbol, (lineno, line)
236         self.start = start
237         lineno, line = lineno + 1, next(f)
238         assert line == "};\n", (lineno, line)
239         try:
240             lineno, line = lineno + 1, next(f)
241         except StopIteration:
242             pass
243         else:
244             assert 0, (lineno, line)
245
246     def finish_off(self):
247         """Create additional useful structures.  (Internal)."""
248         self.keywords = {}  # map from keyword strings to arc labels
249         self.tokens = {}  # map from numeric token values to arc labels
250         for ilabel, (type, value) in enumerate(self.labels):
251             if type == token.NAME and value is not None:
252                 self.keywords[value] = ilabel
253             elif value is None:
254                 self.tokens[type] = ilabel