Синтаксический анализ

Во время синтаксического анализа предложения исходной программы распознаются как языковые конструкции, описывае­мые используемой грамматикой. Мы можем рассматривать этот процесс как построение дерева грамматического разбора для транслируемых предложений. Методы грамматического разбора можно разбить на два больших класса — восходящие и нисходящие—в соответствии с порядком построения дерева грамматического разбора. Нисходящие методы (методы сверху вниз) начинают с правила грамматики, определяющего конечную цель анализа с корня дерева грамматического разбора, и пытаются так его наращивать, чтобы последующие узлы дерева соответствовали синтаксису анализируемого предложения. Вос­ходящие методы (методы снизу вверх) начинают с конечных узлов дерева грамматического разбора и пытаются объединить их построением узлов все более и более высокого уровня до тех пор, пока не будет достигнут корень дерева.

Разработано множество методов грамматического разбора, большинство из которых применимо лишь к грамматикам удовлетворяющим определенным требованиям. В этом разделе мы кратко опишем один нисходящий и одни восходящий метод, а также продемонстрируем применение этих методов к нашему примеру программы. Мы не собираемся описывать все детали обоих методов. Вместо этого мы попытаемся продемонстрировать общий подход и снабдить ссылками читателей, желающих изучить эти методы более подробно.

Восходящий метод грамматического разбора, который мы рассмотрим, называется методом операторного предшествовавания. Он основан на анализе пар последовательно расположен­ных операторов исходной программы и решении вопроса о том, какой из них должен выполняться первым. Рассмотрим, например, арифметическое выражение

A+B*C-D

В соответствии с обычными правилами арифметики умножение и деление осуществляются до сложения и вычитания. Можно сказать, что умножение и деление имеют более высокий уровень предшествования, чем сложение и вычитание. При анализе первых двух операторов (+ и *) выяснится, что оператор +, имеет более низкий уровень предшествования, чем оператор *. Часто это записывают следующим образом:

+ <• *

Аналогично для следующей пары операторов (* и —) оператор * имеет более высокий уровень предшествования, чем оператор —. Мы можем записать это в виде

* •> —

Метод операторного предшествования использует подобные отношения между операторами для управления процессом грамматического разбора. В частности, для рассмотренного арифметического выражения мы получили следующие отношения предшествования:

А + В * С — D
<• •>

Отсюда следует, что подвыражение В*С должно быть вычислено до обработки любых других операторов рассматриваемого выражения, В терминах дерева грамматического разбора это означает, что операция * расположена на более низком уровне узлов дерева, чем операции + или —. Таким образом, рассматриваемый метод грамматического разбора должен распознать конструкцию В*С, интерпретируя ее в терминах заданной грамматики, до анализа соседних термов предложения.

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

Первым шагом при разработке процессора грамматического разбора, основанного на методе операторного предшествования, должно быть установление отношений предшествования между операторами грамматики. При этом под оператором понимается любой терминальный символ (т. е. любая лексема). Таким образом, мы должны, в частности, установить отношение предше­ствования между лексемами BEGIN, READ, id, ( и ). Матрица на рис. 7 задаст отношения предшествования для грамматики, приведенной на рис. 2. Каждая клетка этой матрицы опреде­ляет отношение предшествования (если оно существует) между лексемами, соответствующими строке и столбцу, на пересечении которых находится эта клетка. Например, мы видим, что

PROGRAM == VAR

и

BEGIN <• FOR

Отношение == означает, что обе лексемы имеют одинаковый уровень предшествования и должны рассматриваться грамматическим процессором в качестве составляющих одной конструк­ции языка. Обратите внимание, что для отношения предше­ствования не выполняются некоторые правила, привычные для отношения арифметического порядка. Например,

; •> END но END •> ;

Обратите внимание также на то, что для многих пар лексем отношение предшествования не существует. Это означает, что соответствующие пары лексем не могут находиться рядом ни в каком грамматически правильном предложении. Если подоб­ная комбинация лексем все же встретится в процессе грамматического разбора, то она должна рассматриваться как синтаксическая ошибка.

Существуют алгоритмы автоматического построения матриц предшествования, подобных изображенной на рис. 7, на осно­ве описания грамматики (см., например, Ахо (1977]). Для при­менимости метода операторного предшествования необходимо, чтобы отношения предшествования были заданы однозначно. Например, не должно быть одновременно отношений ; <• BEGIN и ; •> BEGIN. Это требование выполняется для грамматики рис. 5.2, однако надо иметь в виду, что несущественные ее изменения могут привести к тому, что некоторые из отношений перестанут быть однозначными и метод операторного предше­ствования станет неприменимым.

На рис. 8 изображен результат применения метода операторного предшествования к двум предложениям программы рис. 1. На рис. 8а изображен анализ предложения READ строки 9 этой программы. Это предложение анализируется по лексемам слева направо. Для каждой пары соседних операторов определено отношение предшествования. В строке (i) на рис. 8а процессор грамматического разбора выделил фрагмент, ограниченный отношениями <• и •>, для распознавания в терминах грамматики. В данном случае этот фрагмент содержит единственную лексему id. Эта лексема может быть распознана как нетерминальный символ <factor> в соответствии с грамматическим правилом 12. Однако эта лексема может быть также распознана как нетерминальные символы <prog—name> (правило 2) и <id—list> (правило 6). Для рассматриваемого метода не важно, какой конкретно нетерминальный символ рас­познан. Лексема id интерпретируется просто как некоторый нетерминальный символ <n₁>. В строке (ii) на рис. 8а изображен результат анализа предложения, в котором лексема id заменена па <N₁>. Из него следует, что далее надо распозна­вать правый фрагмент предложения.

Строка (ii) на рис. 8а также изображает отношение предшествования для новой версии анализируемого предложения. Процессор грамматического разбора, основанный на отношении предшествования, обычно использует стек для хранения полученных от сканера (но еще грамматически не распознанных) лексем для их последующего распознавания. Отношения пред­шествования определены лишь для терминальных символов. Таким образом, нетерминальный символ <N₁> не будет вовле­чен в этот процесс, и далее отношения предшествования будут установлены между терминальными символами ( и ). В данном случае для последующего распознавания будет выделен фрагмент

READ (<N₁>)

который соответствует, за исключением имени нетерминального символа, грамматическому правилу 13. Это правило является единственным, применимым для этого фрагмента. Однако, так же как и прежде, мы просто обозначим этот фрагмент как не­терминальный символ <N₂>.

На этом разбор предложения READ закончен. Если мы сравним дерево грамматического разбора на рис. За с только что построенным, то увидим, что они полностью совпадают. за исключением используемых имен нетерминальных символов. Это означает, что мы правильно определили синтаксис анализируемого предложения, что и является целью процесса грамматиче­ского разбора. Сами же имена нетерминальных символов были выбраны произвольно автором записи грамматики и не имеют никакого отношения к смыслу предложении исходной про­граммы.

На рис. 8б изображен аналогичный пошаговый процесс грамматического разбора предложения присваивания в строке 14 программы на рис. 5.1. Обратите внимание, что процесс ска­нирования слева направо продолжается на каждом шаге грам­матического разбора лишь до тех пор, пока не определился очередной фрагмент предложения для грамматического распознавания, т. е. первый фрагмент, ограниченный отношениями <• и •>. Как только подобный фрагмент выделен, он интерпретируется как некоторый очередной нетерминальный символ в соответствии с каким-нибудь правилом грамматики. Этот процесс продолжается до тех пор, пока предложение не будет распознано целиком. Вы должны внимательно проследить все этапы, изображенные на рис. 8б, для того, чтобы убедиться в правильном понимании процесса анализа с использованием матрицы предшествования, приведенной на рис. 7. Обратите внимание, что каждый фрагмент дерева грамматического разбора строится, начиная с оконечных узлов вверх, в сторону: корня дерева. Отсюда и возник термин восходящий разбор.

Сравнивая деревья грамматического разбора, изображенные на рис. 8б и рис. 3б, мы обнаружим некоторые различия Например, идентификатор SUMSQ на рис. 3 был сначала интерпретирован как <factor>, а потом как <term>, являющийся одним из операндов операции DIV. На рис. 8б идентификатор SUMSQ интерпретирован как единственный нетерминальный символ <N₁>, являющийся операндом DIV. Таким образом, <N₁> на дереве, изображенном на рис. 8б, соответствует двум нетерминальным символам — <factor> и <term> — на рис. 3б. Имеются и другие подобные различия между этими двумя деревьями.

Они вытекают из свободы образования имен нетерминальных символов, распознаваемых в рамках метода операторного предшествования. Интерпретация SUMSQ на рис. 3б сначала в качестве <factor>, а потом <term> является просто переименованием нетерминальных символов. Такое переименование необходимо, поскольку в соответствии с грамматическим правилом 11 первым операндом операции умножения должен быть <term>, а не <factor>. Так как для метода операторного предшествова­ния имена нетерминальных символов несущественны, то подобное переименование в процессе распознавания становится ненужным. Собственно говоря, три различных имени — <exp>, <term>, <factor> — были включены в грамматику только как средства описания отношения предшествования между операторами (например, для указания того, что умножение следует выполнять прежде сложения). Поскольку эта информация со­держится в нашей матрице предшествования, то становится ненужным различать эти три имени в процессе грамматического разбора.

Хотя мы проиллюстрировали метод операторного предше­ствования только на разборе отдельных предложений, этот ме­тод применим и для всей программы в целом. Вы можете попробовать применить этот метод к программе на рис. 1, ис­пользуя матрицу предшествования на рис. 7. Результат дол­жен совпадать с деревом грамматического разбора, изображен ном на рис. 4, за исключением различий в именах нетерминальных символов, подобных только что рассмотренным.

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

Рассмотрим в качестве примера грамматическое правило 13 на рис. 2. Процедура метода рекурсивного спуска, соответствующая нетерминальному символу <read>, прежде всего исследует две последовательные лексемы, сравнивая их с READ и (. В случае совпадения эта процедура вызывает другую про­цедуру, соответствующую нетерминальному символу <id — list>. Если процедура <id — list> завершится успешно, то процедура <read> сравнивает следующую лексему с ). Если все эти проверки окажутся успешными, то процедура <read> завершается с признаком успеха и устанавливает указатель текущей лексемы на лексему, следующую за ). В противном случае процедура <read> завершается с признаком неудачи.

Эта процедура лишь немного сложнее, чем те несколько определенных грамматикой альтернатив для соответствующих нетерминалов. Дополнительно процедура должна решать, какую альтернативу попробовать в качестве следующей. Для ме­тода рекурсивного спуска необходимо, чтобы соответствующую альтернативу можно было выбрать на основании анализа оче­редной входной лексемы. Существуют другие нисходящие ме­тоды грамматического разбора, для которых это требование может не выполняться. Однако они не являются столь эффек­тивными, как метод рекурсивного спуска. Так, например, про­цедура, соответствующая <stmt>, анализирует очередную лексе­му для того, чтобы выбрать одну из четырех возможных аль­тернатив. Если это лексема READ, то вызывается процедура, соответствующая нетерминальному символу <read>; если это лексема id, то вызывается процедура, соответствующая нетер­минальному символу <assign>, поскольку это единственная аль­тернатива, которая может начинаться с лексемы id, и т. д.

Если мы попытаемся написать полный набор процедур для грамматики на рис. 2, мы столкнемся со следующей труд­ностью. Процедура для <id—list>, соответствующая правилу 6, будет не в состоянии выбрать одну из двух альтернатив, поскольку обе альтернативы id и <id — list> могут начинаться с лексемы id. Тут скрыта и более существенная трудность. Если процедура каким-либо образом решит попробовать вторую альтернативу (<id — list>, id), то она немедленно вызовет рекурсивно саму себя для поиска нетерминального символа <id — list>. Это приведет еще к одному рекурсивному вызову и т. д., в ре­зультате чего образуется бесконечная цепочка рекурсивных вызовов. Причина этого заключается в том, что одна из альтернатив для <id — list> начинается также с <id — list>. Нисходя­щий грамматический разбор не применим непосредственно для грамматик, содержащих подобные левые рекурсии. Те же проблемы возникнут и в отношении правил 3,7, 10 и 11. Методы исключения левой рекурсии из правил грамматики можно найти в работах Грис [1971] и Ахо [1977].

На рис. 9 изображена та же грамматика, что и на рис. 2, но с исключенной левой рекурсией. Рассмотрим, например, правило 6а на рис. 5.9:

<id-list> := id { , id }

Эта нотация, являющаяся широко принятым расширением БНФ, означает, что конструкция, заключенная в фигурные скобки, может быть либо опущена, либо повторяться один или более число раз. Таким образом, правило 6а определяет нетерминаль­ный символ <id.—list> как состоящий из единственной лексе­мы id или же из произвольного числа следующих друг за дру­гом .лексем id, разделенных запятой. Это очевидно, эквивалентно правилу 6 на рис. 2. В соответствии с этим новым определением процедура, соответствующая нетерминальному симво­лу <id — list>, сначала ищет лексему id, а затем продолжает сканировать входной текст до тех пор, пока следующая пара лексем не совпадет с запятой и id. Такая запись устраняет проблему левой рекурсии, а также решает вопрос, какую из возможных альтернатив <id — list> пробовать первой.

Аналогичные изменения сделаны в правилах За, 7а, 10а и 11а на рис. 9. Вам надо сравнить эти правила с соответствующими им правилами на рис. 2 для того, чтобы убедиться в понимании сделанных изменений. Обратите внимание, что грамматика осталась рекурсивной: <ехр> определено в терминах <term>, который в свою очередь определен в терминах <factor>, а одна из альтернатив для нетерминального символа <factor> включает в себя <ехр>. Это означает, что рекурсивные вызовы процедур грамматического разбора по-прежнему возможны. Однако непосредственная левая рекурсия устранена. Цепочка вызовов, начиная с <ехр> и далее процедур, связанных с <term>, <factor> и опять <ехр>, должна продвинуть указатель текущей лексемы из входного файла как минимум на одну лексему вперед.

На рис. 10 изображен грамматический разбор методом рекурсивного спуска предложения READ в строке 9 на рис. 1 с использованием грамматики на рис. 9. На рис. 10а изображены процедуры, соответствующие нетерминальным символам <read> и <id—list>, логика которых совпадает с приведен­ным выше описанием. При этом предполагается, что переменная TOKEN содержит тип следующей лексемы из входного потока (в рамках схемы кодирования, изображенной на рис. 5). Вам надо внимательно ознакомиться с этими процедурами, что­бы убедиться, что вы понимаете, каким образом они получены из исходной грамматики.

Заметьте, что в процедуре IDLIST символ запятая (,), за которым не следует лексема id, рассматривается как ошибка и процедура заканчивается с признаком неудачи. Если же после­довательность лексем типа «id, id» является правильной кон­струкцией языка, то метод рекурсивного спуска не даст правильных результатов. Для такой грамматики необходимо использо­вать более сложные методы грамматического разбора, которые должны допускать во время нисходящего разбора возврат по входной строке после обнаружения того факта, что за послед­ней запятой не следует лексема id.

На рис. 10б графически представлен процесс грамматического разбора методом рекурсивного спуска для анализируемого предложения. На фрагменте (i) изображен вызов процедуры READ, которая обнаружила лексемы READ и ( во входном по­токе (это изображено штриховыми линиями). Во фрагменте (ii) процедура READ вызвала процедуру IDLIST (изображено штриховой линией), которая обработала лексему id. Во фрагменте (iii) процедура IDLIST закончила свою работу, передала управление процедуре READ с признаком успешного заверше­ния; процедура READ обработала входную лексему ). На этом анализ исходного предложения завершен. Процедура READ закончит свою работу с признаком успешного завершения, что означает, что нетерминальный символ <read> обнаружен. 06ратите внимание, что последовательность вызова процедур и обработки лексем целиком определяется структурой предложе­ния READ. Фрагмент (iii) полностью совпадает с деревом грам­матического разбора на рис. 3а. Обратите внимание также на то, что дерево грамматического разбора строилось, начиная со своего корня, что и повлекло за собой термин нисходящий разбор.

На рис. 11 представлен разбор методом рекурсивного спу­ска оператора присваивания в строке 14 на рис. 1. На рис. 1la изображены процедуры для нетерминальных симво­лов, необходимые для разбора этого предложения. Вы должны внимательно сравнить эти процедуры с соответствующими пра­вилами грамматики. На рис. 11б изображены шаги граммати­ческого разбора (вызовы процедур и обработка лексем), ана­логичные приведенным на рис. 10б. Читателю настоятельно рекомендуется проследить каждый шаг анализа этого предложения с использованием процедур рис. 1la. Сравните де­ревья грамматического разбора па рис. 116 и рис. 3б. Обра­тите внимание, что различия между этими двумя деревьями в точности соответствуют различиям между грамматиками, изо­браженными на рис. 9 и рис. 2.

Мы привели примеры грамматического разбора отдельных предложений методом рекурсивного спуска. Однако этот метод применим и ко всей программе в целом. В этом случае для осуществления синтаксического анализа следует просто обратиться к процедуре, соответствующей нетерминальному символу <prog>. В результате работы этой процедуры будет построено дерево грамматического разбора для всей программы. Вы може­те написать недостающие процедуры для всех нетерминальных символов грамматики на рис. 9 и применить метод рекурсив­ного спуска к программе на рис. 1. В качестве результата вы должны получить дерево грамматического разбора, анало­гичное изображенному на рис. 4. Различия должны быть свя­заны только с теми модификациями, которые имеются в грам­матике на рис. 9.

Обратите внимание, что в языке программирования отсут­ствуют какие бы то ни были особенности, заставляющие отдать предпочтение одному из методов грамматического разбора. Мы использовали один восходящий и один нисходящий метод для разбора одной и той же программы с использованием практически одинаковой грамматики. Возможно также одновременное использование этих методов. Некоторые компиляторы используют метод рекурсивного спуска для распознавания конструкций относительно высокого уровня (например, до уровня отдельных предложений языка), а потом переключаются на метод, аналогичный методу операторного предшествования для анализа таких конструкций, как, например, арифметические выражения. Дальнейшее обсуждение методов грамматического разбора содержится в работах Ахо [1977], Льюис [1976] и Грис. [1971]

Предлагаю ознакомиться с аналогичными статьями: