ducklogic/pathos

A recursive decent parser for Python code

Pathos: A Python Parser [DEAD]

This was my attempt at writing a recursive-decent parser by hand, for the python source code.

It worked fairly well (for a subset of code) but it was large and clunky.

I have since decided to try and avoid hand-written parsers ;)

Parser generators

If you're into parser generators, take a look at:

1. parol - LL(k)
2. pest - PEG
3. tree-sitter - LR(1)
4. lalrpop LR(1) or LALR(1)
5. Antlr - Amazing magic but Rust bindings are experimental :(

If you're into parser combinators, take a look at:

1. combine - Looks neat
2. chumsky - Excellent error recovery and messagses
3. nom - Stable

ASTs

I did some work on ASDLR ASTs here. That has since moved to a seperate project.

pathos's Issues

Compile directly to bytecode, skipping most intermediate source generation

This is different than our old approach of AST visitors, because we will still construct an intermediate AST for certain constructs such as patterns.

The rule is no longer 'no allocations', just that we should be able to compile most expressions and statements in a single pass.

More complex source constructs like patterns, closures, generators, and collection literals may require an exception to this rule.

Error recovery

This is a nice-to-have feature, which isnt very useful in the context of an interpreter.

I think the only technique I would reasonably use is panic mode.

Recovering from mismatched tokens and lexer errors would be hard (especially with logos), but other types of unexpected tokens should be easier.

We should also consider switching entirely to aridane for errors, although that's really a separate issue.

Use zerogc for allocation

This will allow python code to access the generated AST, hopefully obseleting the CPython 'ast' module. Note that I've made a few changes from the CPython AST that would complicate this integration (we would have to add some sort of wrapper objects).

It will also allow the parser and bytecode compiler to use garbage collected collections like hashmaps, which would otherwise need to be allocated with malloc.

Hopefully this will also reduce memory usage of the parser and maybe even increase speed.