Skip to main content

LR(1) parser generator for Python and CFSM and GLR parser drivers

Project description

The parsing module implements an LR(1) parser generator, as well as the runtime support for using a generated parser, via the Lr and Glr parser drivers. There is no special parser generator input file format, but the parser generator still needs to know what classes/methods correspond to various aspects of the parser. This information is specified via docstrings, which the parser generator introspects in order to generate a parser. Only one parser specification can be embedded in each module, but it is possible to share modules between parser specifications so that, for example, the same token definitions can be used by multiple parser specifications.

The parsing tables are LR(1), but they are generated using a fast algorithm that avoids creating duplicate states that result when using the generic LR(1) algorithm. Creation time and table size are on par with the LALR(1) algorithm. However, LALR(1) can create reduce/reduce conflicts that don’t exist in a true LR(1) parser. For more information on the algorithm, see:

A Practical General Method for Constructing LR(k) Parsers
David Pager
Acta Informatica 7, 249-268 (1977)

Parsing table generation requires non-trivial amounts of time for large grammars, however it is still quite fast. Internal pickling support makes it possible to cache the most recent version of the parsing table on disk, and use the table if the current parser specification is still compatible with the one that was used to generate the pickled parsing table. Since the compatibility checking is quite fast, even for large grammars, this removes the need to use the standard code generation method that is used by most parser generators.

Parser specifications are encapsulated by the Spec class. Parser instances use Spec instances, but are themselves based on separate classes. This allows multiple parser instances to exist simultaneously, without requiring multiple copies of the parsing tables. There are two separate parser driver classes:

Lr:

Standard Characteristic Finite State Machine (CFSM) driver, based on unambiguous LR(1) parsing tables. This driver is faster than the Glr driver, but it cannot deal with all parsing tables that the Glr driver can.

Glr:

Generalized LR driver, capable of tracking multiple parse trees simultaneously, if the %split precedence is used to mark ambiguous actions. This driver is closely based on Elkhound’s design, which is described in a technical report:

Elkhound: A Fast, Practical GLR Parser Generator
Scott McPeak
Report No. UCB/CSD-2-1214 (December 2002)
http://www.cs.berkeley.edu/~smcpeak/elkhound/

Parser generator directives are embedded in docstrings, and must begin with a ‘%’ character, followed immediately by one of several keywords:

Precedence:

%fail %nonassoc %left %right %split

Token:

%token

Non-terminal:

%start %nonterm

Production:

%reduce

All of these directives are associated with classes except for %reduce. %reduce is associated with methods within non-terminal classes. The Parsing module provides base classes from which precedences, tokens, and non-terminals must be derived. This is not as restrictive as it sounds, since there is nothing preventing, for example, a master Token class that subclasses Parsing.Token, which all of the actual token types then subclass. Also, nothing prevents using multiple inheritance.

Folowing are the base classes to be subclassed by parser specifications:

  • Precedence

  • Token

  • Nonterm

The Parsing module implements the following exception classes:

  • SpecError - when there is a problem with the grammar specification

  • ParsingException - any problem that occurs during parsing

  • UnexpectedToken - when the input sequence contains a token that is not allowed by the grammar (including end-of-input)

In order to maintain compatibility with legacy code, the Parsing module defines the following aliases. New code should use the exceptions above that do not shadow Python’s builtin exceptions.

  • Exception - superclass for all exceptions that can be raised

  • SyntaxError - alias for UnexpectedToken

Additionally, trying to set private attributes may raise:
  • AttributeError

Author: Jason Evans jasone@canonware.com

Github repo: http://github.com/MagicStack/parsing

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

parsing-2.0.4.tar.gz (36.7 kB view details)

Uploaded Source

Built Distributions

parsing-2.0.4-cp311-cp311-win_amd64.whl (219.3 kB view details)

Uploaded CPython 3.11 Windows x86-64

parsing-2.0.4-cp311-cp311-musllinux_1_1_x86_64.whl (476.2 kB view details)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

parsing-2.0.4-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (487.2 kB view details)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

parsing-2.0.4-cp311-cp311-macosx_10_9_x86_64.whl (289.6 kB view details)

Uploaded CPython 3.11 macOS 10.9+ x86-64

parsing-2.0.4-cp310-cp310-win_amd64.whl (220.0 kB view details)

Uploaded CPython 3.10 Windows x86-64

parsing-2.0.4-cp310-cp310-musllinux_1_1_x86_64.whl (476.2 kB view details)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

parsing-2.0.4-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (488.7 kB view details)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

parsing-2.0.4-cp310-cp310-macosx_10_9_x86_64.whl (292.6 kB view details)

Uploaded CPython 3.10 macOS 10.9+ x86-64

parsing-2.0.4-cp39-cp39-win_amd64.whl (219.7 kB view details)

Uploaded CPython 3.9 Windows x86-64

parsing-2.0.4-cp39-cp39-musllinux_1_1_x86_64.whl (466.5 kB view details)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

parsing-2.0.4-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (480.6 kB view details)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

parsing-2.0.4-cp39-cp39-macosx_10_9_x86_64.whl (292.5 kB view details)

Uploaded CPython 3.9 macOS 10.9+ x86-64

parsing-2.0.4-cp38-cp38-win_amd64.whl (219.4 kB view details)

Uploaded CPython 3.8 Windows x86-64

parsing-2.0.4-cp38-cp38-musllinux_1_1_x86_64.whl (462.8 kB view details)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

parsing-2.0.4-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (468.4 kB view details)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

parsing-2.0.4-cp38-cp38-macosx_10_9_x86_64.whl (287.4 kB view details)

Uploaded CPython 3.8 macOS 10.9+ x86-64

parsing-2.0.4-cp37-cp37m-win_amd64.whl (210.3 kB view details)

Uploaded CPython 3.7m Windows x86-64

parsing-2.0.4-cp37-cp37m-musllinux_1_1_x86_64.whl (364.5 kB view details)

Uploaded CPython 3.7m musllinux: musl 1.1+ x86-64

parsing-2.0.4-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (368.8 kB view details)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64

parsing-2.0.4-cp37-cp37m-macosx_10_9_x86_64.whl (280.6 kB view details)

Uploaded CPython 3.7m macOS 10.9+ x86-64

File details

Details for the file parsing-2.0.4.tar.gz.

File metadata

  • Download URL: parsing-2.0.4.tar.gz
  • Upload date:
  • Size: 36.7 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.9.18

File hashes

Hashes for parsing-2.0.4.tar.gz
Algorithm Hash digest
SHA256 08ff194215366defea26e8b2b364363cdcd0d3e464b42b1d49bb86c7642ca504
MD5 2839f2e85f5d6933f7f1bda1144ad958
BLAKE2b-256 1286bb1bc379dec16803a8cda63a1da640a8cfcc7251ff8a6247c06cff30d0f0

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp311-cp311-win_amd64.whl.

File metadata

  • Download URL: parsing-2.0.4-cp311-cp311-win_amd64.whl
  • Upload date:
  • Size: 219.3 kB
  • Tags: CPython 3.11, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.9.18

File hashes

Hashes for parsing-2.0.4-cp311-cp311-win_amd64.whl
Algorithm Hash digest
SHA256 a4e71de67adba771ca759af7238851184e90ec102c5a88c07c9ac065fd48ef8b
MD5 f6d62a31d963531428c17a4c59cdb5cf
BLAKE2b-256 7b987f4fd05db710bc5e8a792aff6add178228f5d5e1b933cc03ab9b12a6c03c

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp311-cp311-musllinux_1_1_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp311-cp311-musllinux_1_1_x86_64.whl
Algorithm Hash digest
SHA256 6a3f98f8f98cb2d3cfb278bdafea1078936e2f310a0bd6a33b1973242fc18ab8
MD5 fef0d6d37dd2c73305be8adb679d38b4
BLAKE2b-256 7ed1090fe8ef530e6442b25384a350354e1b61bd8b0b9e6044e86fb865f6de2e

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 c968acb7520518992cb43bd17f5b6b2df03fa4b28dd8feb3fd3495da7fbaa797
MD5 5108d41234981f5f8a6e7e5dd23b35da
BLAKE2b-256 d8eadea277c3124f20dc58fdde089db3f26678850e25dfff7f4f32dfa6c0bf6a

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp311-cp311-macosx_10_9_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 4d78a2618e57f5f0a93c8180240435e91176a17bc43b69ddc980c90f1f0a43c7
MD5 512c145fb6454511d8110e27b0a740cb
BLAKE2b-256 55dddafc564123d22d9eb262acaa1cd1e6ef4ba2e85ec434fb6fec13827cee70

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp310-cp310-win_amd64.whl.

File metadata

  • Download URL: parsing-2.0.4-cp310-cp310-win_amd64.whl
  • Upload date:
  • Size: 220.0 kB
  • Tags: CPython 3.10, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.9.18

File hashes

Hashes for parsing-2.0.4-cp310-cp310-win_amd64.whl
Algorithm Hash digest
SHA256 a847a9e51b3b11ea10aad723d1c534b7eb953d710b5faf3892a9c1f49d087a97
MD5 e2a41a7aef1a183d65cd0f373ae5892e
BLAKE2b-256 cbd31af18ce7309fab36a0b01544482c72cb04dfe055376779f25846bdf6a769

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp310-cp310-musllinux_1_1_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm Hash digest
SHA256 5d20562a85fc6e86ad87d71c53ad36b2af33c0e79a2055224f71a36ebcc6f307
MD5 241d5dc243e0f70a6035fe2e27fa1ea3
BLAKE2b-256 4bf5c276757a96b2e4d871e5686f957f52504f81f4d2f9bbf4c283b9ecb651d2

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 6eefc1b9007e32824ae3503947f6e252e48bb67b2eb2e6d3ffbcee07235ca4ac
MD5 fd6c7ebfb9c89f77d74fdea92ad8aaf1
BLAKE2b-256 a4eb39b4e7fbeafe02f9cfbfa1fa7710cb63ad4458167f665c36628c5266b9fa

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp310-cp310-macosx_10_9_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 ee0919535578a6177a88047d0630381b874d1c8bda96fabb734eb0c675580115
MD5 7736ce46d4a1de18c9ef5b85b838f375
BLAKE2b-256 59eadc4f4fb0147cdcee6bb1eead3c040a6f982ae724cf82debe67a7cd15ebd1

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp39-cp39-win_amd64.whl.

File metadata

  • Download URL: parsing-2.0.4-cp39-cp39-win_amd64.whl
  • Upload date:
  • Size: 219.7 kB
  • Tags: CPython 3.9, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.9.18

File hashes

Hashes for parsing-2.0.4-cp39-cp39-win_amd64.whl
Algorithm Hash digest
SHA256 b80cceb891af53be1ad9dcfb5e60e083048aa8cfa616133c46f15350a3e7e379
MD5 c1bb47b2558a96c05419d1cb833655c7
BLAKE2b-256 cc69a9f8ac112af7fc47fdfc3d1446467001a1532bc33b8b755691c83d00afaf

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp39-cp39-musllinux_1_1_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm Hash digest
SHA256 bfab47b677843287be0f0eda0a86a113058bee1ff3e20fee4f3daa6e048016df
MD5 f9a1e7bd72febc85350e3a59bc8020ab
BLAKE2b-256 00169bbc082a7042925215b9d2cd2f4282443762407474cedc180659f2b43d74

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 057549b5c6c10fc889d6f4bb7bae08f03daf14e60d2db8fb7ea67acddc2911f2
MD5 3878b13981c3be3f6a9f8ea93f7d0d8c
BLAKE2b-256 1662fffd20cc801e16268cab8d246da8f69ac409a56ca43b717387c42d1e718c

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp39-cp39-macosx_10_9_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 5a038b21552102f9dff6430f6f68bd8d581822888f0539671660d7222d4b909d
MD5 ed96f7f7ca2cb9f01acf506f129c34c8
BLAKE2b-256 ba0e2eb7af4e4a9d225178295bf8afa0875e58a8e2981895fe205b7ab9560352

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp38-cp38-win_amd64.whl.

File metadata

  • Download URL: parsing-2.0.4-cp38-cp38-win_amd64.whl
  • Upload date:
  • Size: 219.4 kB
  • Tags: CPython 3.8, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.9.18

File hashes

Hashes for parsing-2.0.4-cp38-cp38-win_amd64.whl
Algorithm Hash digest
SHA256 d3322a3d7cefb622c5770a7683ae82e50640a5730268c2d18b862acf8378c632
MD5 8f7049a6c521a557f2f40bec74577073
BLAKE2b-256 f1af69bc592c616a4b564be47f172bec6245a3ab6397b6e436d5be94f843b345

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp38-cp38-musllinux_1_1_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm Hash digest
SHA256 b8f91bd6c8dcfa3922a0ee91bba14e39e9d2f362fa0f6e377f2a8b2522132214
MD5 a058f81ded3b4bdd88f9cc0029d95a3f
BLAKE2b-256 75e7c7f5614f234e8064b53a60172e25b34e0a316bd9a6af554743ef6f2b48b0

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 a5109324c3d164ef75b7fabfa930be483374b37b8cd2d09d41430728d6c72590
MD5 7fd09f5a2c28d585d776ab1dbc93579a
BLAKE2b-256 8f2e00bfecec3bf4d182a5e243ea61b4b711781bceff0e3927763e22d8158667

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp38-cp38-macosx_10_9_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 1a00c05e502e9885b3d7763f285db2fa6d3f07a7e473bfcb91989d26116c216f
MD5 cab36af93b34aa2d1561c372c2834bf8
BLAKE2b-256 2b2cd6d40e44c663920201455fc91ea3766b86a071b95247988967fb52603534

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp37-cp37m-win_amd64.whl.

File metadata

  • Download URL: parsing-2.0.4-cp37-cp37m-win_amd64.whl
  • Upload date:
  • Size: 210.3 kB
  • Tags: CPython 3.7m, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.9.18

File hashes

Hashes for parsing-2.0.4-cp37-cp37m-win_amd64.whl
Algorithm Hash digest
SHA256 e34490bfa6106c7862650f38f314d16fbae26fbc1370dfb310caf05db776e7b4
MD5 4611573830979cd0d90da7a80b4d0884
BLAKE2b-256 9ace2e6616f0b83b7df1917c2e67ce84d826b50ea90db83bb47c9576e05d25ab

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp37-cp37m-musllinux_1_1_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm Hash digest
SHA256 0b3ca746d622b9e90da2ab4d63880d68936062dce43fa71ebd726e9c4aeb9f45
MD5 58cbe911d9c9fce08a26481b68fcc9f7
BLAKE2b-256 9ad48cc2a3c285b34b3e48c6434f87da2e5afc2a55d986a8dbebc174dec10809

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 a4bb065646c3d5dc2317aadb7d651d15acd6756977fd9e4a38da7ff3127b46da
MD5 db16c6fe95322fd5144644d065e2f805
BLAKE2b-256 3ab2674505229a1170d8eda0adf69ddce15760349f658acfbfd70eaa720b2f85

See more details on using hashes here.

Provenance

File details

Details for the file parsing-2.0.4-cp37-cp37m-macosx_10_9_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.4-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 44a9a62abb56efe6d475dfcfd5a7465fb1b7c061af3928ab30f4e6c548e033af
MD5 6da446039b0c81dbb29e83bc7c99c382
BLAKE2b-256 2256830e5771832283f5e939ec0f23bc81e9cb03664e96c8b09c5cf48a083334

See more details on using hashes here.

Provenance

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page