Рубрики

ВОРОТА | GATE CS 2013 | Вопрос 65

Каково максимальное количество ходов сокращения, которые могут быть приняты восходящим синтаксическим анализатором для грамматики без epsilon- и unit-production (т. Е. Типа A -> є и A -> a) для анализа строки с n жетоны?
(А) н / 2
(Б) н-1
(С) 2n-1
(D) 2 н

Ответ: (Б)
Пояснение: приведенная в вопросе грамматика без эпсилон- и единичного производства (т. Е. Типа A -> є и A -> a).

Чтобы получить максимальное количество ходов Сокращения, мы должны убедиться, что в каждой предложенной форме сокращен только один терминал. Поскольку производство юнитов отсутствует, последние 2 жетона займут только 1 ход.

Таким образом, чтобы уменьшить входную строку из n токенов, сначала уменьшите n-2 токена, используя n-2 сокращения ходов, а затем уменьшите последние 2 токена, используя производство, которое имело. Таким образом, всего n-2 + 1 = n-1 уменьшить ходы.

Предположим, что строка abcd. (n = 4).

Мы можем написать грамматику, которая принимает эту строку следующим образом:

S->aB
B->bC
C->cd 

Наиболее правый вывод для вышесказанного:

S -> aB ( Reduction 3 )
-> abC ( Reduction 2 )
-> abcd ( Reduction 1 )

Здесь мы видим, что производство не относится к единице или эпсилону. Отсюда 3 сокращения здесь.

Мы можем получить меньшее количество сокращений с помощью некоторой другой грамматики, которая также не производит единичные или эпсилон-произведения,

S->abA
A-> cd

Право Большинство производных для вышеупомянутого как:

S -> abA ( Reduction 2 )
-> abcd ( Reduction 1 )

Следовательно 2 сокращения.

Но мы заинтересованы в том, чтобы знать максимальное количество сокращений, которое следует из 1-й грамматики. Следовательно, всего 3 сокращения как максимум, который здесь (n — 1) при n = 4.

Таким образом, вариант Б.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2013 | Вопрос 65

0.00 (0%) 0 votes