Lemon Parser:此规则不可简化 [英] Lemon Parser: This rule can not be reduced
问题描述
我正在尝试编写语法来分析模板语言，例如 jinja2 (或<您选择的href ="https://twig.symfony.com" rel ="nofollow noreferrer"> twig )，但我无法成功解析switch-case语句.
I'm attempting to write a grammar to parse templating language say jinja2 (or twig at your choose), and I can't successfully parse switch-case statement.
让我展示所需的语法:
{% switch username %}
{% case "Jim" %}
I want to say:
{% case "Nik" %}
Hello man!
{% endcase %}
{% case "Bob" %}
Hi
{% default %}
Who are you?
{% endswitch %}
这里的尾壳只是折断而已.
Here endcase just works as break.
我的语法文件的有效部分:
Worked portion of my grammar file:
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等工作了语法.
This is just part of my grammar and I have worked grammar for for, if, while, do, loop, etc.
但是我不知道:
-
{% case expr %} statement_list(T)没有{% endcase %} -
{% default %} statement_list(T)
{% case expr %} statement_list(T)without{% 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);
}
第一名但没有运气，得到了
for #1 but no luck, got
此规则不能简化.
This rule can not be reduced.
#2相同
坦率地说，我了解问题的根源-缺少大小写/默认值限制，但实际上我不知道如何解决此问题.
Frankly speaking I'm understand the root of problem - the lack of case/default-bound, but actually I have no idea how to address this issue.
任何帮助将不胜感激！
推荐答案
问题是您的语法是LR(2)，而不是LR(1).
The problem is that your grammar is LR(2), not LR(1).
出现许多移位/减少冲突，因为在看到%{之后的标记之前，不知道该怎么做.例如，考虑部分模板(我故意破坏了缩进):
Many shift/reduce conflicts arise because it is impossible to know what to do until the token following a %{ is seen. For example, consider the partial template (I've deliberately destroyed the indentation):
{% switch username %} {% case "Jim" %} I want to say: {%现在，应将粗体部分缩小为case_clause吗?
Now, should the bolded section be reduced to case_clause?
请记住，在LR(k)语法中，必须通过仅查看要缩减序列的末尾的k标记来做出减少的决定. Lemon与大多数LR解析器生成器一样，仅实现LR(1)解析器，因此仅需使用一个前瞻标记(%})来做出决定.但是，如果不知道 next 令牌是什么，就无法做出决定:
Remember that in an LR(k) grammar, the decision to reduce must be made by looking only at the k tokens following the end of the sequence to be reduced. Lemon, like most LR parser generators, only implements LR(1) parsers, so the decision needs to be made using only one lookahead token, which is the %}. But the decision cannot be made without knowing what the next token is:
{% 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上.
In the first input, we do not do the reduction, but we have reached the end of the statement_list. In the second one, we need to reduce because we've found the entire case_clause. And in the third one, we've started a new statement which will need to be appended to the statement_list.
第一个和第三个可能的输入没有问题，因为它们两个都只对应一个换档操作；必要的减少(无论是哪种减少)都将在以后执行.但是第二个值需要在%{之前减少，并且到我们看到case令牌时，已经来不及了.
The first and third possible inputs present no problem, because both of them just correspond to a shift action; the necessary reduction -- whichever one it is -- will be performed later. But the second one needs a reduce to happen before the %{, and by the time we see the case token, it is too late.
最简单的解决方案是强制词法分析器将{% keyword识别为单个标记(每个关键字不同).例如，以下内容与您的语法的不同之处仅在于，每个OPEN_DELIMITER FOO实例都已由OPEN_FOO替换，这没有问题:(为了避免水平滚动，我也将CLOSE_DELIMITER替换为CLOSE.)
The simplest solution, it seems to me, is to force the lexer to recognize {% keyword as a single token (different for each keyword). For example, the following, which differs from your grammar only in that each instance of OPEN_DELIMITER FOO has been replaced by OPEN_FOO, presents no problems: (I also replace CLOSE_DELIMITER with CLOSE to avoid horizontal scrolling.)
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提供空的基本情况:
As a side-note, I'd suggest simplifying your grammar by not special-casing empty statement-lists. Just allow an empty base case for 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:此规则不可简化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
