Lemon Parser: Это правило нельзя уменьшить

Проблема в том, что ваша грамматика 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, будет слишком поздно.

Самое простое решение, как мне кажется, это заставить лексер распознавать {% keyword как единый токен (разный для каждого ключевого слова). Например, следующее, которое отличается от вашей грамматики только тем, что каждый экземпляр 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);
}