使用 OcamlYacc / FsYacc 表示可选语法和重复

Question

我正在尝试建立一些词法分析/解析语法的技能。 我回顾了我为 SQL 编写的一个简单解析器，我对它并不完全满意——似乎应该有一种更简单的方法来编写解析器。

SQL 让我很困惑，因为它有很多可选标记和重复。 例如：

SELECT *
FROM t1
INNER JOIN t2
INNER JOIN t3
WHERE t1.ID = t2.ID and t1.ID = t3.ID

相当于：

SELECT *
FROM t1
INNER JOIN t2 ON t1.ID = t2.ID
INNER JOIN t3 on t1.ID = t3.ID

ON 和 WHERE 子句是可选的，并且可以出现多次。 我在解析器中处理这些问题如下：

%{
open AST
%}

// ...    
%token <string> ID   
%token AND OR COMMA
%token EQ LT LE GT GE
%token JOIN INNER LEFT RIGHT ON
// ...

%%

op: EQ { Eq } | LT { Lt } | LE { Le } | GT { Gt } | GE { Ge }

// WHERE clause is optional    
whereClause:
    |                       { None }
    | WHERE whereList       { Some($2) }        

whereList:
    | ID op ID                    { Cond($1, $2, $3) }
    | ID op ID AND whereList      { And(Cond($1, $2, $3), $5) }
    | ID op ID OR whereList       { Or(Cond($1, $2, $3), $5) }


// Join clause is optional    
joinList:
    |                       { [] }
    | joinClause            { [$1] }
    | joinClause joinList   { $1 :: $2 }

joinClause:
    | INNER JOIN ID joinOnClause    { $3, Inner, $4 }
    | LEFT JOIN ID joinOnClause     { $3, Left, $4 }
    | RIGHT JOIN ID joinOnClause    { $3, Right, $4 }

// "On" clause is optional    
joinOnClause:
    |                       { None }
    | ON whereList          { Some($2) }

// ...
%%

换句话说，我通过将可选语法分解为单独的规则来处理可选语法，并使用递归处理重复。 这是可行的，但它将解析分解为一堆小子例程，并且很难看出语法实际代表什么。

我认为如果我可以在括号内指定可选语法并用 * 或 + 重复，那么编写起来会容易得多。 这会将我的 whereClause 和 joinList 规则减少为以下内容：

whereClause:
    |                       { None }
//    $1    $2, I envision $2 being return as an (ID * op * ID * cond) list
    | WHERE [ ID op ID { (AND | OR) }]+
        { Some([for name1, op, name2, _ in $1 -> name1, op, name2]) }

joinClause:
    |                       { None }

//    $1, returned as (joinType
//                       * JOIN
//                       * ID
//                       * ((ID * op * ID) list) option) list
    | [ (INNER | LEFT | RIGHT) JOIN ID [ON whereClause] ]*
        { let joinType, _, table, onClause = $1;
          Some(table, joinType, onClause) }

我认为这种形式更更易于阅读，并且更直观地表达了它试图捕获的语法。 不幸的是，我在 Ocaml 或 F# 文档中找不到任何支持此表示法或类似内容的内容。

是否有一种简单的方法可以在 OcamlYacc 或 FsYacc 中表示具有可选或重复标记的语法？

Answer 1

Menhir 允许通过另一个符号对非终结符号进行参数化，并提供标准快捷方式库，例如选项和列表，您可以创建自己的。 示例：

option(X): x=X { Some x} 
         | { None }

还有一些语法糖，‘token?’ 相当于“option(token)”，“token+”相当于“nonempty_list(token)”。

所有这些确实缩短了语法定义。 它还受 ocamlbuild 支持，可以直接替代 ocamlyacc。 强烈推荐！

有趣的是，我也用它来解析 SQL :)

Answer 2

当你组合所有的小片段时，你应该会得到你想要的东西。 而不是：

(INNER | RIGHT | LEFT ) 

您只需将

inner_right_left

其定义为这三个关键字的并集。

您还可以在词法分析器中定义联合。 在您定义令牌的方式中，或者使用 camlp4 中，我在该领域没有做太多事情，所以我不能建议您采取这些路线。 而且我不认为它们会像到处都有小部件一样适合你。

编辑：

因此，对于 camlp4，您可以查看 Camlp4 语法模块 和教程 和更好的教程。 请注意，这并不完全是您想要的，但已经非常接近了。 该文档非常糟糕，正如 最近关于 ocaml 的讨论中所表达的那样组，但对于这个特定领域，我认为您不会遇到太多问题。 我用它做了一些工作，可以回答更多问题。