Overview

The LP component converts an input query into an AST.

It first tokenizes the query with LpLexer, then parses the resulting tokens with LpParser.

query
  │
  ▼
LpLexer
  │ list[LpToken]
  ▼
LpParser
  │ Ast
  ▼
AST

LpManager provides the entry point that connects these two stages.

Tokens

LpToken represents a token produced by the lexer.

Each token consists of two fields:

tag: the kind of token
value: the matched text

For example:

SELECT name FROM student;

is tokenized as:

[
    LpToken('WORD', "SELECT"),
    LpToken('WORD', "name"),
    LpToken('WORD', "FROM"),
    LpToken('WORD', "student"),
    LpToken('SC', ";"),
]

Lexer

LpLexer converts an input query into a list of LpToken objects. It combines all lexical rules into a single regular expression with named groups and scans the query from left to right.

Token Rules

Tag	Pattern	Description
`FLOAT`	`\d+\.\d+`	Float literal
`INT`	`\d+`	Integer literal
`BOOL`	`TRUE\|FALSE`	Bool literal
`STRING`	`'[^']*'`	String literal
`WORD`	`[a-zA-Z_][a-zA-Z0-9_]`	Identifier or keyword
`COMP`	`=\|<>\|<=\|>=\|<\|>`	Comparison operator
`COMMA`	`,`	Comma
`LP`	`\(`	Left parenthesis
`RP`	`\)`	Right parenthesis
`DOT`	`\.`	Dot
`SC`	`;`	Semicolon
`WS`	`[ \t\n]+`	Whitespace

Although WS is recognized by the lexer, whitespace tokens are discarded and are not passed to the parser.

Invalid Tokens

The lexer tracks the end position of each regular expression match. The start position of the next match must equal the current position. Any unrecognized part of the query therefore creates a gap between matches and causes LpInvalidTokenError to be raised. The same check is performed after the final match to ensure that the entire query has been consumed.

Parser

LpParser converts a sequence of LpToken objects into an AST. It is organized as a recursive-descent parser: parser methods correspond closely to nonterminals in the grammar and parse their subexpressions by calling other parser methods.

The parser maintains:

tokens: the input token sequence
positions: the current position in the sequence

Basic Operations

Method	Operation
`peek`	Return the current token without advancing.
`consume`	Consume the current token and advance.
`match_tag`	Match a token tag and advance only on success.
`match_keyword`	Match the value of a `WORD` token and advance only on success.
`expect_keyword`	Require and consume a specific keyword.

These operations separate token-stream handling from the implementation of individual grammar rules.

Grammar Structure

Most parse_* methods correspond directly to grammar nonterminals.

For example:

attr
    : WORD
    | WORD DOT WORD

attrs
    : attr
    | attrs COMMA attr

parse_attr parses a single attribute reference. A WORD by itself denotes an attribute without a table name, while WORD DOT WORD denotes a qualified attribute with a table name.

parse_attrs parses one or more attributes separated by COMMA tokens by repeatedly calling parse_attr.

Statements

parse examines the initial WORD token and dispatches to the corresponding statement parser.

An unsupported initial statement causes LpUnknownStatementError.

Parsing Example

Consider:

SELECT student.name FROM student WHERE student.id = 10;

The lexer produces:

[
    LpToken('WORD', "SELECT"),
    LpToken('WORD', "student"),
    LpToken('DOT', "."),
    LpToken('WORD', "name"),
    LpToken('WORD', "FROM"),
    LpToken('WORD', "student"),
    LpToken('WORD', "WHERE"),
    LpToken('WORD', "student"),
    LpToken('DOT', "."),
    LpToken('WORD', "id"),
    LpToken('COMP', "="),
    LpToken('INT', "10"),
    LpToken('SC', ";"),
]

The parser decomposes this sequence as:

select_statement
├── "SELECT"
├── attrs
│   └── attr
├── "FROM"
├── tables
│   └── table
├── where_clause
│   └── conds
│       └── cond
│           ├── attr
│           ├── COMP
│           └── hand
│               └── value
└── SC

The result is an AstSelect containing the parsed attributes, tables, and conditions.

Manager

LpManager provides the interface to the LP component. Its parse method performs the complete pipeline:

tokens = lexer.tokenize(query)
parser = LpParser(tokens)
ast = parser.parse()

Users of the LP component therefore do not need to manage the lexer and parser separately.