Parsing Algorithm

This section will discuss the how [Project Name] parses input. We first introduce the concept of the Parser 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 Parser 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 Parser 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.