| Previous | Next | |
| Parsing_05_parsing_grammars_and_asts | Parsing_06_evaluation | Parsing_07_syntax_vs_semantic_errors |
Parsing: (06) Evaluation Phase
The specific phase where we apply grammar productions and construct an AST
More on Parsing:
- Parsing: (00) Some sample code to refer to—Some code you can run, compile, and consult as go through the tutorial
- Parsing: (01) Background—What is this parsing stuff all about?
- Parsing: (02) Formal Language Specifications—How do we write the rules of a language? (FSAs, CFGs, etc.)
- Parsing: (03) What is parsing?—The general and specific sense of the word, and explanation of three phases: tokenization, parsing, evaluation
- Parsing: (04) Tokenization—Context Free Grammars, EBNF, and Abstract Syntax Trees
- Parsing: (05) Parsing, Grammars and ASTs—Context Free Grammars, EBNF, and Abstract Syntax Trees
- Parsing: (06) Evaluation Phase—The specific phase where we apply grammar productions and construct an AST
- Parsing: (07) Syntax vs. Semantic Errors—The formal definition of the difference
Acknowledgments: this series or articles is joint work, a collaboration between Kyle Dewey and Phill Conrad.
Evaluation
Evaluation, also called interpretation involves taking ASTs and recursively evaluating them to values. In a language like Java, this can get fairly complex, given the complexity of the overall language. As such, we will refrain from using the running example here. Instead, we’ll use a much simpler arithmetic expression language for the purpose of an example.
Consider the AST below, corresponding to the expression 3 * 4 + 2:
Evaluation starts at the top of the AST, which corresponds to the + node in this AST.
The + node first finds the value of its left child, corresponding to the * node.
Evaluation then proceeds to the * node, which gets the value of its left child.
This leads evaluation to the 3 node.
Because the constant 3 trivially evaluates to itself, evaluation returns 3 at this point.
This is illustrated in the image below, which shows values returned from evaluation in red:
Once the 3 node is complete, evaluation goes back to the * node, which gets the value of its right child.
Evaluation then moves to the 4 node, which simply returns 4.
This is illustrated below:
Evaluation now proceeds to the * node, which finally has the values of both of its child nodes.
From here, it multiplies these values together, and returns the result.
This is illustrated below:
At this point, evaluation returns to the + node, which now has the value of its left child (*).
Evaluation then proceeds to the right child, which returns the constant 2, illustrated below:
The + node finally has the values of both of its children, and subsequently adds them together.
This result is then returned.
This is illustrated below:
Note that this entire process followed the general pattern of a recursive depth-first traversal.
More on Parsing:
- Parsing: (00) Some sample code to refer to—Some code you can run, compile, and consult as go through the tutorial
- Parsing: (01) Background—What is this parsing stuff all about?
- Parsing: (02) Formal Language Specifications—How do we write the rules of a language? (FSAs, CFGs, etc.)
- Parsing: (03) What is parsing?—The general and specific sense of the word, and explanation of three phases: tokenization, parsing, evaluation
- Parsing: (04) Tokenization—Context Free Grammars, EBNF, and Abstract Syntax Trees
- Parsing: (05) Parsing, Grammars and ASTs—Context Free Grammars, EBNF, and Abstract Syntax Trees
- Parsing: (06) Evaluation Phase—The specific phase where we apply grammar productions and construct an AST
- Parsing: (07) Syntax vs. Semantic Errors—The formal definition of the difference
| Previous | Next | |
| Parsing_05_parsing_grammars_and_asts | Parsing_06_evaluation | Parsing_07_syntax_vs_semantic_errors |