Системное программное обеспечение. Лабораторный практикум
Шрифт:
Часто одна и та же КС-грамматика может быть отнесена не к одному, а сразу к нескольким классам КС-грамматик, допускающих построение линейных распознавателей. Тогда необходимо решить, какой из нескольких возможных распознавателей выбрать для практической реализации.
Ответить на этот вопрос не всегда легко, поскольку могут быть построены два принципиально разных распознавателя, алгоритмы работы которых несопоставимы. В первую очередь речь идет именно о восходящих и нисходящих
На вопрос о том, какой распознаватель – нисходящий или восходящий – выбрать для построения синтаксического анализатора, нет однозначного ответа. Эту проблему необходимо решать, опираясь на некую дополнительную информацию о том, как будут использованы или каким образом будут обработаны результаты работы распознавателя. Более подробно обсуждение этого вопроса можно найти в [1, 7].
Совет.
Следует вспомнить, что синтаксический анализатор– это один из этапов компиляции. И с этой точки зрения результаты работы распознавателя служат исходными данными для следующих этапов компиляции. Поэтому выбор того или иного распознавателя во многом зависит от реализации компилятора, от того, какие принципы положены в его основу.
Желание использовать более простой класс грамматик для построения распознавателя может потребовать каких-то манипуляций с заданной грамматикой, необходимых для ее преобразования к требуемому классу. При этом нередко грамматика становится неестественной и малопонятной, что в дальнейшем затрудняет ее использование для генерации результирующего кода. Поэтому бывает удобным использовать исходную грамматику такой, какая она есть, не стремясь преобразовать ее к более простому классу.
В целом следует отметить, что, с учетом всего сказанного, интерес представляют как левосторонний, так и правосторонний анализ. Конкретный выбор зависит от реализации конкретного компилятора, а также от сложности грамматики входного языка программирования.
В общем виде процесс построения синтаксического анализатора можно описать следующим образом:
1. Выполнить простейшие преобразования над заданной КС-грамматикой.
2. Проверить принадлежность КС-грамматики, получившейся в результате преобразований, к одному из известных классов КС-грамматик, для которых существуют линейные распознаватели.
3. Если соответствующий класс найден, взять за основу для построения распознавателя алгоритм разбора входных цепочек, известный для этого класса, если найдено несколько классов линейных распознавателей – выбрать из них один по своему усмотрению.
4. Иначе, если соответствующий
5. Если же ни в п. 3, ни в п. 4 соответствующий распознаватель найти не удалось (что для современных языков программирования практически невозможно), необходимо использовать один из универсальных распознавателей.
6. Определить, в какой форме синтаксический распознаватель будет передавать результаты своей работы другим фазам компилятора (эта форма называется внутренним представлением программы в компиляторе).
Реализовать выбранный в п. 3 или 5 алгоритм с учетом структур данных, соответствующих п. 6.
В данной лабораторной работе в заданиях предлагаются грамматики, не требующие дополнительных преобразований. Кроме того, гарантировано, что все они относятся к классу КС-грамматик операторного предшествования, для которых существует известный алгоритм линейного распознавателя. Поэтому создание синтаксического распознавателя для выполнения лабораторной работы существенно упрощается.
Для грамматик, предложенных в заданиях, известно, что они относятся также к классам КС-грамматик LR(1) и LALR(1), для которых также существует известный алгоритм линейного распознавателя, но, по мнению автора, этот алгоритм более сложен (его описание можно найти в [1, 2, 7]). Однако желающие могут не согласиться с автором и использовать для выполнения лабораторной работы любой из этих классов.
После несложных преобразований эти же грамматики могут быть приведены к виду, удовлетворяющему требованиям алгоритма рекурсивного спуска (или алгоритма анализа для LL(1) – грамматик). Этот алгоритм тривиально прост, но для его реализации надо выполнить достаточно несложные неформальные преобразования над заданными грамматиками – автор оставляет эти преобразования для желающих попробовать свои силы.
Выполняющие лабораторную работу могут пойти любым из рекомендованных путей или построить иной синтаксический анализатор по своему усмотрению – в этом направлении их ничто не ограничивает.
В качестве основного пути выполнения лабораторной работы автор предлагает распознаватель на основе грамматик операторного предшествования, поэтому именно этот класс КС-грамматик далее рассмотрен более подробно (описания остальных известных классов и подклассов КС-грамматик можно найти в [1–3, 7]).