2014-02-09
797
Способы представления синтаксиса языка. Задание бесконечного текста конечными средствами. Проблема разбора. Классификация языков
Требования, предъявляемые к грамматикам
Отношения и операции над ними
Пусть есть 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 означает найти такое подмножество элементов c1…cn, для которых выполняется отношение: aRc1,c1Rn-1b,c1Rc2,c2Rn-2b….
n-1 степень R получила название транзитивного замыкания отношения R и обозначается – R+:
R+=R1ÈR2ÈR3È…
R*=R0ÈR1ÈR2È…
R0-единичное отношение (aR0b означает a=b).
R*– рефлексивно-транзитивное замыкание отношения R.
Пусть задана грамматика и нетерминальный символ – U. Необходимо отыскать множество головных символов цепочек, выводимых из U.(т.е.UÞ+Sx).
Префикс U обозначается как SPRU.
Отношение SPRU имеет место Û,когда в грамматике есть правило U=S…
Чтобы отыскать транзитивное замыкание отношения Þ+, должны иметь место выводы:UÞS1…ÞS2…Þ…ÞSn…Þ.
Пусть дана грамматика G{V, S, P, Z}.
Чтобы появиться в в выводе какого-либо предложения, нетерминальный символ должен встретиться в некоторой сентенциальной форме. Из этого нетерминального символа должна выводиться цепочка UÞ + t,содержащая только терминальные символы.
tÎS +;
V- нетерминальные символы;
S -терминальные символы;
1) Из любого нетерминального символа, принадлежащего словарю, должна выводиться цепочка, содержащая терминальные символы.
2) Для того чтобы имело место первое правило, нетерминальный символ из множества V должен хотя бы раз встретиться в сентенциальной форме.
Синтаксическое дерево – это граф без контуров и петель, где корневой вершине поставлен в соответствие начальный символ.
Куст символа – это множество подчинённых ему символов.
Имя куста – это нетерминальный символ.
При чтении слева направо концевые вершины образуют цепочку, вывод которой дан этим деревом.
Пример: Выведем предложение (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 дерева:
| Е |
| Е |
| Е |
| Е |
| Е |
| Е |
| i |
| i |
| Е |
| i |
| i |
| i |
| Е |
| Е |
| Е |
| i |
+ *
* +
Из обоих этих деревьев выделяется нужная цепочка. В этом случае для построения цепочки есть альтернатива, в отличие от предыдущего примера. Эта грамматика неоднозначная. Критерием неоднозначности являются различные деревья.
Если какое-либо предложение, генерированное грамматикой, имеет более 1-го дерева разбора, то говорят, что грамматика неоднозначна. Задача установления неоднозначности в какой-либо грамматике неразрешима, т.е. не существует алгоритма, который бы за конечное число шагов, рассмотрев предложение, ответил бы – однозначна грамматика его породившая, или нет.
Задачи разбора заключаются в том, чтобы распознать: принадлежит ли предложение языка программирования рассматриваемой грамматике. Различают 2 категории алгоритмов: нисходящий (развертка) и восходящий (свертка).
Итеративная форма задания грамматик
Цель: создание бесконечного числа цепочек конечным (минимальным) количеством правил. Вводится мета-символ { }, который означает: элемент, находящийся внутри { }, может повторяться многократно.
E:=E+T|T эквивалентно E:=T{+T}0.
