1. Существуют ли какие-либо общие способы преобразования таких не-LALR (1) грамматик в грамматики LALR (1)?
Нет. Может быть или не будет возможно преобразовать произвольную контекстно-свободную грамматику (CFG) в грамматику LALR (1). Для этого нет общего алгоритма, даже если вы как-то знаете, что это возможно. Более того, если у вас есть CFG и LALR (1) грамматика, вы не можете определить, распознают ли они один и тот же язык. (Хуже, нет алгоритма, который даже скажет вам, будет ли произвольный CFG распознавать каждую возможную строку для своего алфавита.)
2. Если две грамматики генерируют точно такие же языки, и мы знаем, что это не LALR (1), можем ли мы знать, является ли другой LALR (1)?
Опять же, нет. Как и выше, нет алгоритма, который может проверить, что два грамматики генерируют один и тот же язык, но даже предполагая, что вы знаете, что две грамматики генерируют один и тот же язык, тот факт, что один из них не LALR (1) ничего не говорит о другом один.
Существует, однако, один полезный результат. Если у вас есть грамматика LALR (k) с конечным k > 1, вы можете сгенерировать грамматику LALR (1). Другими словами, нет такой вещи, как LALR (k) язык для k > 1; если язык имеет грамматику LALR (k), он имеет грамматику LALR (k ') для любого k' такой, что 1 ≤ k '< k.
Это не поможет вам с вашей грамматикой, потому что конфликт не может быть устранен путем увеличения взгляда до любого конечного значения.
Существует простой способ избавиться от этого конкретного конфликта сдвига, однако, и это техника, которая часто работает.Рассмотрим две противоречащие друг другу правила:
lval := lval '[' expr ']'
expr := ID '[' expr ']' OF expr
Проблема заключается в том, что в первом случае, ID должна быть уменьшена до lval немедленно (или, по крайней мере, до следующего expr уменьшается), но во втором случае это не может сокращаться до lval. Но мы не можем сказать, в каком случае мы находимся, пока мы не уменьшим expr и не столкнемся с OF (или нет).
Если бы мы могли закончить lval производства, не делая сокращение интерьера lval, то мы бы не проблема, потому что фактическое сокращение будет происходить, когда маркер после ] виден.
Возможно, для этого существует технический термин, но я этого не знаю. Я всегда описывал это как «сокращение отсрочки», и во многих случаях это не очень сложно:
lval' := ID `[` expr `]`
| lval' `[` expr `]`
lval := ID
| lval'
expr := lval
| ID '[' expr ']' OF expr
Очень информативный ответ. Вопрос о тех методах, которые вы использовали в ответе, как я могу найти эти общие методы для грамматических преобразований? Большое спасибо. – MingyanGuo
@MingyanGuo: Мне жаль, что у меня нет ссылки. Я уверен, что я не думал, что это один, но я не смог отправить ссылку на Google, и я использовал ее так долго, что не могу вспомнить, откуда она взялась. Сожалею. Результат неразрешимости прост и хорошо известен; он основан на построении грамматики, которая представляет собой вычисление машины Тьюринга. Я почти уверен, что это у Хопкрофта и Ульмана. Я получил LALR (k> 1) сокращение от Sippu & Soisalon-Soinenen (Теория парсинга), но я думаю, вы можете найти его в любой хорошей ссылке. – rici
Собственно, теперь, когда я думаю об этом, техника, которую я использовал, очень похожа на алгоритм покрытия LR (k), как описано S & S-S. Предположим, вы построили парсер LR (k) для грамматики; по сути, вы вычислили множество возможных взглядов для каждой продукции. Таким образом, вы можете заменить каждый нетерминальный N множеством нетерминалов (N, L1, L2 ... Lk-1), выработать подстановки для каждого нетерминального в RHS. Это, очевидно, дает вам грамматику LR (1). Иногда вы можете сделать что-то подобное с неканоническими (например, не-терминалами). Я думаю, что это то, что я сделал. – rici