The Abstract Syntax Tree – Using the AST

The Abstract Syntax Tree, or AST, is a subset of the concrete syntax tree. That is, a partial representation of the full syntax of the parsed input string. As such, the AST has three features of interest here.

• it only has nodes representing the rules of interest to the application
• it only has successful phrase matches to those rules
• the full matched phrase for the rule is known to the application at both the downward and upward traversal of the node

While call back functions from the rule name node operations during the actual parsing traversal of the full syntax tree can be useful and often complete, there is one serious pitfall that the application needs to be aware of and able to handle that is not present when traversing or translating from the AST. Namely, successfully matched rule nodes in branches that ultimately fail. If attempting to translate directly from the syntax tree, precautions need to be taken to recognize this situation and delete any translated information from failed branches.

Many real-life examples no doubt exist, but specifically see the "domainlabel" rule in the Session Initiation Protocol (SIP) example or the "sub-domain" rule in case 2 of the apgex example.

Here, however, only an extremely simple grammar will be used to illustrate the problem.

• application code must include header files:
  • ../../api/api.h (for parser generation, includes utlities.h)
• application compilation must include source code from the directories:
  • ../../api
  • ../../library
  • ../../utilities
• application compilation must define macros:
  • APG_AST

The compiled example will execute the following cases. Run the application with no arguments for application usage.

• case 1: Display application information. (type names, type sizes and defined macros)
• case 2: Illustrate rule call back function pitfall and solution with AST.