Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

Ответить на этот вопрос не всегда легко, поскольку могут быть построены два принципиально разных распознавателя, алгоритмы работы которых несопоставимы. В первую очередь речь идет именно о восходящих и нисходящих распознавателях: в основе первых лежит алгоритм подбора альтернатив, в основе вторых – алгоритм «сдвиг-свертка».

На вопрос о том, какой распознаватель – нисходящий или восходящий – выбрать для построения синтаксического анализатора, нет однозначного ответа. Эту проблему необходимо решать, опираясь на некую дополнительную информацию о том, как будут использованы или каким образом будут обработаны результаты работы распознавателя. Более подробно обсуждение этого вопроса можно найти в [1, 7].

Совет.

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

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

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

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

1. Выполнить простейшие преобразования над заданной КС-грамматикой.

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

3. Если соответствующий класс найден, взять за основу для построения распознавателя алгоритм разбора входных цепочек, известный для этого класса, если найдено несколько классов линейных распознавателей – выбрать из них один по своему усмотрению.

4. Иначе, если соответствующий класс по п. 2 не был найден или же найденный класс КС-грамматик не устраивает разработчиков компилятора – попытаться выполнить над грамматикой неформальные преобразования с целью подвести ее под интересующий класс КС-грамматик для линейных распознавателей и вернуться к п. 2.

5. Если же ни в п. 3, ни в п. 4 соответствующий распознаватель найти не удалось (что для современных языков программирования практически невозможно), необходимо использовать один из универсальных распознавателей.

6. Определить, в какой форме синтаксический распознаватель будет передавать результаты своей работы другим фазам компилятора (эта форма называется внутренним представлением программы в компиляторе).

Реализовать выбранный в п. 3 или 5 алгоритм с учетом структур данных, соответствующих п. 6.

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

Для грамматик, предложенных в заданиях, известно, что они относятся также к классам КС-грамматик LR(1) и LALR(1), для которых также существует известный алгоритм линейного распознавателя, но, по мнению автора, этот алгоритм более сложен (его описание можно найти в [1, 2, 7]). Однако желающие могут не согласиться с автором и использовать для выполнения лабораторной работы любой из этих классов.

После несложных преобразований эти же грамматики могут быть приведены к виду, удовлетворяющему требованиям алгоритма рекурсивного спуска (или алгоритма анализа для LL(1) – грамматик). Этот алгоритм тривиально прост, но для его реализации надо выполнить достаточно несложные неформальные преобразования над заданными грамматиками – автор оставляет эти преобразования для желающих попробовать свои силы.