Стр. 12 - Информационные структуры и их преобразование

10 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
R ∗=R 0∪R1 ∪R2 ∪…
R 0-единичное отношение (aR 0b означает a=b).
R ∗– рефлексивно-транзитивное замыкание отношения R.
Пусть задана грамматика и нетерминальный символ – U. Необходимо
отыскать множество головных символов цепочек, выводимых из
U.(т.е.U⇒+Sx ).
Префикс U обозначается как SPRU.
Отношение SPRU имеет место ⇔,когда в грамматике есть правило
U=S…
Чтобы отыскать транзитивное замыкание отношения ⇒+, должны
иметь место выводы :U⇒S1…⇒S2… ⇒…⇒Sn…⇒.
1.4. Требования, предъявляемые к грамматикам
Пусть дана грамматика G{V, Σ, P, Z}.
Чтобы появиться в в выводе какого-либо предложения,
нетерминальный символ должен встретиться в некоторой сентенциальной
форме. Из этого нетерминального символа должна выводиться цепочка U⇒
+ t,содержащая только терминальные символы.
t∈Σ +;
V- нетерминальные символы;
Σ -терминальные символы;
1) Из любого нетерминального символа, принадлежащего словарю,
должна выводиться цепочка, содержащая терминальные символы.
2) Для того чтобы имело место первое правило, нетерминальный
символ из множества V должен хотя бы раз встретиться в сентенциальной
форме.
1.5. Способы представления синтаксиса языка. Задание
бесконечного текста конечными средствами. Проблема разбора.
Классификация языков
Синтаксические деревья и неоднозначность
Синтаксическое дерево – это граф без контуров и петель, где
корневой вершине поставлен в соответствие начальный символ.
Куст символа – это множество подчинённых ему символов.
Имя куста – это нетерминальный символ.
При чтении слева направо концевые вершины образуют цепочку,
вывод которой дан этим деревом.