М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
 Скачать 0.92 Mb.
|
5.7.Трансляция паскаль-программы в язык ССоставить рефал-программу, преобразующую текст программы, записанной на подмножестве языка Паскаль [12] в текст эквивалентной программы, написанной на языке С [11]. В качестве подмножества Паскаля можно взять язык, описанный в предыдущем варианте задания, дополнив его процедурами и функциями. В функции программы-транслятора входит: ввод паскаль-программы из текстового файла; лексический и синтаксический анализ введённой программы с выдачей сообщений о найденных ошибках; преобразование синтаксически правильной паскаль-программы в эквивалентную программу на языке С; выполнение некоторых преобразований полученной С-программы, упрощающих её или оптимизирующих проводимые вычисления (например, преобразующих выражение присваивания i+=1 в ++i); вывод (печать) результирующей программы с учетом принятых для этого языка правил структурирования вложенных конструкций. Для выполнения задания необходимо дополнить необходимыми БНФ-правилами описание подмножества Паскаля, приведённое в предыдущем варианте задания. 5.8.Методические указания к вариантамВо всех вариантах рекомендуется выделить следующие предварительные этапы обработки исходных символьных выражений – лексический и синтаксический анализ. Задача лексического анализа – выделение лексем исходного выражения и, возможно, перевод их во внутреннее представление, в котором: числовые константы (последовательности цифр) преобразованы в символы-цифры или макроцифры; имена переменных (последовательности букв и цифр, начинающиеся с буквы) заключены в структурные скобки или преобразованы в символ-метки; имена функций (sin, cos и др. в варианте дифференцирования выражения) или служебные имена (begin, end, case, integer и др. в вариантах интерпретации и трансляции паскаль-программы) преобразованы в соответствующие символы-метки (/sin/, /cos/, /begin/ и т.п.); знаки операций, состоящие из нескольких символов, заменены на соответствующие им символы-метки (например, в варианте вычисления выражения языка С: знаки операции ++ можно заменить на символ-метку /pp/, а знаки *= на символ-метку /mulassign/); унарные знаки + и – заменены на другие символы – для того, чтобы отличать их от знаков бинарных операций + и –. Основная задача синтаксического анализа – выявление структуры обрабатываемого выражения и перевод его во внутреннее представление, удобное для дальнейших преобразований. Для этого: необходимо заменить в исходном выражении символы круглых скобок на структурные скобки; в варианте вычисления выражения языка С в ходе расстановки структурных скобок целесообразно считать знаки тернарной операции ? и : особым видом парных скобок и заменить каждую пару таких символов на пару структурных скобок и символов-меток, например, /question/ и /two-spot/, или же заключить в структурные скобки каждую пару символов ?: вместе со стоящим между ними выражением; в вариантах интерпретации и трансляции паскаль-программы после замены обычных круглых скобок на структурные следует зафиксировать вложенность операторов паскаль-программы расстановкой структурных скобок вокруг фрагментов операторов, начинающихся и заканчивающихся соответственно символами-метками /begin/ и /end/, /then/ и /else/, /case/ и /endcase/, /repeat/ и /until/ (введёнными на этапе лексического анализа). Таким образом, в ходе лексического и синтаксического анализа входное символьное выражение будет преобразовано во внутреннее представление, упрощающее его последующую обработку (дифференцирование, вычисление, интерпретацию, трансляцию и т.п. – в зависимости от варианта задания). Для хранения значений переменных в ходе вычислений целесообразно использовать копилку. 6.ЛитератураТурчин В.Ф. Алгоритмический язык рекурсивных функций (РЕФАЛ). М: ИПМ АН СССР, Препринт № 4, 1968. Романенко С.А., Турчин В.Ф. РЕФАЛ-компилятор. // Труды 2-й Всесоюзной конференции по программированию. ВЦ СОАН. Новосибирск, 1970. Турчин В.Ф. Базисный РЕФАЛ. Описание языка и основные приемы программирования (метод. рекомендации) . Фонд алгоритмов и программ в отрасли "Строительство", vol. 5, N 33. ЦНИПИАСС. М: 1974. Климов Анд.В., Климов Арк.В., Красовский А.Г., Романенко С.А., Травкина Е.В., Турчин В.Ф., Хорошевский В.Ф., Щенков И.Б. Базисный РЕФАЛ и его реализация на вычислительных машинах (метод. рекомендации). Фонд алгоритмов и программ для ЭВМ (в отрасли "Строительство"), специальный раздел, vol. 5, N 40. М: 1977. Климов А.В., Романенко С.А. Метавычислитель для языка Рефал. Основные понятия и примеры. М: ИПМ АН СССР, препринт № 71, 1987. Романенко С.А. Метаалгоритмический язык Рефал и тенденции его развития // Искусственный интеллект в 3-х кн., Кн. 3. Программные и аппаратные средства: Справочник / под ред.Захарова В.Н., Хорошевского В.Ф., – М: Радио и связь, 1990, стр. 47–55. Марков А.А. Нагорный Н.М. Теория алгоритмов. – М.: Фазис, 1996. Романенко С.А. Реализация Рефала-2. М: ИПМ АН СССР, препринт № 71, 1987. Turchin V. REFAL-5, Programming Guide and Reference Manual – New England Publishing Co., Holyoke, 1989. Турчин В.Ф. РЕФАЛ-5. Руководство по программированию и справочник. http://www.refal.net/rf5_frm.htm Керниган Б., Ритчи Д. Язык программирования Си. – М: Финансы и статистика, 1992. Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка. – М: Финансы и статистика, 1982. Приложение 1. Синтаксис языка Рефал-2Рефал-программа ::= имя_программы START рефал-предложения_и_директивы END имя_программы ::= идентификатор рефал-предложения_и_директивы ::= единица_программы | единица_программы рефал-предложения_и_директивы единица_программы ::= директива | описание_спецификатора | описание_функции директива ::= ENTRY-директива | EXTRN-директива | EMPTY-директива ENTRY-директива ::= ENTRY Go EXTRN-директива ::= EXTRN список_объявлений_функций список_объявлений_функций ::= объявление_функции | объявление_функции, список_объявлений_функций объявление_функции ::= идентификатор | идентификатор(внешний_идентификатор) EMPTY-директива ::= EMPTY список_идентификаторов список_идентификаторов ::= идентификатор | идентификатор, список_идентификаторов описание_спецификатора ::= имя_спецификатора S набор_ограничений имя_спецификатора ::= идентификатор набор_ограничений ::= цепочка_элементов_спецификации | цепочка_элементов_спецификации (цепочка_элементов_спецификации) набор_ограничений цепочка_элементов_спецификации ::= пусто | элемент_спецификации цепочка_элементов_спецификации элемент_спецификации ::= символ-литера | символ-число | символ-метка | стандартное_множество | спецификатор спецификатор ::= :имя_спецификатора: символ-литера ::= 'символ' символ-число ::= /последовательность_цифр/ последовательность_цифр ::= цифра | цифра последовательность_цифр символ-метка ::= /идентификатор/ стандартное_множество ::= S | F | N | O | L | D | B | W описание_функции ::= имя_функции послед-ть_рефал-предложений | Go = начальное_состояние_поля_зрения имя_функции ::= идентификатор начальное_состояние_поля_зрения ::= рабочее_выражение послед-ть_рефал-предложений ::= пусто | рефал-предложение послед-ть_рефал-предложений рефал-предложение ::= знак_отождествления выражение-образец = выражение знак_отождествления ::= пусто | L | R выражение-образец ::= пусто | терм1 выражение-образец терм1 ::=символ-литера | символ-число | символ-метка | переменная | (выражение-образец) выражение ::= пусто | терм выражение терм ::=символ-литера | символ-число | символ-метка | переменная | (выражение) | <имя_функции выражение> рабочее_выражение ::= пусто | терм2 рабочее_выражение терм2 ::=символ-литера | символ-число | символ-метка | (рабочее_выражение) | <имя_функции рабочее_выражение> переменная ::= тип индекс | тип спецификация индекс тип::=s | S | w | W | e | E | v | V индекс ::= буква | цифра спецификация ::= спецификатор | (набор_ограничений) пусто ::= Приложение 2. Синтаксис языка Рефал-5программа ::= определение_функции | определение_функции программа | определение_функции ; программа | external-директива ; программа | программа external- директива ; определение_функции ::= имя_функции { блок } | $ENTRY имя_функции { блок } external- директива ::= $EXTERNAL список_имён_функций | $EXTERN список_имён_функций | $EXTRN список_имён_функций список_имён_функций ::= имя_функции | имя_функции , список_имён_функций имя_функции ::= идентификатор блок ::= предложение | предложение ; | предложение ; блок предложение ::= образец последовательность_условий = выражение | образец последовательность_условий , присоединённый_блок последовательность_условий ::= , условие последовательность_условий | пусто условие ::= аргумент : образец аргумент ::= выражение образец ::= пусто | терм_образца образец терм_образца ::=символ-литера | макроцифра | идентификатор | переменная | (образец) присоединённый_блок ::= аргумент : { блок } выражение ::= пусто | терм выражение терм ::=символ-литера | макроцифра | идентификатор | переменная | (выражение) | <имя_функции выражение> переменная ::= признак_типа буква | признак_типа цифра | признак_типа.идентификатор | признак_типа.макроцифра указатель_типа ::= s | t | e символ-литера ::= 'символ' макроцифра ::= последовательность_цифр |