NAME
    Parse.pm -- query parsing and translation into query trees.

DESCRIPTION
    This module includes the implementation of a parser for the algebra
    expressions. The algebra expressions are checked for syntactical errors
    and then translated into query trees.

    Lexical analysis is implemented using very simple lexer which converts a
    query into a sequence of tokens including operation codes and constants.
    Parsing and translation are realized by a top-down examination of the
    query expressions based on methods for LL(0) grammars.

    Module is used for translating queries as well as the rules for query
    optimization which are loaded into the system at the startup time.
    Briefly, the rules are pairs of query expressions which terminate by
    using special operators called spans; see man pages of *Rule.pm* for
    more details.

Query tree
    The query expressions are represented during the query compilation and
    execution as query trees. Two types of nodes are used for the
    representation of queries: the query nodes representing set operations
    (operations *select*, *join*, etc.), and the query nodes for the
    representation of parameter expressions (eg. join parameter expression).

    The basic skeleton of the query tree is constructed during the parsing
    process. The variables and the names of the data sources and spans are
    stored in symbol table *%symtab*. The basic syntax of the rule
    terminators is checked and the rules are inserted in the pool of active
    rules. The data sources are checked and read into the object buffer.

Symbol table
    A symbol name appearing in the query expression can be either the name
    of a data source, a query variable or the name of a span. The entry of
    the symbol table *%symtab* includes the name of symbol and the reference
    to the query node representing data source, variable or span. The symbol
    table is used for handling query variables during parsing and
    type-checking, and for preparing rules for matching.

COMMENTS
    This module is part of the *qios* programming environment.