Идея грамматического разбор снизу вверх. Отношения в грамматиках

Синтаксический анализ (3) Лекция 6 Содержание 1. 2. 3. 4. 5. Идея грамматического разбор снизу-вверх Отношения в грамматиках Отношения предшествования Определение грамматики предшествования Операторное предшествование и операторные грамматики 2 1. Идея грамматического разбора снизу-вверх 3 Грамматических разбор снизу-вверх • Грамматический разбор снизу-вверх начинается с конечных узлов дерева грамматического разбора и в процессе выполнения пытается объединить их построением узлов более высокого уровня до тех пор, пока не будет достигнут корень дерева Z. • В этом смысле разбор снизу-вверх можно противопоставить разбору сверху-вниз. 4 5 • На каждом шаге свертки подцепочка, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода (свертка) • Для осуществления разбора необходимо выделить комбинацию символов из правой части правила и свернуть в левую часть (предлог) 6 Пример • U ::= VZ, те. VZ сворачивается в U (U=> VZ) 7 НО! ВСТАЕТ ПРОБЛЕМА С чего начинать разбор?? 8 2. ОТНОШЕНИЯ В ГРАММАТИКАХ 9 Применение отношений в грамматиках • Бинарным отношением на множестве является любое свойство, которым обладают (или не обладают) любые два упорядоченных символа этого множества. 10 Пример 1 • i0 • Отношение МЕНЬШЕ ЧЕМ (<), определенное на множестве целых числе: i < j тогда и только тогда, когда j - i является положительным ненулевым целым числом. 11 Пример 2 • Отношение РЕБЕНОК на множестве людей • Некто A либо является ребенком В, либо нет 12 Обозначение отношений • Используем инфиксные обозначения для отношений: • Если между элементами c и d некоторого множества имеет место отношение (Relation) , то мы пишем cRd. • Порядок следования ВАЖЕН! Т.е. из cRd автоматически не следует dRC • Можно также рассматривать отношение как множество упорядоченных пар, для которых данное отношение справедливо: (c, d) ϵ R тогда и только тогда, когда cRd 13 • Отношение P включает другое отношение R, если из (c, d) ϵ R следует (c, d) ϵ P. 14 Обратные отношения • Отношение, обратное отношению R, записывается как R-1 и определяется следующим образом: • сR-1d тогда и только тогда, когда dRc • Отношение обратное отношению БОЛЬШЕ ЧЕМ, есть МЕНЬШЕ ЧЕМ. • Отношение обратное отношению РЕБЕНОК есть РОДИТЕЛЬ 15 Рефлексивные отношения • Отношение R называется рефлексивным, если cRc справедливо для всех элементов c принадлежащих множеству. • Например, • Отношение МЕНЬШЕ ЧЕМ ИЛИ РАВНО (≤) является рефлексивным i ≤ i для всех действительных числе i, тогда как отношение МЕНЬШЕ ЧЕМ таковым не является 16 Транзитивные отношения • Отношение R называется транзитивным, если aRb и bRc влечет за собой aRc. • Отношение МЕНЬШЕ ЧЕМ над целыми числами является транзитивным. 17 Отношение РЕБЕНОК • Отношение РЕБЕНОК не является транзитивным ДЖИЛ ДЖЕК • Если Джон сын Джека и Джек сын Джила, то, очевидно, Джон не является сыном Джила. ДЖОН 18 Транзитивное замыкание • R+ - транзитивное замыкание R • Включается в любое транзитивное отношение, которое включает в себя R. • Другими словами, предположим, что P – транзитивное отношение, которое включает в себя R : из (c, d) ϵ R следует (c, d) ϵ P. Тогда P также включает в себя R+. 19 Произведение отношений • Если R и P определены на одном и том же множестве, то RP – произведение R и P: • cRPd тогда и только тогда, когда существует такое e, что cRe и ePd. • Умножение бинарных отношений ассоциативно: • P (RQ) = (RP) Q для любых отношений R, P и Q. 20 Пример • Рассмотрим отношения R и P над целыми числами • aRb тогда и только тогда, когда b = a + 1 • aPb тогда и только тогда, когда b = a+ 2 • Очевидно, что aRPb тогда и только тогда, когда есть такое c, что aRc и cPb, т.е. тогда и только тогда, когда b=a+3 21 Степени отношения • R1 = R, R2 = RR, Rn = Rn-1R = RRn-1 для n>1 • R0 – единичное отношение • aR0b тогда и только тогда, когда a = b 22 Транзитивное замыкание • R+ - транзитивное замыкание • aR+b тогда и только тогда, когда aRnb для некоторого n>0 • Очевидно, что если aRb, то и aR+b • R+ = R1 υ R2 υ R3… • … - цепочка, возможно пустая, которая в данный момент нас не интересует • Рефлексивное транзитивное замыкание R* • aR*b тогда и только тогда, когда a = b или aR+b • R* = R0 υ R1 υ R2 … 23 «ГОЛОВА» • Пусть задана грамматика и нетерминальный символ U • Необходимо знать множество головных символов в цепочке, выводимых из U • Если U=>+ Sx • =>+ - транзитивное замыкание отношения => • То цепочка Sx выводима из U и S принадлежит множеству. • U – голова • Голова (U) ::= {S | U=>+S…} • Т.е. «голова» - множество символов, с которых начинается правая часть правила для U 24 Отношение FIRST • Определим отношение FIRST (первый) для конечного словаря V грамматики следующим образом: • U FIRST S тогда и только тогда, когда существует правило U::=S… • U FIRST* S тогда и только тогда, когда существует непустая последовательность правил • U::=S1…, S1::=S2…., … Sn::=S… • U FIRST+ S тогда и только тогда, когда U=>+S… • Если отношение FIRST+ рассматривать как множество, то оно полностью определяет множество голова (U) для всех символов U словаря V: • голова (U)= {S | (U, S) в FIRST+} 25 Пример Правило Отношение A::=Af A FIRST A A::=B A FIRST B B::=DdC B FIRST D B::=De B FIRST D C::=e C FIRST e D::=Bf D FIRST B FIRST+: (A,A) (A,B) (A, D) (B, B) (B, D) (D, B) (D, D), (C, e) Следовательно, головными символами цепочек, выводимых из A, будут A, B и D, из B – B и D, из C - e 26 Отношение LAST • Множество символов, которыми оканчиваются цепочки, выводимые из некоторого символа U • U LAST S тогда и только тогда, когда существует правило • U::=…S 27 Отношение WITHIN • Множество внутренних символов цепочек, выводимых из нетерминала U • U WITHIN S, тогда и только тогда, когда существует правило: • U::=…S.. 28 Отношение SYMB • Множество символов S, которые выводимы из нетерминала U • U SYMB S тогда и только тогда, когда существует правило U::=S 29 3. Отношения предшествования 30 • Исходя из описанных положений построения отношений FIRST, LAST и WITHIN можно предложить систему отношений между символами, стоящими рядом в некоторой строке. 31 Отношения между символами • Пусть имеем два произвольных символа R, S ϵ (N+T) • Рассмотрим некоторую строку «…RS…» • R – левый символ (LEFT) • S – рядом стоящий правый символ (RIGHT) • Для того чтобы выделить предлог и произвести свертку, необходимо построить систему отношений между R и S 32 Система отношение между символами R и S 1. R ·= S – обе лексемы имеют один уровень предшествования и должны рассматриваться как составляющие одной конструкции языка и сворачиваться одновременно. Отношение носит название: равенство по предшествию. 2. R ·> S – R предшествует S ( выше по предшествованию). R находится в предлоге, а S – нет. R сворачивается раньше S. 3. R <· S – R не предшествует S (ниже по предшествованию). S находится в предлоге, а R – нет. S сворачивается раньше R. 4. Если отношение предшествования не существует, то такие лексемы не могут находиться рядом 33 Пример • • • • • A+B*C–D “+” – имеет более низкий уровень предшествования, чем “*” +<·* “*” – имеет более высокий уровень предшествования, чем – *·>– • Тогда A + B * C – D <· ·> Следовательно, подвыражение B * C должно быть обработано ранее 34 Пример Дана грамматика • Z ::= bMb • M ::= (L | a • L ::= Ma) • Запишем элементы грамматики с равными отношениями предшествования: 35 Сентенциальные формы (дерево) 36 Матрица предшествования для примера 37 Другая матрица предшествования 38 Основные особенности метода • Универсальность • Сложность реализации (необходимы специальные алгоритмы для автоматизации построения матрицы предшествия) • Строится на базе стека и таблицы предшествия. • Метод предшествия применим к языковым конструкциям, построенным на базе грамматик предшествования. 39 4. Определение грамматики предшествования 40 Грамматика предшествования типа (1,1) • Грамматика G называется простой грамматикой предшествования типа (1,1) если 1. Не более чем одно отношение имеется между любыми двумя рядом стоящими символами 2. Никакие два правила не имеют одинаковых правых частей 41 Грамматики с иными предшествиями • (n, m) – грамматики расширенного предшествования • Грамматики слабого предшествования • Грамматики смешанной стратегии предшествования • Грамматики операторного предшествования 42 Пример • Разбор предложения •#b(aa)b# 43 Алгоритм разбора на основе простого предшествования • i – индекс стека • S, к – индекс символа в строке разбора • R – текущий символ в строке разбора • Предложение будет соответствовать грамматике, если в конце разбора i = 2, S(i) = Z и R = # 44 Алгоритм разбора на основе простого предшествования i=1 k=1 S(i)=# нет S(i) -> R? R=Tk i=i+1 S(i)=R k=k+1 да j=1 S(j-1) S(j), то проводим дугу из S(i) в S(j) • Если S(i) <· = S(j), то проводим дугу из S(j) в S(i) 3. Подсчитывается количество вершин, доступных из каждой вершины с помощью переходов +1. Это и будет значением соответствующей функции для вершины. 49 Алгоритм построения функций предшествия Для грамматики из предыдущего примера: R\f S\g Z Z b b M M f(Z)=1, f(M)=2, g(Z)=2 50 Пример. Таблица функций предшествия • Для предыдущей матрицы предшествия значения функций предшествия могут быть представлены так: 51 5. Операторное предшествование и операторные грамматики 52 Операторное предшествование • Каждому оператору языка ставится уровень предшествования. Но основе этого уровня выносится решение о том, какой оператор должен выполняться раньше. • В терминах синтаксического дерева это означает, что оператор с более высоким уровнем предшествования ближе к листьям дерева и, соответственно, дальше от корня. • В рамках этого метода анализируемое предложение сканируется слева направо, пока не будет найдено подвыражение, операторы которого имеют более высокий уровень предшествования. • Это подвыражение распознается в терминах правил вывода используемой грамматики и заменяется соответствующим нетерминалом. • Процесс продолжается, пока предложение не будет распознано целиком. 53 Пример А+B*C–D + имеет более низкий уровень предшествования, чем * (+ <· *) * имеет более высокий уровень предшествования, чем - (* ·> -) Тогда, А + B * C – D <· ·> Следовательно, подвыражение B * C должно быть обработано ранее 54 Метод операторного предшествования • В рамках этого метода анализируемое предложение сканируется слева направо, пока не будет найдено подвыражение, операторы которого имеют более высокий уровень предшествования. • Это подвыражение распознается в терминах правил вывода используемой грамматики и заменяется соответствующим нетерминалом. • Процесс продолжается, пока предложение не будет распознано целиком. 55 • Матрица предшествия операторов меньше полной матрицы предшествия. • Рассматриваются отношения только между операторами и обобщенным символом идентификатора - i 56 Пример • В реализации этого метода используется 2 стека: • Стек операторов OPTOR • Стек операндов OPAND • В стеке операторов может находиться • Признак начала/конца предложения ”#” • Символ стека S(i) 57 Алгоритм метода 1. Если R – идентификатор, то он помещается в стек операндов 2. Если f(S(i)) <= g(R), то R помещается в стек операторов 3. Если f(S(i)) > g(R), то вызывается некоторая семантическая процедура для S(i), с ее помощью из стека удаляются и, возможно, некоторые другие операторы и/или операнды. 4. Переход к шагу 1. 58 Пример • #A + B + C# • Переменная Ti хранит результат действия семантической процедуры (результат предыдущего действия) 59 Преимущества/недостатки • Преимущество • удобно реализовывать семантические процедуры • Недостатки • Необходимость помещать одноместные операторы отдельно, т.е. (-B+C) содержимое между скобками должно быть обработано в одной процедуре • Метод применим только к операторным грамматикам 60 • Использование операторной грамматики – это еще один из методов разбора снизу-вверх. • В этом методе ищется не предлог, а так называемая первичная фраза, то есть последовательность символов Tj, которые заключены между знаками «< ·» и «· > » 61 ОПРЕДЕЛЕНИЯ (1) • Определение 1: грамматика является операторной, если не имеет правил формы U::=…VW…, где V и W нетерминалы (т.е. нахождение в правых частях правил двух РЯДОМ стоящих нетерминальных символов запрещено) • Определение 2: операторная грамматика является грамматикой предшествия операторов, если существует не более одного отношения между двумя любыми терминалами. 62 ОПРЕДЕЛЕНИЯ (2) • Определение 3: пусть имеем операторную грамматики, тогда: • R · = S, тогда и только тогда, когда имеется правило U::=…RS… или U::=…RVS…, где V нетерминал • R < · S, тогда и только тогда, когда имеется правило U::=…RW…, W=>+S…, или W=>+VS… • R · > S, тогда и только тогда, когда имеется правило U::=…WS…, W=>+…R, или W=>+…RV 63 Пример. Матрица предшествия операторов Грамматика: • E ::= E+T | T • T ::= T * F | F • F ::= (E) | i • R – первый оператор в строке • S – последующий • i – обобщенный идентификатор 64 Пример Строка разбора i * (i + i) 65 • В данном методе нетерминальные символы не имеют весомого значения – нам не важно, какой именно символ – F, T или E стоит внутри правой части правила – важно, что это нетерминал. N представляет постановку для ЛЮБОГО нетерминального символа 66 Общая идея • Ищется конец первичной фразы. • Первичная фраза заменяется на соответствующую ей строку с использованием нетерминала N, так как все нетерминалы могут быть заменены этим символом • В конце разбора: N – начальный символ грамматики 67 Спасибо за внимание! 68