ВОРОТА | ВОРОТА КС 2021 | Набор 1 | Вопрос 15

Рассмотрим следующие утверждения.

• S1: Каждая грамматика SLR(1) однозначна, но есть определенные однозначные грамматики, которые не являются SLR(1).
• S2: Для любой контекстно-свободной грамматики существует синтаксический анализатор, которому требуется не более O(n ³ ) времени для анализа строки длины n.

Какой из следующих вариантов правильный?
(А) S1 верно, а S2 ложно
(B) S1 ложно, а S2 верно
(C) верно S1 и верно S2
(D) S1 ложно, а S2 ложно

Ответ: (С)
Объяснение: Типы парсеров:

Утверждение (S1) верно.

Используя алгоритм CYK, мы можем проверить проблему принадлежности CFG. Разбор строки длины n занимает не более O(n ³ ) времени.

Утверждение (S2) также верно.

Викторина этого вопроса