Debian Codegraph @

doc/source/parser.rst

raw
1
2 Syntactic analysis
3 ==================
4
5 .. py:decorator:: production(prod, priority=None)
6
7 Use this decorator to declare a grammar production:
8
9 .. code-block:: python
10
11 from ptk.lexer import ReLexer, token
12 from ptk.parser import LRParser, production
13
14 class MyParser(LRParser, ReLexer):
15 @production('E -> E "+" E')
16 def sum(self):
17 pass
18
19 See the :ref:`production-syntax` section.
20
21 The *priority* argument may be specified to declare that the production has the same priority as an existing token type. Typical use for unary minus:
22
23 .. code-block:: python
24
25 from ptk.lexer import ReLexer, token
26 from ptk.parser import LRParser, production
27
28 class MyParser(LRParser, ReLexer):
29 # omitting productions for binary +, -, * and /
30 @production('E -> "-" E', priority='*')
31 def minus(self):
32 pass
33
34 You can also use a token type that has not been declared to the lexer as long as you have declared an explicit priority for it, using one of the associativity decorators:
35
36 .. code-block:: python
37
38 from ptk.lexer import ReLexer, token
39 from ptk.parser import LRParser, production, left_assoc, non_assoc
40
41 @left_assoc('+', '-')
42 @left_assoc('*', '/')
43 @non_assoc('UNARYMINUS') # Non associative, higher priority than anything else
44 class MyParser(LRParser, ReLexer):
45 @production('E -> "-" E', priority='UNARYMINUS')
46 def minus(self):
47 pass
48
49 .. automodule:: ptk.parser
50 :members:
51 :member-order: bysource
52
53 .. _production-syntax:
54
55 Production syntax
56 -----------------
57
58 Basics
59 ^^^^^^
60
61 The productions specified through the :py:func:`production` decorator must be specified in a variant of BNF; for example
62
63 .. code-block:: python
64
65 from ptk.lexer import ReLexer
66 from ptk.parser import LRParser, production
67
68 class Parser(LRParser, ReLexer):
69 @production('E -> E plus E')
70 def binaryop_sum(self):
71 pass
72
73 @production('E -> E minus E')
74 def binaryop_minus(self):
75 pass
76
77 Here non terminal symbols are uppercase and terminals (token types) are lowercase, but this is only a convention.
78
79 When you don't need separate semantic actions you can group several productions by using either the '|' symbol:
80
81 .. code-block:: python
82
83 from ptk.lexer import ReLexer
84 from ptk.parser import LRParser, production
85
86 class Parser(LRParser, ReLexer):
87 @production('E -> E plus E | E minus E')
88 def binaryop(self):
89 pass
90
91 Or decorating the same method several times:
92
93 .. code-block:: python
94
95 from ptk.lexer import ReLexer
96 from ptk.parser import LRParser, production
97
98 class Parser(LRParser, ReLexer):
99 @production('E -> E plus E')
100 @production('E -> E minus E')
101 def binaryop(self):
102 pass
103
104 Semantic values
105 ^^^^^^^^^^^^^^^
106
107 The semantic value associated with a production is the return value of the decorated method. Values for items on the right side of the production are not passed to the method by default; you have to use a specific syntax to associate each item with a name, which will then be used as the name of a keyword argument passed to the method. The name must be specified between brackets after the item, for instance:
108
109 .. code-block:: python
110
111 from ptk.lexer import ReLexer
112 from ptk.parser import LRParser, production
113
114 class Parser(LRParser, ReLexer):
115 @production('E -> E<left> plus E<right>')
116 def sum(self, left, right):
117 return left + right
118
119 You can thus use alternatives and default argument values to slightly change the action's behavior depending on the actual matched production:
120
121 .. code-block:: python
122
123 from ptk.lexer import ReLexer
124 from ptk.parser import LRParser, production
125
126 class Parser(LRParser, ReLexer):
127 @production('SYMNAME -> identifier<value> | identifier<value> left_bracket identifier<name> right_bracket')
128 def symname(self, value, name=None):
129 if name is None:
130 # First form, name not specified
131 else:
132 # Second form
133
134 Position in code
135 ^^^^^^^^^^^^^^^^
136
137 You may want to store the position in the input stream at which a
138 production matched, for warning reporting for example. The same syntax
139 as for the named used in the left part of the production lets you get
140 this information as a keyword argument:
141
142 .. code-block:: python
143
144 from ptk.lexer import ReLexer
145 from ptk.parser import LRParser, production
146
147 class Parser(LRParser, ReLexer):
148 @production('SYMNAME<position> -> identifier<value> | identifier<value> left_bracket identifier<name> right_bracket')
149 def symname(self, position, value, name=None):
150 if name is None:
151 # First form, name not specified
152 else:
153 # Second form
154
155 In this case, the `position` argument will hold a named 2-tuple with
156 attributes `column` and `line`. Those start at 1.
157
158 Litteral tokens
159 ^^^^^^^^^^^^^^^
160
161 A litteral token name may appear in a production, between double quotes. This allows you to skip declaring "simple" tokens at the lexer level.
162
163 .. code-block:: python
164
165 from ptk.lexer import ReLexer
166 from ptk.parser import LRParser, production
167
168 class Parser(LRParser, ReLexer):
169 @production('E -> E "+" E')
170 def sum(self):
171 pass
172
173 .. note::
174
175 Those tokens are considered "declared" after the ones explicitely declared through the :py:func:`token` decorator. This may be important because of the disambiguation rules; see the notes for the :py:func:`token` decorator.
176
177 Litteral tokens may be named as well.
178
179 Repeat operators
180 ^^^^^^^^^^^^^^^^
181
182 A nonterminal in the right side of a production may be immediately
183 followed by a repeat operator among "*", "+" and "?", which have the
184 same meaning as in regular expressions. Note that this is only
185 syntactic sugar; under the hood additional productions are
186 generated.
187
188 .. code-block:: none
189
190 A -> B?
191
192 is equivalent to
193
194 .. code-block:: none
195
196 A ->
197 A -> B
198
199 The semantic value is None if the empty production was applied, or the
200 semantic value of B if the 'A -> B' production was applied.
201
202 .. code-block:: none
203
204 A -> B*
205
206 is equivalent to
207
208 .. code-block:: none
209
210 A ->
211 A -> L_B
212 L_B -> B
213 L_B -> L_B B
214
215 The semantic value is a list of semantic values for B. '+' works the
216 same way except for the empty production, so the list cannot be empty.
217
218 Additionally, the '*' and '+' operators may include a separator
219 specification, which is a symbol name or litteral token between parens:
220
221 .. code-block:: none
222
223 A -> B+("|")
224
225 is equivalent to
226
227 .. code-block:: none
228
229 A -> L_B
230 L_B -> B
231 L_B -> L_B "|" B
232
233 The semantic value is still a list of B values; there is no way to get
234 the values for the separators.
235
236 Wrapping it up
237 --------------
238
239 Fully functional parser for a four-operations integer calculator:
240
241 .. literalinclude:: ../../samples/calc.py
242 :language: python
243
244 Parsing lists of integers separated by commas:
245
246 .. code-block:: python
247
248 from ptk.lexer import ReLexer, token
249 from ptk.parser import LRParser, production
250
251 class Parser(LRParser, ReLexer):
252 @token('[1-9][0-9]*')
253 def number(self, tok):
254 tok.value = int(tok.value)
255 @production('LIST -> number*(",")<values>')
256 def integer_list(self, values):
257 print('Values are: %s' % values)
258
259
260 Conflict resolution rules
261 =========================
262
263 Conflict resolution rules are the same as those used by Yacc/Bison. A shift/reduce conflict is resolved by choosing to shift. A reduce/reduce conflict is resolved by choosing the reduction associated with the first declared production. :py:func:`left_assoc`, :py:func:`right_assoc`, :py:func:`non_assoc` and the *priority* argument to :py:func:`production` allows you to explicitely disambiguate.