Lemon Parser：这个规则不能减少

Question

我正在尝试编写语法来解析模板语言，比如 jinja2 (or twig 由您选择），但我无法成功解析 switch-case 语句。

让我显示所需的语法：

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

这里的endcase只是作为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 等语法。

但我不知道：

{% case expr %} statement_list(T) 没有 {% endcase %}
{% 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);
}

#1 但运气不好，得到了

This rule can not be reduced.

#2 相同

坦率地说，我理解问题的根源——缺少 case/default-bound，但实际上我不知道如何解决这个问题。

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

Answer 1

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

许多 shift/reduce 冲突的发生是因为在看到 %{ 之后的标记之前不可能知道该做什么。例如，考虑部分模板（我故意破坏了缩进）：

{% switch username %} <b>{% case "Jim" %} I want to say:</b> {%

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

请记住，在 LR(k) 文法中，必须通过仅查看要归约序列末尾后面的 k 个标记来做出归约决定。 Lemon 与大多数 LR 解析器生成器一样，仅实现 LR(1) 解析器，因此需要仅使用一个前瞻标记来做出决定，即 %}。但是如果不知道 next 令牌是什么，就无法做出决定：

{% switch username %} <b>{% case "Jim" %} I want to say:</b> {% <b><i>endcase</i></b>

{% switch username %} <b>{% case "Jim" %} I want to say:</b> {% <b><i>case</i></b>

{% switch username %} <b>{% case "Jim" %} I want to say:</b> {% <b><i>switch</i></b>

在第一个输入中，我们没有做归约，但是我们已经到了statement_list的结尾。在第二个中，我们需要减少，因为我们找到了整个 case_clause。在第三个中，我们开始了一个新的 statement，需要将其附加到 statement_list.

第一个和第三个可能的输入没有问题，因为它们都只对应一个shift动作；必要的削减 -- -- 无论是哪一个 -- -- 将在以后进行。但是第二个需要在 %{ 之前进行 reduce，当我们看到 case 标记时，为时已晚。

在我看来，最简单的解决方案是强制词法分析器将 {% <em>keyword</em> 识别为单个标记（不同对于每个关键字）。例如，以下与您的语法的不同之处仅在于 OPEN_DELIMITER FOO 的每个实例都已替换为 OPEN_FOO，没有问题：（我还将 CLOSE_DELIMITER 替换为 CLOSE 以避免水平滚动。）

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);
}

Lemon Parser：这个规则不能减少

Lemon Parser: This rule can not be reduced

grammar

parsing

lalr

lemon