/YARDP

Yet Another Recursive Descent Parser.

Primary LanguagePythonMIT LicenseMIT

YARDP

Yet Another Recursive Descent Parser.

About

Mostly a toy project to help me understand more about how parsers and compilers work. Currently(and I don't imagine this changing) this is a REPL.

Features

  1. Generates an XML like Syntax Tree
  2. Provides an iterator based approach to loop over lexemes
  3. Understands binary operators like /, *, +, -, **.
  4. Understands + and - unary operators
  5. Support for Bitwise operators &, |, ~ and ^
  6. Can evaluate expressions
  7. Operator precedence works as expected
  8. ( and ) are allowed and so are decimals

Implementation

Here are some of the implementation details

  1. The parser supports infinite lookahead - this is a property of Recursive Descent Parsers.
  2. The grammar is LL1 - this means that the output tree is the leftmost derivation of the input string and that we need just 1 lookahead to parse the input.
  3. The parser presently emits "ghost" tokens - these tokens are tokens which don't exist in the input but should be - this helps simplify the error handling
  4. Whitespace is preserved by the lexer but the parser currently ignores it
  5. Currently, only the Concrete Syntax Tree is generated - there isn't really any reason for this other than the fact that I found this easier to implement. In theory, it shouldn't be too difficult to convert this CST to an AST.

Examples

A simple expression

image

One with operators of different precendence

image

A more complicated expression

image

One with parenthesis

image

One with nested parenthesis

image

One with the power operator

image

One with errors

image

One with no closing parenthesis

image

Run

There is one optional dependency - termcolor for generating colored outputs. If you don't want colored outputs, you need not install anything.

git clone https://github.com/TheTrio/YARDP.git
cd YARDP
python -m src.main

If you use poetry, you can do

poetry install
poetry shell
python -m src.main

By default, color support is disabled. To enable it, ensure that the termcolor package is installed and then run the program with the --color flag.

python -m src.main --color

Linting/Testing

The tests are in the /tests directory. To lint the code and run the tests, do

poetry shell
pytest
flake8