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

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

В общем виде последовательность построения распознавателя для КС-грамматики операторного предшествования G(VT,VN,P,S) можно описать следующим образом:

1. На основе множества правил грамматики Р построить множества крайних левых и крайних правых символов для всех нетерминальных символов грамматики

2. На основе множества правил грамматики Р и построенных на шаге 1 множеств L(U) и R(U) построить множества крайних левых и крайних правых терминальных символов для всех нетерминальных символов грамматики

: L_t(U) и R_t(U).

3. На основе построенных на шаге 2 множеств L_t(U) и R_t(U) для всех терминальных символов грамматики

заполняется матрица операторного предшествования.

4. Исходная грамматика G(VT,VN,P,S) преобразуется в остовную грамматику G'(VT,{S},P,S) с одним нетерминальным символом.

5. На основе построенной матрицы предшествования и остовной грамматики строится распознаватель на базе алгоритма «сдвиг-свертка» для грамматик операторного предшествования.

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

Далее в примере выполнения работы проиллюстрирован именно такой подход к построению распознавателя.

Требования к выполнению работы

Порядок выполнения работы

Для выполнения лабораторной работы требуется написать программу, которая выполняет лексический анализ входного текста в соответствии с заданием, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде символьного (текстового) файла. Синтаксис входного языка и перечень допустимых лексем указаны в задании. Допускается исходить из условия, что текст содержит не более одного предложения входного языка.

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

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

Для выполнения лексического анализа рекомендуется использовать программные модули, созданные в результате выполнения лабораторной работы № 2.

Длину идентификаторов и строковых констант можно считать ограниченной 32 символами. Программа должна допускать наличие комментариев неограниченной длины во входном файле. Форму организации комментариев предлагается выбрать самостоятельно.

1. Получить вариант задания у преподавателя.

2. Построить множества крайних левых и крайних правых символов, множества крайних правых и крайних левых терминальных символов и матрицу операторного предшествования для заданной грамматики (если для построения синтаксического распознавателя предполагается использовать другой механизм, отличный от грамматик операторного предшествования, то форму его надо предварительно согласовать с преподавателем).

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

4. Подготовить и защитить отчет.

5. Написать и отладить программу на ЭВМ.