3.1.3. Отношения и операции над ними

Пусть есть 2 отношения: aRb и aPb, где a,bÎA. Рассмотрим отношение RP и назовем его произведением отношений R и P.Отношение RP имеет место тогда и только тогда, когда на множестве A есть элемент c , для которого выполняется aRc и cPb.Тогда между a и b есть отношение RP, т.е. aRPb.

Пример: aRb: b=a+1; aPb: b=a+2

Из этих двух предложений следует, что aRPb b=a+3

Отыскать n-ю степень отношения R на множестве A означает найти такое подмножество элементов c₁…c_n, для которых выполняется отношение: aRc₁,c₁R^n-1b,c₁Rc₂,c₂R^n-2b… .

n-1 степень R получила название транзитивного замыкания отношения R и обозначается – R⁺:

R⁺=R¹ÈR²ÈR³È…

R^*=R⁰ÈR¹ÈR²È…

R⁰-единичное отношение (aR⁰b означает a=b).

R^*– рефлексивно-транзитивное замыкание отношения R.

Пусть задана грамматика и нетерминальный символ – U. Необходимо отыскать множество головных символов цепочек, выводимых из U.(т.е.UÞ+S_x).

Префикс U обозначается как SPRU.

Отношение SPRU имеет место Û,когда в грамматике есть правило U=S…

Чтобы отыскать транзитивное замыкание отношения Þ+, должны иметь место выводы :UÞS₁…ÞS₂…Þ…ÞS_n…Þ.

3.1.4. Требования, предъявляемые к грамматикам

Пусть дана грамматика G{V, S, P, Z}.

Чтобы появиться в в выводе какого-либо предложения, нетерминальный символ должен встретиться в некоторой сентенциальной форме. Из этого нетерминального символа должна выводиться цепочка UÞ + t,содержащая только терминальные символы.

tÎS⁺;

V- нетерминальные символы;

S-терминальные символы;

1. Из любого нетерминального символа, принадлежащего словарю, должна выводиться цепочка, содержащая терминальные символы.

2. Для того чтобы имело место первое правило, нетерминальный символ из множества V должен хотя бы раз встретиться в сентенциальной форме.

5. Способы представления синтаксиса языка. Задание бесконечного текста конечными средствами. Проблема разбора. Классификация языков

Синтаксические деревья и неоднозначность

Синтаксическое дерево – это граф без контуров и петель, где корневой вершине поставлен в соответствие начальный символ.

Куст символа – это множество подчинённых ему символов.

Имя куста – это нетерминальный символ.

При чтении слева направо концевые вершины образуют цепочку, вывод которой дан этим деревом.

Пример: Выведем предложение (i+i)i.

Левосторонний вывод – это такой вывод, при котором на каждом шаге заменяется самый левый символ.

Используем правила из примера:

E=>T=>T*F=>F*F=>(E)*F=>(E+T)F=>(T+T)F=>(F+T)F=>(i+T)F=>(i+F)F=>(i+i)F=>(i+i)i .

Правосторонний вывод:

E=>T=>T*F=>F*F=>(E)F=>(E+T)F=>(T+T)F=>(F+T)F=>(i+T)F=>(i+F)F=>(i+i)F=>(i+i)i .

Рассмотрим грамматику : E:=E+E|E*E; E:=i.

Нужно вывести предложение i+i*i . Рассмотрим 2 дерева:

+ *

* +

Из обоих этих деревьев выделяется нужная цепочка. В этом случае для построения цепочки есть альтернатива, в отличие от предыдущего примера. Эта грамматика неоднозначная. Критерием неоднозначности являются различные деревья.

Если какое-либо предложение, генерированное грамматикой, имеет более 1-го дерева разбора, то говорят, что грамматика неоднозначна. Задача установления неоднозначности в какой-либо грамматике неразрешима, т.е. не существует алгоритма, который бы за конечное число шагов, рассмотрев предложение, ответил бы – однозначна грамматика его породившая, или нет.

Задачи разбора заключаются в том, чтобы распознать: принадлежит ли предложение языка программирования рассматриваемой грамматике. Различают 2 категории алгоритмов: нисходящий (развертка) и восходящий (свертка).

Итеративная форма задания грамматик

Цель: создание бесконечного числа цепочек конечным (минимальным) количеством правил. Вводится мета-символ { }, который означает: элемент, находящийся внутри { }, может повторяться многократно.

E:=E+T|T эквивалентно E:=T{+T}⁰.

Классификация языков

Классификацию языков ввел Хомский. В терминах формальных грамматик определяется 4 основных класса:

1. грамматика типа 0 порождает язык с фразовой структурой (естественные языки).

U⁺: = V^*, где UÎ V È S, U⁺Î{ V È S }⁺.

2. грамматика типа 1 – контекстно-зависимая или контекстно-чувствительная.

xUy: = xuy , где UÎV, uÎ{ V È S }⁺.

3. грамматика типа 2 – контекстно-свободная.

U: = u, где UÎV, uÎ{ V È S }^*.

4. грамматика типа 3 – регулярная (автоматная).

Q: = RT|T, где Q,RÎV, TÎS.

Языки, порождаемые автоматной грамматикой, получили название регулярных множеств.