Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 10

Что из следующего описывает дескриптор (применимый к LR-синтаксическому анализу) надлежащим образом?
(A) Это позиция в форме предложения, где произойдет следующая операция сдвига или уменьшения

(B) Нетерминал, производство которого будет использовано для сокращения на следующем этапе
(C) Это произведение, которое может использоваться для сокращения на следующем шаге вместе с позицией в форме предложения, где произойдет следующая операция сдвига или уменьшения
(D) Это произведение p будет использоваться для сокращения на следующем шаге вместе с позицией в форме предложения, где можно найти правую часть произведения

Ответ: (D)
Пояснение: Давайте сначала разберемся в терминологии, используемой здесь.

LR Parsing — здесь «L» обозначает скрининг входной строки слева направо, а «R» обозначает деривацию правого большинства в обратном направлении (потому что речь идет об анализе снизу вверх).

Форма предложения — Предположим, что для заданной свободной грамматики контекста G у нас есть начальный символ S, а затем для определения языка, сгенерированного грамматикой G, то есть L (G), мы начинаем деривацию, начиная с S, используя правила производства грамматики. После одного полного вывода мы получаем строку w, которая состоит только из терминальных символов, т. Е. W принадлежит L (G). Тогда мы можем сказать, что w является предложением грамматики G. Теперь, когда процесс деривации, если он принимает некоторую форму q, где q может содержать некоторую нетерминальную форму, тогда мы говорим, что q является формой предложения грамматики G. Даже начальный символ S также является формой предложения грамматики G (поскольку он также содержит нетерминал S).


For Ex :

Grammar is :

S-> aAcBe

A->Ab|b

B->d

Input string : abbcde

Derivation : ( Top-Down, Right Most Derivation)

S->aAcBe
->aAcde
->aAbcde
->abbcde 

Здесь {abbcde} является предложением грамматики (поскольку оно содержит только терминальные символы), а {S, aAcBe, aAcde, aAbcde} являются формами предложения G (поскольку эти формы содержат нетерминалы во время процесса деривации)

Теперь давайте посмотрим на вопрос.

Вопрос связан с разбором LR, который является анализом снизу вверх.

Давайте возьмем ту же самую грамматику выше, поскольку это синтаксический анализ снизу вверх, нам нужно начать со строки «abbcde» и попытаться получить S, используя правила производства.


: abbcde

->aAbcde ( using A-> b )

->aAcde ( using A-> Ab )

->aAcBe ( using B -> d )

->S ( using S-> aAcBe ) 

Вышеуказанный процесс называется сокращением.

RHS производства, который заменяется их LHS, называется Handle, поэтому {b, Ab, d, aAcBe} являются дескрипторами, а замена его на LHS называется Handle-Pruning.

Следовательно, вариант D подходит лучше всего.

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

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

ВОРОТА | GATE CS 2008 | Вопрос 10

0.00 (0%) 0 votes