Matching

The starting nonterminal, by design, should always be a DEF node. A DEF node is matched if one of its arguments is matched. In most cases the DEF node would have SEQ or ALT nodes in its arguments, but it could be a singular NON or TOK node. If the former, we attempt to match the SEQ or ALT node by iterating through its arguments. Recall, a SEQ node is matched if all of its arguments are matched and an ALT node is matched if one of its arguments is matched. If the latter, we try to match the nonterminal represented by the NON node or match the token represented by the TOK node. This process is repeated until the DEF node of the starting nonterminal is matched, indicating the input was accepted by the AFG.

The following diagram is a high-level illustration of the navigation of the generated AFParser data structure, when parsing, as described above.

When attempting to match a nonterminal (NON) node, the parser determines if the flow variables for the NON node differs from that of its formal definition, a DEF node. If it does, it saves the flow variables of the formal definition and changes the formal definition to have the flow variables of the nonterminal instance. We then attempt to match the nonterminal’s DEF node, if successful the formal definition’s flow variables are restored and the nonterminal is matched. Recall, a DEF node is matched if one of its arguments is matched.

When attempting to match a terminal (TOK node), we check to see if the token code of the next input token matches that of the terminal we are expecting. If the code matches, we match the TOK node.