A pure-Python module that implements an LR(1) parser generator, as well as CFSM and GLR parser drivers.

Navigation

Verified details

These details have been verified by PyPI
Maintainers
Avatar for edgedb-ci from gravatar.com edgedb-ci Avatar for Elvis.Pranskevichus from gravatar.com Elvis.Pranskevichus Avatar for yselivanov from gravatar.com yselivanov

Unverified details

These details have not been verified by PyPI
Project links
Meta
  • License: MIT License (MIT)
  • Author: Jason Evans
  • Requires: Python >=3.7.0
Classifiers

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

Verified details

These details have been verified by PyPI
Maintainers
Avatar for edgedb-ci from gravatar.com edgedb-ci Avatar for Elvis.Pranskevichus from gravatar.com Elvis.Pranskevichus Avatar for yselivanov from gravatar.com yselivanov

Unverified details

These details have not been verified by PyPI
Project links
Meta
  • License: MIT License (MIT)
  • Author: Jason Evans
  • Requires: Python >=3.7.0
Classifiers

Release history Release notifications | RSS feed

2.0.4

2.0.3

2.0.2

2.0.1

This version

2.0.0

1.6.1

1.6.0

1.5.0

1.4.1

1.4

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.0.tar.gz (35.8 kB view details)

Uploaded Source

Built Distributions

parsing-2.0.0-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl (997.5 kB view details)

Uploaded CPython 3.10 manylinux: glibc 2.12+ x86-64 manylinux: glibc 2.5+ x86-64

parsing-2.0.0-cp310-cp310-macosx_10_9_x86_64.whl (233.6 kB view details)

Uploaded CPython 3.10 macOS 10.9+ x86-64

parsing-2.0.0-cp39-cp39-win_amd64.whl (198.5 kB view details)

Uploaded CPython 3.9 Windows x86-64

parsing-2.0.0-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl (992.6 kB view details)

Uploaded CPython 3.9 manylinux: glibc 2.12+ x86-64 manylinux: glibc 2.5+ x86-64

parsing-2.0.0-cp39-cp39-macosx_10_9_x86_64.whl (233.4 kB view details)

Uploaded CPython 3.9 macOS 10.9+ x86-64

parsing-2.0.0-cp38-cp38-win_amd64.whl (196.3 kB view details)

Uploaded CPython 3.8 Windows x86-64

parsing-2.0.0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl (941.7 kB view details)

Uploaded CPython 3.8 manylinux: glibc 2.12+ x86-64 manylinux: glibc 2.5+ x86-64

parsing-2.0.0-cp38-cp38-macosx_10_9_x86_64.whl (230.5 kB view details)

Uploaded CPython 3.8 macOS 10.9+ x86-64

parsing-2.0.0-cp37-cp37m-win_amd64.whl (195.6 kB view details)

Uploaded CPython 3.7m Windows x86-64

parsing-2.0.0-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl (845.6 kB view details)

Uploaded CPython 3.7m manylinux: glibc 2.12+ x86-64 manylinux: glibc 2.5+ x86-64

parsing-2.0.0-cp37-cp37m-macosx_10_9_x86_64.whl (225.4 kB view details)

Uploaded CPython 3.7m macOS 10.9+ x86-64

File details

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

File metadata

  • Download URL: parsing-2.0.0.tar.gz
  • Upload date:
  • Size: 35.8 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.9.7

File hashes

Hashes for parsing-2.0.0.tar.gz
Algorithm Hash digest
SHA256 804f91faff30192ccb6798c4cc28317556cfb1a1f80f30fab8d23c8f84884987
MD5 f58644fa4a6e388ea263976856d7638f
BLAKE2b-256 4f4eed56edd1503cfd37882d67c09d00aa3c9ef7a249aabaf5840d85bda0d9ae

See more details on using hashes here.

File details

Details for the file parsing-2.0.0-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.0-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 ddd537d9c38913f309aa398b003dbb9bec31b5bfd163eab1183335f2935a7589
MD5 a0a3d08e3f139bad6a0d4d17828a9770
BLAKE2b-256 f42fd5eda1095e94f413d59ee8ea5a74ac45f0f8c9ecc868e66eaf70ad1a7eb9

See more details on using hashes here.

File details

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

File metadata

  • Download URL: parsing-2.0.0-cp310-cp310-macosx_10_9_x86_64.whl
  • Upload date:
  • Size: 233.6 kB
  • Tags: CPython 3.10, macOS 10.9+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.9.7

File hashes

Hashes for parsing-2.0.0-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 78eb082c455ece4695574c52300b81e09ddbf82473f9ecba04e7d2c292c52bbb
MD5 b99ac39e741adc70c885c081af17bde0
BLAKE2b-256 409c6f50939ba0f791937d137f0d5e310ca77d99d166a66d6c8211e704c47a62

See more details on using hashes here.

File details

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

File metadata

  • Download URL: parsing-2.0.0-cp39-cp39-win_amd64.whl
  • Upload date:
  • Size: 198.5 kB
  • Tags: CPython 3.9, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.9.7

File hashes

Hashes for parsing-2.0.0-cp39-cp39-win_amd64.whl
Algorithm Hash digest
SHA256 a89a0b1b2285173a4e35f140d672f6a6f23261550e1180389381f9b13ecc496f
MD5 8c22d042fb3975d8ebdc011d3dbf319c
BLAKE2b-256 99928b212aa4c4d14b0439cd52e7011ad4cefad328d82ed389625aabd1cf28cc

See more details on using hashes here.

File details

Details for the file parsing-2.0.0-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.0-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 dc139a7249931e3f8467f6362e9b42081b901da6d1fe7e6b5297d0f26bc5a499
MD5 dfc631374f77445b07956410efe2970a
BLAKE2b-256 45cb482931dc91e99e5d7ce287c1c7f0cba1bd196a696686fa9637110931d770

See more details on using hashes here.

File details

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

File metadata

  • Download URL: parsing-2.0.0-cp39-cp39-macosx_10_9_x86_64.whl
  • Upload date:
  • Size: 233.4 kB
  • Tags: CPython 3.9, macOS 10.9+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.9.7

File hashes

Hashes for parsing-2.0.0-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 913eceb33e755817188e53d0636d3d0193126a7110b05bd47f3c24ae923ed630
MD5 7f57074fd1c60681790a2615eb969a6e
BLAKE2b-256 04a918aadba437e660691a83ff2205779fa758a0e8b8f49511cfa92871796585

See more details on using hashes here.

File details

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

File metadata

  • Download URL: parsing-2.0.0-cp38-cp38-win_amd64.whl
  • Upload date:
  • Size: 196.3 kB
  • Tags: CPython 3.8, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.9.7

File hashes

Hashes for parsing-2.0.0-cp38-cp38-win_amd64.whl
Algorithm Hash digest
SHA256 f635f75ef71b7eccc491777d0adafd14db811e09be1ddf7b7ba24e75cf4331dc
MD5 3158c562a007f2ccc218c88580a4144a
BLAKE2b-256 dd67a0e4fd264e81ff5292f60fa7874f072560ddc797253ec41a40657bdd5895

See more details on using hashes here.

File details

Details for the file parsing-2.0.0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 94ce786961fa6d450eb3fc09b3b7875515982f7dc2653eb4f7a6ab77b02ec770
MD5 2e3f6a3130247f89f45fd3cf41d080f1
BLAKE2b-256 19e40d9661df2b3c505dbf22832b9c0e83461fa48f631bb11fbc2b84a164cc34

See more details on using hashes here.

File details

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

File metadata

  • Download URL: parsing-2.0.0-cp38-cp38-macosx_10_9_x86_64.whl
  • Upload date:
  • Size: 230.5 kB
  • Tags: CPython 3.8, macOS 10.9+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.9.7

File hashes

Hashes for parsing-2.0.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 cb43385dedfb14478aaca0f9d2f2f5cf3cff9b7a87013faa801438b3ed47c17c
MD5 7bfaaf78ebc52c604125394f85bf249d
BLAKE2b-256 c8f8cb70a56dfc757e2a516e152aae891fc6ccc5998d76840b419178bf45c644

See more details on using hashes here.

File details

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

File metadata

  • Download URL: parsing-2.0.0-cp37-cp37m-win_amd64.whl
  • Upload date:
  • Size: 195.6 kB
  • Tags: CPython 3.7m, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.9.7

File hashes

Hashes for parsing-2.0.0-cp37-cp37m-win_amd64.whl
Algorithm Hash digest
SHA256 9982faf61512d7df4881d3f705af8efd506b43d33f618a144d083b73f12ae711
MD5 204445e60ec37393ee9e43bd0d7bbe79
BLAKE2b-256 7dfa56935e625ebbe8af31bf1783092cc51efe03b09ce9b0b29c40098635c89f

See more details on using hashes here.

File details

Details for the file parsing-2.0.0-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl.

File metadata

File hashes

Hashes for parsing-2.0.0-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 25819f65bc05f38553d89d7d1ea7e0a3669d2916e367a137a0d9571d55069773
MD5 1d27733611dbdaa619e75e4ba6dfd5d6
BLAKE2b-256 cabdfb0e25bf8ff30164a15d0e3abe666122db6a00aa3e147e589ce0cf2fe9e9

See more details on using hashes here.

File details

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

File metadata

  • Download URL: parsing-2.0.0-cp37-cp37m-macosx_10_9_x86_64.whl
  • Upload date:
  • Size: 225.4 kB
  • Tags: CPython 3.7m, macOS 10.9+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.9.7

File hashes

Hashes for parsing-2.0.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 b9394d038038b11a24c0d52adf3ded5d62194e27f85596c6ee3005492a252092
MD5 69c05cd73c6f4f0c3e3755cbac4fcf23
BLAKE2b-256 bfb1d310d27a2f44ed06684a9a6362388c4b7c3b920eec5903796d4c4a6d166d

See more details on using hashes here.

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