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

1) счетчик ни при каких обстоятельствах не становится отрицательным;

2) при завершении работы счетчик будет на нуле.

Допустимы следующие структуры скобок:

( ( ) ( ) ( ) )

( ) ( ( ( ( ) ) ) )

Приводимые ниже структуры

( ) ( ) ) ( ( ( ) ( ( )

недопустимы, так как счетчик в первом случае оказывается отрицательным, а во втором не является нулевым при завершении работы.

В большинстве языков программирования встречаются различные типы скобок, например

if fi

case esac

begin end

Применения описанного выше алгоритма, рассматривающего все открывающие скобки как «(», а все закрывающие как «)», недостаточно, поскольку последовательность

[( )]

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

1) при чтении закрывающей скобки не окажется, что она не соответствует открывающей скобке, помещенной в вершине стека, или если стек не будет пустым;

2) при завершении работы стек станет пустым.

Ошибка в употреблении скобок должна отразиться в четком сообщении компилятора, таком, как

bracket mismatch Если ошибка возникла из-за того, что не достает закрывающей скобки, то тип недостающей скобки модно вывести на основании той скобки, которая находится в вершине стека. Один из возможных путей исправления ошибки заключается в том, что берется предполагаемая недостающая закрывающая скобка, открывающая скобка удаляется из стека, и выдается сообщение с указанием предполагаемого источника ошибки, например (в предположении, что в верхней части стека находилось if)

missing fi?

Диагностическое сообщение, однако, появится не в том месте, где допущен пропуск скобки, так как ошибка останется незначительной до тех пор, пока не встретится другая закрывающая скобка (иногда типа). При продолжении синтаксического анализа желательно, чтобы скобочная структура была исправлена. Рассмотрим (недопустимый) фрагмент программы:

if b then x else (p + q x r 2 fi

Здесь пропущена закрывающая скобка «)». Это не обнаружится до тех пор, пока не встретится fi. Однако не ясно, где должна стоять эта скобка: после r, после q или, что мене вероятно, после p или 2. Выяснить, что предполагал программист, невозможно. Поэтому самый легкий способ «исправления» - поставить закрывающую скобку непосредственно перед fi. По крайней мере, это позволит синтаксическому анализатору продолжать работу без выдачи другого сообщения об ошибке из-за недостающей скобки. Существуют более сложные алгоритмы исправления структур [4].

12.4. СИНТАКСИЧЕСКИЕ ОШИБКИ

Термин «синтаксическая ошибка» употребляется для обозначения ошибки, обнаруживаемой контекстно-свободным синтаксическим анализатором. LL(1) - LR(1) -анализаторы обладают этим важным свойством - обнаруживать синтаксически неправильную программу на первом недопустимом символе, т. е. они могут генерировать сообщение при чтении символа, который не должен следовать за прочитанной к тому времени последовательностью символов. Некоторые же анализаторы (например, анализаторы с приоритетами знаков операций) такого свойства не имеют. Далее в этом разделе мы полагаем, что синтаксические ошибки обнаруживаются при первой возможности.

При описании методов исправления ошибок мы будем ориентироваться на LL(1) -анализаторы. Что касается ошибок в употреблении скобок, то синтаксические ошибки не обязательно обнаруживаются вблизи от того места, где программист допустил ошибку. Ошибка в виде пропуска или неправильного употребления, допущенная на более раннем этапе, может проявиться совсем в другом месте программы. Проиллюстрируем это положение с помощью Алгола 68. Рассмотрим цикл

while x > y do something od

Синтаксис этого языка не разрешает ставить перед do знак «;». Однако мы покажем, что если «;» стоит, анализатор не сможет обнаружить ошибку и этом месте

В Алголе 68 можно записать бесконечный цикл (т.е. цикл, который заставит программу работать бесконечное число раз, если ее не остановит такая конструкция, как goto) следующим образом:

something else

В программе могут оказаться два вложенных цикла:

while x := 1; do something else od; x > y do something od

где частью while внешнего цикла является последовательное предложение (точнее, выясняющее предложение), которое содержит элемент, представляющий собой бесконечный цикл. Интересно еще и то, что этот фрагмент программы включает последовательность

Поэтому, если бы написали

while x > y ; do something od

то никакого сообщения об ошибке при встрече «;» или do не последовало бы, так как на данной стадии синтаксический анализатор не может исключить вероятность того, что do служит началом бесконечного цикла, и не связано с предшествующим while. Конечно, следует ожидать появления другого do в пару while, и это должно произойти прежде, чем закроется скобочная структура, открытая перед while. Ошибка (если она имела место) обнаружится при чтении какой-либо закрывающей скобки и о ней будет выдано сообщение, что может случиться через много строк после того места, где была поставлена недопустимая точка с запятой.

Сообщив о синтаксической ошибке, анализатор в большинстве случаев постарается продолжить разбор. Для этого ему может понадобиться исключить какие-либо символы, включить какие-либо или изменить их (исключить и включить). Существует ряд стратегий исправления ошибок. Некоторые простые стратегии описываются здесь. Практически все они хорошо срабатывают в одних случаях и плохо - в других. «Хорошая» стратегия заключается в том, чтобы обнаружить как можно больше синтаксических ошибок и генерировать как можно меньше сообщения в связи с каждой ошибкой. Обычно наилучшими являются методы, зависимые от языка, т.е. от знания исходного языка и от того, как он употребляется.

1. Режим переполоха

Один из наиболее общеупотребительных методов исправления синтаксических ошибок носит название режима переполоха. При появлении недопустимого символа весь последующий исходный текст, вплоть до соответствующего ограничителя, например «;» или end, игнорируется. Ограничитель заканчивает какую-то конструкцию языка, и элементы удаляются от стека разбора до тех пор, пока не встретится адрес возврата. Этот элемент тоже удаляется из стека, а разбор содержащего следующий входной символ. Такой метод довольно легко реализуется, но имеет серьезный недостаток; длинные последовательности кода, соответствующие игнорируемым символам, не анализируются.

2. Исключение символов

Этот метод также легко реализуется и не требует изменения стека разбора. Когда считывается недопустимый символ, и он сам, и все последующие символы исключаются из исходной строки до тех пор, пока не встретится допустимый. Хотя при таком методе могут исключаться длинные последовательности символов, в определенных случаях он весьма эффективен. Например, в

c := d + 3; end