| 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. |