Элементы компиляции программ
Синтаксический анализ
После того как лексемы входного потока распознаны, транслятору необходимо удостовериться, что вся их совокупность является синтаксически правильной. Вопрос: зачем? Заглянем немного вперед и задумаемся о том, каким образом производится генерация кода. Если рассматривать этот вопрос схематично, то можно утверждать, что для каждого нетерминала грамматики существует некий шаблон кода, который подставляется в определенное место выходного кода. Настройка этого шаблона производится значениями лексем, распознанными сканером. Извлечь эту информацию можно, если соответствующая конструкция в исходном коде синтаксически правильна. В конечном итоге мы должны доказать, что вся программа синтаксически правильна.
Цель синтаксического анализа – доказать существование дерева грамматического разбора в контекстно-свободной грамматике G для входной цепочки s, состоящей из терминальных символов.
Существует много различных методов синтаксического анализа программ. Но главное понимать, что все они неявно стремятся доказать одно и тоже – существование синтаксического дерева для транслируемой программы. Ведь применительно к нашей грамматике не может блок описания переменных следовать где-то в середине или конце программы, за операторами, которые эти переменные используют. Кстати, посмотрите сейчас еще раз на правило грамматики, соответствующее начальному символу языка. В этом правиле определена общая структура программы и в ней видно место блока описаний переменных. Вместо списка стоит нетерминал. Можно нарисовать воображаемую дугу к правилу грамматики, соответствующему нетерминалу блока описания переменных, и т. д.
То есть мы действительно начали строить грамматическое дерево. И если нам удастся его построить для данной программы, то последняя действительно синтаксически правильна. Если на каком-то шаге построения этого дерева у нас случится ошибка, допустим в том же блоке описания переменных программы вместо идентификатора будет стоять целое число, то дерево мы построить не сможем. То есть программа синтаксически неправильная. Можно формировать соответствующее диагностическое сообщение.
Таким образом, можно утверждать, что если возможно построение дерева трансляции для данного входного потока, то он синтаксически правилен. Понятно, что для другого текста программы дерево трансляции будет другое, но в любом случае листьями этого дерева будут лексемы программы, а корнем – начальный символ языка. Причем если совершить обход листьев дерева слева направо, то получим вытянутый в строку текст нашей программы.
Если судить по рисунку, то программа синтаксически правильная. Но каким образом выясняет этот факт транслятор? Как отмечено выше, существует несколько методов выполнения синтаксического анализа. Все они делятся на два класса в зависимости от того, как они движутся по дереву трансляции во время разбора – сверху вниз или снизу вверх. Алгоритмы "сверху вниз" стремятся построить дерево трансляции начиная вывод от начального символа языка к анализируемой цепочке. И наоборот, алгоритмы "снизу вверх" строят дерево трансляции от анализируемой цепочки терминалов к начальному символу языка. Важно подчеркнуть, что на самом деле никакого дерева в памяти нет и не строится. Как показано выше, его структура заложена в правилах грамматики. Используя алгоритм конкретного метода синтаксического разбора и представленные определенным образом в памяти правила грамматики, мы и производим движение по воображаемому дереву трансляции.
На практике не исключены случаи комбинированного применения восходящих и нисходящих методов синтаксического анализа. Например, арифметические выражения удобно разбирать с помощью восходящих методов, а общий разбор программы делать нисходящими методами. В большинстве случаев достаточно одного универсального метода – метода рекурсивного спуска. Для краткости будем называть синтаксический анализатор распознавателем.
Метод рекурсивного спуска
Главное свойство нисходящих методов – их целенаправленность. Метод рекурсивного спуска – наиболее яркий и простой представитель этих методов. Основ ной его недостаток – сильная зависимость от конкретного языка. Программа распознавателя рекурсивного спуска представляет собой, по сути, набор рекурсивных процедур – по одной для каждого из нетерминалов грамматики. Первой получает управление процедура, соответствующая нетерминалу – начальному символу языка. Эта процедура уже знает, что она должна делать. Если первый символ в этом правиле – терминал, то процедура знает об этом и ждет его.
Это ожидание заключается в том, что процедура сравнивает код терминала, который должен быть первым, согласно правилу, с кодом первой лексемы из лексической свертки входной строки. Если они совпадают, то процесс разбора идет дальше. Если они не совпадают, то фиксируется ошибка. Если очередным символом правила должен быть нетерминал, то в этом месте вызывается соответствующая ему процедура. Эта процедура тоже построена исходя из правила грамматики для этого нетерминала, поэтому ее действия также уже предопределены. И так будет продолжаться до тех пор, пока разбор не вернется к первому правилу, то есть управление вернется процедуре, соответствующей правилу грамматики для начального символа языка. В нашем случае последним должен быть проанализирован факт того, что последний символ во входной строке – терминал кон_прог.
При реализации метода рекурсивного спуска в чистом виде возможны сложности. Посмотрим на правила грамматики, подобные следующим:
dec-list › dec | dec-list; dec id-list › ID | id-list. ID term › factor | term * factor | term div factor strut-list › stmt | stmt-list; stmt
Видно, что эти правила леворекурсивны. Например, рассмотрим следующее правило:
id-list › ID | ID-LIST, ID
В этом правиле вторая альтернатива начинается с нетерминала ID-LIST, то есть в процессе разбора при обращении к процедуре, соответствующей этому нетерминалу, получится бесконечный цикл. Ее необходимо устранить. Для этого соответствующие правила подправляются следующим образом:
dec-list › dec | dec-list; dec id-HSts" ID I {. ID}
stmt-list › stmt | {: stmt} exp › term {+ term | – term}
term › factor {* factor | div factor}
Теперь для принятия решения о дальнейшем пути выполнения рекурсивной процедуры необходимо просматривать один символ вперед. Если он совпадает с тем, что в правиле, то процедура рекурсивно вызывается снова. Если этот символ любой другой, то производится возврат из этой процедуры. Таким образом, процесс написания программы неявно представляет собой строительство дерева разбора начиная от его корня – начального символа языка. То есть это действительно нисходящий метод.
Остается заметить еще одно достоинство метода рекурсивного спуска. Если очередная языковая конструкция распознана, то почему бы сразу в соответствующей рекурсивной процедуре не "навесить" семантику, то есть генерацию кода.
Но метод рекурсивного спуска не всегда применим. В сложных случаях, когда имеется скрытая левая рекурсия, необходимо применять более сложные методы для ее устранения или замены правой рекурсией.
После этого обсуждения мы готовы написать распознаватель, но делать этого не будем, так как цель, достижению которой был посвящен материал данного раздела, достигнута. Все остальное – техника программирования. Остается добавить, что разговор о проблемах трансляции мы продолжим в главе 10.