Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 56

Студент написал две не зависящие от контекста грамматики G1 и G2 для генерации одного C-подобного объявления массива. Размерность массива равна как минимум одному. Например,

int a[10][3]; 

Грамматики используют D в качестве начального символа и используют шесть терминальных символов int; id [] номер

Grammar G1
D → int L;
L → id [E
E → num]
E → num] [E

Grammar G2
D → int L;
L → id E
E → E[num]
E → [num] 

Какая из грамматик правильно генерирует объявление, упомянутое выше?

(A) и G1, и G2
(B) Только G1
(С) только G2
(D) Ни G1, ни G2

Ответ: (А)
Пояснение: контекстно-свободные грамматики

Контекстно-свободная грамматика (CFG) — это набор правил рекурсивного переписывания (или продукций), используемых для генерации шаблонов строк.

CFG состоит из следующих компонентов:
1) Набор терминальных символов, которые являются символами алфавита, которые появляются в строках, генерируемых грамматикой.
2) Набор нетерминальных символов, которые являются заполнителями для шаблонов терминальных символов, которые могут быть сгенерированы нетерминальными символами.
3) Набор продукций, которые представляют собой правила замены (или переписывания) нетерминальных символов (в левой части продукции) в строке другими нетерминальными или терминальными символами (в правой части продукции).
4) Начальный символ, который является специальным нетерминальным символом, который появляется в исходной строке, созданной грамматикой.

Чтобы сгенерировать строку терминальных символов из CFG, мы:
1) Начните со строки, состоящей из начального символа;
2) Примените один из спектаклей с начальным символом слева от размера, заменив начальный символ с правой стороны производства;
3) Повторите процесс выбора нетерминальных символов в строке и замены их правой частью некоторого соответствующего произведения, пока все нетерминалы не будут заменены терминальными символами.


Если задана грамматика G с начальным символом S, если существует некоторая последовательность произведений, которая при применении к исходной строке S приводит к строке s, то s находится на L (G), языке грамматики.

Источник: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/cfg.html

Нам нужно проверить, какая из двух грамматик правильно генерирует «int a [10] [3];». Это означает, что мы должны проверить, если int id [num] [num];

Grammar G1
D → int L;
L → id [E
E → num]
E → num] [E

Grammar G2
D → int L;
L → id E
E → E[num]
E → [num] 

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 56

0.00 (0%) 0 votes