Lemon Parser:这个规则不能减少

Question

我正试图编写一个语法来解析模板语言say jinja2(或您选择的trick)，但我无法成功解析switch-case语句。

让我展示想要的语法：

{% switch username %}
{% case "Jim" %}
I want to say: 
{% case "Nik" %}
Hello man!
{% endcase %}
{% case "Bob" %}
Hi
{% default %}
Who are you?
{% endswitch %}

这里的尾数只是作为break。

我的语法文件的工作部分：

program ::= template_language(Q) . {
status->ret = Q;
}
template_language(R) ::= statement_list(L) . {
R = L;
}
statement_list(R) ::= statement_list(L) statement(S) . {
R = my_list(L, S);
}
statement_list(R) ::= statement(S) . {
R = my_list(NULL, S);
}
statement(R) ::= switch_statement(E) . {
R = E;
}
// empty {% switch expr %} {% endswitch %}
switch_statement(R) ::= OPEN_DELIMITER SWITCH expr(E) CLOSE_DELIMITER OPEN_DELIMITER ENDSWITCH CLOSE_DELIMITER . {
R = my_switch_statement(E, NULL, status->scanner_state);
}
switch_statement(R) ::= OPEN_DELIMITER SWITCH expr(E) CLOSE_DELIMITER case_clauses(C) OPEN_DELIMITER ENDSWITCH CLOSE_DELIMITER . {
R = my_switch_statement(E, C, status->scanner_state);
}
case_clauses(R) ::= case_clauses(C) case_clause(K) . {
R = my_list(C, K);
}
case_clauses(R) ::= case_clause(K) . {
R = my_list(NULL, K);
}
// empty {% case expr %} {% endcase %}
case_clause(R) ::= OPEN_DELIMITER CASE expr(E) CLOSE_DELIMITER OPEN_DELIMITER ENDCASE CLOSE_DELIMITER . {
R = case_clause(E, NULL, status->scanner_state);
}
case_clause(R) ::= OPEN_DELIMITER CASE expr(E) CLOSE_DELIMITER statement_list(T) OPEN_DELIMITER ENDCASE CLOSE_DELIMITER . {
R = case_clause(E, T, status->scanner_state);
}

这只是我语法的一部分，我已经为for、if、while、do、loop等编写了语法。

但我不知道：

1. {% case expr %} statement_list(T)不带{% endcase %}
2. {% default %} statement_list(T)

例如，我尝试使用：

case_clause(R) ::= OPEN_DELIMITER CASE expr(E) CLOSE_DELIMITER statement_list(T) . {
R = case_clause(E, T, status->scanner_state);
}

排名第一但运气不佳，获得

此规则无法缩减。

#2 也是如此

坦率地说，我理解问题的根源——缺乏案例/默认约束，但实际上我不知道如何解决这个问题。

如有任何帮助，我们将不胜感激！

Answer 1

问题是您的语法是LR(2)，而不是LR(1)。

由于在看到%{之后的令牌之前不可能知道该怎么做，因此会出现许多移位/减少冲突。例如，考虑部分模板(我故意破坏了缩进)：

{% switch username %}{% case "Jim" %} I want to say:{%

现在，是否应该将粗体部分缩减为case_clause？

请记住，在LR(k)语法中，必须通过只查看要减少的序列结束后的k标记来做出减少的决定。Lemon和大多数LR解析器生成器一样，只实现LR(1)解析器，因此只需要使用一个前瞻性令牌(即%})来做出决策。但是，如果不知道下一个令牌是什么，就无法做出决定：

{% switch username %}{% case "Jim" %} I want to say:{%endcase

{% switch username %}{% case "Jim" %} I want to say:{%case

{% switch username %}{% case "Jim" %} I want to say:{%switch

在第一个输入中，我们没有进行归约，但我们已经到达了statement_list的末尾。在第二个例子中，我们需要减少，因为我们已经找到了整个case_clause。在第三个例子中，我们开始了一个新的statement，它需要附加到statement_list。

第一个和第三个可能的输入没有问题，因为它们都只对应于一个换档动作；必要的减少——无论是哪一个——将在以后进行。但第二个需要在%{之前进行减少，当我们看到case令牌时，已经太晚了。

在我看来，最简单的解决方案是强制lexer将{%keyword识别为单个令牌(每个关键字不同)。例如，以下内容与您的语法的不同之处在于，OPEN_DELIMITER FOO的每个实例都被OPEN_FOO替换了，它没有任何问题：(我还用CLOSE替换了CLOSE_DELIMITER，以避免水平滚动。)

program ::= template_language(Q) . {
status->ret = Q;
}
template_language(R) ::= statement_list(L) . {
R = L;
}
statement_list(R) ::= statement_list(L) statement(S) . {
R = my_list(L, S);
}
statement_list(R) ::= statement(S) . {
R = my_list(NULL, S);
}
statement(R) ::= switch_statement(E) . {
R = E;
}
// empty {% switch expr %} {% endswitch %}
switch_statement(R) ::= OPEN_SWITCH expr(E) CLOSE OPEN_ENDSWITCH CLOSE . {
R = my_switch_statement(E, NULL, status->scanner_state);
}
switch_statement(R) ::= OPEN_SWITCH expr(E) CLOSE case_clauses(C) OPEN_ENDSWITCH CLOSE . {
R = my_switch_statement(E, C, status->scanner_state);
}
case_clauses(R) ::= case_clauses(C) case_clause(K) . {
R = my_list(C, K);
}
case_clauses(R) ::= case_clause(K) . {
R = my_list(NULL, K);
}
// empty {% case expr %} {% endcase %}
case_clause(R) ::= OPEN_CASE expr(E) CLOSE OPEN_ENDCASE CLOSE . {
R = case_clause(E, NULL, status->scanner_state);
}
case_clause(R) ::= OPEN_CASE expr(E) CLOSE statement_list(T) OPEN_ENDCASE CLOSE . {
R = case_clause(E, T, status->scanner_state);
}
case_clause(R) ::= OPEN_CASE expr(E) CLOSE statement_list(T) . {
R = case_clause(E, T, status->scanner_state);
}

case_clause(R) ::= OPEN_DEFAULT CLOSE statement_list(T) . {
R = case_clause(E, T, status->scanner_state);
}

---

顺便说一句，我建议通过不使用特殊大小写空语句列表来简化语法。只允许statement_list:有一个空的基本情况

program ::= template_language(Q) . {
status->ret = Q;
}
template_language(R) ::= statement_list(L) . {
R = L;
}
statement_list(R) ::= statement_list(L) statement(S) . {
R = my_list(L, S);
}
statement_list(R) ::= . {
R = NULL;
}
statement(R) ::= switch_statement(E) . {
R = E;
}
switch_statement(R) ::= OPEN_SWITCH expr(E) CLOSE case_clauses(C) OPEN_ENDSWITCH CLOSE . {
R = my_switch_statement(E, C, status->scanner_state);
}
case_clauses(R) ::= case_clauses(C) case_clause(K) . {
R = my_list(C, K);
}
case_clauses(R) ::= . {
R = NULL;
}
case_clause(R) ::= OPEN_CASE expr(E) CLOSE statement_list(T) OPEN_ENDCASE CLOSE . {
R = case_clause(E, T, status->scanner_state);
}
case_clause(R) ::= OPEN_CASE expr(E) CLOSE statement_list(T) . {
R = case_clause(E, T, status->scanner_state);
}
case_clause(R) ::= OPEN_DEFAULT CLOSE statement_list(T) . {
R = case_clause(E, T, status->scanner_state);
}