5.11 Semantics terms

Rarely is an application interested only in the tree. Traditionally and most often, the tree is an intermediate step in producing the “value” of the parse run. A value of a parse run is a “meaning” of the input string.

Grammars almost always have a semantics associated with them. The purpose of parsing is to use the grammar and its semantics to find the value of the input string. Finding the value of a parse tree is called evaluating a tree. More loosely, we also speak of evaluating the parse run, or evaluating the input string.

We recall that Libmarpa provides instructions for stack manipulation. See Value methods. Libmarpa does not directly do evaluation because Libmarpa is usually used together with a higher-level language, and the semantics is first known, and the evaluation is most easily performed, in the higher-level language.

In the most common method of evaluating a parse tree, every node has a value associated with it. An application might determine the value of a terminal node from

• the node’s symbol;
• a “token value”, which Libmarpa allows the user to specify for each input symbol at the time the input symbol is recognized;
• context information, including the node’s location information; or
• any combination of the above.

In determining the value of nulled nodes, the application may also consider the node’s symbol and context information. Libmarpa prunes nulled subtrees back to their root, which usually is what the application expects. The evaluation of nulled nodes is discussed in detail in the chapter on nullability. See Nullability.

To find the value of a rule node, an application may use the rule, context information, and the values of the rule node’s children. Let nd be a rule node, and let childCount be the number of children of nd. Frequently, the semantics of nd is implemented as a “semantic function”. The arguments of the semantic function are typically a scratchpad variable, call it scratch, followed by the values of the children of nd, so that the number of arguments for the function is childCount+1. The return value of the semantic function becomes the value of nd.

Semantic functions often have side effects. For example, a grammar for a language often wants its semantic functions to build and refer to a symbol table. The scratch variable allows for this.

Implementing this traditional method of tree evaluation requires a bottom-up traversal of the parse tree. In the final step of a bottom-up traversal, the start node is evaluated, and the value of the start node becomes the value of the parse run.