Typped: Typed Pratt parsers employing dispatching

The Typped package provides a general Python framework for defining and using Pratt parsers. The parsed languages can optionally be typed, with basic types which are checked at parse-time. Overloading on types is also allowed.

Default parser methods are provided for many standard constructs such as infix operators and ordinary function calls. Users can define their own customized functions or methods in order to parse more-complicated and/or more-specific grammatical constructs. An EBNF-like Python syntax is also provided, which can be used to define and implement recursive descent parsing of a grammar within the Typped framework (integrated with Pratt parsing).

Although the framework is general, the package was originally designed to parse logic languages and mathematical languages which use syntax approximating the syntax which is used in practice. Because it is based on Pratt parsing it is especially good at parsing expression languages which have various operators at different precedence levels. Pratt parsing tends to be fairly efficient in this context, but the Typped package focuses more on ease-of-use than execution speed. The parsers and lexers are modifiable on-the-fly, allowing the parsed languages to be fully dynamic.

Note

This is alpha-level software. The basic parts work but many features are experimental and/or partially implemented. The documentation is incomplete. The user API can still change — probably in minor ways, but not necessarily.

Installation

The current way to install is to clone the GitHub repo and install with pip:

git clone https://github.com/abarker/typped
cd typped
pip install .

As usual, use a virtual environment or at least run pip with the --user option. (If you really want to modify the system Python installation the command needs to be run with administrative privileges.) Use the -e option to pip if you want to experiment with the code. See the comments in the setup.py file for how to compile with Cython.

At a more stable development point Typped will be uploaded to PyPI so users can install Typped directly:

pip install typped

Content

• 1. Basic usage
  • 1.1. Example 1: Parsing a simple expression
  • 1.2. Example 2: Parsing a simple expression without using builtins
  • 1.3. Example 3 : A simple untyped string and number language
  • 1.4. Example 4 : A simple string and number language with evaluation and dynamic typing
  • 1.5. Example 5: A simple string and number language with evaluation and static typing
    • 1.5.1. Defining a new construct for type definitions
• 2. Introduction to Pratt parsing and its terminology
  • 2.1. What is a Pratt parser?
  • 2.2. Basic assumptions
  • 2.3. Operator precedence
  • 2.4. Subexpressions
  • 2.5. Basic parsing
  • 2.6. The handler functions head and tail
    • 2.6.1. Token literals
    • 2.6.2. Non-literal syntatical constructs
  • 2.7. An example parse
  • 2.8. Summary
  • 2.9. References
• 3. Constructs and preconditioned dispatching
  • 3.1. What is preconditioned dispatching?
  • 3.2. Using dispatching
  • 3.3. Example: Defining standard functions with lookahead
  • 3.4. Modifications to recursive_parse
  • 3.5. Uniqueness of constructs
• 4. Example: Implementing a simple calculator
  • 4.1. The main procedure
  • 4.2. The read-evaluate-print loop
  • 4.3. Defining the grammar
• 5. Implementing typed languages
  • 5.1. Declaring types
  • 5.2. Type signatures
  • 5.3. Overview of type-checking
  • 5.4. Implementation details
• 6. Juxtaposition operators (jops)
  • 6.1. Assumptions for inferring jops
  • 6.2. Disambiguating jops
• 7. Recursive descent parsing in Typped
  • 7.1. Similarities and differences between the parsing methods
  • 7.2. Example
  • 7.3. Recursive descent with Typped’s EBNF-like grammar
• 8. Parsers calling other parsers
• 9. Lookbehind and other extra data
• 10. APIs and code for the modules in the Typped package
  • 10.1. typped.pratt_parser
    • 10.1.1. User-accessible parser attributes
    • 10.1.2. User-accessible token attributes
    • 10.1.3. Implementation details
    • 10.1.4. Code
  • 10.2. typped.builtin_parse_methods
  • 10.3. typped.predefined_token_sets
  • 10.4. typped.shared_settings_and_exceptions
  • 10.5. typped.pratt_constructs
  • 10.6. typped.pratt_types
  • 10.7. typped.ebnf_classes_and_operators
    • 10.7.1. Terminology and notation
    • 10.7.2. Implementation
    • 10.7.3. Wrapper functions
    • 10.7.4. Overloaded operator API
    • 10.7.5. Modifiers for items
    • 10.7.6. Operator precedences expressed in grammar
    • 10.7.7. Optimizing the grammar
    • 10.7.8. Code
  • 10.8. typped.register_grammar_with_parser
    • 10.8.1. Rules and guidelines
    • 10.8.2. Precedences
    • 10.8.3. Code
  • 10.9. typped.lexer
    • 10.9.1. Defining tokens
    • 10.9.2. Begin and end tokens
    • 10.9.3. Using the lexer
    • 10.9.4. User-accessible methods and attributes of Lexer
    • 10.9.5. User-accessible attributes of tokens
    • 10.9.6. Initialization options
    • 10.9.7. Code
  • 10.10. typped.matcher
    • 10.10.1. Using the matcher
    • 10.10.2. Using a custom matcher
    • 10.10.3. Code
• 11. Appendix A: Possible (but currently unimplemented) generalizations
  • 11.1. Modifiable token precedence values
  • 11.2. Subexpression lookahead
  • 11.3. Constructs with multiple possible trigger tokens
  • 11.4. More complex types
  • 11.5. Floating point precedence values

Indices and tables

• Index
• Module Index
• Search Page