glebec / functional-math-compiler Goto Github PK

6.0 1.0 1.0 120 KB

Exercise creating a functional JavaScript math expression compiler

License: MIT License

JavaScript 100.00%

compiler mathematical-expressions parser lexer generator reverse-polish-notation evaluator ll1 grammar ebnf

functional-math-compiler's Introduction

Functional JS Arithmetic Expression Compiler

Compiler exercise for education. Parsing infix arithmetic expressions via LL(1) recursive descent, adhering to functional approaches.

Features

Pure functions only: no side effects (apart from STDOUT), no mutations, all const etc.
Uses daggy for tagged unions (aka sum types)
- Enables type checking e.g. Token.Number.is(x) and Token.is(x)
- Enables simple pattern matching / catamorphisms e.g. someToken.cata({ Mul: () => true, Div: () => false }) with automatic errors in case of match failure
Uses Immutable.js List for functional collections
- Enables efficient unshift, push, and slice
- Immutability provides strong reasoning benefits

Use

yarn # installs
yarn test # passes
yarn start '-9 * 2 / -(3 + 7) + ((-4 * 1/2) - -21)' # outputs RPN string
yarn start '-9 * 2 / -(3 + 7) + ((-4 * 1/2) - -21)' --eval # outputs num

Supports

Integers
Negation
Addition
Subtraction
Multiplication
Division
Grouping (parens)

Lexer

Converts raw input string to an Immutable.js List of Daggy types (tokens):

Number (string of digits)
Lparen
Rparen
Mul
Div
Add
Sub

Parser

Converts list of tokens to a parse tree, aka concrete syntax tree:

Epsilon
Factor (sign, child)
F2 (op, factor, childF2)
T2 (op, term, childT2)
Term (factor, childF2)
Expression (term, childT2)

Note that a CST / PT preserves all or almost all of the syntax as represented by the language's grammar, whereas an Abstract Syntax Tree (AST) reduces the information to the bare minimum necessary for a given use case. Currently our CST simplifies parenthetical expressions, though we could make it preserve parens.

Generator

Dispatches based on node type to recursively process the parse tree. Two generators included:

an infix -> RPN compiler
a numerical evaluator

The latter generator can be chosen from the command line by appending the --eval flag.

Grammar

A grammar is the set of production rules for a language; that is, substitutions which eventually generate any valid string in the language. A simple grammar for expressions (starting from E) is:

E -> (E)
E -> E + E
E -> E * E
E -> number

Unfortunately, while the above grammar is valid (producing sentences in the language), it is also ambiguous (could be represented by different parse trees, affecting the semantic meaning of the expression). The following is an unambiguous grammar:

E -> E + T
E -> T
T -> T ∗ F
T -> F
F -> (E)
F -> number

Unfortunately, this grammar is left-recursive, which makes it impossible to parse via LL recursive descent (one of the easiest parsers to implement). The following refactors the grammar to be parsed via an LL(1) algorithm:

E  ->   T T2
T2 -> + T T2
T2 -> ε
T  ->   F F2
F2 -> * F F2
F2 -> ε
F  -> (E)
F  -> number

A formal EBNF notation of a similar grammar is included in the docs folder, with the augmentation that we allow for multiplication, subtraction, and negative factors.

Resources

Stanford CS143 Notes on Parsing (PDF)
Online RPN <-> Infix Compiler / Evaluator (useful for double-checking)

functional-math-compiler's People

Contributors

Stargazers

Watchers

Forkers

baltazarv

functional-math-compiler's Issues

Action required: Greenkeeper could not be activated 🚨

🚨 You need to enable Continuous Integration on all branches of this repository. 🚨

To enable Greenkeeper, you need to make sure that a commit status is reported on all branches. This is required by Greenkeeper because it uses your CI build statuses to figure out when to notify you about breaking changes.

Since we didn’t receive a CI status on the greenkeeper/initial branch, it’s possible that you don’t have CI set up yet. We recommend using Travis CI, but Greenkeeper will work with every other CI service as well.

If you have already set up a CI for this repository, you might need to check how it’s configured. Make sure it is set to run on all new branches. If you don’t want it to run on absolutely every branch, you can whitelist branches starting with greenkeeper/.

Once you have installed and configured CI on this repository correctly, you’ll need to re-trigger Greenkeeper’s initial pull request. To do this, please delete the greenkeeper/initial branch in this repository, and then remove and re-add this repository to the Greenkeeper App’s white list on Github. You'll find this list on your repo or organization’s settings page, under Installed GitHub Apps.

Complete CST to include parens

Losing the parens makes the parse tree lose information that could be used e.g. to rebuild the original expression. In other words, we technically have an AST, not a CST. Refactoring to be a CST could work if the Factor tree nodes have lhs, child, and rhs fields as follows:

Production Rule	`lhs`	`child`	`rhs`
F -> (E)	Lparen	E	Rparen
F -> -F	Sub	F	EpsilonF
F -> num	EpsilonF	num	EpsilonF

That way the catamorphism for the recursive generators could look like:

{
  Factor: (lhs, child, rhs) => generate(lhs) * generate(child) * generate(rhs),
  LParen: () => 1, // identity: '' for RPN, '(' for rebuilding original, etc.
  Rparen: () => 1,
}

This is an artifact of the way tree nodes can have varying shape, making it difficult to apply identical logic to every node. An alternative is to simply embrace different node shapes and embed explicit conditional logic in the generator, instead of relying entirely on daggy's cata function for branching.