(KO) PostgreSQL 파서 — 렉싱, LALR(1) 문법, 의미 분석

이론적 배경
DBMS 공통 설계
PostgreSQL의 접근법
소스 탐방
소스 검증 (2026-06-05 기준)
PostgreSQL 너머 — 비교 설계와 연구 프런티어
출처

이론적 배경

모든 쿼리 처리기는 동일한 파이프라인에서 시작한다. 문자들의 연속이 토큰 스트림이 되고, 토큰 스트림이 문법에 맞는지 검증되어 구조화된 트리로 변환되며, 마지막으로 그 트리가 시스템 카탈로그의 메타데이터로 보강되어 나머지 엔진이 타입 부여·범위 지정·플래닝 가능한 객체로 다룰 수 있게 된다. 세 단계 — 어휘 분석, 구문 분석, 의미 분석 — 는 고전 컴파일러 이론에 그대로 대응한다(Compilers: Principles, Techniques, and Tools, Aho 외, 2006, §§2–5; Engineering a Compiler, Cooper & Torczon, 2012, ch. 2–4 참고).

어휘 분석 (렉싱)은 입력 문자 스트림을 토큰 — 키워드, 식별자, 리터럴, 연산자, 구두점 — 으로 분할한다. 스캐너는 보통 Flex 같은 도구가 정규 표현식 집합으로부터 자동 생성한다. 고성능 스캐너에 필요한 핵심 성질은 백트랙 없음이다. 입력의 어떤 접두사에 대해서도 어느 한 규칙이 매칭될 수 있어야 하므로, 스캐너는 문자를 다시 읽을 필요가 없다. 백트랙 없는 스캔은 규칙 순서를 신중히 잡고 모호한 겹침 패턴을 피함으로써 달성한다.

구문 분석 (파싱)은 토큰 시퀀스가 언어 문법에 부합하는지 검증하고 파스 트리 또는 추상 구문 트리(AST)를 만든다. SQL과 대부분의 프로그래밍 언어에 지배적으로 쓰이는 기법은 LALR(1) 상향식 파싱이다(Aho 외, §4.7). 파서는 문법 상태들의 스택을 유지하며 토큰을 쌓은 뒤, 스택 꼬리가 완전한 오른쪽 항과 일치할 때마다 비단말 기호로 reduce(접기)한다. LALR(1)이란 파서가 shift·reduce 여부를 결정할 때 정확히 한 토큰만 앞서 본다는 뜻이다. 이는 모호하지 않은 대부분의 문법에 충분하지만, 문법 자체를 충돌 없이 설계해야 한다.

LALR(1) 제약으로부터 두 가지 설계 선택이 파생되며, 이것이 모든 SQL 파서의 형태를 결정한다.

키워드와 식별자의 긴장. SQL에는 수백 개의 예약 키워드가 있다. 테이블이나 컬럼 이름으로 select나 from을 쓰면 shift/reduce 충돌이 생긴다. 해결책은 키워드를 등급별로 분류하는 것이다 — 완전 예약, 비예약, 타입·함수 전용 — 와, 비예약 단어를 특정 위치에서 맨 식별자로 허용하는 문법 규칙 몇 가지다.
다단어 토큰. SQL에는 NOT BETWEEN, NULLS FIRST, WITH ORDINALITY 같이 다음 토큰에 따라 의미가 달라지는 다단어 구성이 있다. 순수 LALR(1) 문법은 특별한 장치 없이 이를 처리할 수 없다. 표준 해결책은 특정 단일 토큰을 복합 토큰(NOT_LA, NULLS_LA, WITH_LA)으로 교체하는 선독 필터를 렉서와 파서 사이에 두는 것이다. 이렇게 하면 문법 자체는 LALR(1)을 유지할 수 있다.

의미 분석 (파스 분석, 변환)은 카탈로그 정보가 없는 원시 트리를 받아, 완전히 타입 부여·범위 지정·주석 처리된 쿼리 트리로 변환한다. 이 단계에서 비로소 카탈로그를 연다. 테이블 이름을 relcache로 OID에 해석하고, 컬럼 이름을 속성 번호로 해석하고, 함수 이름을 pg_proc 항목으로 해석하며, 인수 타입을 강제 변환하고, 와일드카드를 확장한다. 출력이 리라이터와 플래너가 동작하는 Query 노드다.

두 단계 분리 — 원시 파싱 후 의미 분석 — 는 gram.y 파일 헤더에 명시된 PostgreSQL의 의도적인 설계 선택이다. “이 파일 안에서는 데이터베이스 접근이나 변경 가능한 상태에 대한 의존이 있어서는 안 된다.” 이 덕분에 원시 파싱은 카탈로그 접근이 금지된 중단된 트랜잭션 안에서도 진행할 수 있다. 또한 다중 구문 문자열 전체가 첫 번째 구문이 실행되기 전에 완전히 파싱된다.

DBMS 공통 설계

세 단계 파이프라인(렉스 → 파스 → 분석)은 보편적이지만, 실제 SQL 파서들은 교과서가 명시적으로 설명하지 않는 공학적 관례를 공유한다.

상태 변수를 갖춘 백트랙 없는 Flex 스캐너

모든 상용 SQL 스캐너는 Flex가 .l 파일로부터 생성한다. 핵심 품질 기준은 백트랙 없음 성질이다. Flex는 백킹업이 필요한 상태를 나열하는 lex.backup 보고서를 생성할 수 있으며, 깨끗한 스캐너는 이 보고서에 항목이 없다. 백트랙 없음은 모든 입력 접두사에서 적어도 한 규칙이 매칭되도록 보장함으로써, 보통 부분 매칭 접두사에 명시적 규칙을 추가하거나 Flex의 “후행 컨텍스트” 기법을 신중하게 쓰는 방식으로 달성한다. 이점은 원시 파싱 처리량의 수 퍼센트다.

스캐너는 렉서 상태 변수 — 보통 소수의 플래그와 리터럴 누적 버퍼 — 도 갖는다. 여러 규칙에 걸쳐 처리되는 구성(달러-인용 문자열, 이스케이프 유니코드 시퀀스, 주석)을 다루기 위해서다.

이진 탐색 정렬 배열로서의 키워드 테이블

SQL에는 수백 개의 키워드가 있다. 이것들을 Flex 규칙으로 인코딩하면 DFA 테이블이 폭발하므로, 주요 SQL 파서들은 키워드를 정렬된 배열에 보관하고 각 IDENT 토큰마다 이진 탐색을 수행한다. 배열 항목에는 키워드의 Bison 토큰 값과 분류(예약, 비예약, 타입·함수명 전용, 컬럼명 전용)가 들어 있으며, 분류는 어떤 문법 위치에서 그 키워드를 맨 식별자로 쓸 수 있는지를 결정한다.

스캐너와 파서 사이의 한 토큰 선독 필터

LALR(1) 파서는 정확히 한 토큰만 선독하지만, SQL에는 두 토큰을 봐야 분명히 구분되는 구성(NOT BETWEEN, NULLS FIRST/LAST, WITH ORDINALITY/TIME)이 있다. 해결책은 Flex 스캐너와 Bison 파서 사이에 얇은 필터 함수를 두는 것이다. 현재 토큰이 문제가 되는 소수의 집합 중 하나일 때 다음 토큰을 들여다보고, 필요하면 현재 토큰을 선독 주석이 달린 변형으로 교체한다. 이렇게 하면 스캐너에 파서 수준 지식을 부담시키지 않고 문법은 LALR(1)을 유지한다.

원시 파스 트리: 카탈로그 없는 노드 그래프

문법 액션 코드는 NodeTag로 타입이 표시된 구조체를 할당하고 트리로 연결한다. 중요한 점은 모든 리프가 구문적 내용만 담는다는 것이다. 이름은 OID가 아닌 평문 char * 문자열이고, 표현식은 타입 부여 없는 미평가 트리이며, 컬럼 참조는 정수 (relid, attnum)가 아닌 (relname, attname) 쌍이다. 이 카탈로그 없는 성질 덕분에 원시 파싱은 중단된 트랜잭션 안에서도 진행할 수 있다.

ParseState: 의미 분석 중의 네임스페이스 누산기

의미 분석은 모든 재귀 변환 호출에 꿰어진 ParseState 구조체가 구동한다. 주요 필드에는 현재까지 구성된 range-table 항목(p_rtable), 컬럼 조회에 가시적인 네임스페이스 항목(p_namespace), CTE 네임스페이스, 잠금 절, 감지 플래그(집계 있음, 윈도우 함수 있음, 서브링크 있음)가 누적된다. 서브쿼리는 parentParseState로 부모에 연결된 자체 자식 ParseState를 갖는다.

명령 유형 분배: 최적화 가능 vs. 유틸리티

의미 분석기는 구문 유형을 두 그룹으로 나눈다. 최적화 가능 구문(SELECT, INSERT, UPDATE, DELETE, MERGE, VALUES)은 완전한 변환을 받는다. range table 구성, 표현식 트리 재작성, 타입 강제 변환, 집계·윈도우 감지가 모두 이루어진다. 결과는 commandType이 CMD_SELECT, CMD_INSERT 등인 Query다. 유틸리티 구문(DDL, GRANT, EXPLAIN, COPY …)은 commandType = CMD_UTILITY인 Query로 감싸진 채 대부분 변환 없이 통과한다. 깊은 분석은 실행 시점으로 미뤄진다. EXPLAIN / DECLARE CURSOR / CREATE TABLE AS는 예외로, 내포된 최적화 가능 쿼리를 지금 분석하되 바깥 쉘은 유틸리티로 유지한다.

이론 ↔ PostgreSQL 대응표

이론 / 관례	PostgreSQL 이름
어휘 분석기	`scan.l` → 생성된 `scan.c` (Flex)
백트랙 없음 보장	`lex.backup` 빈 파일 (Makefile에서 검증)
키워드 정렬 테이블	`kwlist.h` (521줄), `ScanKeywords[]` / `ScanKeywordTokens[]`
한 토큰 선독 필터	`parser.c`의 `base_yylex`
LALR(1) 문법	`gram.y` (~19,700줄, Bison)
원시 AST 루트	`raw_parser`가 반환하는 `List ` of `RawStmt `
원시 구문 노드	`RawStmt` — `Node *stmt` 하나 + 위치 정보 래퍼
의미 분석 진입점	`parse_analyze_fixedparams` / `parse_analyze_varparams` / `parse_analyze_withcb`
변환 디스패처	`transformStmt` (`NodeTag`로 라우팅)
네임스페이스 누산기	`ParseState` (서브쿼리용 스택 연결)
Range table 항목	`ParseState.p_rtable` 안의 `RangeTblEntry`
최적화 가능 결과	`commandType ∈ {CMD_SELECT, CMD_INSERT, CMD_UPDATE, CMD_DELETE, CMD_MERGE}`인 `Query`
유틸리티 결과	`commandType = CMD_UTILITY`인 `Query`
분석 후 훅	`post_parse_analyze_hook`

PostgreSQL의 접근법

PostgreSQL 파서는 두 단계 파이프라인이다. 1단계(raw_parser → scan.l + gram.y)는 카탈로그 없는 원시 파스 트리를 만든다. 2단계(parse_analyze_* → analyze.c + parse_*.c)는 그것을 타입 부여·범위 지정된 Query 트리로 변환한다. 두 단계는 엄격히 분리된다. 1단계에는 카탈로그 접근이 전혀 없다.

1단계 — 렉싱과 원시 파싱

진입점은 parser.c의 raw_parser(str, mode)다. 이 함수는 Flex 스캐너를 초기화하고, 한 토큰 선독 필터를 연결하며, Bison 파서를 호출한 뒤 yyextra.parsetree — RawStmt 노드의 List — 를 반환한다.

// raw_parser — src/backend/parser/parser.c
List *
raw_parser(const char *str, RawParseMode mode)
{
    core_yyscan_t yyscanner;
    base_yy_extra_type yyextra;

    /* 키워드 테이블과 함께 Flex 스캐너 초기화 */
    yyscanner = scanner_init(str, &yyextra.core_yy_extra,
                             &ScanKeywords, ScanKeywordTokens);

    /* PL/pgSQL 서브 파서를 위한 모드별 선독 토큰 주입 */
    if (mode == RAW_PARSE_DEFAULT)
        yyextra.have_lookahead = false;
    else {
        static const int mode_token[] = {
            [RAW_PARSE_DEFAULT]         = 0,
            [RAW_PARSE_TYPE_NAME]       = MODE_TYPE_NAME,
            [RAW_PARSE_PLPGSQL_EXPR]    = MODE_PLPGSQL_EXPR,
            [RAW_PARSE_PLPGSQL_ASSIGN1] = MODE_PLPGSQL_ASSIGN1,
            /* ... */
        };
        yyextra.have_lookahead    = true;
        yyextra.lookahead_token   = mode_token[mode];
    }

    parser_init(&yyextra);           /* Bison 글루 구조체 설정 */
    yyresult = base_yyparse(yyscanner);
    scanner_finish(yyscanner);

    return yyresult ? NIL : yyextra.parsetree;
}

그림 1 — 1단계 데이터 흐름.

flowchart LR
    S["SQL 문자열\n(const char *)"]
    SI["scanner_init\n(scan.l / Flex)"]
    BL["base_yylex 필터\n(parser.c)"]
    BY["base_yyparse\n(gram.y / Bison)"]
    RT["List of RawStmt\n(원시 파스 트리)"]

    S --> SI
    SI -->|"토큰 스트림\ncore_yylex"| BL
    BL -->|"필터링된 토큰\nNOT_LA / NULLS_LA / …"| BY
    BY --> RT

그림 1 — raw_parser는 scan.l을 base_yylex 선독 필터를 거쳐 gram.y로 공급한다. 결과는 RawStmt 노드의 List이며 카탈로그 접근은 없다.

Flex 렉서 (scan.l)

scan.l은 약 1,300줄의 Flex 명세다. 설계 주석에 *“규칙들은 스캐너가 절대 백트랙하지 않도록 설계되었다”*고 명시돼 있다. Makefile이 flex -b를 실행해 lex.backup이 비어 있는지 검증한다.

키워드는 Flex DFA 밖에서 처리한다. 스캐너는 [A-Za-z_][A-Za-z0-9_$]* 패턴을 후보 식별자로 매칭한 뒤 ScanKeywordLookup — src/common/keywords.c의 정렬된 ScanKeywords 배열에 대한 이진 탐색 — 을 호출한다. 탐색에 성공하면 kwlist.h의 PG_KEYWORD 매크로 확장으로 만들어진 ScanKeywordTokens[]에서 토큰 값을 가져온다. 탐색에 실패하면 토큰은 IDENT다. REL_18 기준 키워드 테이블에는 521개 항목이 네 가지 분류에 걸쳐 있다.

분류	예시	맨 식별자로 사용 가능 여부
`RESERVED_KEYWORD`	`SELECT`, `FROM`, `WHERE`	불가
`UNRESERVED_KEYWORD`	`ABORT`, `ACCESS`, `ACTION`	항상 가능
`TYPE_FUNC_NAME_KEYWORD`	`BETWEEN`, `BIGINT`, `BIT`	타입·함수 위치에서만 가능
`COL_NAME_KEYWORD`	`BETWEEN`, `OUTER`	컬럼명 위치에서만 가능

scan.l은 런타임에 달라지는 세 가지 동작을 위해 GUC 결합 상태 변수를 갖는다. backslash_quote, escape_string_warning, standard_conforming_strings다. 파일 헤더는 이것을 스캐너가 변경 가능한 상태에 의존해서는 안 된다는 규칙에 대한 *“직접적인 위반”*이라고 명시하며, 제거할 수 있을 때까지 유지한다고 설명한다.

선독 필터 (base_yylex)

Bison은 토큰을 scan.l의 core_yylex에서 직접 받지 않는다. parser.c의 base_yylex로만 받는다. 이 필터는 한 토큰 버퍼(yyextra->have_lookahead)를 유지한다. 현재 토큰이 FORMAT, NOT, NULLS_P, WITH, WITHOUT, UIDENT, USCONST 중 하나이면, 필터는 다음 토큰을 들여다보고 현재 토큰을 선독 주석이 달린 변형으로 교체할 수 있다.

// base_yylex — src/backend/parser/parser.c (condensed)
switch (cur_token)
{
    case NOT:
        /* BETWEEN, IN, LIKE, ILIKE, SIMILAR이 뒤따르면 NOT_LA로 교체 */
        switch (next_token) {
            case BETWEEN: case IN_P: case LIKE: case ILIKE: case SIMILAR:
                cur_token = NOT_LA;  break;
        }
        break;
    case NULLS_P:
        /* FIRST 또는 LAST가 뒤따르면 NULLS_LA로 교체 */
        switch (next_token) {
            case FIRST_P: case LAST_P:
                cur_token = NULLS_LA;  break;
        }
        break;
    case WITH:
        /* TIME 또는 ORDINALITY가 뒤따르면 WITH_LA로 교체 */
        switch (next_token) {
            case TIME: case ORDINALITY:
                cur_token = WITH_LA;  break;
        }
        break;
    case UIDENT: case USCONST:
        /* UESCAPE를 찾아 유니코드 디이스케이핑 적용 */
        /* ... condensed ... */
        cur_token = (cur_token == UIDENT) ? IDENT : SCONST;
        break;
}
return cur_token;

유니코드 식별자·문자열 디이스케이핑(UIDENT/USCONST + 선택적 UESCAPE)도 여기서 처리한다. 필터는 두세 토큰으로 이루어진 시퀀스를 Bison이 보기 전에 단일 IDENT 또는 SCONST로 축약한다.

Bison 문법 (gram.y)

gram.y는 약 19,700줄로, PostgreSQL 백엔드 소스에서 가장 큰 단일 파일이다. 최상위 생성 규칙은 stmtmulti(961행)이며, 세미콜론으로 구분된 toplevel_stmt → stmt 노드들의 리스트다. 각 stmt 생성 규칙은 하나의 SQL 구문 유형과 매칭되어 makeNode(T_XxxStmt)와 필드 할당으로 Node *를 만든다. 문법은 #define YYMALLOC palloc으로 현재 메모리 컨텍스트에서 할당하므로, 오류 발생 시 자동으로 해제된다.

파일 헤더의 규칙은 명확하다. “이 파일 안에서는 데이터베이스 접근이나 변경 가능한 상태에 대한 의존이 있어서는 안 된다.” 액션은 makeNode, palloc, 리스트 함수, 소수의 헬퍼(SystemFuncName, SystemTypeName, makeStringConst …)를 호출할 수 있지만, heap_open, SearchSysCache, 또는 릴레이션을 건드리는 어떤 함수도 호출해서는 안 된다.

2단계 — 의미 분석 (파스 분석)

analyze.c의 진입점은 세 가지다.

// parse_analyze_fixedparams — src/backend/parser/analyze.c
Query *
parse_analyze_fixedparams(RawStmt *parseTree, const char *sourceText,
                          const Oid *paramTypes, int numParams,
                          QueryEnvironment *queryEnv)
{
    ParseState *pstate = make_parsestate(NULL);
    Query      *query;
    JumbleState *jstate = NULL;

    pstate->p_sourcetext = sourceText;
    if (numParams > 0)
        setup_parse_fixed_parameters(pstate, paramTypes, numParams);
    pstate->p_queryEnv = queryEnv;

    query = transformTopLevelStmt(pstate, parseTree);

    if (IsQueryIdEnabled())
        jstate = JumbleQuery(query);
    if (post_parse_analyze_hook)
        (*post_parse_analyze_hook)(pstate, query, jstate);

    free_parsestate(pstate);
    pgstat_report_query_id(query->queryId, false);
    return query;
}

세 변형이 있다. parse_analyze_fixedparams는 알려진 $n 타입을 쓰며 단순 쿼리에 사용된다. parse_analyze_varparams는 컨텍스트로부터 타입을 추론하며 확장 쿼리 프로토콜에 사용된다. parse_analyze_withcb는 콜백 기반 파라미터 해석을 쓰며 플래너의 SPI 계열 호출자에 사용된다. 셋 모두 transformTopLevelStmt → transformStmt로 위임한다.

ParseState

ParseState(parse_node.h 정의)는 모든 변환 호출에 스레드처럼 꿰어진 변경 가능한 컨텍스트다. 주요 필드들이 변환 함수에 필요한 모든 정보를 누적한다.

// ParseState — src/include/parser/parse_node.h (condensed)
struct ParseState
{
    ParseState *parentParseState;   /* 서브쿼리용 스택 연결 */
    const char *p_sourcetext;       /* 오류 커서 위치용 */
    List       *p_rtable;           /* 구성 중인 range table */
    List       *p_rteperminfos;     /* 권한 검사 항목 */
    List       *p_joinlist;         /* FROM 절 항목 → FromExpr.fromlist */
    List       *p_namespace;        /* 이름 조회에 가시적인 현재 RTE */
    List       *p_ctenamespace;     /* 범위 내 WITH 절 CTE */
    Relation    p_target_relation;  /* INSERT/UPDATE/DELETE/MERGE 대상 */
    ParseExprKind p_expr_kind;      /* 표현식 변환 컨텍스트 */
    int         p_next_resno;       /* 다음 TargetEntry resno */
    bool        p_hasAggs;
    bool        p_hasWindowFuncs;
    bool        p_hasSubLinks;
    /* ... PL/pgSQL과 SPI 호출자용 훅 함수 포인터 ... */
};

make_parsestate(parentParseState)는 새 ParseState를 할당하고 0으로 초기화하며, 부모가 있으면 훅 함수 포인터를 복사한다. free_parsestate는 열려 있으면 p_target_relation을 닫고 구조체를 해제한다.

transformStmt 디스패치

transformStmt는 NodeTag로 라우팅한다.

// transformStmt — src/backend/parser/analyze.c (condensed)
Query *
transformStmt(ParseState *pstate, Node *parseTree)
{
    Query *result;
    switch (nodeTag(parseTree))
    {
        case T_InsertStmt:
            result = transformInsertStmt(pstate, (InsertStmt *) parseTree);
            break;
        case T_DeleteStmt:
            result = transformDeleteStmt(pstate, (DeleteStmt *) parseTree);
            break;
        case T_UpdateStmt:
            result = transformUpdateStmt(pstate, (UpdateStmt *) parseTree);
            break;
        case T_MergeStmt:
            result = transformMergeStmt(pstate, (MergeStmt *) parseTree);
            break;
        case T_SelectStmt:
            result = transformSelectStmt(pstate, (SelectStmt *) parseTree);
            /* 또는 transformValuesClause / transformSetOperationStmt */
            break;
        /* ... 다른 최적화 가능 구문 유형 ... */
        default:
            /* 유틸리티 구문 */
            result = makeNode(Query);
            result->commandType = CMD_UTILITY;
            result->utilityStmt = parseTree;
            break;
    }
    return result;
}

유틸리티 구문은 477행에서 얇은 Query(CMD_UTILITY) 쉘로 감싼다. EXPLAIN, DECLARE CURSOR, CREATE TABLE AS는 예외다. 이 세 가지는 내포된 최적화 가능 쿼리를 transformStmt가 재귀적으로 분석한다.

transformSelectStmt — 절 단위 오케스트레이터

transformSelectStmt는 Query가 조립되는 방식의 전형적인 예다. 이 함수는 Query를 할당하고 commandType = CMD_SELECT를 설정한 뒤, SQL 절마다 전문 변환 함수를 하나씩 데이터 의존성을 존중하는 고정 순서로 호출한다. FROM 절을 가장 먼저 처리해야 그 네임스페이스가 이후 모든 절에서 가시적이 된다. ORDER BY는 GROUP BY와 DISTINCT보다 먼저 처리하는데, 후자 둘이 정렬 결과를 재활용하기 때문이다. 마지막에 ParseState 누산기(p_rtable, p_joinlist, p_hasAggs …)에서 최종 Query 필드를 수확한다.

// transformSelectStmt — src/backend/parser/analyze.c (condensed)
qry->commandType = CMD_SELECT;
if (stmt->withClause)                       /* WITH first, independent of all else */
    qry->cteList = transformWithClause(pstate, stmt->withClause);

pstate->p_locking_clause = stmt->lockingClause;   /* visible to addRangeTableEntry */
pstate->p_windowdefs    = stmt->windowClause;

transformFromClause(pstate, stmt->fromClause);    /* builds RTEs + namespace */

qry->targetList = transformTargetList(pstate, stmt->targetList,
                                      EXPR_KIND_SELECT_TARGET);
markTargetListOrigins(pstate, qry->targetList);

qual          = transformWhereClause(pstate, stmt->whereClause,
                                     EXPR_KIND_WHERE, "WHERE");
qry->havingQual = transformWhereClause(pstate, stmt->havingClause,
                                       EXPR_KIND_HAVING, "HAVING");
qry->sortClause  = transformSortClause(pstate, stmt->sortClause, &qry->targetList, ...);
qry->groupClause = transformGroupClause(pstate, stmt->groupClause, ..., qry->sortClause, ...);
/* ... DISTINCT, LIMIT/OFFSET, window clauses ... */

qry->rtable      = pstate->p_rtable;        /* harvest accumulators into Query */
qry->rteperminfos = pstate->p_rteperminfos;
qry->jointree    = makeFromExpr(pstate->p_joinlist, qual);
qry->hasSubLinks = pstate->p_hasSubLinks;
qry->hasAggs     = pstate->p_hasAggs;

assign_query_collations(pstate, qry);       /* collation walk, after all exprs built */
if (pstate->p_hasAggs || qry->groupClause || qry->groupingSets || qry->havingQual)
    parseCheckAggregates(pstate, qry);      /* validate aggregate semantics last */
return qry;

소스 주석에 명시된 순서 불변량에 주목할 필요가 있다. ORDER BY는 GROUP BY/DISTINCT보다 먼저 실행되고(후자가 정렬 리스트를 재사용한다), parseCheckAggregates는 assign_query_collations 이후에 실행된다. 집계 검증 중 표현식 비교가 완전히 콜레이션이 부여된 트리를 보게 하기 위해서다.

FROM 절 처리 — range table과 네임스페이스 구성

transformFromClause는 문법의 RangeVar / RangeSubselect / RangeFunction / JoinExpr 항목 리스트를 왼쪽에서 오른쪽으로 순회한다. 왼쪽-오른쪽 순서는 LATERAL 참조 가시성에서 의미가 있다. 각 항목은 join-tree 노드 하나와 ParseNamespaceItem 하나가 된다. refname 충돌 검사를 거친 뒤 p_joinlist와 p_namespace 양쪽에 추가된다.

// transformFromClause — src/backend/parser/parse_clause.c (condensed)
foreach(fl, frmList)
{
    Node               *n = lfirst(fl);
    ParseNamespaceItem *nsitem;
    List               *namespace;

    n = transformFromClauseItem(pstate, n, &nsitem, &namespace);
    checkNameSpaceConflicts(pstate, pstate->p_namespace, namespace);
    setNamespaceLateralState(namespace, true, true);   /* visible only to LATERAL for now */

    pstate->p_joinlist  = lappend(pstate->p_joinlist, n);
    pstate->p_namespace = list_concat(pstate->p_namespace, namespace);
}
/* once the whole FROM list is parsed, make every item unconditionally visible */
setNamespaceLateralState(pstate->p_namespace, false, true);

일반 테이블의 경우 range-table 항목을 실제로 만드는 리프 함수는 addRangeTableEntryForRelation이다. 카탈로그 상태가 처음 개입하는 지점이기도 하다. 릴레이션은 이미 상위에서 열리고 잠겨 있으므로 이 함수는 락이 잡혀 있음을 단언한다. RTE에는 릴레이션 OID, relkind, 락 모드가 기록된다. 컬럼 별칭은 tuple descriptor에서 구체화되고, ACL_SELECT가 포함된 RTEPermissionInfo가 등록된다. RTE는 p_rtable에 추가되며, 그 1-기반 위치가 플래너가 나중에 사용하는 varno가 된다.

// addRangeTableEntryForRelation — src/backend/parser/parse_relation.c (condensed)
RangeTblEntry *rte = makeNode(RangeTblEntry);
Assert(CheckRelationLockedByMe(rel, lockmode, true));   /* lock already taken upstream */

rte->rtekind     = RTE_RELATION;
rte->relid       = RelationGetRelid(rel);
rte->relkind     = rel->rd_rel->relkind;
rte->rellockmode = lockmode;
rte->eref        = makeAlias(refname, NIL);
buildRelationAliases(rel->rd_att, alias, rte->eref);    /* effective column names */

perminfo = addRTEPermissionInfo(&pstate->p_rteperminfos, rte);
perminfo->requiredPerms = ACL_SELECT;

pstate->p_rtable = lappend(pstate->p_rtable, rte);      /* index = its varno */
return buildNSItemFromTupleDesc(rte, list_length(pstate->p_rtable), perminfo, rel->rd_att);

대상 리스트 구성과 별표 확장

transformTargetList는 문법의 ResTarget 하나하나를 하나 이상의 TargetEntry 노드로 변환한다. 표현식 변환 외에 구조적으로 처리하는 핵심 작업은 별표 확장이다. something.* 참조(문법이 A_Star로 끝나는 ColumnRef 또는 A_Star로 끝나는 A_Indirection으로 남겨둔 것)는 현재 네임스페이스를 기준으로 컬럼마다 하나의 대상으로 펼쳐진다. 나머지는 모두 단일 transformTargetEntry 호출이다.

// transformTargetList — src/backend/parser/parse_target.c (condensed)
expand_star = (exprKind != EXPR_KIND_UPDATE_SOURCE);    /* no '*' on UPDATE source */
foreach(o_target, targetlist)
{
    ResTarget *res = (ResTarget *) lfirst(o_target);

    if (expand_star && IsA(res->val, ColumnRef) &&
        IsA(llast(((ColumnRef *) res->val)->fields), A_Star))
    {
        p_target = list_concat(p_target,
                               ExpandColumnRefStar(pstate,
                                                   (ColumnRef *) res->val, true));
        continue;                                       /* one '*' → many targets */
    }
    /* ... A_Indirection '*' handled symmetrically via ExpandIndirectionStar ... */

    p_target = lappend(p_target,
                       transformTargetEntry(pstate, res->val, NULL,
                                            exprKind, res->name, false));
}

표현식 변환 — 재귀 노드 디스패치

표현식을 담는 모든 절은 최종적으로 transformExpr를 호출한다. 그 내부 워커 transformExprRecurse는 nodeTag에 대한 switch로 각 원시 문법 노드를 분석된 대응물로 재작성한다. A_Const는 타입이 부여된 Const(via make_const)가 되고, ColumnRef는 네임스페이스에서 Var(via transformColumnRef)로 해석되며, FuncCall은 함수 또는 집계 OID로 해석된다. 첫 줄은 깊이 중첩된 표현식으로 인한 스택 오버플로우를 방지한다.

// transformExprRecurse — src/backend/parser/parse_expr.c (condensed)
check_stack_depth();                        /* deeply nested exprs are user-supplied */
switch (nodeTag(expr))
{
    case T_ColumnRef:
        result = transformColumnRef(pstate, (ColumnRef *) expr);    /* → Var / field */
        break;
    case T_ParamRef:
        result = transformParamRef(pstate, (ParamRef *) expr);      /* $n → Param */
        break;
    case T_A_Const:
        result = (Node *) make_const(pstate, (A_Const *) expr);     /* literal → Const */
        break;
    case T_A_Expr:
        switch (((A_Expr *) expr)->kind) {
            case AEXPR_OP:      result = transformAExprOp(pstate, a);      break;  /* a + b */
            case AEXPR_IN:      result = transformAExprIn(pstate, a);      break;  /* IN (...) */
            case AEXPR_BETWEEN: result = transformAExprBetween(pstate, a); break;
            /* ... AEXPR_OP_ANY/ALL, DISTINCT, NULLIF, LIKE/ILIKE/SIMILAR ... */
        }
        break;
    case T_FuncCall:
        result = transformFuncCall(pstate, (FuncCall *) expr);      /* name → pg_proc OID */
        break;
    case T_SubLink:
        result = transformSubLink(pstate, (SubLink *) expr);        /* child ParseState */
        break;
    /* ... BoolExpr, TypeCast, CaseExpr, CoalesceExpr, etc. ... */
}

transformColumnRef는 p_expr_kind(ParseExprKind, 호출자가 설정한 값 — 예: EXPR_KIND_WHERE 대 EXPR_KIND_GROUP_BY)를 기준으로 분배한다. 컬럼 참조가 허용되지 않는 위치(기본값 표현식, 파티션 경계)에서는 네임스페이스 조회를 시도하기 전에 거부한다. 이 ParseExprKind는 위의 transformSelectStmt가 각 절 변환에 실어 보내는 것과 같은 값이다.

parse_*.c 전문 파일들

parser/ 디렉터리의 각 전문 파일은 의미 분석의 한 관심사를 담당한다.

파일	역할
`parse_relation.c`	RTE를 range table에 추가; 이름·컬럼 조회; `addRangeTableEntry`, `checkNameSpaceConflicts`
`parse_expr.c`	재귀 표현식 변환; `transformExpr`, `ParseExprKind` 디스패치
`parse_func.c`	함수 이름 해석; 집계 감지; `ParseFuncOrColumn`
`parse_coerce.c`	타입 강제 변환; `coerce_to_target_type`, 묵시적 캐스트 삽입
`parse_clause.c`	WHERE, ORDER BY, GROUP BY, HAVING, LIMIT/OFFSET; `transformWhereClause`, `transformSortClause`
`parse_agg.c`	집계·윈도우 함수 검사; `transformAggregateCall`, `parseCheckAggregates`
`parse_cte.c`	WITH 절 CTE; 재귀 CTE 타입 해석
`parse_target.c`	대상 리스트 구성; `transformTargetList`, 별표 확장
`parse_collate.c`	표현식 변환 완료 후 콜레이션 할당 워크
`parse_merge.c`	MERGE 구문 변환; `transformMergeStmt`

SELECT에 대한 전반적인 의미 분석 흐름은 다음과 같다.

flowchart TD
    TS["transformSelectStmt\n(analyze.c:1389)"]
    FR["transformFromClause\n릴레이션·서브쿼리별 addRangeTableEntry\n(parse_relation.c)"]
    WH["transformWhereClause\n술어에 transformExpr 적용\n(parse_clause.c)"]
    TL["transformTargetList\n별표 확장, 별칭 해석\n(parse_target.c)"]
    GB["transformGroupClause\nGROUP BY / HAVING\n(parse_clause.c)"]
    OB["transformSortClause\nORDER BY\n(parse_clause.c)"]
    AG["parseCheckAggregates\n집계·윈도우 검증\n(parse_agg.c)"]
    CO["assign_collations_to_grouplist\n(parse_collate.c)"]
    QN["Query 노드\nCMD_SELECT"]

    TS --> FR --> WH --> TL --> GB --> OB --> AG --> CO --> QN

그림 2 — transformSelectStmt는 전문 변환 함수들을 순서대로 호출한다. 각 단계는 서브쿼리가 있으면 transformStmt를 재귀 호출하고, parentParseState로 연결된 자식 ParseState를 만든다.

오류 위치 보고

원시 파스 트리 노드는 원래 SQL 문자열의 바이트 오프셋인 location 필드를 갖는다. 의미 분석 단계는 parser_errposition(pstate, location)으로 이 바이트 오프셋을 1-기반 문자 인덱스(via pg_mbstrlen_with_len)로 변환해 오류 보고에 errposition()으로 전달한다. 클라이언트 오류 메시지에 나타나는 친숙한 ^ 커서가 이렇게 만들어진다. ParseState를 받지 못하는 함수 안에서 오류가 발생하는 경우, setup_parser_errposition_callback이 위치를 자동으로 주입하는 오류 컨텍스트 콜백을 설치한다.

쿼리 ID와 분석 후 훅

transformTopLevelStmt가 반환하면, parse_analyze_fixedparams는 선택적으로 JumbleQuery를 실행해 쿼리 지문(query->queryId)을 계산하고, post_parse_analyze_hook을 발화한다. 이 훅은 pg_stat_statements 같은 확장이 완전히 변환된 쿼리를 리라이터에 도달하기 전에 가로채는 데 쓴다.

소스 탐방

1단계 — 렉싱과 원시 파싱

raw_parser (parser.c) — 최상위 진입점; Flex 스캐너와 Bison 파서를 초기화하고 RawStmt의 List *를 반환한다.
scanner_init / scanner_finish (scan.l) — Flex 스캐너 상태(core_yyscan_t) 할당·해제; 키워드 테이블 설치.
core_yylex (scan.l) — Flex 생성 내부 스캐너; 원시 토큰 방출.
base_yylex (parser.c) — 한 토큰 선독 필터; NOT→NOT_LA, NULLS_P→NULLS_LA, WITH→WITH_LA 변환, UIDENT/USCONST 유니코드 시퀀스 해석.
base_yyparse (gram.y, Bison 생성) — LALR(1) 파서; 노드 할당 액션으로 원시 AST 구성.
parser_init (gram.y) — Bison 글루 구조체 초기화.
ScanKeywordLookup (src/common/keywords.c) — 키워드 테이블 이진 탐색; scan.l이 모든 식별자 토큰마다 호출.
ScanKeywords / ScanKeywordTokens / kwlist.h — 521항목 정렬 키워드 테이블.

2단계 — 의미 분석

parse_analyze_fixedparams / parse_analyze_varparams / parse_analyze_withcb (analyze.c) — 세 진입점; ParseState 래핑, transformTopLevelStmt 호출, 훅 발화.
transformTopLevelStmt (analyze.c) — 구문 위치 데이터를 이전하고 transformStmt를 호출하는 얇은 래퍼.
transformStmt (analyze.c) — NodeTag 기반 디스패치 스위치; 최적화 가능 구문은 전문 변환으로, 유틸리티는 CMD_UTILITY로 래핑.
transformSelectStmt (analyze.c:1389) — 서브쿼리 처리를 포함한 완전한 SELECT 변환.
transformInsertStmt (analyze.c:633) — ON CONFLICT 포함 INSERT.
transformUpdateStmt (analyze.c:2472) — UPDATE 할당 리스트.
transformDeleteStmt (analyze.c:553) — USING 포함 DELETE.
transformMergeStmt (parse_merge.c:107) — MERGE WHEN 절.
transformSetOperationStmt (analyze.c:1751) — UNION/INTERSECT/EXCEPT.
transformValuesClause (analyze.c:1532) — VALUES 리스트.
transformReturnStmt (analyze.c:2441) — PL/pgSQL RETURN.
transformPLAssignStmt (analyze.c:2783) — PL/pgSQL 할당.
parse_sub_analyze (analyze.c:222) — 서브쿼리용 재귀 진입점.
make_parsestate / free_parsestate (parse_node.c) — ParseState 할당·해제; 부모에서 훅 포인터 복사.
parser_errposition (parse_node.c:106) — 오류 커서를 위한 바이트 오프셋→문자 인덱스 변환.
make_const (parse_node.c:347) — A_Const 문법 노드를 타입 부여된 Const(INT4, INT8, NUMERIC, BOOL, UNKNOWN, BIT)로 변환.
post_parse_analyze_hook (analyze.c:59) — 완전한 변환 후 발화하는 확장성 훅; pg_stat_statements가 사용.

위치 힌트 테이블 (2026-06-05 기준, 커밋 273fe94)

심볼	파일	줄
`raw_parser`	`src/backend/parser/parser.c`	42
`base_yylex`	`src/backend/parser/parser.c`	111
`str_udeescape`	`src/backend/parser/parser.c`	372
`scanner_init`	`src/backend/parser/scan.l`	1249
`scanner_finish`	`src/backend/parser/scan.l`	1291
`ScanKeywordTokens` 배열	`src/backend/parser/scan.l`	81
`stmtmulti` 생성 규칙	`src/backend/parser/gram.y`	961
`parser_init`	`src/backend/parser/gram.y`	19725
`post_parse_analyze_hook`	`src/backend/parser/analyze.c`	59
`parse_analyze_fixedparams`	`src/backend/parser/analyze.c`	105
`parse_analyze_varparams`	`src/backend/parser/analyze.c`	145
`parse_analyze_withcb`	`src/backend/parser/analyze.c`	186
`parse_sub_analyze`	`src/backend/parser/analyze.c`	222
`transformTopLevelStmt`	`src/backend/parser/analyze.c`	249
`transformStmt`	`src/backend/parser/analyze.c`	312
`transformDeleteStmt`	`src/backend/parser/analyze.c`	553
`transformInsertStmt`	`src/backend/parser/analyze.c`	633
`transformSelectStmt`	`src/backend/parser/analyze.c`	1389
`transformValuesClause`	`src/backend/parser/analyze.c`	1532
`transformSetOperationStmt`	`src/backend/parser/analyze.c`	1751
`transformReturnStmt`	`src/backend/parser/analyze.c`	2441
`transformUpdateStmt`	`src/backend/parser/analyze.c`	2472
`transformPLAssignStmt`	`src/backend/parser/analyze.c`	2783
`make_parsestate`	`src/backend/parser/parse_node.c`	39
`free_parsestate`	`src/backend/parser/parse_node.c`	72
`parser_errposition`	`src/backend/parser/parse_node.c`	106
`make_const`	`src/backend/parser/parse_node.c`	347
`transformMergeStmt`	`src/backend/parser/parse_merge.c`	107
`ParseState` 구조체	`src/include/parser/parse_node.h`	192
`RawParseMode` 열거형	`src/include/parser/parser.h`	38

소스 검증 (2026-06-05 기준)

검증된 사실

raw_parser는 Bison 실패 시 오류를 throw하지 않고 NIL을 반환한다. parser.c 82행에서 확인: if (yyresult) return NIL;. 호출자가 빈 리스트를 감지하고 오류를 발생시킬 책임을 진다. 스캐너 수준 오류는 ereport(ERROR)를 직접 사용하며 반환하지 않는다는 점이 대조적이다.
백트랙 없음 성질은 빌드 시스템이 강제한다. scan.l 파일 헤더에 *“flex에 -b 옵션을 주어 백트랙이 필요 없는지 확인하라 … (PostgreSQL 9.2 이후 Makefile이 자동으로 이 검사를 수행한다)“*고 명시돼 있다. 생성된 lex.backup은 비어 있어야 한다. src/backend/parser/Makefile에서 -b 플래그와 공백 검사가 빌드의 일부임을 확인했다.
gram.y는 약 19,700줄, kwlist.h는 521개 키워드 항목을 갖는다. 직접 계산: wc -l gram.y = 19,728; wc -l kwlist.h = 521. 키워드 수는 새 SQL 기능이 예약어를 추가할 때마다 메이저 버전마다 늘어난다.
base_yylex가 선독을 필요로 하는 토큰 유형은 정확히 여섯 가지다: FORMAT, NOT, NULLS_P, WITH, WITHOUT, UIDENT/USCONST. parser.c 138–161행과 196–321행의 switch (cur_token)을 읽어 확인했다. 나머지 토큰은 모두 default: return cur_token; 분기로 즉시 통과한다.
post_parse_analyze_hook은 analyze.c에 선언되고 NULL로 초기화된다. 59행에서 확인. 확장(pg_stat_statements 등)은 라이브러리 로드 시 훅을 설치한다. 훅은 JumbleQuery 이후에 발화하므로 queryId가 이미 설정돼 있다.
유틸리티 구문은 세 가지 예외를 제외하고 파스 시점에 분석되지 않는다. transformStmt의 437행 주석에 예외가 열거돼 있다. DECLARE CURSOR, EXPLAIN, CREATE TABLE AS는 각각 내포된 최적화 가능 쿼리를 즉시 분석한다.
ParseState는 PL/pgSQL과 SPI 확장성을 위해 파서 훅 함수 포인터를 갖는다. parse_node.h 238–242행에 p_pre_columnref_hook, p_post_columnref_hook, p_paramref_hook, p_coerce_param_hook이 선언돼 있다. 이것들은 make_parsestate에서 부모에서 자식 ParseState로 복사된다. PL/pgSQL은 자체 훅을 설치해 컬럼 참조 해석과 파라미터 바인딩을 가로챈다.

미결 질문

scan.l의 GUC 변수. 세 GUC 변수(backslash_quote, escape_string_warning, standard_conforming_strings)가 스캐너에서 직접 읽힌다. 파일 헤더는 이를 GUC 의존 코드 규칙에 대한 “직접적인 위반”이라고 부른다. 조사 경로: PG18에서 이것들을 스캐너의 extra 상태로 이전할 계획이 있는지, 아니면 PG9.1 이후 standard_conforming_strings = on이 기본값이 되어 문제가 실질적으로 무력화됐는지 확인한다.
parse_utilcmd.c의 역할. README는 parse_utilcmd.c를 “실행 시점에 수행되는 유틸리티 명령의 파스 분석”으로 설명한다. 이 파일은 analyze.c의 디스패치 밖에 있으며 ProcessUtility에서 호출된다. 조사 경로: parse_utilcmd.c의 transformCreateStmt / transformIndexStmt를 어떤 유틸리티 명령이 호출하는지 추적하고, 이것들이 ProcessUtility가 카탈로그 락을 획득하기 전에 카탈로그 락을 취득하지 않는지 확인한다.
query->queryId 안정성. JumbleQuery는 정규화된 쿼리 트리의 지문을 만든다. 마이너 PG 버전 업그레이드(새 표현식 노드 유형 추가 등) 간 이 지문의 안정성은 문서화되지 않았다. 조사 경로: nodes/queryjumble.c의 jumble_query 로직을 읽어 노드 유형 추가가 기존 지문을 무효화하는지 확인한다.

PostgreSQL 너머 — 비교 설계와 연구 프런티어

직접 작성한 재귀 하향 파서. MySQL 8.0은 더 나은 오류 메시지와 증분 파싱을 위해 Bison 문법을 직접 작성한 재귀 하향 파서로 교체했다. PostgreSQL의 생성된 LALR(1) 방식과의 비교 분석은 오류 품질 대 문법 유지보수성의 트레이드오프를 보여줄 것이다. PostgreSQL은 오류 메시지 품질보다 문법 표현력을 우선시해왔다.
증분 / 부분 파싱. PostgreSQL 파서는 호출마다 전체 쿼리 문자열을 다시 파싱한다. libpg_query나 pg_query Go/Ruby 래퍼 같은 도구들이 raw_parser를 외부에 노출한다. tree-sitter 문법에 관한 연구(Brunsfeld 외, 2018)는 편집 간 파스 상태 재사용을 보여준다. 이를 PostgreSQL 문법에 적용하면 IDE와 쿼리 분석 도구에 이점을 줄 것이다.
문법 기반 쿼리 정규화. nodes/queryjumble.c의 JumbleQuery 경로는 원시 텍스트가 아닌 분석된 쿼리 트리에 지문을 찍는다. 이는 구문적으로 다르지만 의미상 동등한 쿼리(SELECT 1 대 SELECT 1::int4)가 다른 ID를 받을 수 있음을 뜻한다. 의미 분석 이전 원시 파스 단계에서 표준형 축약에 기반한 접근법이 pg_stat_statements 이슈 트래커에서 탐구되고 있다.
확장성 면으로서의 파서 훅. post_parse_analyze_hook, p_pre_columnref_hook, p_paramref_hook 슬롯은 확장에 파스 분석 내부에 대한 접근을 제공한다. 이 훅을 사용하는 확장들(Citus, TimescaleDB, pg_stat_statements, PL/pgSQL 자신)을 조사하면 실제 훅 계약이 무엇인지 문서화할 수 있다.

출처

인트리 문서

src/backend/parser/README — 각 파일의 모듈 수준 설명.
src/backend/parser/gram.y (파일 헤더) — 카탈로그 없음 규칙과 LALR(1) 요건의 설계 근거.
src/backend/parser/scan.l (파일 헤더) — 백트랙 없음 규칙 및 psqlscan.l / pgc.l과의 동기화 요건.

교과서

Aho, Lam, Sethi, Ullman. Compilers: Principles, Techniques, and Tools (Dragon Book), 2판, 2006. §§2–5 (어휘 분석, 파싱, LALR).
Cooper & Torczon. Engineering a Compiler, 2판, 2012. Ch. 2–4.

소스 코드 경로

src/backend/parser/ — 모든 파서 소스 파일.
src/include/parser/ — parser.h, parse_node.h, kwlist.h, gramparse.h.
src/common/keywords.c — ScanKeywordLookup (프런트엔드 도구들과 공유).
src/nodes/queryjumble.c — 쿼리 지문 생성을 위한 JumbleQuery.