Parsing Algorithm

This section will discuss how LL(k) AFParser objects are created with the AFP Library to parse some input. We first introduce the concept of the AFParser Data Structure, which is a representation of the AFG we want to accept the language of, and how the data structure is created. We then discuss the algorithm which navigates the data structure to determine a match. Finally, we discuss how backtracking is handled.

Background

The AFParser Data Structure consists of BaseParser objects, where each BaseParser object maintains a std::vector of BaseParser pointers pointing to other BaseParser objects in the data structure. Each BaseParser object has a tag_ member data which indicates a more specific type. The possible tag_ values and what they indicate about the BaseParser object are as follows:

• DEF – Formal definition of a nonterminal
• NON – Instance of a nonterminal; maintains information about flow variables
• TOK – Formal definition or instance of a terminal; can maintain information about flow variables
• SEQ – Sequence
• ALT – Alternation
• ACT – Semantic Action

We often refer to BaseParser objects in the AFParser Data Structure as nodes. Thus, a BaseParser object with its tag_ set to DEF is a “DEF node”, a BaseParser object with its tag_ set to NON as a “NON node”, and so on. Each of these different types of nodes play a different role when parsing input.