Заданную КС-грамматику приведите к грамматике Вирта (простого предшествования). Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по информатике
Заданную КС-грамматику приведите к грамматике Вирта (простого предшествования)

Заданную КС-грамматику приведите к грамматике Вирта (простого предшествования) .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Заданную КС-грамматику приведите к грамматике Вирта (простого предшествования). Для этого устраните факультативные [ ] и итеративные { } скобки путем добавления новых альтернатив и праворекурсивных правил. Постройте матрицу простого предшествования. Проведите свертку указанной правильной цепочки с использованием построенных Вами отношений предшествования. S :: = CALL <идентификатор><список фактических параметров> <список фактических параметров> :: = <параметр>{,< параметр >} <параметр> :: = < идентификатор> | <константа > <идентификатор> - обозначаем @; <константа> - обозначаем k; Цепочка для свертки: CALL PRIMER1 ( ABC, 27, 15 )

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Переобозначим нетерминалы для сокращения записи и избавимся от факультативных и итеративных скобок:
S-> CALL @ ( L )
L-> P | P, L
P-> @ | k
Новая грамматика не является грамматикой простого предшествования, т.к. между символами L и ) двойственные отношения:
L = ) и L > ) так как R(L) > DO , a L является R(L) из-за наличия в грамматике правила L-> P, L
Введя новый нетерминал L1 и правило для него L1->L избавимся от двойственных отношений и получим грамматику простого предшествования эквивалентную заданной:
S-> CALL @ ( L1 )
L1-> L
L-> P | P, L
P-> @ | k
Построим таблицу самых левых и самых правых символов для нетерминалов грамматики:
N L(N) R(N)
S CALL )
L1 L P @ k L P @ k
L P @ k P L @ k
P @ k @ k
Таблица простого предшествования будет иметь вид:
S CALL @ ( L1 ) L P , k
S
CALL
=
@
=
>
>
(
<
=
< <
<
L1
=
)
L
>
P
>
=
,
<
= <
<
k
>
>
Проведем свертку заданной цепочки:
# CALL PRIMER1 ( ABC , 27 , 15 ) #
< = = < >
# CALL PRIMER1 ( P , 27 , 15 ) #
< = = < = < >
# CALL PRIMER1 ( P , P , 15 ) #
< = = < = < = < >
# CALL PRIMER1 ( P , P , P ) #
< = = < = < = < >
# CALL PRIMER1 ( P , P , L ) #
< = = < = < = = >
# CALL PRIMER1 ( P , L ) #
< = = < = = >
# CALL PRIMER1 ( L ) #
< = = < >
# CALL PRIMER1 ( L1 ) #
< = = = = >
# S #

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу