Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
: , , ! , , , / , , , ; , ( , ) , d c ´0´; gc(); gc(); clear(); add(); gc(); gc(); clear( ); add( ); gc(); j look(buf, TD); Lex(dlms[j], j); add( ); gc(); j look(buf, TD); Lex(dlms[j], j); Lex(LEX_FIN); gc() ; Lex(LEX_NEQ); j look(buf, TD); Lex(dlms[j], j); Lex(LEX_NUM, d); j look(buf, TW); Lex(words[j], j); или j TID.put(buf); Lex(LEX_ID, j); Элементы теории трансляции / Задачи лексического анализа 45 На рис. 9 приведена диаграмма состояний для модельного языка. Лексический анализ может проводиться независимо от последующих этапов трансляции. В этом случае исходный файл с текстом программы преобразуется в последовательность лексем во внутреннем пред- ставлении согласно построенной ДС; затем эта последовательность подается на вход синтак- сическому анализатору. Мы реализуем другой подход: лексический анализатор выдает очередную лексему по требованию синтаксического анализатора и затем «замирает», пока к нему не обратятся за следующей лексемой. При таком подходе действие Lex(k, l); в ДС означает return Lex(k, l);. Кроме того, вместо перехода в состояние ошибки ER генерируется исключение с указанием символа, который привел к ошибочной ситуации. Перехватываться и обрабатываться ис- ключения будут не в лексическом анализаторе, а в основной программе, содержащей анали- затор. Обработка исключения состоит в выводе сообщения об ошибке и корректном завер- шении программы. Непосредственно реализует ЛА по ДС функция get_lex(): Lex Scanner::get_lex () { int d, j; CS = H; do { switch ( CS ) { case H: if ( c ==' ' || c =='\n' || c=='\r' || c =='\t' ) gc (); else if ( isalpha(c) ) { clear (); add (); gc (); CS = IDENT; } else if ( isdigit(c) ) { d = c - '0'; gc (); CS = NUMB; } else if ( c== '{' ) { gc (); CS = COM; } else if ( c== ':' || c== '<' || c== '>') { clear (); add (); gc (); CS = ALE; } else if ( c == '@' ) return Lex(LEX_FIN); Элементы теории трансляции / Задачи лексического анализа 46 else if ( c == '!' ) { clear (); add (); gc (); CS = NEQ; } else CS = DELIM; break; case IDENT: if ( isalpha(c) || isdigit(c) ) { add (); gc (); } else if ( j = look (buf, TW) ) return Lex (words[j], j); else { j = TID.put(buf); return Lex (LEX_ID, j); } break; case NUMB: if ( isdigit(c) ) { d = d * 10 (c - '0'); gc(); } else return Lex ( LEX_NUM, d ); break; case COM: if ( c == '}' ) { gc (); CS = H; } else if (c == '@' || c == '{' ) throw c; else gc (); break; case ALE: if ( c == '=' ) { add (); gc (); j = look ( buf, TD ); return Lex ( dlms[j], j ); } else { Элементы теории трансляции / Синтаксический анализ 47 j = look (buf, TD); return Lex ( dlms[j], j ); } break; case NEQ: if ( c == '=' ) { add (); gc (); j = look ( buf, TD ); return Lex ( LEX_NEQ, j ); } else throw '!'; break; case DELIM: clear (); add (); if ( j = look(buf, TD) ) { gc (); return Lex ( dlms[j], j ); } else throw c; break; } // end switch } while ( true ); } Можно упростить реализацию метода get_lex(), вынеся обращение к gc() из тела switch и вставив его непосредственно перед оператором switch. Синтаксический анализ На этапе синтаксического анализа нужно: 1) установить, имеет ли цепочка лексем структуру, заданную синтаксисом язы- ка, и 2) зафиксировать эту структуру. Следовательно, снова надо решать задачу разбора: дана цепочка лексем, и надо опре- делить, выводима ли она в грамматике, определяющей синтаксис языка. Если да, то постро- ить вывод этой цепочки или дерево вывода. Однако структура таких конструкций как выра- жение, описание, оператор и т.п., более сложная, чем структура идентификаторов и чисел. Поэтому для описания синтаксиса языков программирования нужны более мощные грамма- тики, чем регулярные. Обычно для этого используют КС-грамматики, правила которых име- ют вид A → , где A N, (T N ) * . Грамматики этого класса, с одной стороны, позволя- ют вполне адекватно описать синтаксис реальных языков программирования; с другой сто- роны, для разных подклассов КС-грамматик построены достаточно эффективные алгоритмы разбора. Элементы теории трансляции / Синтаксический анализ 48 Из теории синтаксического анализа известно, что существует алгоритм, который по любой данной КС-грамматике и данной цепочке выясняет, принадлежит ли цепочка языку, порождаемому этой грамматикой. Но время работы такого алгоритма (синтаксического ана- лиза с возвратами) экспоненциально зависит от длины цепочки, что с практической точки зрения совершенно неприемлемо. Существуют табличные методы анализа ([3]), применимые ко всему классу КС- грамматик и требующие для разбора цепочек длины n времени Cn 3 (алгоритм Кока-Янгера- Касами), где C — константа, либо Cn 2 (алгоритм Эрли). Их разумно применять только в том случае, если для интересующего нас языка не существует грамматики, по которой можно по- строить анализатор с линейной временной зависимостью от длины цепочки (такими языками могут быть, например, подмножества естественного языка). При разработке языков программирования их синтаксис обычно стараются сделать таким, чтобы время на анализ было прямо пропорционально длине программы. Алгоритмы анализа, расходующие на обработку входной цепочки линейное время, применимы только к некоторым подклассам КС-грамматик. Различные методы синтаксического анализа, или разбора, основываются на разных принципах, и используют различные техники построения дерева вывода. Каждый метод предполагает свой способ построения по грамматике программы-анализатора, которая будет осуществлять разбор цепочек. Корректный анализатор завершает свою работу для любой входной цепочки и выдает верный ответ о принадлежности цепочки языку. Анализатор не- корректен, если: не распознает хотя бы одну цепочку, принадлежащую языку; распознает хотя бы одну цепочку, языку не принадлежащую; зацикливается на какой-либо цепочке. Говорят, что метод анализа примени м к данной грамматике, если анализатор, постро- енный в соответствии с этим методом, корректен. Рассмотрим один из фундаментальных методов разбора, применимый к некоторому подклассу КС-грамматик. Метод рекурсивного спуска Пример: пусть дана грамматика G 1 {a, b, c, d}, {S, A, B}, P, S , где P: S → ABd A → a | cA B → bA и надо определить, принадлежит ли цепочка cabad языку L(G 1 ). Построим левый вывод этой цепочки: S → ABd → cABd → caBd → cabAd → cabad. Следовательно, цепочка cabad принадлежит языку L(G 1 ). Построение левого вывода эквивалентно построению дерева вывода методом сверху- вниз (нисходящим методом), при котором на очередном шаге раскрывается самый левый не- терминал в частично построенном дереве ( рис. 10): Элементы теории трансляции / Синтаксический анализ 49 S b a d a c S A b a d a c B S A b a d a c B A S A b a d a c B A S A b a A d a c B A S A b a A d a c B A Рис. 10. Построение левого вывода. Метод рекурсивного спуска (РС-метод) реализует разбор сверху-вниз и делает это с помощью системы рекурсивных процедур. Для каждого нетерминала грамматики создается своя процедура, носящая его имя; ее задача — начиная с указанного места исходной цепочки найти подцепочку, которая выво- дится из этого нетерминала. Если такую подцепочку найти не удается, то процедура завершает свою работу, сиг- нализируя об ошибке. Это означает, что цепочка не принадлежит языку; разбор останавлива- ется. Если подцепочку удалось найти, то работа процедуры считается нормально завер- шенной и осуществляется возврат в точку вызова. Тело каждой такой процедуры пишется непосредственно по правилам вывода (по аль- тернативам) соответствующего нетерминала: для правой части каждого правила осуществля- ется поиск подцепочки, выводимой из этой правой части. При этом терминалы из правой ча- сти распознаются самой процедурой, а нетерминалы соответствуют вызовам процедур, но- сящих их имена. После распознавания каждого терминала процедура считывает следующий символ из исходной цепочки, который становится текущим анализируемым символом. Вы- бор нужной альтернативы осуществляется процедурой по первому символу из еще нерас- смотренной части исходной цепочки (т. е. по текущему символу). Работа системы процедур начинается с главной функции main( ). Она считывает пер- вый символ исходной цепочки (заданной во входном потоке stdin) и вызывает процедуру S( ), которая проверяет, выводится ли входная цепочка из начального символа S (в общем случае это делается с участием других процедур, которые, в свою очередь, рекурсивно могут вызы- вать и саму S( ) для анализа фрагмента исходной цепочки). Будем полагать, что в конце лю- бой анализируемой цепочки всегда присутствует символ (признак конца цепочки) 16) , так что в задачу main( ) входит также распознавание символа . Можно считать, что main( ) соот- ветствует добавленному в грамматику правилу M → S , где M — новый начальный символ. 16) На практике этим признаком может быть ситуация «конец файла» или «конец строки». Элементы теории трансляции / Синтаксический анализ 50 Пример. Совокупность процедур рекурсивного спуска для грамматики G 1 : S → ABd A → a | cA B → bA будет такой: #include { cin >> c; // считать очередной символ } void S () { cout << "S-->ABd, "; // применяемое правило вывода A(); B(); if ( c != 'd' ) throw c; gc (); } void A () { if ( c =='a' ) { cout << "A-->a, "; gc (); } else if ( c =='c' ) { cout << "A-->cA, "; gc (); A (); } else throw c; } void B () { if ( c =='b' ) { cout << "B-->bA, "; gc (); A (); } Элементы теории трансляции / Синтаксический анализ 51 else throw c; } int main () { try { gc (); S (); if ( c != ' ' ) throw c; cout << "SUCCESS !!!" << endl; return 0; } catch ( int c ) { cout << "ERROR on lexeme" << c << endl; return 1; } } Для цепочки, выводимой из S,программа напечатает (помимо сообщения об успехе) последовательность правил, применяемых при нисходящем построении дерева вывода для данной цепочки (эта же последовательность годится для построения левого вывода). Вместо печати применяемых правил можно вставить действия по формированию дерева в динамиче- ской памяти в виде узлов, связанных указателями. Такое дерево может использоваться на по- следующих этапах трансляции. Заметим, что даже если специально не фиксировать структуру анализируемой цепоч- ки, система рекурсивных процедур все равно неявно обходит дерево вывода этой цепочки. Действительно, распознавание терминала b процедурой B( )соответствует в дереве вывода вет- ви b B, а вызов процедуры A( ) из процедуры B( ) соответствует ветви B A . Добавив в процедуры анализа дополнительные действия, можно наряду с проверкой синтаксиса определять смысл (семантику) входной цепочки. Например, смыслом арифметического выражения является его значение, и оно может быть вычислено в процессе неявного обхода дерева при разборе этого выражения системой рекурсивных процедур. Выбор нужной альтернативы при анализе методом рекурсивного спуска легко осуще- ствим, если все альтернативы начинаются с попарно различных терминальных символов. Сформулируем достаточное условие применимости метода рекурсивного спуска. Достаточное условие применимости метода рекурсивного спуска Для применимости метода рекурсивного спуска достаточно, чтобы каждое правило в грамматике удовлетворяло одному из двух видов: (а) X → , где (T N ) * и это единственное правило вывода для этого нетерминала; (б) X → a 1 1 | a 2 2 | ... | a n n , Элементы теории трансляции / Синтаксический анализ 52 где a i T для всех i 1, 2,..., n ; a i a j для i j; i (T N ) * , т. е. если для не- терминала X правил вывода несколько, то они должны начинаться с термина- лов, причем все эти терминалы должны быть попарно различными; Это условие не является необходимым. Грамматику, удовлетворяющую данному условию, называют s-грамматикой. Метод рекурсивного спуска является одной из возможных реализаций нисходящего анализа с прогнозируемым выбором альтернатив. Прогнозируемый выбор означает, что по грамматике можно заранее предсказать, какую альтернативу нужно будет выбрать на оче- редном шаге вывода в соответствии с текущим символом (т.е. первым символом из еще не прочитанной части входной цепочки). Далее мы подробно рассмотрим этот подход и сфор- мулируем критерий его применимости. Нисходящий анализ с прогнозируемым выбором альтернатив В процессе построения левого вывода для произвольной цепочки в грамматике G 1 : S → ABd A → a | cA B → bA можно отметить следующее: (1) любой вывод начинается с применения правила S → ABd ; (2) если на очередном шаге сентенциальная форма имеет вид wB , где w T — начало анализируемой цепочки, нетерминал B — самый левый в сентенциальной форме, то для продолжения вывода его нужно заменить на bA (других альтерна- тив нет); (3) если на очередном шаге сентенциальная форма имеет вид wA , где w T — начало анализируемой цепочки, то выбор нужной альтернативы для замены A можно однозначно предсказать по тому, какой символ в анализируемой цепочке следует за начальной подцепочкой w: если символ a, то применяется альтернатива A → a, если символ c, то альтернатива A → cA;если какой-то иной символ — фиксируется ошибка: анализируемая цепочка не принадлежит языку L(G 1 ); (4) если на каком-то шаге получилась сентенциальная форма вида w , отличная от (2) и (3), где w — максимально длинное начало, состоящее только из терминалов, то если пуста и w совпадает с анализируемой цепочкой, процесс вывода успеш- но завершается, иначе фиксируется ошибка: анализируемая цепочка не принад- лежит языку L(G 1 ). Отмеченные факты по поводу выбора нужной альтернативы на очередном шаге выво- да в грамматике G 1 представим в виде так называемой таблицы прогнозов (или таблицы предсказаний): a b c d S S → ABd S → ABd S → ABd S → ABd A A → a A → cA B B → bA Имея такую таблицу прогнозов (предсказаний) для КС-грамматики G, можно предло- жить следующий алгоритм нисходящего анализа (построение левого вывода): Элементы теории трансляции / Синтаксический анализ 53 1. Начать построение вывода с сентенциальной формы, состоящей из одного началь- ного символа S. 2. Пока не будет получена цепочка, совпадающая с анализируемой, повторять следу- ющие действия: Пусть wY — очередная сентенциальная форма, где w T . Если w не совпадает с началом анализируемой цепочки, то прекратить построение вывода и сообщить об ошибке: цепочка не принадлежит L(G). В случае, когда w совпа- дает с началом, и следующим после w символом в анализируемой цепочке яв- ляется символ z,заменить нетерминал Y на правую часть правила, которое находится в ячейке таблицы прогнозов на пересечении строки Y и столбца z. Если указанная ячейка пуста, прекратить построение вывода и сообщить об ошибке: цепочка не принадлежит L(G). Как мы видели выше, один из способов реализовать программу-анализатор для нис- ходящего анализа с прогнозируемым выбором альтернатив заключается в построении систе- мы рекурсивных процедур 17) . Это метод рекурсивного спуска. Техника построения рекурсивных процедур уже была рассмотрена и продемонстри- рована на примере, но остался открытым вопрос: как в общем случае «запрограммировать» процедуру на выбор нужной альтернативы по текущему символу. Ответ теперь известен — использовать таблицу прогнозов. К сожалению, не для каждой КС-грамматики существует таблица с однозначными прогнозами, позволяющая безошибочно осуществить выбор альтернативы на каждом шаге вывода. В некоторых случаях заранее спрогнозировать выбор альтернативы невозможно: может оказаться, что подходящими в данной ситуации являются сразу несколько альтерна- тив (неоднозначный прогноз) 18) Таким образом, нисходящий анализ с прогнозируемым выбором альтернатив приго- ден лишь для некоторого подкласса КС-грамматик. Метод рекурсивного спуска примени м к грамматике, если для нее существует таблица однозначных прогнозов. О применимости метода рекурсивного спуска Очевидно, что метод рекурсивного спуска (без возвратов) непримени м к неоднознач- ным грамматикам. Например, по грамматике G 2 : S → aA |B | d A → d | aA B → aA | a 17) Другой способ, с явным использованием стека для хранения нетерминальной части сентенциальной формы, известен как LL(1)-анализатор. 18) Обобщение рассматриваемого метода — рекурсивный спуск с возвратами — «пробует» по очереди все воз- можные альтернативы в случае неоднозначного прогноза; о неудаче сообщается только в том случае, если ни одна из альтернатив не привела к успеху. Если грамматика неоднозначна, обобщенный метод построит все возможные деревья выводов. Мы не рассматриваем подробно рекурсивный спуск с возвратами, по- скольку время, затрачиваемое на анализ при таком подходе, может экспоненциально зависеть от длины входной цепочки. Элементы теории трансляции / Синтаксический анализ 54 нельзя дать однозначный прогноз, что делатьна первом шаге при анализе цепочки, начина- ющейся с символа a, т.е. по текущему символу a невозможно сделать однозначный выбор: S → aA или S → B . Как показывает следующий пример, грамматика может быть однозначной, однако од- нозначных прогнозов для нее также не существует: G 3 : S → A | B A → aA | d B → aB | b Действительно, каждая цепочка, выводимая в G 3 из S, оканчивается либо символом b, либо символом d, и имеет единственное дерево вывода. Но невозможно предсказать, с какой альтернативы ( S → A или S → B ) начинать вывод, не просмотрев всю цепочку до конца и не увидев последний символ. Наличие в грамматике нетерминала X справилами вида X → и X → , из правых частей которых выводятся цепочки, начинающиеся одним и тем же терминалом a, т. е. a и a , делает неоднозначным прогноз по символу a. Так что нисходящий ана- лиз с прогнозируемым выбором альтернатив невозможен по такой грамматике, и метод ре- курсивного спуска непримени м. Сформулируем это условие более формально. |