Лекции (1) (Презентации лекций (PDF))

Синтаксический анализЗадачи синтаксического анализа установить, имеет ли цепочка лексем структуру, заданную синтаксисомязыка, т.е. решить задачу разбора по заданной грамматике, зафиксировать эту структуру.Для описания синтаксиса языков программирования используются КСграмматики, правила которых имеют видA → ,где A  N,   (T  N)*.Для разных подклассов КС-грамматик существуют достаточно эффективныеалгоритмы разбора.Некоторые общие алгоритмы анализа по КС-грамматикам:- синтаксический анализ с возвратами(время работы экспоненциально зависит от длины цепочки);- алгоритм Кока-Янгера-Касами(для разбора цепочек длины n требуется время cn3 );- алгоритм Эрли(для разбора цепочек длины n требуется время cn3 ).Эти (и подобные им по времени работы) алгоритмы практически неприемлемы.Алгоритмы анализа, расходующие на обработку входной цепочки линейноевремя, применимы только к некоторым подклассам КС-грамматик.Применимость синтаксических анализаторовКаждый метод синтаксического анализа основан на своей техникепостроения дерева вывода и предполагает свой способ построения пограмматике программы-анализатора, которая будет осуществлять разборцепочек.Корректный анализатор завершает свою работу для любой входнойцепочки и выдает верный ответ о принадлежности цепочки языку.Анализатор некорректен, если:не распознает хотя бы одну цепочку, принадлежащую языку;распознает хотя бы одну цепочку, языку не принадлежащую;зацикливается на какой-либо цепочке.Метод анализа применим к данной грамматике, если анализатор,построенный в соответствии с этим методом, корректен и строит всевозможные выводы цепочек в данной грамматике.Метод рекурсивного спуска (РС-метод)Пусть дана грамматикаP:S → ABA → a | cAB → bAG_рс = ({ a,b,c,  }, { S,A,B }, P, S), гдеL(G) = { cnabcma | n,m >=0 }и надо определить, принадлежит ли цепочка caba языку L(G).Построим вывод этой цепочки:S → AB → cAB → caB → cabA → cabaСледовательно, цепочка принадлежит языку L(G).Последовательность применений правил вывода эквивалентнапостроению дерева разбора методом "сверху вниз”, а методрекурсивного спуска фактически реализует этот способ разбора.SSAcabcaBabaSSABAABAcabacabaSSABAAABAcabaAcabaМетод рекурсивного спуска (РС-метод)Для каждого нетерминала грамматики создается своя процедура, носящаяего имя; задача этой процедуры - начиная с указанного места исходнойцепочки, найти подцепочку, которая выводится из этого нетерминала.Если такую подцепочку считать не удается, то процедура завершает своюработу, сигнализируя об ошибке, что означает, что цепочка не принадлежитязыку, и останавливая разбор.Если подцепочку удалось найти, то работа процедуры считается нормальнозавершенной и осуществляется возврат в точку вызова.Тело каждой такой процедуры пишется непосредственно по правиламвывода из соответствующего нетерминала.Текущая анализируемая лексема входной цепочки должны быть ужепрочитана и доступна в процедуре, именно по ней осуществляется выборнужной альтернативы.Для каждой альтернативы из правой части правила вывода осуществляетсяпоиск подцепочки, выводимой из этой альтернативы.

При этом:- терминалы проверяются в самой процедуре, ив случае удачной проверки считывается очередная лексема;- нетерминалам соответствуют вызовы процедур,носящих их имена.Метод рекурсивного спускаРабота системы процедур, построенных в соответствии с РС-методом,начинается с главной функции main ( ), которая:считывает первый символ исходной цепочки(заданной во входном потоке stdin),затем вызывает процедуру S ( ), которая проверяет, выводится ливходная цепочка из начального символа S(в общем случае это делается с участием других процедур,которые, в свою очередь, рекурсивно могут вызывать и саму S ( )для анализа фрагментов исходной цепочки).Считаем, что в конце любой анализируемой цепочки всегдаприсутствует символ  (признак конца цепочки).

На практике этимпризнаком может быть ситуация «конец файла» или маркер «конецстроки».В задачу main ( ) входит также распознавание символа .Можно считать, что main ( ) соответствует добавленному в грамматикуправилу M → S , где M — новый начальный символ.Реализация РС-метода для грамматики G_рс.int c;void A ( );void B ( );void gc ( ) {cin >> c;}void A ( ) {if (c == 'a') gc ();elseif (c == 'c') { gc ( ); A ( ); }else throw c;}void S ( ) {А ( );B ( );if (c != '')}void B ( ) {if (c == 'b') { gc ( ); A ( ); }else throw c;}throw c;int main ( ) {try { gc ( );S ( );cout << "SUCCESS !!!" << endl;return 0;}catch ( int c ) {cout << "ERROR on lexeme" << c << endl;return 1;}}Достаточное условие применимости РС-методаМетод рекурсивного спуска применим к КС-грамматике, если каждая ее группаправил вывода из А имеет один из следующих видов:1.

либо A →  ,где   (T  N)*и это единственное правило выводадля этого нетерминала;2. либо A → a11 | a22 | ... | ann ,где ai  T для всех i = 1, 2,..., n ; ai  aj для i  j; i  (T  N)*,3. либо A → a11 | a22 | ... | ann |  ,где ai  T для всех i = 1, 2,..., n ; ai  aj для i  j; i  (T  N)*,и first (A)  follow (A) = .Множество first (A) - это множество терминальных символов, которыминачинаются цепочки, выводимые из А в грамматике G = (T, N, P, S):first (А)  { a  T | А  a, где А  N,   ( T  N )* }.Множество follow (A) - это множество терминальных символов, которыеследуют за цепочками, выводимыми из А в грамматике G = (T, N, P, S),follow (A)  { a  T | S  A,   a , A  N, , ,   (T  N)*}.Если все правила вывода заданной КС-грамматики G удовлетворяютуказанному условию, то РС-метод к ней применим, при этом грамматика Gназывается грамматикой канонического вида для РС-метода.О применимости РС-методаСформулированное выше условие не является необходимым.Метод рекурсивного спуска представляет собой одну из возможных реализацийнисходящего анализа с прогнозируемым выбором альтернатив.Прогнозируемый выбор означает, что по грамматике можно заранеепредсказать, какую альтернативу нужно будет выбрать на очередном шагевывода в соответствии с текущим символом (т.е.

первым символом из еще непрочитанной части входной цепочки).РС-метод неприменим, если такой выбор неоднозначен.Например, для грамматикиG:S→A|BA → aA | dB → aB | bРС-метод неприменим, поскольку, если первый прочитанный символ есть ‘а’, товыбор альтернативы правила вывода из S неоднозначен.РС-метод неприменим к неоднозначным грамматикам, так как на каком-либошаге анализа выбор альтернативы вывода обязательно будет неоднозначным.Критерий применимости РС-методаПусть G — КС-грамматика.РС-метод применим к G, тогда и только тогда, когда для любой парыальтернативX→|выполняются следующие условия:1.2.3.first()  first ()   ;справедливо не более чем одно из двух соотношений:  ,    ;если    , то first()  follow( X )   .Множество first () — это множество терминальных символов,которыми начинаются цепочки, выводимые из цепочки  в грамматикеG  ( T, N, P, S ), т.

е.first ()  { a  T |   a, где   ( T  N )+,   ( T  N )* }.Множество follow(A) — это множество терминальных символов,которые могут появляться в сентенциальных формах грамматикиG  (T, N, P, S) непосредственно справа от A (или от цепочек, выводимыхиз A) , т.е.follow(A)  { a  T | S  A,   a , A  N, , ,   (T  N)*}.Итерационные правила в КС-грамматикахНаличие в грамматике итерационных правил видаА→{},где А  N,   ( T  N )+, ,   (T  N)*скрывает правила с -альтернативой.Чтобы проверить грамматику с итерационными правилами на применимостьРС-метода, надо заменить итерационные правила обычными правиламиследующим образом: каждое правило видаА→{}заменить на два правилаА→WW → W |  ,(где W – новый нетерминал, ранее не принадлежавший множеству N),а затем поверить критерий применимости РС-метода.Процедура по РС-методу для итерационных правил пишется по следующейсхеме:void A () {< анализ цепочки  >;while (<текущий_символ_входной_цепочки == первый_символ_  >)< анализ цепочки  >;< анализ цепочки  >;}Преобразования грамматикПроблема возможности построения грамматики, к которой применимметод рекурсивного спуска, эквивалентной грамматике, неудовлетворяющей критерию применимости РС-метода, являетсяалгоритмически неразрешимой проблемой.1) Если в грамматике есть нетерминалы, правила вывода которыхлеворекурсивны, т.е.

имеют видA → A1 | ... | An | 1 | ... | m,//A → A | где i  (T  N)+, j  (T  N)*, i = 1, 2, ..., n; j =1, 2 ,..., m,то непосредственно применять РС-метод нельзя.Левую рекурсию всегда можно заменить правой:A → 1A’ | ... | mA’A’ → 1A’ | ... | nA’ | // A → A’// A’ → A’ | Будет получена грамматика, эквивалентная данной, т.к. изнетерминала A по-прежнему выводятся цепочки видаj {i}, где i = 1,2,...,n; j = 1,2,...,m.Преобразования грамматик2) Если в грамматике есть нетерминал, у которого несколько правилвывода, и среди них есть правила, начинающиеся нетерминальнымисимволами, т.е.