#gStore-weekly | SPARQL 解析（下）

SPARQL 解析（下）

1.1 上期回顾

在 SPARQL 解析（上）中，我们详细分析了 QueryTree 类的结构和 QueryParser 类中的驱动函数 QueryParser::SPARQLParse 。在本篇中，我们将以一个简单的 SPARQL 查询为例，介绍 QueryParser 类在遍历语法解析树的过程中调用的关键函数。

1.2 示例 SPARQL 查询

以下的 SPARQL 查询将会返回所有名字为张三的人物：

SELECT ?person WHERE { ?person  "张三" . }
1

1.3 入口函数：QueryParser::visitQuery

上期中我们提到 QueryParser::SPARQLParse 为 SPARQL 解析的驱动函数，其中调用了 SPARQLBaseVisitor::visitEntry 函数（SPARQLBaseVisitor 为 QueryParser 的父类），而 SPARQLBaseVisitor::visitEntry 函数中调用的即是 QueryParser::visitQuery 函数，因此它是 SPARQL 解析的入口。

函数原型：

antlrcpp::Any visitQuery(SPARQLParser::QueryContext *ctx);
1

注意所有名称以 visit 开头的函数均用于访问语法解析树中相应的结点。如 visitQuery 访问的即是 query 结点，对应的语法生成式为 query : prologue( selectquery | constructquery | describequery | askquery ) 。（SPARQL 的完整语法在 Parser/SPARQL/SPARQL.g4 中给出。）

在 SPARQLBaseVisitor 类中，visit 函数均被定义为虚函数，默认实现为访问该结点的所有孩子结点（调用孩子结点对应的 visit 函数）。如 Parser/SPARQL/SPARQLBaseVisitor.h 中 visitEntry 函数的定义为：

virtual antlrcpp::Any visitEntry(SPARQLParser::EntryContext *ctx) override {
  return visitChildren(ctx);
}
1
2
3

在 QueryParser 类中重载的 visit 函数将会覆盖 SPARQLBaseVisitor 类中的默认实现。QueryParser::visitQuery 函数即是这样一个重载的例子。

由于 gStore 目前支持的查询类型为 SELECT 和 ASK（暂不支持 CONSTRUCT 和 DESCRIBE 查询），在遇到这两类查询时，在成员变量 query_tree_ptr 所指向的 QueryTree 类对象中相应地设置查询类型，并进一步访问对应类型的孩子结点。关键代码如下：

if (ctx->selectquery())
{
  query_tree_ptr->setQueryForm(QueryTree::Select_Query);
  visit(ctx->selectquery());
}
...
if (ctx->askquery())
{
  query_tree_ptr->setQueryForm(QueryTree::Ask_Query);
  visit(ctx->askquery());
}
1
2
3
4
5
6
7
8
9
10
11

由于上述示例查询为 SELECT 查询，实际执行的是第一个 if 分支；visit 将会调用相应的名称以 visit 开头的函数，如 visit(ctx->selectquery()) 将会调用 QueryParser::visitSelectquery 函数，visit(ctx->askquery()) 将会调用 QueryParser::visitAskquery 函数。

以 QueryParser::visitQuery 为入口，上述示例查询在 QueryParser 类中的函数调用树如下图所示（仅包含 visit 函数）：

接下来，我们将会重点介绍其中执行最主要功能的 QueryParser::visitSelectClause 和 QueryParser::visitTripleSameSubjectpath 函数。

1.4 QueryParser::visitSelectClause

QueryParser::visitSelectClause 用于解析 SELECT 查询头，即 SELECT 查询中说明要求返回哪些变量、聚合函数或其他内建函数的部分，对应的语法生成式为 selectClause : K_SELECT ( K_DISTINCT | K_REDUCED )? ( ( var | expressionAsVar )+ | ‘*’ ) 。如上述示例查询中查询头即为 SELECT ?person 。

函数原型：

antlrcpp::Any QueryParser::visitSelectClause(SPARQLParser::SelectClauseContext *ctx;
1

关键代码段说明如下。

首先通过判断当前结点的第 1 个孩子结点是否叶子结点（生成式中全大写的或以字符串表示的为词法单元，即为语法解析树中的叶子结点），判断是否存在 DISTINCT 或 REDUCED 关键词，或需返回所有变量结果（*）；并相应地设置 query_tree_ptr 所指向 QueryTree 类对象的属性。（由于 gStore 暂不支持 REDUCED 关键词，遇到时将抛出异常。）上述示例查询不会进入此分支。

if (ctx->children[1]->children.size() == 0)
{
  string tmp = ctx->children[1]->getText();
  transform(tmp.begin(), tmp.end(), tmp.begin(), ::toupper);
  if (tmp == "DISTINCT")
    query_tree_ptr->setProjectionModifier(QueryTree::Modifier_Distinct);
  else if (tmp == "REDUCED")
    throw runtime_error("[ERROR]	REDUCED is currently not supported.");
  else if (tmp == "*")
    query_tree_ptr->setProjectionAsterisk();
}
1
2
3
4
5
6
7
8
9
10
11

由于还可能出现形如 SELECT DISTINCT * 的查询头，额外添加以下分支处理（上述示例查询不会进入此分支）：

if (ctx->children.size() == 3 && ctx->children[2]->children.size() == 0)	// '*'
		query_tree_ptr->setProjectionAsterisk();
1
2

除此之外，即为 SELECT 变量、聚合函数或其他内建函数，用以下分支处理：

else
{
  // Order of selected elements does not matter
  for (auto var : ctx->var())
  {
    query_tree_ptr->addProjectionVar();
    ProjectionVar &proj_var = query_tree_ptr->getLastProjectionVar();
    proj_var.aggregate_type = ProjectionVar::None_type;
    proj_var.var = var->getText();
  }
  for (auto expressionAsVar : ctx->expressionAsVar())
    parseSelectAggregateFunction(expressionAsVar->expression(), \
      expressionAsVar->var());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

其中第一个 for 循环处理变量，第二个 for 循环处理聚合函数或其他内建函数。对于上述示例查询，ctx->var() 中仅有一个元素，对应变量 ?person ；它在第一个 for 循环中被设置为投影变量。

1.5 QueryParser::visitTripleSameSubjectpath

QueryParser::visitTripleSameSubjectpath 用于解析查询主体（即 SELECT 查询中以大括号括起的部分，表示需要匹配的图模式）中的一条三元组或主语相同、谓词-宾语列表对以分号分隔（其中谓词相同的宾语之间以逗号分隔）的多条三元组，对应的语法生成式为 triplesSameSubjectpath : varOrTerm propertyListpathNotEmpty | triplesNodepath propertyListpath。

函数原型：

antlrcpp::Any QueryParser::visitTriplesSameSubjectpath(SPARQLParser::TriplesSameSubjectpathContext *ctx, GroupPattern &group_pattern);
1

关键代码段说明如下。

首先获取主语，并调用 QueryParser::replacePrefix 函数将其中可能存在的前缀转换为 IRI 形式：

subject = ctx->varOrTerm()->getText();
replacePrefix(subject);
1
2

对于上述示例查询，变量 subject 将会被设置为字符串 “?person” ，QueryParser::replacePrefix 函数不会对其作改动（由于没有前缀）。

接下来的 for 循环对每个谓词-宾语对作处理：（其中 verbpathOrSimple 即为当前谓词-宾语对的指针）

int numChild = propertyListpathNotEmpty->verbpathOrSimple().size();
for (int i = 0; i < numChild; i++)
{
  ...
  auto verbpathOrSimple = propertyListpathNotEmpty->verbpathOrSimple(i);
  ...
}
1
2
3
4
5
6
7

其中，首先处理谓词：

if (verbpathOrSimple->verbpath())
{
  ...
}
else
  predicate = verbpathOrSimple->getText();
if (predicate == "a")
  predicate = "";
replacePrefix(predicate);
1
2
3
4
5
6
7
8
9

第一个 if 分支用于处理谓词为属性路径的情形（目前 gStore 仅支持单个 IRI 的 Kleene 闭包）；若为普通谓词，则进入 else 分支，直接获取谓词的字符串表示放入 predicate 变量。如对于上述示例查询，即进入 else 分支，predicate 设置为 。当谓词为 a 时，做特殊替换处理；并调用 QueryParser::replacePrefix 函数将其中可能存在的前缀转换为 IRI 形式（示例查询中 predicate 值不会被改动）。

然后处理宾语（ i 是否为 0 仅影响获取 objectpath 指针的方式，以下以 i 为 0 为例介绍）：

for (auto objectpath : propertyListpathNotEmpty->objectListpath()->objectpath())
{
  if (objectpath->graphNodepath()->varOrTerm() \
    && objectpath->graphNodepath()->varOrTerm()->graphTerm() \
    && objectpath->graphNodepath()->varOrTerm()->graphTerm()->numericLiteral())
    object = getNumeric(objectpath->graphNodepath()->varOrTerm()->graphTerm()->numericLiteral());
  else if (objectpath->graphNodepath()->varOrTerm() \
    && objectpath->graphNodepath()->varOrTerm()->graphTerm() \
    && objectpath->graphNodepath()->varOrTerm()->graphTerm()->booleanLiteral())
    object = "\"" + (objectpath->getText()) + "\"" + "^^";
  else
    object = getTextWithRange(objectpath);
  replacePrefix(object);
  addTriple(subject, predicate, object, kleene, group_pattern);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

其中 if - else if - else 分支分别处理内建数值类型、内建布尔类型和其他类型的宾语，若是前两种类型，需要添加相应的后缀 （由于内建数值类型有多种，通过调用 QueryParser::getNumeric 函数添加恰当的后缀）；若是其他类型，调用 QueryParser::getTextWithRange 做合法性检查。对于上述示例查询，object 被设置为字符串 “张三” 。然后调用 QueryParser::replacePrefix 函数将其中可能存在的前缀转换为 IRI 形式（示例查询中 object 值不会被改动）。最后，调用 QueryParser::addTriple ，将迄今为止获取的一条三元组（包含主语、谓词、宾语）存入 QueryTree 。

1.6 小结

本篇介绍了 gStore 的 SPARQL 解析机制，主要详细分析了 QueryParser 类在遍历语法解析树的过程中调用的关键函数，包括入口函数 QueryParser::visitQuery 、解析 SELECT 查询头的 QueryParser::visitSelectClause 、以及解析三元组的 QueryParser::visitTripleSameSubjectpath ；建议在阅读的同时结合源码Parser/QueryParser.cpp 一起分析，会更容易理解。