解析器必须检查查询串（以普通 ASCII 文本形式到达）的语法是否有效。如果语法正确，就构建一棵解析树并返回；否则返回错误。实现时使用了著名的 Unix 工具 lex 和 yacc。

词法分析器定义在文件 scan.l 中，负责识别 标识符、SQL 关键字 等。每找到一个关键字或标识符，就会生成一个 词元 并交给解析器。

解析器定义在文件 gram.y 中，由一组 语法规则 和 动作 组成，每当某条规则被触发时，对应动作就会执行。动作中的代码（实际上是 C 代码）用于构造解析树。

文件 scan.l 会被转换成 C 源文件 scan.c，所用程序是 lex；而 gram.y 则会被转换成 gram.c，所用程序是 yacc。这些转换完成之后，就可以使用普通的 C 编译器来构建解析器。绝不要修改这些生成出来的 C 文件，因为下一次调用 lex 或 yacc 时，它们都会被覆盖。

对 yacc 的详细描述，或者对 gram.y 中给出的语法规则的说明，都超出了本文的范围。有许多书籍和文档专门讨论 lex 和 yacc。在开始研究之前，你应该先熟悉 yacc，然后再去看 gram.y 中给出的语法，否则你将无法理解其中发生了什么。

为了更好地理解 PostgreSQL 在处理查询时所使用的数据结构，我们用一个例子来说明这些数据结构在每个阶段所发生的变化。这个例子包含下面这个简单的查询，它将被用于后续各节的各种描述和图示中。该查询假设 The Supplier Database（供应商数据库）中给出的各个表已经定义好。

select s.sname, se.pno
    from supplier s, sells se
    where s.sno > 2 and s.sno = se.sno;
      

图 \ref{parsetree} 展示了 gram.y 中的语法规则和动作为 例 2.1 中给出的查询所构建的 解析树（其中不含 where 子句的操作符树，后者见图 \ref{where_clause}，因为一张图放不下两个数据结构）。

树的顶层节点是一个 SelectStmt 节点。对于 SQL 查询 from 子句中出现的每一个表项，都会创建一个 RangeVar 节点，其中保存着 别名的名称，以及一个指向 RelExpr 节点的指针，后者保存着 关系的名称。所有 RangeVar 节点都被收集到一个列表中，挂接在 SelectStmt 节点的 fromClause 字段上。

对于 SQL 查询 选择列表中出现的每一个表项，都会创建一个 ResTarget 节点，其中保存着一个指向 Attr 节点的指针。Attr 节点保存着该表项的关系名，以及一个指向 Value 节点的指针，后者保存着属性的名称。所有 ResTarget 节点都被收集到一个列表中，连接到 SelectStmt 节点的 targetList 字段上。

图 \ref{where_clause} 展示了为 例 2.1 中给出的 SQL 查询的 where 子句构建的操作符树，它挂接在 SelectStmt 节点的 qual 字段上。操作符树的顶层节点是一个表示 AND 运算的 A_Expr 节点。该节点有两个分别称为 lexpr 和 rexpr 的后继，分别指向两棵子树。挂接在 lexpr 上的子树表示限定条件 s.sno > 2，挂接在 rexpr 上的子树表示 s.sno = se.sno。对于每个属性，都会创建一个 Attr 节点，其中保存着关系的名称以及一个指向 Value 节点的指针，后者保存着属性的名称。对于查询中出现的常量项，则创建一个保存该值的 Const 节点。

转换过程以解析器返回的树作为输入，并递归地遍历它。如果找到一个 SelectStmt 节点，就把它转换为一个 Query 节点，后者将成为新数据结构的最顶层节点。图 \ref{transformed} 展示了转换后的数据结构（转换后的 where 子句部分见图 \ref{transformed_where}，因为一张图放不下所有部分）。

接下来检查 FROM 子句中的关系名是否为系统所知。对于每一个出现在系统目录中的关系名，都会创建一个 RTE 节点，其中包含关系名、别名和关系 id。从这时起，就用关系 id 来引用查询中给出的各个关系。所有 RTE 节点都被收集到范围表项列表中，该列表连接到 Query 节点的 rtable 字段上。如果在查询中检测到一个系统未知的关系名，将返回错误并且查询处理将被中止。

再接下来检查所用的属性名是否包含在查询给出的各个关系之中。对于找到的每一个属性，都会创建一个 TLE 节点，其中保存着一个指向 Resdom 节点（保存着列的名称）的指针和一个指向 VAR 节点的指针。VAR 节点中有两个重要的编号：varno 字段给出包含当前属性的关系在上述范围表项列表中的位置；varattno 字段给出该属性在关系内部的位置。如果找不到某个属性的名称，将返回错误并且查询处理将被中止。