聲明：本文的部分內(nèi)容參考了他人的文章。在編寫過程中，我們尊重他人的知識(shí)產(chǎn)權(quán)和學(xué)術(shù)成果，力求遵循合理使用原則，并在適用的情況下注明引用來源。
本文主要參考了《PostgresSQL數(shù)據(jù)庫內(nèi)核分析》一書

查詢處理

??在PostgreSQL中，查詢處理是指處理和執(zhí)行SQL查詢語句的整個(gè)過程。這個(gè)過程涵蓋了從接收客戶端發(fā)送的查詢到返回結(jié)果的整個(gè)流程。**PostgreSQL查詢處理涵蓋了從接收客戶端發(fā)送的SQL查詢到返回結(jié)果的整個(gè)過程。**其主要職責(zé)包括：

1. 查詢解析：接收客戶端發(fā)送的SQL查詢，并進(jìn)行語法和語義解析，確保查詢語句正確且符合數(shù)據(jù)庫規(guī)范。如果查詢語句存在錯(cuò)誤，將向客戶端返回相應(yīng)的錯(cuò)誤信息。
2. 查詢重寫：對(duì)已解析的查詢進(jìn)行重寫和轉(zhuǎn)換，應(yīng)用查詢優(yōu)化規(guī)則和重寫規(guī)則來改進(jìn)查詢的執(zhí)行計(jì)劃。通過查詢重寫，可以將查詢轉(zhuǎn)換為更高效的形式，以便更快地獲取所需的數(shù)據(jù)。
3. 查詢優(yōu)化：根據(jù)查詢的代價(jià)模型和統(tǒng)計(jì)信息，創(chuàng)建多個(gè)可能的執(zhí)行計(jì)劃，并選擇最優(yōu)的執(zhí)行計(jì)劃以最小化查詢的總成本。優(yōu)化器會(huì)嘗試不同的執(zhí)行策略，比較它們的代價(jià)，并選擇執(zhí)行成本最低的方案。
4. 執(zhí)行計(jì)劃生成：根據(jù)查詢優(yōu)化器選擇的最佳執(zhí)行計(jì)劃，生成一個(gè)由操作符組成的執(zhí)行計(jì)劃樹。這個(gè)執(zhí)行計(jì)劃樹描述了查詢?cè)跀?shù)據(jù)庫中的執(zhí)行過程，包括數(shù)據(jù)訪問、連接、過濾、排序等操作。
5. 查詢執(zhí)行：按照生成的執(zhí)行計(jì)劃，執(zhí)行查詢操作。查詢引擎會(huì)根據(jù)執(zhí)行計(jì)劃中的操作符逐步執(zhí)行查詢，從數(shù)據(jù)庫中獲取數(shù)據(jù)，并進(jìn)行相應(yīng)的數(shù)據(jù)操作和計(jì)算。
6. 鎖定和并發(fā)控制：在執(zhí)行查詢時(shí)，確保正確的鎖定機(jī)制和并發(fā)控制，以防止數(shù)據(jù)不一致和并發(fā)沖突。這對(duì)于多用戶同時(shí)訪問數(shù)據(jù)庫的情況至關(guān)重要。
7. 統(tǒng)計(jì)信息維護(hù)：在查詢執(zhí)行過程中，維護(hù)和更新數(shù)據(jù)庫中的統(tǒng)計(jì)信息，包括表和索引的數(shù)據(jù)分布、行數(shù)估計(jì)等。這些統(tǒng)計(jì)信息對(duì)于優(yōu)化器的選擇非常重要。
8. 查詢緩存管理：在查詢處理過程中，嘗試在查詢緩存中查找相同查詢的執(zhí)行計(jì)劃，從而避免重復(fù)的查詢編譯和優(yōu)化，提高查詢性能。
9. 錯(cuò)誤處理和異常處理：負(fù)責(zé)捕獲和處理查詢執(zhí)行過程中可能發(fā)生的錯(cuò)誤和異常情況，并向客戶端返回相應(yīng)的錯(cuò)誤信息。

??查詢處理是數(shù)據(jù)庫系統(tǒng)的核心功能之一，它直接影響到數(shù)據(jù)庫的性能和響應(yīng)時(shí)間。PostgreSQL的查詢處理器通過查詢解析、優(yōu)化、執(zhí)行和并發(fā)控制等職責(zé)來確保高效、可靠地處理各種類型的SQL查詢。優(yōu)化器和執(zhí)行引擎的優(yōu)化算法和策略在此過程中發(fā)揮著至關(guān)重要的作用。
??以下分別展示了查詢處理的完整流程圖和查詢處理的各模塊說明。

查詢分析

查詢處理與查詢分析的關(guān)系

??查詢分析是查詢處理的一個(gè)子過程。查詢處理是一個(gè)更廣泛的概念，包含了整個(gè)查詢的生命周期，從接收查詢到最終的結(jié)果返回。在查詢處理過程中，查詢分析是其中的一個(gè)重要組成部分。查詢分析的結(jié)果會(huì)影響到查詢優(yōu)化器的選擇，從而影響最終的執(zhí)行計(jì)劃生成和查詢執(zhí)行階段。通過查詢分析，我們可以了解查詢的執(zhí)行情況，并進(jìn)行必要的優(yōu)化，以提高查詢的性能和數(shù)據(jù)庫的整體性能。
??查詢分析和查詢處理是數(shù)據(jù)庫查詢過程中的兩個(gè)重要環(huán)節(jié)。查詢分析用于分析已執(zhí)行查詢的性能并優(yōu)化查詢，而查詢處理負(fù)責(zé)整個(gè)查詢的處理和執(zhí)行。查詢分析是查詢處理過程的一部分，通過優(yōu)化查詢分析結(jié)果，可以改善整個(gè)查詢處理的性能和效率。

查詢分析執(zhí)行流程

??查詢分析是查詢編譯的第一個(gè)模塊，它包括詞法分析、語法分析和語義分析三個(gè)部分。它將用戶輸人的SQL命令轉(zhuǎn)換為查詢樹（Query結(jié)構(gòu))。其中詞法分析和語法分析分別借助詞法分析工具Lex和語法分析工具Yacc來完成各自的工作。
??查詢分析的基本流程如下所示：

??如下展示了查詢分析中主要的函數(shù)調(diào)用關(guān)系：

??對(duì)于用戶的SQL命令，統(tǒng)一由exec_simple_query函數(shù)處理，該函數(shù)將調(diào)用pg_parse_query完成詞法和語法分析并產(chǎn)生分析樹，接下來調(diào)用pg_analyze_and_rewrite函數(shù)逐個(gè)對(duì)分析樹進(jìn)行語義分析和重寫:在該函數(shù)中又會(huì)調(diào)用函數(shù) parse _ analyzer進(jìn)行語義分析并創(chuàng)建查詢樹(Query 結(jié)構(gòu))，函數(shù)pg_rewrite _query則負(fù)責(zé)對(duì)查詢樹進(jìn)行重寫。
??查詢分析的處理過程如下：

1. exec_simple_query調(diào)用函數(shù) pg_parse_query進(jìn)入詞法和語法分析的主體處理過程，然后函數(shù)pg_parse_query調(diào)用詞法和語法分析的人口函數(shù)raw_parser生成分析樹（原始分析樹鏈表raw_parse-tree_list)。
   注：exec_simple_query函數(shù)源碼如下所示，路徑在：/postgresql-10.1/src/backend/tcop/postgres.c下。
   
   
2. 函數(shù)pg_parse_query返回分析樹給外部函數(shù)。函數(shù)pg_parse_query的源碼如下所示。

/*
 * pg_parse_query - 解析輸入的SQL查詢語句，返回解析樹的列表
 *
 * 輸入?yún)?shù):
 *     query_string - 要解析的SQL查詢字符串
 *
 * 返回值:
 *     List類型的指針，包含解析樹的列表
 *
 * 該函數(shù)的作用是將輸入的SQL查詢字符串解析成解析樹的列表，并返回該列表。
 * 解析樹是一個(gè)由C語言數(shù)據(jù)結(jié)構(gòu)構(gòu)成的樹狀表示，用于表示SQL查詢的結(jié)構(gòu)和邏輯。
 */

List *
pg_parse_query(const char *query_string)
{
    List *raw_parsetree_list;

    // 記錄查詢解析開始的追蹤日志
    TRACE_POSTGRESQL_QUERY_PARSE_START(query_string);

    // 如果需要記錄解析器統(tǒng)計(jì)信息，就重置統(tǒng)計(jì)信息
    if (log_parser_stats)
        ResetUsage();

    // 調(diào)用原始解析器進(jìn)行解析，得到原始解析樹列表
    raw_parsetree_list = raw_parser(query_string);

    // 如果需要記錄解析器統(tǒng)計(jì)信息，就顯示統(tǒng)計(jì)信息
    if (log_parser_stats)
        ShowUsage("PARSER STATISTICS");

    // 可選的調(diào)試檢查：通過copyObject()函數(shù)復(fù)制原始解析樹列表，用于調(diào)試
    // 這里通過比較原始解析樹列表和復(fù)制后的列表來檢查copyObject()和equal()是否正確
#ifdef COPY_PARSE_PLAN_TREES
    {
        List *new_list = copyObject(raw_parsetree_list);

        // 這里比較兩個(gè)列表是否相等，以確保copyObject()正確工作
        if (!equal(new_list, raw_parsetree_list))
            elog(WARNING, "copyObject() failed to produce an equal raw parse tree");
        else
            raw_parsetree_list = new_list;
    }
#endif

    // 記錄查詢解析結(jié)束的追蹤日志
    TRACE_POSTGRESQL_QUERY_PARSE_DONE(query_string);

    // 返回原始解析樹列表
    return raw_parsetree_list;
}

??其中，raw_parser為詞法和語法分析的入口函數(shù)。

??raw_parser函數(shù)(在src/backend/parser/parser.c下)主要通過調(diào)用采用Lex和Yacc配合預(yù)生成的base_yyparse函數(shù)來實(shí)現(xiàn)詞法分析和語法分析的工作。raw_parser的源代碼如下所示。

/*
 * raw_parser
 *		Given a query in string form, do lexical and grammatical analysis.
 *	    對(duì)給定的查詢字符串進(jìn)行詞法和語法分析。
 *
 * Returns a list of raw (un-analyzed) parse trees.  The immediate elements
 * of the list are always RawStmt nodes.
 * 返回一個(gè)原始（未經(jīng)分析）解析樹列表。該列表的直接元素總是RawStmt節(jié)點(diǎn)。
 */
List *
raw_parser(const char *str)
{
	core_yyscan_t yyscanner;
	base_yy_extra_type yyextra;
	int			yyresult;

	/* initialize the flex scanner */
	/* 初始化flex掃描器 */
	yyscanner = scanner_init(str, &yyextra.core_yy_extra,
							 ScanKeywords, NumScanKeywords);

	/* base_yylex() only needs this much initialization */
	/* base_yylex()只需要這么多的初始化 */
	yyextra.have_lookahead = false;

	/* initialize the bison parser */
	/* 初始化bison解析器 */
	parser_init(&yyextra);

	/* Parse! */
	/* 開始解析! */
	yyresult = base_yyparse(yyscanner);

	/* Clean up (release memory) */
	/* 清理（釋放內(nèi)存） */
	scanner_finish(yyscanner);

	if (yyresult)				/* error */
		return NIL;

	return yyextra.parsetree;
}

??返回值為L(zhǎng)ist結(jié)構(gòu)體，定義如下：（路徑為：src/include/nodes/pg_list.h）

typedef struct ListCell ListCell;

typedef struct List
{
	NodeTag		type;			/* T_List, T_IntList, or T_OidList */
	int			length;
	ListCell   *head;
	ListCell   *tail;
} List;

struct ListCell
{
	union
	{
		void	   *ptr_value;
		int			int_value;
		Oid			oid_value;
	}			data;
	ListCell   *next;
};

??這段代碼定義了一個(gè)簡(jiǎn)單的鏈表數(shù)據(jù)結(jié)構(gòu) List，它由節(jié)點(diǎn) ListCell 組成。每個(gè)節(jié)點(diǎn)可以存儲(chǔ)不同類型的數(shù)據(jù)，并通過指針 next 連接在一起，形成一個(gè)鏈表。

4. exec_simple_query接著調(diào)用函數(shù)pg_analyze_and_rewrite進(jìn)行語義分析和查詢重寫。首先調(diào)用函數(shù)parse_analyze進(jìn)行語義分析并生成查詢樹（用Query結(jié)構(gòu)體表示)，之后會(huì)將查詢樹傳遞給函數(shù)pg_rewrite_query進(jìn)行查詢重寫。

??pg_analyze_and_rewrite的源代碼如下：

/*
 * Given a raw parsetree (gram.y output), and optionally information about
 * types of parameter symbols ($n), perform parse analysis and rule rewriting.
 * 給定一個(gè)原始解析樹（gram.y的輸出），以及可選的參數(shù)符號(hào)（$n）的類型信息，
 * 執(zhí)行解析分析和規(guī)則重寫。
 * 
 * A list of Query nodes is returned, since either the analyzer or the
 * rewriter might expand one query to several.
 * 返回一個(gè)Query節(jié)點(diǎn)的列表，因?yàn)榻馕龇治銎骰蛑貙懫骺赡軙?huì)將一個(gè)查詢展開成多個(gè)查詢。
 *
 * NOTE: for reasons mentioned above, this must be separate from raw parsing.
 * 注意：由于上述原因，這必須與原始解析分開。
 */
List *
pg_analyze_and_rewrite(RawStmt *parsetree, const char *query_string,
					   Oid *paramTypes, int numParams,
					   QueryEnvironment *queryEnv)
{
	Query	   *query;
	List	   *querytree_list;

	TRACE_POSTGRESQL_QUERY_REWRITE_START(query_string);

	/*
	 * (1) Perform parse analysis.
	 * (1) 執(zhí)行解析分析
	 */
	if (log_parser_stats)
		ResetUsage();
		
	// 調(diào)用parse_analyze()函數(shù)進(jìn)行解析分析，得到解析后的Query節(jié)點(diǎn)
	query = parse_analyze(parsetree, query_string, paramTypes, numParams,
						  queryEnv);
						  
	// 如果需要記錄解析器統(tǒng)計(jì)信息，就顯示統(tǒng)計(jì)信息
	if (log_parser_stats)
		ShowUsage("PARSE ANALYSIS STATISTICS");

	/*
	 * (2) Rewrite the queries, as necessary
	 * 重寫查詢，必要時(shí)進(jìn)行重寫
	 */
	 // 調(diào)用pg_rewrite_query()函數(shù)重寫查詢
	querytree_list = pg_rewrite_query(query);

	// 記錄查詢重寫結(jié)束的追蹤日志
	TRACE_POSTGRESQL_QUERY_REWRITE_DONE(query_string);

	// 返回重寫后的查詢列表
	return querytree_list;
}

??在 PostgreSQL 中，Query 節(jié)點(diǎn)是解析分析器生成的一個(gè)重要數(shù)據(jù)結(jié)構(gòu)，用于表示一條SQL查詢語句的邏輯結(jié)構(gòu)。Query 節(jié)點(diǎn)是由解析器在解析 SQL 查詢時(shí)構(gòu)建的，它以樹狀結(jié)構(gòu)的形式表示查詢的各個(gè)部分和子句。
??在查詢處理的過程中，Query 節(jié)點(diǎn)會(huì)經(jīng)歷多個(gè)階段的處理，例如解析分析、查詢重寫、優(yōu)化和執(zhí)行等。通過 Query 節(jié)點(diǎn)，PostgreSQL 可以在內(nèi)部進(jìn)行各種操作，從而執(zhí)行和優(yōu)化復(fù)雜的查詢語句。在數(shù)據(jù)庫內(nèi)部，多個(gè) Query 節(jié)點(diǎn)可能相互關(guān)聯(lián)形成一個(gè)查詢計(jì)劃的樹狀結(jié)構(gòu)，代表整個(gè)查詢的執(zhí)行計(jì)劃和邏輯流程。
??Query的結(jié)構(gòu)如下：

/*
 * Query -
 *	  Parse analysis turns all statements into a Query tree
 *	  for further processing by the rewriter and planner.
 *
 *	  Utility statements (i.e. non-optimizable statements) have the
 *	  utilityStmt field set, and the rest of the Query is mostly dummy.
 *
 *	  Planning converts a Query tree into a Plan tree headed by a PlannedStmt
 *	  node --- the Query structure is not used by the executor.
 */

/*
 * Query -
 *	  解析分析將所有語句轉(zhuǎn)換成一個(gè)Query樹，以便后續(xù)由重寫器和規(guī)劃器進(jìn)行進(jìn)一步處理。
 *	  實(shí)用語句（即不可優(yōu)化的語句）會(huì)設(shè)置utilityStmt字段，而Query的其余部分大多是虛擬的。
 *	  規(guī)劃將Query樹轉(zhuǎn)換成由PlannedStmt節(jié)點(diǎn)為頭的Plan樹 --- 執(zhí)行器不使用Query結(jié)構(gòu)。
 */
 
typedef struct Query
{
    NodeTag     type;               /* 結(jié)點(diǎn)類型，必須為 T_Query */
    QueryCommandType commandType;   /* 查詢類型，例如 SELECT、INSERT、UPDATE 等 */
    bool        canSetTag;          /* 命令類型是否可以設(shè)置標(biāo)記（用于DML） */
    bool        hasAggs;            /* 查詢中是否含有聚合函數(shù) */
    bool        hasWindowFuncs;     /* 查詢中是否含有窗口函數(shù) */
    bool        hasSubLinks;        /* 查詢中是否含有子查詢 */
    bool        hasDistinctOn;      /* 查詢中是否含有DISTINCT ON子句 */
    bool        hasRecursive;       /* 查詢中是否包含遞歸CTE */
    bool        hasModifyingCTE;    /* 查詢中是否含有修改的CTE */
    bool        hasForUpdate;       /* 查詢中是否含有FOR UPDATE子句 */
    bool        hasRowSecurity;     /* 查詢中是否使用行級(jí)安全性 */
    bool        hasPartialPlans;    /* 查詢中是否包含部分計(jì)劃 */
    List       *rtable;             /* 查詢的表引用列表（RangeTblEntry節(jié)點(diǎn)的列表） */
    FromExpr   *jointree;           /* 查詢的關(guān)聯(lián)表達(dá)式樹（FROM子句） */
    List       *targetList;         /* 查詢的目標(biāo)列表（TargetEntry節(jié)點(diǎn)的列表） */
    List       *returningList;      /* 查詢的 RETURNING 子句列表 */
    List       *groupClause;        /* 查詢的 GROUP BY 子句列表 */
    Node       *havingQual;         /* 查詢的 HAVING 子句 */
    List       *distinctClause;     /* 查詢的 DISTINCT 子句列表 */
    List       *sortClause;         /* 查詢的 ORDER BY 子句列表 */
    List       *limitOffset;        /* 查詢的 OFFSET 子句 */
    List       *limitCount;         /* 查詢的 LIMIT 子句 */
    List       *rowMarks;           /* 查詢中的行標(biāo)記列表（RowMarkClause節(jié)點(diǎn)的列表） */
    List       *setOperations;      /* SET操作子查詢的列表（SetOperationStmt節(jié)點(diǎn)的列表） */
    Node       *constraintDeps;     /* 查詢約束的依賴關(guān)系（IndexedExpr節(jié)點(diǎn)的鏈表） */
    List       *withCheckOptions;   /* WITH CHECK OPTION的列表 */
    List       *returningLists;     /* 規(guī)范化CTE RETURNING 子句的列表（TargetEntry節(jié)點(diǎn)的列表） */
    List       *placeholder_list;   /* 用于構(gòu)建樹狀查詢計(jì)劃的占位符（Placeholder節(jié)點(diǎn)的列表） */
    List       *query_parallel;     /* 查詢中的并行計(jì)劃的列表（Query節(jié)點(diǎn)的列表） */
    Node       *partColsUpdated;    /* 對(duì)于處理過的的ROW類型屬性，列更新模式的布爾表達(dá)式 */
    int         commandTypeIndexId; /* 記錄為特定命令類型重新編號(hào)的RangeTblEntry索引 */
    int         resultRelation;     /* 查詢結(jié)果的目標(biāo)表的范圍表?xiàng)l目索引 */
    int         utilityStmt;        /* 對(duì)于UTILITY命令，此處包含原始StatementType值 */

	/*
	 * The following two fields identify the portion of the source text string
	 * containing this query.  They are typically only populated in top-level
	 * Queries, not in sub-queries.  When not set, they might both be zero, or
	 * both be -1 meaning "unknown".
	 */
    int         stmt_location;      /* 在原始字符串中的語句的位置 */
    int         stmt_len;           /* 在原始字符串中的語句的長(zhǎng)度 */
} Query;

??介紹完以上流程，接著我們回到raw_parser函數(shù)中，raw_parser是通過Lex和Yacc生成的代碼來進(jìn)行詞法和語法分析并生成分析樹。Lex和Yacc是詞法與語法分析工具，兩者相配合可以生成用于詞法和語法分析的C語言源代碼。在raw_parser中，就是通過調(diào)用采用它倆預(yù)生成的函數(shù)base_yyparse來實(shí)現(xiàn)詞法和語法分析工作。

Lex和Yacc

??Lex和Yacc是兩個(gè)經(jīng)典的工具，用于構(gòu)建詞法分析器（Lexical Analyzer）和語法分析器（Parser）。它們是編譯器設(shè)計(jì)和開發(fā)過程中非常重要的工具，用于處理輸入的源代碼，并將其轉(zhuǎn)換成抽象語法樹或其他數(shù)據(jù)結(jié)構(gòu)以便進(jìn)一步處理。

Lex：

??Lex（也稱為Flex）是一個(gè)詞法分析器生成器。它接受一個(gè)包含詞法規(guī)則的輸入文件，并生成一個(gè)用于掃描源代碼的詞法分析器。詞法分析器讀取源代碼字符流，識(shí)別出各個(gè)詞法單元（token），并將它們傳遞給語法分析器。每個(gè)詞法規(guī)則由正則表達(dá)式和相應(yīng)的動(dòng)作代碼組成，用于識(shí)別不同的詞法單元。

Yacc：

??Yacc（也稱為Bison）是一個(gè)語法分析器生成器。它接受一個(gè)包含語法規(guī)則的輸入文件，并生成一個(gè)用于解析源代碼的語法分析器。語法分析器接收詞法分析器傳遞的詞法單元，根據(jù)語法規(guī)則構(gòu)建抽象語法樹或解析樹。每個(gè)語法規(guī)則由一系列產(chǎn)生式（產(chǎn)生式左側(cè)是非終結(jié)符，右側(cè)是終結(jié)符或非終結(jié)符）和相應(yīng)的動(dòng)作代碼組成，用于構(gòu)造語法分析樹。
??使用Lex和Yacc，編譯器開發(fā)人員可以將源代碼轉(zhuǎn)換為抽象語法樹，從而更方便地進(jìn)行語義分析、優(yōu)化和代碼生成。它們可以大大簡(jiǎn)化編譯器的設(shè)計(jì)和開發(fā)過程，使得編譯器的實(shí)現(xiàn)更加模塊化和可維護(hù)。除了編譯器，Lex和Yacc也被廣泛用于解析和處理其他領(lǐng)域的文本數(shù)據(jù)，例如配置文件解析、網(wǎng)絡(luò)協(xié)議解析等。

詞法分析工具Lex

??以下是一個(gè)簡(jiǎn)單的 Lex 文件示例，用于識(shí)別簡(jiǎn)單的算術(shù)表達(dá)式中的運(yùn)算符和數(shù)字：

%{
#include <stdio.h>
%}

// 定義一些詞法單元的模式
DIGIT       [0-9]
OPERATOR    [+|\-|*|/]
WHITESPACE  [ \t\n]

%%
// 正則表達(dá)式和對(duì)應(yīng)的動(dòng)作代碼

{DIGIT}+    { printf("NUMBER: %s\n", yytext); }
{OPERATOR}  { printf("OPERATOR: %s\n", yytext); }
{WHITESPACE} { /* 忽略空格和換行符 */ }

.           { printf("INVALID CHARACTER: %s\n", yytext); }

%%

int main(void) {
    // 初始化詞法分析器
    yylex();

    return 0;
}

??在這個(gè)例子中，我們定義了一些詞法單元的模式，例如 DIGIT 表示數(shù)字的正則表達(dá)式 [0-9]，OPERATOR 表示運(yùn)算符的正則表達(dá)式 [+-*/]，WHITESPACE 表示空格和換行符的正則表達(dá)式 [ \t\n]。
??在 %% 之后，我們定義了一系列正則表達(dá)式和對(duì)應(yīng)的動(dòng)作代碼。例如，當(dāng)遇到一串?dāng)?shù)字時(shí)，我們執(zhí)行 {DIGIT}+ 中的動(dòng)作代碼，打印出 NUMBER: 后跟著該數(shù)字的文本。同樣，當(dāng)遇到一個(gè)運(yùn)算符時(shí)，我們執(zhí)行 {OPERATOR} 中的動(dòng)作代碼，打印出 OPERATOR: 后跟著該運(yùn)算符的文本。對(duì)于空格和換行符，我們只是忽略它們，不做任何動(dòng)作。
??最后，我們使用 yylex() 來啟動(dòng)詞法分析器，它會(huì)讀取標(biāo)準(zhǔn)輸入中的字符流并執(zhí)行相應(yīng)的動(dòng)作代碼。通過運(yùn)行該示例程序并輸入一些算術(shù)表達(dá)式，我們可以看到詞法分析器輸出的識(shí)別結(jié)果。

讓我們假設(shè)你輸入以下算術(shù)表達(dá)式：
12 + 34 * 5 - 6 / 2
那么程序的輸出結(jié)果將是：

NUMBER: 12
OPERATOR: +
NUMBER: 34
OPERATOR: *
NUMBER: 5
OPERATOR: -
NUMBER: 6
OPERATOR: /
NUMBER: 2

??Lex 生成的掃描器在成功識(shí)別模式后，通過Lex變量（參見表5-3）存儲(chǔ)該模式對(duì)應(yīng)的值，并將其返回給上層調(diào)用者（通常是 Yacc生成的語法分析器)。

語法分析工具Yacc

??Yacc（Yet Another Compiler Compiler）是一種語法分析器生成器，用于構(gòu)建語法分析器（Parser）。它接受一個(gè)包含語法規(guī)則的輸入文件，并生成一個(gè)用于解析源代碼的語法分析器。
??Yacc 解析輸入的文法規(guī)則，并根據(jù)這些規(guī)則構(gòu)建一個(gè) LALR（Look-Ahead Left-to-Right Rightmost derivation）語法分析器。LALR 語法分析器用于將輸入的源代碼解析成語法樹或抽象語法樹，從而進(jìn)行進(jìn)一步的語義分析、優(yōu)化和代碼生成。
??Yacc 通常與 Lex（詞法分析器生成器）配合使用。在 Lex 中識(shí)別出詞法單元后，Yacc 將這些詞法單元組合成更復(fù)雜的語法結(jié)構(gòu)，形成一個(gè)完整的解析樹。這樣，Lex 和 Yacc 一起構(gòu)成了編譯器的前端（Frontend），負(fù)責(zé)將輸入的源代碼轉(zhuǎn)換為抽象語法樹或解析樹，以便進(jìn)行后續(xù)的編譯器處理。

案例：當(dāng)我們?cè)谟?jì)算器中輸入簡(jiǎn)單的算術(shù)表達(dá)式時(shí)，我們可以使用 Yacc 來構(gòu)建一個(gè)語法分析器。以下是一個(gè)簡(jiǎn)單的 Yacc 示例，用于解析類似于 1 + 2 * 3 這樣的算術(shù)表達(dá)式：

// Yacc
%{
#include <stdio.h>
#include <stdlib.h>
%}

// 定義詞法分析器返回的詞法單元
%token NUMBER
%token PLUS
%token TIMES

// 定義語法規(guī)則
%left PLUS
%left TIMES

%%
// 語法規(guī)則和對(duì)應(yīng)的動(dòng)作代碼

expression: NUMBER
    { printf("%d\n", $1); }
    ;

expression: expression PLUS expression
    { $$ = $1 + $3; }
    ;

expression: expression TIMES expression
    { $$ = $1 * $3; }
    ;
%%

int yylex(void) {
    int c = getchar();
    if (c == '+') return PLUS;
    if (c == '*') return TIMES;
    if (isdigit(c)) {
        ungetc(c, stdin);
        scanf("%d", &yylval);
        return NUMBER;
    }
    return c;
}

int main(void) {
    // 初始化語法分析器
    yyparse();

    return 0;
}

解釋：在這個(gè)示例中，我們定義了三個(gè)詞法單元 NUMBER、PLUS 和 TIMES，分別用于表示數(shù)字、加號(hào)和乘號(hào)。然后我們定義了三條語法規(guī)則，用于描述算術(shù)表達(dá)式的結(jié)構(gòu)。在每個(gè)規(guī)則的右側(cè)，我們執(zhí)行一些動(dòng)作代碼，用于計(jì)算表達(dá)式的值。
??在 yylex() 函數(shù)中，我們實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的詞法分析器，它從標(biāo)準(zhǔn)輸入中讀取字符，并根據(jù)輸入的字符返回相應(yīng)的詞法單元。例如，如果遇到加號(hào)，則返回 PLUS，如果遇到數(shù)字，則讀取完整的數(shù)字，并返回 NUMBER 并保存數(shù)字的值。
??最后，在 main() 函數(shù)中，我們調(diào)用 yyparse() 來啟動(dòng)語法分析器，它會(huì)讀取詞法分析器返回的詞法單元，并根據(jù)定義的語法規(guī)則構(gòu)建解析樹。然后我們可以計(jì)算和輸出表達(dá)式的值。
??當(dāng)輸入 1 + 2 * 3 時(shí)，程序?qū)⑤敵?7，因?yàn)樗_地處理了乘法優(yōu)先級(jí)。這個(gè)簡(jiǎn)單的示例演示了如何使用 Yacc 來構(gòu)建一個(gè)簡(jiǎn)單的語法分析器，從而解析和計(jì)算算術(shù)表達(dá)式。請(qǐng)注意，此示例是簡(jiǎn)化的，實(shí)際的語法分析器可能需要處理更復(fù)雜的語法規(guī)則和錯(cuò)誤處理。

使用Lex和Yacc的案例

??當(dāng)使用 Lex 和 Yacc 結(jié)合時(shí)，經(jīng)典的案例之一是構(gòu)建一個(gè)簡(jiǎn)單的計(jì)算器，可以解析和計(jì)算簡(jiǎn)單的算術(shù)表達(dá)式。讓我們來看一個(gè)使用 Lex 和 Yacc 結(jié)合的計(jì)算器示例：

1. Lex 文件（calculator.lex）：

%{
#include <stdio.h>
#include "y.tab.h" // 包含 Yacc 生成的頭文件
%}

DIGIT       [0-9]
OPERATOR    [+|\-|*|/]

%%
{DIGIT}+    { yylval = atoi(yytext); return NUMBER; }
{OPERATOR}  { return *yytext; }
[ \t\n]     { /* 忽略空格和換行符 */ }
.           { return *yytext; }
%%

int yywrap() {
    return 1;
}

2. Yacc 文件（calculator.y）：

%{
#include <stdio.h>
%}

%token NUMBER
%left '+' '-'
%left '*' '/'

%%
expression:
    NUMBER { $$ = $1; }
    | expression '+' expression { $$ = $1 + $3; }
    | expression '-' expression { $$ = $1 - $3; }
    | expression '*' expression { $$ = $1 * $3; }
    | expression '/' expression { $$ = $1 / $3; }
    | '(' expression ')' { $$ = $2; }
    ;
%%

int main() {
    yyparse();
    return 0;
}

int yyerror(const char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
    return 1;
}

3. 編譯和運(yùn)行：
   首先，我們需要生成 Lex 和 Yacc 的解析器和詞法分析器代碼。在終端中執(zhí)行以下命令：

lex calculator.lex
yacc -d calculator.y
gcc lex.yy.c y.tab.c -o calculator
(需要安裝flex包：sudo apt install flex)
(需要安裝byacc包：sudo apt install byacc)

執(zhí)行命令后可以看到生成的文件：

然后，我們可以運(yùn)行生成的計(jì)算器程序：./calculator

詞法和語法分析

??詞法分析和語法分析是解析 SQL 查詢語句的兩個(gè)重要步驟。

1. 詞法分析（Lexical Analysis）：
   ??詞法分析是將輸入的 SQL 查詢字符串分解為一系列詞法單元（tokens）的過程。每個(gè)詞法單元代表 SQL 查詢中的一個(gè)獨(dú)立元素，例如關(guān)鍵字、標(biāo)識(shí)符、運(yùn)算符、常量等。詞法分析器（通常由 Lex 或 Flex 工具生成）會(huì)按照預(yù)定義的規(guī)則掃描輸入字符串，并將識(shí)別出的詞法單元傳遞給語法分析器。
   ??在 Postgres 中，詞法分析器將 SQL 查詢字符串轉(zhuǎn)換為一系列詞法單元，每個(gè)詞法單元包含一個(gè)標(biāo)記（token）和可能的附加信息（例如標(biāo)識(shí)符的名稱、常量的值等）。這些詞法單元將在語法分析階段用于構(gòu)建語法樹。
2. 語法分析（Syntax Analysis）：
   ??語法分析是將詞法分析得到的詞法單元序列轉(zhuǎn)換為抽象語法樹（Abstract Syntax Tree，簡(jiǎn)稱 AST）的過程。在這個(gè)階段，語法分析器（通常由 Yacc 或 Bison 工具生成）會(huì)根據(jù)預(yù)定義的語法規(guī)則對(duì)詞法單元進(jìn)行組合，并生成一棵表示 SQL 查詢結(jié)構(gòu)的語法樹。

??在 Postgres 中，語法分析器將通過遞歸下降或其他解析算法，根據(jù) SQL 查詢語句的語法規(guī)則構(gòu)建語法樹。語法樹的節(jié)點(diǎn)表示查詢語句的不同部分，例如 SELECT 子句、FROM 子句、WHERE 子句等。每個(gè)節(jié)點(diǎn)都包含了查詢的結(jié)構(gòu)和語義信息。


??詞法和語法分析的入口函數(shù)是raw_parser，該函數(shù)返回的List結(jié)構(gòu)用于存儲(chǔ)生成的分析樹。

以SELECT語句為例講解 PostgreSQL中查詢語句如何被解析并生成分析樹。

SelectStmt: select_no_parens			%prec UMINUS
			| select_with_parens		%prec UMINUS
		;

select_with_parens:
			'(' select_no_parens ')'				{ $$ = $2; }
			| '(' select_with_parens ')'			{ $$ = $2; }
		;

對(duì)如上代碼的詳細(xì)解釋：

1. SelectStmt 是一個(gè)非終結(jié)符，代表 SELECT 查詢語句的規(guī)則。
2. select_no_parens 和 select_with_parens 也是非終結(jié)符，分別代表不帶括號(hào)和帶括號(hào)的 SELECT 查詢語句的規(guī)則。
3. %prec UMINUS 是一個(gè)優(yōu)先級(jí)聲明，它表示在解析 SELECT 查詢語句時(shí)，應(yīng)該優(yōu)先考慮 -（負(fù)號(hào)）運(yùn)算符。這是為了處理負(fù)號(hào)運(yùn)算符在 SELECT 查詢語句中的正確優(yōu)先級(jí)。
4. ‘|’ 是一個(gè)選擇符，它表示在解析 SELECT 查詢語句時(shí)可以選擇使用 select_no_parens 或 select_with_parens 中的任意一個(gè)規(guī)則。
5. 在 select_with_parens 規(guī)則中，我們定義了兩個(gè)產(chǎn)生式，分別處理帶括號(hào)的 SELECT 查詢語句：
   （1）‘(’ select_no_parens ‘)’ { $$ = $2; }：這個(gè)產(chǎn)生式表示帶括號(hào)的 SELECT 查詢語句中，括號(hào)內(nèi)的查詢語句由 select_no_parens 規(guī)則來處理。$$ 表示當(dāng)前規(guī)則的結(jié)果，$2 表示括號(hào)內(nèi)的查詢語句的結(jié)果。這里的意思是去掉外層的括號(hào)，直接將括號(hào)內(nèi)的查詢語句作為整個(gè) SELECT 查詢語句的結(jié)果。
   （2）‘(’ select_with_parens ‘)’ { $$ = $2; }：這個(gè)產(chǎn)生式表示帶括號(hào)的 SELECT 查詢語句中，括號(hào)內(nèi)的查詢語句由 select_with_parens 規(guī)則來處理。與前一個(gè)產(chǎn)生式類似，它也去掉外層的括號(hào)，直接將括號(hào)內(nèi)的查詢語句作為整個(gè) SELECT 查詢語句的結(jié)果。

??不帶括號(hào)的SELECT的語法定義如下：

select_no_parens:
			simple_select						{ $$ = $1; }
			| select_clause sort_clause
				{
					insertSelectOptions((SelectStmt *) $1, $2, NIL,
										NULL, NULL, NULL,
										yyscanner);
					$$ = $1;
				}
			| select_clause opt_sort_clause for_locking_clause opt_select_limit
				{
					insertSelectOptions((SelectStmt *) $1, $2, $3,
										list_nth($4, 0), list_nth($4, 1),
										NULL,
										yyscanner);
					$$ = $1;
				}
			| select_clause opt_sort_clause select_limit opt_for_locking_clause
				{
					insertSelectOptions((SelectStmt *) $1, $2, $4,
										list_nth($3, 0), list_nth($3, 1),
										NULL,
										yyscanner);
					$$ = $1;
				}
			| with_clause select_clause
				{
					insertSelectOptions((SelectStmt *) $2, NULL, NIL,
										NULL, NULL,
										$1,
										yyscanner);
					$$ = $2;
				}
			| with_clause select_clause sort_clause
				{
					insertSelectOptions((SelectStmt *) $2, $3, NIL,
										NULL, NULL,
										$1,
										yyscanner);
					$$ = $2;
				}
			| with_clause select_clause opt_sort_clause for_locking_clause opt_select_limit
				{
					insertSelectOptions((SelectStmt *) $2, $3, $4,
										list_nth($5, 0), list_nth($5, 1),
										$1,
										yyscanner);
					$$ = $2;
				}
			| with_clause select_clause opt_sort_clause select_limit opt_for_locking_clause
				{
					insertSelectOptions((SelectStmt *) $2, $3, $5,
										list_nth($4, 0), list_nth($4, 1),
										$1,
										yyscanner);
					$$ = $2;
				}
		;

select_clause:
			simple_select							{ $$ = $1; }
			| select_with_parens					{ $$ = $1; }
		;

??上述代碼是在 PostgreSQL 的語法規(guī)則中描述 SELECT 查詢語句的一部分，使用了 Bison（Yacc）的語法規(guī)則。代碼段中定義了多個(gè)產(chǎn)生式來處理不同形式的 SELECT 查詢。

1. select_no_parens 是一個(gè)非終結(jié)符，代表不帶括號(hào)的 SELECT 查詢語句的規(guī)則。
2. select_clause 也是一個(gè)非終結(jié)符，它代表簡(jiǎn)單的 SELECT 查詢或帶括號(hào)的 SELECT 查詢。
3. 在 select_no_parens 規(guī)則中，有多個(gè)產(chǎn)生式來處理不同形式的 SELECT 查詢：
   （1）simple_select：這個(gè)產(chǎn)生式表示一個(gè)簡(jiǎn)單的 SELECT 查詢，沒有排序、限制或鎖定選項(xiàng)。$$ = $1; 表示將結(jié)果設(shè)置為 simple_select 規(guī)則的結(jié)果。
   （2）select_clause sort_clause：這個(gè)產(chǎn)生式表示一個(gè)帶排序選項(xiàng)的 SELECT 查詢。insertSelectOptions 函數(shù)用于將排序選項(xiàng)插入到查詢中。$1 代表 select_clause 規(guī)則的結(jié)果，而 $2 代表 sort_clause 規(guī)則的結(jié)果。$$ = $1; 表示將結(jié)果設(shè)置為 select_clause 規(guī)則的結(jié)果。
   （3）其他產(chǎn)生式與上面類似，用于處理帶排序、限制、鎖定等選項(xiàng)的 SELECT 查詢。
4. select_clause 規(guī)則中，也有兩個(gè)產(chǎn)生式：
   simple_select 和 select_with_parens：這兩個(gè)產(chǎn)生式與 select_no_parens 規(guī)則中的對(duì)應(yīng)產(chǎn)生式相同，用于處理簡(jiǎn)單的 SELECT 查詢和帶括號(hào)的 SELECT 查詢。

??從以上代碼可以看出，一條不帶括號(hào)的SELECT語句可以定義為一條簡(jiǎn)單的SELECT語句（用標(biāo)識(shí)符simple_select表示)，也可以定義為在簡(jiǎn)單SELECT語句后接排序子句（標(biāo)識(shí)符sort_clause)，LIMIT子句（標(biāo)識(shí)符select_limit）等構(gòu)成的復(fù)雜語句?？梢钥吹?，對(duì)于整個(gè)語句的語法分析實(shí)際上是將語句拆分成很多小的語法單元，然后分別對(duì)這些小的單元進(jìn)行分析。因此，只要弄清楚各個(gè)小語法單元的做法，就可以把它們組合在一起形成整個(gè)語法樹。這里我們著重分析simple_select的語法定義。

源碼如下：

simple_select:
			SELECT opt_all_clause opt_target_list
			into_clause from_clause where_clause
			group_clause having_clause window_clause
				{
					SelectStmt *n = makeNode(SelectStmt);
					n->targetList = $3;
					n->intoClause = $4;
					n->fromClause = $5;
					n->whereClause = $6;
					n->groupClause = $7;
					n->havingClause = $8;
					n->windowClause = $9;
					$$ = (Node *)n;
				}
			| SELECT distinct_clause target_list
			into_clause from_clause where_clause
			group_clause having_clause window_clause
				{
					SelectStmt *n = makeNode(SelectStmt);
					n->distinctClause = $2;
					n->targetList = $3;
					n->intoClause = $4;
					n->fromClause = $5;
					n->whereClause = $6;
					n->groupClause = $7;
					n->havingClause = $8;
					n->windowClause = $9;
					$$ = (Node *)n;
				}
			| values_clause							{ $$ = $1; }
			| TABLE relation_expr
				{
					/* same as SELECT * FROM relation_expr */
					ColumnRef *cr = makeNode(ColumnRef);
					ResTarget *rt = makeNode(ResTarget);
					SelectStmt *n = makeNode(SelectStmt);

					cr->fields = list_make1(makeNode(A_Star));
					cr->location = -1;

					rt->name = NULL;
					rt->indirection = NIL;
					rt->val = (Node *)cr;
					rt->location = -1;

					n->targetList = list_make1(rt);
					n->fromClause = list_make1($2);
					$$ = (Node *)n;
				}
			| select_clause UNION all_or_distinct select_clause
				{
					$$ = makeSetOp(SETOP_UNION, $3, $1, $4);
				}
			| select_clause INTERSECT all_or_distinct select_clause
				{
					$$ = makeSetOp(SETOP_INTERSECT, $3, $1, $4);
				}
			| select_clause EXCEPT all_or_distinct select_clause
				{
					$$ = makeSetOp(SETOP_EXCEPT, $3, $1, $4);
				}
		;

源碼分析：

1.第一個(gè)產(chǎn)生式

SELECT opt_all_clause opt_target_list
into_clause from_clause where_clause
group_clause having_clause window_clause
{
    SelectStmt *n = makeNode(SelectStmt);
    n->targetList = $3;
    n->intoClause = $4;
    n->fromClause = $5;
    n->whereClause = $6;
    n->groupClause = $7;
    n->havingClause = $8;
    n->windowClause = $9;
    $$ = (Node *)n;
}

??這個(gè)產(chǎn)生式表示處理普通的 SELECT 查詢，其中包含了多個(gè)可選子句，如 DISTINCT、INTO、WHERE、GROUP BY、HAVING、WINDOW。當(dāng)解析到這種形式的 SELECT 查詢時(shí)，使用產(chǎn)生式的動(dòng)作部分將解析到的各個(gè)子句信息填入 SelectStmt 結(jié)構(gòu)體中，并將結(jié)果設(shè)置為該結(jié)構(gòu)體的指針。

2.第二個(gè)產(chǎn)生式

SELECT distinct_clause target_list
into_clause from_clause where_clause
group_clause having_clause window_clause
{
    SelectStmt *n = makeNode(SelectStmt);
    n->distinctClause = $2;
    n->targetList = $3;
    n->intoClause = $4;
    n->fromClause = $5;
    n->whereClause = $6;
    n->groupClause = $7;
    n->havingClause = $8;
    n->windowClause = $9;
    $$ = (Node *)n;
}

??這個(gè)產(chǎn)生式表示處理帶 DISTINCT 子句的 SELECT 查詢。與前一個(gè)產(chǎn)生式類似，將解析到的子句信息填入 SelectStmt 結(jié)構(gòu)體中，并將結(jié)果設(shè)置為該結(jié)構(gòu)體的指針。

3.第三個(gè)產(chǎn)生式

values_clause
{
    $$ = $1;
}

??這個(gè)產(chǎn)生式表示處理 VALUES 子句，用于創(chuàng)建一個(gè)虛擬表以供查詢。

4.第三個(gè)產(chǎn)生式

TABLE relation_expr
{
    /* same as SELECT * FROM relation_expr */
    ColumnRef *cr = makeNode(ColumnRef);
    ResTarget *rt = makeNode(ResTarget);
    SelectStmt *n = makeNode(SelectStmt);

    cr->fields = list_make1(makeNode(A_Star));
    cr->location = -1;

    rt->name = NULL;
    rt->indirection = NIL;
    rt->val = (Node *)cr;
    rt->location = -1;

    n->targetList = list_make1(rt);
    n->fromClause = list_make1($2);
    $$ = (Node *)n;
}

??這個(gè)產(chǎn)生式表示處理形如 TABLE name 的查詢，其效果相當(dāng)于 SELECT * FROM name，即選擇表 name 的所有列。

5.后續(xù)三個(gè)產(chǎn)生式

select_clause UNION all_or_distinct select_clause
{
    $$ = makeSetOp(SETOP_UNION, $3, $1, $4);
}
select_clause INTERSECT all_or_distinct select_clause
{
    $$ = makeSetOp(SETOP_INTERSECT, $3, $1, $4);
}
select_clause EXCEPT all_or_distinct select_clause
{
    $$ = makeSetOp(SETOP_EXCEPT, $3, $1, $4);
}

??這三個(gè)產(chǎn)生式分別表示處理 UNION、INTERSECT 和 EXCEPT 三種集合操作，將兩個(gè) SELECT 查詢進(jìn)行合并。
總結(jié)：
??以上代碼中的產(chǎn)生式定義了不同形式的 SELECT 查詢，并通過動(dòng)作部分將解析到的子句信息填入 SelectStmt 結(jié)構(gòu)體中，用于構(gòu)建查詢語句的抽象語法樹。這些語法規(guī)則將用于在 PostgreSQL 中解析 SELECT 查詢語句，并生成對(duì)應(yīng)的抽象語法樹，表示查詢的結(jié)構(gòu)。

??SelectStmt結(jié)構(gòu)體如下所示：（路徑：src/include/nodes/parsenodes.h）

typedef struct SelectStmt
{
	NodeTag		type;

	/*
	 * These fields are used only in "leaf" SelectStmts.
	 */
	List	   *distinctClause; /* NULL, list of DISTINCT ON exprs, or
								 * lcons(NIL,NIL) for all (SELECT DISTINCT) */
	IntoClause *intoClause;		/* target for SELECT INTO */
	List	   *targetList;		/* the target list (of ResTarget) */
	List	   *fromClause;		/* the FROM clause */
	Node	   *whereClause;	/* WHERE qualification */
	List	   *groupClause;	/* GROUP BY clauses */
	Node	   *havingClause;	/* HAVING conditional-expression */
	List	   *windowClause;	/* WINDOW window_name AS (...), ... */

	/*
	 * In a "leaf" node representing a VALUES list, the above fields are all
	 * null, and instead this field is set.  Note that the elements of the
	 * sublists are just expressions, without ResTarget decoration. Also note
	 * that a list element can be DEFAULT (represented as a SetToDefault
	 * node), regardless of the context of the VALUES list. It's up to parse
	 * analysis to reject that where not valid.
	 */
	List	   *valuesLists;	/* untransformed list of expression lists */

	/*
	 * These fields are used in both "leaf" SelectStmts and upper-level
	 * SelectStmts.
	 */
	List	   *sortClause;		/* sort clause (a list of SortBy's) */
	Node	   *limitOffset;	/* # of result tuples to skip */
	Node	   *limitCount;		/* # of result tuples to return */
	List	   *lockingClause;	/* FOR UPDATE (list of LockingClause's) */
	WithClause *withClause;		/* WITH clause */

	/*
	 * These fields are used only in upper-level SelectStmts.
	 */
	SetOperation op;			/* type of set op */
	bool		all;			/* ALL specified? */
	struct SelectStmt *larg;	/* left child */
	struct SelectStmt *rarg;	/* right child */
	/* Eventually add fields for CORRESPONDING spec here */
} SelectStmt;

中文版本如下：

typedef struct SelectStmt
{
	NodeTag		type;  // 結(jié)點(diǎn)類型標(biāo)記

	/*
	 * 這些字段僅在“葉子”SelectStmt中使用。
	 */
	List	   *distinctClause; // DISTINCT子句，可以是NULL，表示沒有DISTINCT，或者是DISTINCT ON表達(dá)式的列表，或者是lcons(NIL, NIL)表示所有的(SELECT DISTINCT)
	IntoClause *intoClause; // SELECT INTO的目標(biāo)
	List	   *targetList; // 目標(biāo)列表，即SELECT后面的表達(dá)式列表（ResTarget）
	List	   *fromClause; // FROM子句，表示查詢的數(shù)據(jù)來源
	Node	   *whereClause; // WHERE條件，用于過濾查詢結(jié)果
	List	   *groupClause; // GROUP BY子句，表示按照哪些列進(jìn)行分組
	Node	   *havingClause; // HAVING條件表達(dá)式，用于過濾分組后的結(jié)果
	List	   *windowClause; // WINDOW子句，表示定義的窗口函數(shù)

	/*
	 * 在表示VALUES列表的"葉子"節(jié)點(diǎn)中，上面的字段都為空，取而代之的是設(shè)置了這個(gè)字段。
	 * 注意，子列表的元素只是表達(dá)式，沒有ResTarget裝飾。
	 * 還要注意，列表元素可以是DEFAULT（表示為SetToDefault節(jié)點(diǎn)），而不管VALUES列表的上下文是什么。解析分析時(shí)將在不合法的情況下拒絕。
	 */
	List	   *valuesLists; // 未轉(zhuǎn)換的表達(dá)式列表的列表

	/*
	 * 這些字段在“葉子”SelectStmt和上層SelectStmt中都使用。
	 */
	List	   *sortClause; // 排序子句（SortBy列表）
	Node	   *limitOffset; // 跳過的結(jié)果元組數(shù)目
	Node	   *limitCount; // 返回的結(jié)果元組數(shù)目
	List	   *lockingClause; // FOR UPDATE子句（LockingClause列表）
	WithClause *withClause; // WITH子句

	/*
	 * 這些字段僅在上層SelectStmt中使用。
	 */
	SetOperation op; // 集合操作的類型
	bool		all; // 是否指定了ALL
	struct SelectStmt *larg; // 左子樹
	struct SelectStmt *rarg; // 右子樹
	/* 最終在這里添加CORRESPONDING spec的字段 */
} SelectStmt;

舉例：

假設(shè)我們有以下簡(jiǎn)單的 SELECT 查詢語句：
SELECT column1, column2 FROM table_name WHERE column3 = 10;

查詢語句的解析過程如下：
3. 詞法分析（Lexical Analysis）：
??詞法分析器將查詢字符串分解為一系列詞法單元（tokens）。在這個(gè)例子中，可能的詞法單元包括：

SELECT   (關(guān)鍵字)
column1  (標(biāo)識(shí)符)
,        (逗號(hào))
column2  (標(biāo)識(shí)符)
FROM     (關(guān)鍵字)
table_name (標(biāo)識(shí)符)
WHERE    (關(guān)鍵字)
column3  (標(biāo)識(shí)符)
=        (等號(hào))
10       (常量)
;        (分號(hào))

4. 語法分析（Syntax Analysis）：
   ??語法分析器根據(jù)預(yù)定義的語法規(guī)則將詞法單元序列轉(zhuǎn)換為抽象語法樹（AST）。在這個(gè)例子中，語法樹的節(jié)點(diǎn)表示查詢的不同部分：

       SELECT
        /   \
column1     column2
        \   /
        FROM
          |
     table_name
          |
        WHERE
        /   \
    column3  =
          |
          10

??在上述語法樹中，每個(gè)節(jié)點(diǎn)代表查詢語句的一部分。例如，根節(jié)點(diǎn)是 SELECT 關(guān)鍵字，它有兩個(gè)子節(jié)點(diǎn)分別代表 column1 和 column2。FROM 子句也是根節(jié)點(diǎn)的子節(jié)點(diǎn)，它有一個(gè)子節(jié)點(diǎn)代表表名 table_name。WHERE 子句是 FROM 子句的子節(jié)點(diǎn)，它有兩個(gè)子節(jié)點(diǎn)分別代表 column3 和等號(hào)操作符，以及一個(gè)子節(jié)點(diǎn)代表常量 10。

5. 分析樹（Parse Tree）生成：
   ??在語法分析過程中，語法分析器構(gòu)建了抽象語法樹。該語法樹稱為分析樹（Parse Tree），它是表示查詢語句結(jié)構(gòu)的一種層次結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)都表示查詢語句的一個(gè)組成部分，并且具有與之相關(guān)的語義信息。分析樹將用于后續(xù)的查詢優(yōu)化和執(zhí)行。
   ??值得注意的是，語法分析器在生成分析樹時(shí)可能會(huì)對(duì)輸入進(jìn)行驗(yàn)證，例如檢查語法錯(cuò)誤和語義錯(cuò)誤。如果存在錯(cuò)誤，語法分析器將報(bào)告錯(cuò)誤并終止解析過程。

語義分析

??語義分析（Semantic Analysis）是編譯器或解釋器中的一個(gè)重要階段，用于對(duì)源代碼進(jìn)行深層次的語義檢查和解釋。它的主要作用是確保程序在語義上是合法的，并進(jìn)行語義轉(zhuǎn)換和語義解釋，以便進(jìn)行后續(xù)的優(yōu)化和執(zhí)行。
??語義分析的目的是檢查程序的語義正確性，即確定程序是否符合編程語言的語義規(guī)則和約束。它涉及對(duì)語句、表達(dá)式、類型、作用域、符號(hào)引用等進(jìn)行分析和驗(yàn)證。具體來說，語義分析會(huì)執(zhí)行以下任務(wù)：

1. 類型檢查：驗(yàn)證表達(dá)式和操作符之間的類型兼容性，確保不會(huì)出現(xiàn)類型錯(cuò)誤，例如將字符串與數(shù)字相加。
2. 符號(hào)表管理：建立符號(hào)表并管理標(biāo)識(shí)符的聲明和引用。檢查變量、函數(shù)、類等標(biāo)識(shí)符的作用域、可見性和重復(fù)定義等問題。
3. 語義約束檢查：檢查語法規(guī)則以外的語義約束，例如數(shù)組索引必須是整數(shù)、函數(shù)調(diào)用的參數(shù)數(shù)量與聲明的參數(shù)數(shù)量匹配等。
4. 類型推導(dǎo)：在一些語言中，根據(jù)上下文推導(dǎo)出表達(dá)式的類型，以減少顯式類型注釋的需求。
5. 常量折疊：對(duì)于常量表達(dá)式，進(jìn)行計(jì)算和簡(jiǎn)化，以便在編譯時(shí)進(jìn)行優(yōu)化。
   ??通過進(jìn)行語義分析，編譯器或解釋器能夠檢測(cè)和報(bào)告源代碼中的潛在錯(cuò)誤，并確保程序在語義上是一致和合法的。它為后續(xù)的代碼優(yōu)化、代碼生成和程序執(zhí)行提供了準(zhǔn)確的基礎(chǔ)。

??exec_simple_query 在從詞法和語法分析模塊獲取了parsetree_list之后，會(huì)對(duì)其中每一棵分析樹調(diào)用pg_analyze_and_rewrite進(jìn)行語義分析和查詢重寫，而在其中負(fù)責(zé)語義分析的則是analyze. c文件中的parse_analyze 函數(shù)。parse_analyze 會(huì)根據(jù)分析樹生成一個(gè)對(duì)應(yīng)的查詢樹，而查詢重寫模塊則繼續(xù)對(duì)這一查詢樹進(jìn)行修改，并且有可能會(huì)將這個(gè)查詢樹改寫成一個(gè)包含多棵查詢樹的鏈表。因此，pg_analyze_and_rewrite最終返回給exec_simple_query的將是一個(gè)查詢樹鏈表。
??parse_analyze的源碼如下：

/*
 * parse_analyze
 *		Analyze a raw parse tree and transform it to Query form.
 *	    對(duì)原始解析樹進(jìn)行分析并轉(zhuǎn)換為查詢表單。
 *
 * Optionally, information about $n parameter types can be supplied.
 * References to $n indexes not defined by paramTypes[] are disallowed.
 *
 * The result is a Query node.  Optimizable statements require considerable
 * transformation, while utility-type statements are simply hung off
 * a dummy CMD_UTILITY Query node.
 * 結(jié)果是一個(gè) Query 節(jié)點(diǎn)。
 * 可優(yōu)化的語句需要進(jìn)行相當(dāng)大的轉(zhuǎn)換，
 * 而實(shí)用程序類型的語句只需掛在一個(gè)虛擬的 CMD_UTILITY Query 節(jié)點(diǎn)上。
 */
Query *
parse_analyze(RawStmt *parseTree, const char *sourceText,
			  Oid *paramTypes, int numParams,
			  QueryEnvironment *queryEnv)
{
	/* 創(chuàng)建一個(gè)解析狀態(tài)結(jié)構(gòu)體 */
	ParseState *pstate = make_parsestate(NULL);
	Query	   *query;

	/* 檢查源文本是否為空（從8.4版本開始是必需的） */
	Assert(sourceText != NULL);

	/* 將源文本保存到解析狀態(tài)結(jié)構(gòu)體中 */
	pstate->p_sourcetext = sourceText;

	/* 如果提供了參數(shù)類型信息，則將參數(shù)設(shè)置為解析狀態(tài)結(jié)構(gòu)體中 */
	if (numParams > 0)
		parse_fixed_parameters(pstate, paramTypes, numParams);

	/* 設(shè)置查詢環(huán)境 */
	pstate->p_queryEnv = queryEnv;

	/* 轉(zhuǎn)換原始解析樹為查詢樹 */
	query = transformTopLevelStmt(pstate, parseTree);

	/* 如果有后解析分析鉤子函數(shù)，則在此調(diào)用 */
	if (post_parse_analyze_hook)
		(*post_parse_analyze_hook) (pstate, query);

	/* 釋放解析狀態(tài)結(jié)構(gòu)體的內(nèi)存 */
	free_parsestate(pstate);

	/* 返回轉(zhuǎn)換后的查詢樹 */
	return query;
}

??在parse_analyze函數(shù)中，將根據(jù)命令類型分七種情況處理（參考函數(shù)transformStmt)，如圖5-15所示。經(jīng)過語義分析之后，會(huì)生成查詢樹（Query 結(jié)構(gòu)，見數(shù)據(jù)結(jié)構(gòu)5.6)。其中SELECT/INSERDELETE/UPDATE這四種情況所生成的查詢樹會(huì)經(jīng)由查詢重寫和查詢優(yōu)化作進(jìn)一步處理。

??該過程涉及兩個(gè)重要的結(jié)構(gòu)體:Query 和 ParseState。Query (用于存儲(chǔ)查詢樹）是查詢分析的最終輸出結(jié)果，其中許多字段可以在分析樹的相關(guān)結(jié)構(gòu)體中找到對(duì)應(yīng)項(xiàng)，其詳細(xì)介紹參考先前的代碼結(jié)構(gòu)。ParseState結(jié)構(gòu)則用于記錄語義分析的中間信息。

ParseState源碼如下：

struct ParseState
{
	struct ParseState *parentParseState;	/* stack link */
	const char *p_sourcetext;	/* source text, or NULL if not available */
	List	   *p_rtable;		/* range table so far */
	List	   *p_joinexprs;	/* JoinExprs for RTE_JOIN p_rtable entries */
	List	   *p_joinlist;		/* join items so far (will become FromExpr
								 * node's fromlist) */
	List	   *p_namespace;	/* currently-referenceable RTEs (List of
								 * ParseNamespaceItem) */
	bool		p_lateral_active;	/* p_lateral_only items visible? */
	List	   *p_ctenamespace; /* current namespace for common table exprs */
	List	   *p_future_ctes;	/* common table exprs not yet in namespace */
	CommonTableExpr *p_parent_cte;	/* this query's containing CTE */
	Relation	p_target_relation;	/* INSERT/UPDATE/DELETE target rel */
	RangeTblEntry *p_target_rangetblentry;	/* target rel's RTE */
	bool		p_is_insert;	/* process assignment like INSERT not UPDATE */
	List	   *p_windowdefs;	/* raw representations of window clauses */
	ParseExprKind p_expr_kind;	/* what kind of expression we're parsing */
	int			p_next_resno;	/* next targetlist resno to assign */
	List	   *p_multiassign_exprs;	/* junk tlist entries for multiassign */
	List	   *p_locking_clause;	/* raw FOR UPDATE/FOR SHARE info */
	bool		p_locked_from_parent;	/* parent has marked this subquery
										 * with FOR UPDATE/FOR SHARE */
	bool		p_resolve_unknowns; /* resolve unknown-type SELECT outputs as
									 * type text */

	QueryEnvironment *p_queryEnv;	/* curr env, incl refs to enclosing env */

	/* Flags telling about things found in the query: */
	bool		p_hasAggs;
	bool		p_hasWindowFuncs;
	bool		p_hasTargetSRFs;
	bool		p_hasSubLinks;
	bool		p_hasModifyingCTE;

	Node	   *p_last_srf;		/* most recent set-returning func/op found */

	/*
	 * Optional hook functions for parser callbacks.  These are null unless
	 * set up by the caller of make_parsestate.
	 */
	PreParseColumnRefHook p_pre_columnref_hook;
	PostParseColumnRefHook p_post_columnref_hook;
	ParseParamRefHook p_paramref_hook;
	CoerceParamHook p_coerce_param_hook;
	void	   *p_ref_hook_state;	/* common passthrough link for above */
};

??函數(shù)parse_analyze首先將生成一個(gè)ParseState結(jié)構(gòu)用于記錄語義分析的狀態(tài)，然后通過調(diào)用函數(shù)transformStmt 來完成語義分析過程。函數(shù)transformStmt 會(huì)根據(jù)不同的查詢類型調(diào)用相應(yīng)的函數(shù)進(jìn)行處理。從詞法和語法分析中介紹的數(shù)據(jù)結(jié)構(gòu)可以看到，PostgreSQL 中幾乎每一個(gè)數(shù)據(jù)結(jié)構(gòu)的第一個(gè)字段都是NodeTag類型的 type。在 PostgreSQL為了傳遞參數(shù)方便，把很多數(shù)據(jù)節(jié)點(diǎn)的指針都通過指針類型轉(zhuǎn)換成Node結(jié)構(gòu)的指針，Node結(jié)構(gòu)中只有一個(gè)類型為NodeTag名為type的字段，通過這樣一種方式PostgreSQL把大多數(shù)要傳遞的數(shù)據(jù)結(jié)構(gòu)都包裝成了稱為“Node”(節(jié)點(diǎn)〉的統(tǒng)一形式,從而通過一套統(tǒng)一的操作函數(shù)進(jìn)行處理。為了能夠確定接收到的數(shù)據(jù)結(jié)構(gòu)到底是哪一種，Post-greSQL中把 NodeTag設(shè)計(jì)成了一個(gè)枚舉類型，每一種數(shù)據(jù)結(jié)構(gòu)都在其中對(duì)應(yīng)–個(gè)值，這些值的名稱都由“T_”及其數(shù)據(jù)類型名稱組成，例如SelectStmt數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)的NodeTag值就是“T_SelectStmt”。
??transformStmt函數(shù)只有兩個(gè)參數(shù)，一個(gè)是ParseState，另一個(gè)就是要處理的包裝成節(jié)點(diǎn)的分析樹。通過節(jié)點(diǎn)type字段，transformStmt可以處理七種分析樹，相應(yīng)的處理函數(shù)見表5-9。
文章來源地址http://www.zghlxwxcb.cn/news/detail-580479.html

到了這里，關(guān)于【PostgreSQL內(nèi)核學(xué)習(xí)（二）—— 查詢分析】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！