Parsing - Transforming SQL Text into Structure

1
2
3
4
5
6
7

SELECT customer_name, SUM(order_total)
FROM   orders o
       INNER JOIN customers c ON o.cust_id = c.id
WHERE  order_date >= '2024-01-01'
       AND status = 'completed'
GROUP BY customer_name
HAVING SUM(order_total) > 1000.00;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// Simplified SQL lexer pseudocode
 
class SQLLexer:
    input: String       // SQL text to tokenize
    position: Integer   // Current position in input
    tokens: List<Token> // Accumulated tokens
    
    function tokenize() -> List<Token>:
        while not at_end():
            skip_whitespace()
            if at_end(): break
            
            char = peek()
            
            if char is letter or underscore:
                read_identifier_or_keyword()
            else if char is digit:
                read_number()
            else if char is single_quote:
                read_string_literal()
            else if char is double_quote:
                read_quoted_identifier()
            else if char is operator_start:
                read_operator()
            else if char is delimiter:
                emit_single_char_token()
            else if char is '-' and next is '-':
                skip_line_comment()
            else if char is '/' and next is '*':
                skip_block_comment()
            else:
                raise LexicalError("Unexpected character: " + char)
        
        emit(Token(EOF, ""))
        return tokens
    
    function read_identifier_or_keyword():
        start = position
        while is_alphanumeric(peek()) or peek() == '_':
            advance()
        
        text = input[start..position]
        
        // Check if it's a reserved keyword
        if text.upper() in KEYWORDS:
            emit(Token(KEYWORD, text.upper()))
        else:
            emit(Token(IDENTIFIER, text))
    
    function read_number():
        start = position
        while is_digit(peek()):
            advance()
        
        if peek() == '.' and is_digit(peek_next()):
            advance()  // consume '.'
            while is_digit(peek()):
                advance()
            emit(Token(FLOAT_LITERAL, input[start..position]))
        else:
            emit(Token(INTEGER_LITERAL, input[start..position]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

(* Simplified SQL SELECT grammar in EBNF notation *)
 
select_statement = 
    SELECT [DISTINCT | ALL] select_list
    FROM   table_reference_list
    [WHERE  condition]
    [GROUP BY expression_list [HAVING condition]]
    [ORDER BY order_by_list]
    [LIMIT limit_specification] ;
 
select_list = 
    '*' 
    | select_item { ',' select_item } ;
 
select_item = 
    expression [AS alias] ;
 
table_reference_list = 
    table_reference { ',' table_reference } ;
 
table_reference = 
    table_name [alias]
    | table_reference join_type table_reference ON condition
    | '(' select_statement ')' [alias] ;
 
join_type = 
    [INNER] JOIN 
    | LEFT [OUTER] JOIN 
    | RIGHT [OUTER] JOIN 
    | FULL [OUTER] JOIN 
    | CROSS JOIN ;
 
condition = 
    expression comparison_op expression
    | expression IN '(' value_list ')'
    | expression BETWEEN expression AND expression
    | expression IS [NOT] NULL
    | expression LIKE pattern
    | condition AND condition
    | condition OR condition
    | NOT condition
    | '(' condition ')' ;
 
expression = 
    literal
    | column_reference
    | function_call
    | expression arith_op expression
    | '(' expression ')'
    | '(' select_statement ')' ;
 
(* ... and hundreds more rules for complete SQL support *)

SELECT name, age
FROM   users
WHERE  age > 21;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

/* PostgreSQL-style parse tree node structures */
 
/* Base node type - all nodes start with this */
typedef struct Node {
    NodeTag type;       /* Discriminator for node type */
} Node;
 
/* SELECT statement node */
typedef struct SelectStmt {
    NodeTag type;               /* T_SelectStmt */
    List *distinctClause;       /* NULL, DISTINCT, or DISTINCT ON */
    List *targetList;           /* Result columns (ResTarget nodes) */
    List *fromClause;           /* FROM clause (table refs/joins) */
    Node *whereClause;          /* WHERE qualification */
    List *groupClause;          /* GROUP BY columns */
    Node *havingClause;         /* HAVING predicate */
    List *sortClause;           /* ORDER BY columns */
    Node *limitCount;           /* LIMIT expression */
    Node *limitOffset;          /* OFFSET expression */
    /* ... additional fields ... */
} SelectStmt;
 
/* Result target (select list item) */
typedef struct ResTarget {
    NodeTag type;               /* T_ResTarget */
    char *name;                 /* Column alias (AS name) */
    List *indirection;          /* Subscripts/field selections */
    Node *val;                  /* Expression to compute value */
    int location;               /* Token position for errors */
} ResTarget;
 
/* Column reference (e.g., "table.column") */
typedef struct ColumnRef {
    NodeTag type;               /* T_ColumnRef */
    List *fields;               /* List of identifiers (schema.table.column) */
    int location;               /* Token position for errors */
} ColumnRef;
 
/* Simple expression (operator expression) */
typedef struct A_Expr {
    NodeTag type;               /* T_A_Expr */
    A_Expr_Kind kind;           /* AND, OR, NOT, OP, etc. */
    List *name;                 /* Operator name (String list) */
    Node *lexpr;                /* Left operand */
    Node *rexpr;                /* Right operand */
    int location;               /* Token position for errors */
} A_Expr;
 
/* Constant value */
typedef struct A_Const {
    NodeTag type;               /* T_A_Const */
    Value val;                  /* The value (integer, float, string) */
    int location;               /* Token position for errors */
} A_Const;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Parsing: SELECT id FROM t WHERE x = 5
 
Stack                       Input                   Action
------------------------------------------------------------------
[0]                         SELECT id FROM t...     SHIFT (push SELECT, goto 3)
[0 SELECT 3]                id FROM t WHERE...      SHIFT (push id, goto 7)
[0 SELECT 3 id 7]           FROM t WHERE x = 5      REDUCE (id -> column_ref)
[0 SELECT 3 column_ref 12]  FROM t WHERE x = 5      REDUCE (column_ref -> select_item)
[0 SELECT 3 select_item 15] FROM t WHERE x = 5      REDUCE (select_item -> select_list)
[0 SELECT 3 select_list 20] FROM t WHERE x = 5      SHIFT (push FROM, goto 25)
[... 20 FROM 25]            t WHERE x = 5 ;         SHIFT (push t, goto 30)
[... FROM 25 t 30]          WHERE x = 5 ;           REDUCE (t -> table_name)
[... FROM 25 table_name 33] WHERE x = 5 ;           REDUCE (table_name -> table_ref)
[... FROM 25 table_ref 35]  WHERE x = 5 ;           SHIFT (push WHERE, goto 40)
...
[0 select_stmt 99]          ;                       SHIFT (push ;, goto 100)
[0 select_stmt 99 ; 100]    <EOF>                   REDUCE (complete stmt)
[0 statement 1]             <EOF>                   ACCEPT
 
Parsing successful! Parse tree constructed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

-- Query with typo: FORM instead of FROM
postgres=# SELECT id FORM users;
ERROR:  syntax error at or near "users"
LINE 1: SELECT id FORM users;
                       ^
 
-- Missing closing parenthesis
postgres=# SELECT COUNT(* FROM orders;
ERROR:  syntax error at or near "FROM"
LINE 1: SELECT COUNT(* FROM orders;
                       ^
 
-- Invalid keyword order
postgres=# SELECT * WHERE id = 1 FROM users;
ERROR:  syntax error at or near "WHERE"
LINE 1: SELECT * WHERE id = 1 FROM users;
                 ^
HINT: You may need a FROM clause before the WHERE clause.
 
-- Unterminated string literal
postgres=# SELECT * FROM users WHERE name = 'John;
ERROR:  unterminated quoted string at or near "'John;"
LINE 1: SELECT * FROM users WHERE name = 'John;
                                         ^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

-- PostgreSQL folds unquoted identifiers to lowercase
 
CREATE TABLE MyTable (Id INT, Name TEXT);
-- Actually creates: mytable(id, name)
 
SELECT * FROM MyTable;  -- Works (MyTable -> mytable)
SELECT * FROM MYTABLE;  -- Works (MYTABLE -> mytable)
SELECT * FROM mytable;  -- Works (already lowercase)
 
-- To preserve case, use double quotes
CREATE TABLE "MyTable" ("Id" INT, "Name" TEXT);
-- Creates exactly: MyTable(Id, Name)
 
SELECT * FROM "MyTable";     -- Works
SELECT * FROM MyTable;       -- ERROR: relation "mytable" does not exist
SELECT * FROM "mytable";     -- ERROR: relation "mytable" does not exist
 
-- Common gotcha: mixed quoted/unquoted access
CREATE TABLE "Users" (id INT);
SELECT * FROM Users;         -- Looks for 'users', not found!
SELECT * FROM "Users";       -- Correct