3
Я знаю, что каждый LL (1) также является LR (1). Но как насчет взаимосвязи между LL (1) и LR (0), может ли LL (1) быть LR (0)?Является ли каждая грамматика LL (1) грамматикой LR (0)?
A
ответ
3
Вы задаете два вопроса: один в заголовке и другой в теле сообщения. Ни указать ли вы спрашиваете о языках или грамматике, но основные ответы такие же:
ли все LL (1) языки LR (0)?
№ Язык, который содержит как строку, так и собственный префикс этой строки, не может быть LR (0). Но многие языки LL (1) имеют такую форму.
Есть некоторые языки LL (1) LR (0)?
Несомненно.
(Неиспользуемый вопрос) Есть ли языки LR (0) не LL (1).
Да. Например, язык
{ambnc | m≥n≥0}является LR (0), но он не имеет грамматики LL (1).
+0
Итак, отвечая, я могу сказать, что .. если мы не получим дубликатов записей в таблице LL (1) для грамматики ... тогда эта грамматика ... хотя она оставлена факторированной .. может быть LR (0) (тогда и только тогда, когда грамматика конфликтует (сдвиг/сокращение) бесплатно в таблице LR (0)). – bopia
+0
@bopia: грамматика LR (0), если таблица LR (0) не содержит конфликтов. Ничто другое не имеет отношения к делу. – rici
+0
Не могли бы вы дать грамматику LR (0) для {a^mb^n | m≥n≥0}, пожалуйста? – qznc
Это может быть более проблематичным для Computer Science SE (сосредоточено на теории), чем StackOverflow (сфокусировано на практике). –