LLK

TreeParser Notes

TreeParser

TreeParser is a validating tree walker that walk an AST according to the tree parser grammar rules. Each rule defines all the possible children that the node can has. Each rule method take a node as input and match its children against the rule definition. Rule definition is consist of the following elements:
  • TokenRef
  • A tokenRef() match the referenced node type. Children of the referenced node is not verified (nor visited). It can be used to bypass the transversal of children that can be ignored.
  • RuleRef
  • RuleRef() reference a rule that is not a defined input token type, the rule method is called to verify against the current input token (not its children) and its siblings. If the referenced rule declared a node type, an output node would be created just as in normal parser. On return, the next sibling of the last token matched in the referenced rule would be matched.
  • TreeRef
  • TreeRef() match a tree of nodes. The root node must match the input token (LT1), and children of the treeRef() must match the children of the input token (LT1) exactly, no more or no less. After the children are matched, the next sibling of the treeRef() would be matched.
  • Before trying to match the children of a node, LLK push the node onto a node stack. llkGetParent() return the node on top of the node stack and provide convenient access to the parent node of the node being matched. llkGetParent() can also be used for error reporting when LT1()==null (eg. when end of children list is reached unexpectedly).
There are of course other element like, lookahead(), action(), ... etc. just as for normal parser. Each rule or element can also be tagged with a node descriptor and construct an output AST just like the normal parsers.