Rewriting Module

Rewriting Module

This module is in charge of parsing the REQL query and creating the logical VA. Also, it creates a variable catalog that encapsulates the logic related to the variables in the query. It is defined in src/rematch/parsing.

Parsing

For the parsing of the REQL query, we are using ANTLR. The grammar and the files generated by ANTLR are in the grammar directory.

In the constructor of the Regex object, the parser object gets called. In its constructor, it parses the query and generates a syntax tree.

Variable Catalog

After generating the syntax tree, a visitor is used to extract the variables present in the query and store them in a catalog. The visitor is defined in variable_catalog_visitor.hpp.

The visitor is in charge of these tasks:

• Adding the variables to the catalog: When the visitor reaches an assignation node, it adds the variable in the REQL to the catalog if it is not stored already.
• Merging the variables of different catalogs: When the visitor reaches an expression node or an alternation node, it combines the variable catalogs of each subtree.

Logical VA

To create the logical VA, a second visitor is used, which is defined in char_class_visitor.hpp. The construction is based on the union of smaller logical VAs. In summary, a base logical VA is created in these functions.

• VisitEscape
• VisitSpecial
• VisitAnchor
• VisitCharacterClass
• VisitSingleSharedAtom

In the VisitEscape, the VisitSpecial and the VisitAnchor methods, the visitor creates a logical VA with a single filter transition. In the VisitCharacterClass and the VisitSingleSharedAtom, first the visitor traverses the child nodes and collects the character codes present in the character class. Then, it converts the codes into UTF-8 enconding and builds a logical VA from these codes. The VisitAssignation function adds capture transitions to the automaton.

The VisitAlternation, VisitExpr, VisitElement, VisitGroup and VisitQuantifier functions are in charge of combining the automaton of each of the subtrees.