parsing

LR(1) parser generator for Python

These details have not been verified by PyPI

Project links

Homepage

Development Status
- 5 - Production/Stable
Intended Audience
- Developers
License
- OSI Approved :: MIT License
Operating System
- OS Independent
Programming Language
- Python :: 3
Topic
- Software Development :: Compilers
- Text Processing :: General

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

These details have not been verified by PyPI

Project links

Homepage

Development Status
- 5 - Production/Stable
Intended Audience
- Developers
License
- OSI Approved :: MIT License
Operating System
- OS Independent
Programming Language
- Python :: 3
Topic
- Software Development :: Compilers
- Text Processing :: General

Release history Release notifications | RSS feed

2.0.4

Nov 24, 2023

2.0.3

Jun 29, 2023

This version

2.0.2

Jun 29, 2023

2.0.1

Jun 21, 2023

2.0.0

Aug 31, 2021

1.6.1

Jan 9, 2019

1.6.0

Jul 24, 2017

1.5.0

Nov 17, 2015

1.4.1

Aug 14, 2015

1.4

Dec 15, 2012

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

Uploaded Jun 29, 2023 Source

Built Distributions

parsing-2.0.2-cp311-cp311-win_amd64.whl (220.5 kB view details)

Uploaded Jun 29, 2023 CPython 3.11 Windows x86-64

parsing-2.0.2-cp311-cp311-musllinux_1_1_x86_64.whl (478.9 kB view details)

Uploaded Jun 29, 2023 CPython 3.11 musllinux: musl 1.1+ x86-64

parsing-2.0.2-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (491.5 kB view details)

Uploaded Jun 29, 2023 CPython 3.11 manylinux: glibc 2.17+ x86-64

parsing-2.0.2-cp311-cp311-macosx_10_9_x86_64.whl (290.9 kB view details)

Uploaded Jun 29, 2023 CPython 3.11 macOS 10.9+ x86-64

parsing-2.0.2-cp310-cp310-win_amd64.whl (220.6 kB view details)

Uploaded Jun 29, 2023 CPython 3.10 Windows x86-64

parsing-2.0.2-cp310-cp310-musllinux_1_1_x86_64.whl (478.5 kB view details)

Uploaded Jun 29, 2023 CPython 3.10 musllinux: musl 1.1+ x86-64

parsing-2.0.2-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (493.1 kB view details)

Uploaded Jun 29, 2023 CPython 3.10 manylinux: glibc 2.17+ x86-64

parsing-2.0.2-cp310-cp310-macosx_10_9_x86_64.whl (293.8 kB view details)

Uploaded Jun 29, 2023 CPython 3.10 macOS 10.9+ x86-64

parsing-2.0.2-cp39-cp39-win_amd64.whl (220.2 kB view details)

Uploaded Jun 29, 2023 CPython 3.9 Windows x86-64

parsing-2.0.2-cp39-cp39-musllinux_1_1_x86_64.whl (470.2 kB view details)

Uploaded Jun 29, 2023 CPython 3.9 musllinux: musl 1.1+ x86-64

parsing-2.0.2-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (484.8 kB view details)

Uploaded Jun 29, 2023 CPython 3.9 manylinux: glibc 2.17+ x86-64

parsing-2.0.2-cp39-cp39-macosx_10_9_x86_64.whl (293.6 kB view details)

Uploaded Jun 29, 2023 CPython 3.9 macOS 10.9+ x86-64

parsing-2.0.2-cp38-cp38-win_amd64.whl (220.3 kB view details)

Uploaded Jun 29, 2023 CPython 3.8 Windows x86-64

parsing-2.0.2-cp38-cp38-musllinux_1_1_x86_64.whl (466.8 kB view details)

Uploaded Jun 29, 2023 CPython 3.8 musllinux: musl 1.1+ x86-64

parsing-2.0.2-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (472.6 kB view details)

Uploaded Jun 29, 2023 CPython 3.8 manylinux: glibc 2.17+ x86-64

parsing-2.0.2-cp38-cp38-macosx_10_9_x86_64.whl (288.0 kB view details)

Uploaded Jun 29, 2023 CPython 3.8 macOS 10.9+ x86-64

parsing-2.0.2-cp37-cp37m-win_amd64.whl (209.9 kB view details)

Uploaded Jun 29, 2023 CPython 3.7m Windows x86-64

parsing-2.0.2-cp37-cp37m-musllinux_1_1_x86_64.whl (365.2 kB view details)

Uploaded Jun 29, 2023 CPython 3.7m musllinux: musl 1.1+ x86-64

parsing-2.0.2-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (369.4 kB view details)

Uploaded Jun 29, 2023 CPython 3.7m manylinux: glibc 2.17+ x86-64

parsing-2.0.2-cp37-cp37m-macosx_10_9_x86_64.whl (280.8 kB view details)

Uploaded Jun 29, 2023 CPython 3.7m macOS 10.9+ x86-64

File details

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

File metadata

Download URL: parsing-2.0.2.tar.gz
Upload date: Jun 29, 2023
Size: 36.0 kB
Tags: Source
Uploaded using Trusted Publishing? No
Uploaded via: twine/4.0.2 CPython/3.9.17

File hashes

Hashes for parsing-2.0.2.tar.gz
Algorithm	Hash digest
SHA256	`1cb6768d0d7a670031dd8912c7b289fca9cfd619062efaab544d8cf41bf2009d`
MD5	`c522a5a966ed3bcdc7d459b299c68109`
BLAKE2b-256	`f8ea445dcfe1798d302cbb45710334bdf983866e07c232a9807536cf2de1f144`

Algorithm	Hash digest
SHA256	`42fb3d7a88d13012d74f0e64924ee1fba5dde677541a2288533b9e44d319659b`
MD5	`56640569d15cca77662a10fa68f96b7c`
BLAKE2b-256	`041226b8c11ca6eef1f7919b05fe013c57d0653932f11b8673bb0f05d3358ad2`

Algorithm	Hash digest
SHA256	`820c48237a8ea2d23bcaca3abaa0eb25052828736a34b69f4f1b730fc1258c93`
MD5	`66cc645c1aa678fb904f85e8546578ac`
BLAKE2b-256	`a1eba84a9af12ef63acd792a26bd0b76424c04b9ccc113c223d1eb1fab96dcd4`

Algorithm	Hash digest
SHA256	`37b75a35ca28414a9d7a6975d981977c0f4a3bb9984241dcbd67c750d11439b4`
MD5	`6176ef82f0f74645dd4ae1cf88372663`
BLAKE2b-256	`1de99e2e8b0ed47a7f3bd71da41f32d14087817d0c16a63a37d088c049225a06`

Algorithm	Hash digest
SHA256	`1a070f540728ba50a8a80847b27dcf9cd774d2c995eedfbe0a9e6b0c0965c90a`
MD5	`cff28faafaafca2aad3a0d519b5315fb`
BLAKE2b-256	`83df21360ad14150a31a56afb96b6763a64aaa51c3dbcb9808312695f3c0c65a`

Algorithm	Hash digest
SHA256	`058f0ce9bf290bde4768aea2439641a0c361f1ffee77fa1a261f4a05acfa803e`
MD5	`aecfe167f8427f1015196146dc05b050`
BLAKE2b-256	`6e16bcbf4fb7bcc6a68312a021512af3baf8a9412e6e56ffd34ed4d91bd1b35a`

Algorithm	Hash digest
SHA256	`9d16ceb20ee139ecf4b2763366fc68030ea2ae8075ba83a853babebb5073f29b`
MD5	`d649ebf0f0f6ef105d1199a2d2ccabb8`
BLAKE2b-256	`292c0be5c57082c7d43c36832813f7d2be55cfefa620b5eefa57c71704c18b65`

Algorithm	Hash digest
SHA256	`6b44cfa52fc7e5da8102002411cf182e50171fdbc866e9ef7474f1132314c287`
MD5	`d14d49b6e6f55b8529ea64f52c925404`
BLAKE2b-256	`d66d3c504c287689793b678c3575db4cd57b7ce9b3befe2835d0e79346829fd4`

Algorithm	Hash digest
SHA256	`e69bc8ad3f26c90a92f5bab6aad36744e7149c296b264aaa0954f17647e2d100`
MD5	`cadb20912f6a7c1e4fd0b946c98faa39`
BLAKE2b-256	`684e53b83b15847d8e42b8e83d6ae44429d4a6ebbb1ee5b1d7e345177fe0a442`

Algorithm	Hash digest
SHA256	`a49401c0d5e9d24b43a08d6baabbcfc4ed0732316952bd4548e997b5986f95c4`
MD5	`3522dc8eed2b221e3c3541a2ef782c5e`
BLAKE2b-256	`471d16d48346b2aecb3f66d3645b48c9f9bb24ddd6292fbbb09cd0d3d4f7120b`

Algorithm	Hash digest
SHA256	`b8de16751c8378734a9a08a4cd3eefb607b36cb3bd36abc65d8460bd06252812`
MD5	`beb92a930b0ce11e54018142392302e7`
BLAKE2b-256	`01be1ec07fe6c4c7a03ddb0083ef003fbe717b290119a7b3eddee32bab5da951`

Algorithm	Hash digest
SHA256	`8e597eb3003ed16938c29f5bb5957a216e778c42a0cd803a6ef613090d2f5a8d`
MD5	`e7720455a7b38ea68d60a9855afd2fb6`
BLAKE2b-256	`2daedffc5a4fb59f1531a16682eb8e3c09a2d21cb943ece939abc65e03a955b9`

Algorithm	Hash digest
SHA256	`346be7c07e4e3846d2302bb69c367e0db52d64822d905e2d9a6581cc535b28cb`
MD5	`ea91671a6166d533df1d9657ce7b96e8`
BLAKE2b-256	`2296cf9760279da5cdf6061f6636ee23fbacac947cf19442436703fa3d7b1836`

Algorithm	Hash digest
SHA256	`e72ab0e6705b647435997ff39f0932b960851870f7aac93699edb570339657da`
MD5	`17c35033ef528fe59a600f15a5324099`
BLAKE2b-256	`3726ca563323b9c10d945c378e3e1a30e3baf13f2e60ad54693fe8c0e6f9a692`

Algorithm	Hash digest
SHA256	`a3eb6a248cb4e191321244ebe8470d27c235b8991192df97396d26998bcfeaf6`
MD5	`3d1a91bc1358c6c38b80efe044544d40`
BLAKE2b-256	`6d2873d75260bab825b2c633f4f5a333e0286e5c816c1fe2686f6c22ff6eb85d`

Algorithm	Hash digest
SHA256	`0d30f0d57afa0158ff03949cc8dc84abd434477c655e62426af54cdb4bc205ba`
MD5	`59fc5223dd8ffb59bddabb166d1311fe`
BLAKE2b-256	`fbc0db75982e2eeee20da669e6081c58e49032ac8f6f2f68108b08e370c7b2d6`

Algorithm	Hash digest
SHA256	`2bec6baa62c5c8c3118d7f8ae7be0bd2063e2cdedff65392f553161f1ba4c72f`
MD5	`e61ce1f579d58544b7cb86887cdf9d80`
BLAKE2b-256	`e707587390d1c2be8c77bb0abeb9fdc310858400016b1880dc3b2378930d178d`

Algorithm	Hash digest
SHA256	`e5ea75a20f6f8068448723add59f214cff391d271386f43b058a3a3fe10f7f5c`
MD5	`dc5838bf2b6e8294aacc42a04acf5a8c`
BLAKE2b-256	`34564e023fde110a36f4eb55e625c446486516ead2eaed422b9b0cffb283fdb2`

Algorithm	Hash digest
SHA256	`42cd32fef9d7f8c9f480e6758f8963ecd509c777c8926f8e56008366b204b1c6`
MD5	`cb50040fcdfca72347ff1d17b6d1f0f4`
BLAKE2b-256	`4d1de353e5a4a1ac6c02f54ec91feb95fab24383ed7b5d8bb6ae3f90dd547694`

Algorithm	Hash digest
SHA256	`3b9212f5853bcaac39fda923ef8e95e2b6a497366020b96f1c14a001446ecba2`
MD5	`1c0e7c0e4aecf1b2fd75d185430083a4`
BLAKE2b-256	`3fb00bcc5d935d09a60be12eb89e60ae762d200fd89af7e3467908a01105522b`

Algorithm	Hash digest
SHA256	`d8ee4192109f5eb0d6c8c756cec4ea73dfa482cbf0fb91b291986431c970566e`
MD5	`234039a161ea3922ea5137ef809d6aba`
BLAKE2b-256	`4fab57a056683e1ca8666c5df1156edbd18633c819ab4edfd6f9c377515838f6`

parsing 2.0.2

Navigation

Verified details

Maintainers

Unverified details

Project links

Meta

Classifiers

Project description

Project details

Verified details

Maintainers

Unverified details

Project links

Meta

Classifiers

Release history Release notifications | RSS feed

Download files

Source Distribution

Built Distributions

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes

File details

File metadata

File hashes