Building the parser
The parser is the module in our project that constructs the AST, which is a tree of nodes with each node representing a token (a number or an arithmetic operator). The AST is a recursive tree structure of token nodes, that is, the root node is a token, which contains child nodes that are also tokens.
Parser data structure
The parser is a higher-level entity compared to the Tokenizer. While the Tokenizer converts user input into fine-grained tokens (for example, various arithmetic operators), the parser uses the Tokenizer outputs to construct an overall AST, which is a hierarchy of nodes. The structure of the AST constructed from the parser is illustrated in the following diagram:
Figure 2.7 – Our AST
In the preceding figure, each of the following are nodes:
- Number(2.0)
- Number(3.0)
- Multiply(Number(2.0),Number(3.0))
- Number(6.0)
- Add(Multiply(Number(2.0),Number(3.0)),Number(6.0))
Each of these...