Transforms Function Composition into Mathematical Expression
This project is running on Golang, make sure to have installed version (~1.21). Use the command below to run this project.
make brun EXPR="add(5, mul(3, sub(10, pow(6, 4))))"The Merlin Server is running a version of Golang that supports the verification of this project.
In this section, the implementation details are covered for this project. Discussing the components of the compilers and how this program implements those components to obtain the objective.
The lexical analyzer is responsible for tokenizing the input string. The process of tokenization can be further explored in tokenize.go, where it utilizes Regular Expression to identify lexemes of the input string. The regular expressions are in const.go.
Input : "add(5, mul(10,32.3e+10))"
Output : [{FUNCTION add} {SYM_OPP (} {NUMERIC 5} {SYM_COMMA ,} {FUNCTION add} {SYM_OPP (} {NUMERIC 10} {SYM_COMMA ,} {NUMERIC 32.3e+10} {SYM_CLP )} {SYM_CLP )}]
During incorrect scanning, the program will raise a LexicalError signifying that there are unknown lexemes/character
that doesn't fit any of the regular expressions for this language.
Input : "add(5,gcd(10, 5))"
Output : "LexicalError: Unidentified token type for `gcd(10, 5))`"
The parser utilizes Top-Down Parsing of Recursive Descent. This process is tailored towards the requirements of grammatical rules and is executed if tokenization is successful. The implementation can be found in recursive.go.
Rule Explanation :
* Uppercase are Non-terminals, Lowercase are Terminals
1. ROOT -> FUNC
2. FUNC -> sym_opp EXPR comma EXPR sym_clp
3. EXPR -> FUNC
4. EXPR -> number
The recursive descent implementation also creates an Abstract Syntax Tree upon which Syntax Direct Translation with transform our expression. Here is the Tree visualized with PrintSyntaxTree function.
Input : "add(5,sub(10, 5))"
Output : add.Left -> 5
add.Right -> sub
sub.Left -> 10
sub.Right -> 5
However, if the given expression does not conform to the grammatical rules, then the program will
raise a SyntaxError as follows.
Input : "add(5, mod(10))"
Output : "SyntaxError: Expected SYM_COMMA, Got SYM_CLP"
The implementation towards generating the final output of mathematical expression involves the process of traversing the outputted Abstract Syntax Tree from the Parsing process and converting a Postfix Notation into an Infix Notation.
In translate.go, the program utilizes an auxiliary function to traverse the Syntax Tree using PostOrder Traversal and form a Postfix Notation Stack. This we then operate to generate our Infix Notation.
Input : "mul(5, pow(10, add(10, 10)))"
Postfix : 5 10 10 10 + ^ *
Infix (Target) : 5 * 10 ^ (10 + 10)
- Abhishta Gatya Adyatma (xadyata00) - 255965