Transmuter front-end

Front-end libraries and utilities for the Transmuter language processing infrastructure.

Features

Aether -- a self-declared language declaration language
Conditional declaration of language features

Lexical Analysis

POSIX ERE-based language
NFA-based implementation
O(n) complexity
Ignorable tokens (for eg. comments, newlines and whitespaces)
On-demand and memoized tokenization
Longest match tokenization
- Ambiguous generalization as workaround
Ambiguous tokenization
- Precedence-based disambiguation

Syntactic Analysis

Generalized CFG-based language (including ambiguities and left-recursion)
Recursive Descent-based implementation (using backtracking instead of lookahead)
- Memoized parsing
O(n^3) complexity
Recursive Ascent-based left-recursion implementation
- Iteration-based alternative to (left-)recursion
SPACE(n^3) ambiguous BSR-based output
- Ordered choice and longest match-based disambiguation
Syntax sugar for optionals and expression grouping

Semantic Analysis

Dual BSR / Syntax Tree APIs
- Visitors, transformers and folds
- BSR <-> Syntax Tree converters
Symbol Table

Licensing

This codebase is licensed under the GNU GPL version 3 or any later version. Since the code generated by this codebase makes use of this codebase as a library, itself and its source Aether files must both be licensed under a compatible license.

References

THOMPSON, K. Programming Techniques: Regular expression search algorithm. Communications of the ACM, v. 11, n. 6, p. 419–422, 1968. Available at: https://doi.org/10.1145/363347.363387.
TARJAN, R. Depth-first search and linear graph algorithms. SIAM journal on computing, v. 1, n. 2, p. 146–160, 1972. Available at: https://doi.org/10.1137/0201010.
FROST, R. A.; HAFIZ, R.; CALLAGHAN, P. C. Modular and efficient top-down parsing for ambiguous left-recursive grammars. Proceedings of the 10th International Conference on Parsing Technologies - IWPT ’07. Morristown, NJ, USA: Association for Computational Linguistics, 2007. Available at: https://doi.org/10.3115/1621410.1621425.
COX, R. Regular expression matching can be simple and fast, 2007. Available at: https://swtch.com/~rsc/regexp/regexp1.html.
SCOTT, E.; JOHNSTONE, A. GLL Parsing. Electronic Notes in Theoretical Computer Science, v. 253, n. 7, p. 177–189, 2010. Available at: https://doi.org/10.1016/j.entcs.2010.08.041.
SCOTT, E.; JOHNSTONE, A.; VAN BINSBERGEN, L. T. Derivation representation using binary subtree sets. Science of Computer Programming, v. 175, p. 63–84, 2019. Available at: https://doi.org/10.1016/j.scico.2019.01.008.
THE IEEE AND THE OPEN GROUP. Regular Expressions. In: __________. The Open Group Base Specifications, Issue 8, v. 1, c. 9, 2024. Available at: https://pubs.opengroup.org/onlinepubs/9799919799/basedefs/V1_chap09.html.
WIKIPEDIA CONTRIBUTORS. Tarjan’s strongly connected components algorithm. Available at: https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm.