Язык РЕФАЛ: первичные функции и примеры составления программ

Первичные функции

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

Функции ввода/вывода

Функции ввода/вывода предназначены для организации диалогового взаимодействия между пользователем и программой. Для ввода строки с клавиатуры используется функция card. Для вывода информации на экран используются операции print, prout, которые различаются возвращаемым значением и способом представления информации на экране. Ввод/вывод может быть переназначен в произвольный файл стандартным образом.

Функция card осуществляется вызовом

k/card/ .

и дает возможность читать строку символов из входного потока. После вызова функции программа переходит в состояние ожидания ввода строки. По окончании ввода строки следует нажать клавишу "Enter". Возвращаемым значением является введенная строка.

Функция print осуществляется вызовом

k/print/ <E>.

где E - произвольное рефал-выражение (возможно, и пустое), и выводит c новой строки это выражение. При пустом выражении пропускается 1 печатная строка. При непустом выражении символы-литеры выводятся в виде соответствующих литер, структурные скобки выводятся как круглые скобки, а составные символы выводятся с ограничителями ' вместо "/". Возвращаемым значением является выводимое выражение.

Например, функция

k/print/ 'функция'(/f1/).

возвратит выражение

'функция'(/f1/).

При этом на устройство вывода будет выдана строка

'функция'('f1') ,

Функция prout осуществляется вызовом

k/prout/ <E>.

где E - произвольное рефал-выражение (возможно, и пустое), и выводит c новой строки это выражение. Отличием от функции print является то, что всегда возвращается пустое выражение.

Арифметические функции

Функции работают только с целыми числами, каковыми являются в представлении Рефала - символы-числа с возможно предшествующим знаком минус '-'. Например, '-'/7/, /0/, /2007/. Нуль представляется либо нулевым символом-числом, либо пустым выражением.

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

К арифметическим функциям относятся:

Для преобразования целых чисел в символьный вид и обратно используются функции symb и numb.

Функции add, mul, sub осуществляются вызовом

k/op/ (<N1>) <N2>. ,

где op - одна из операций add, mul, sub, а N1 и N2 - макроцифры. Этот вызов возвращает макроцифру (для положительного результата знак '+' не ставится) суммы, произведения или разности N1-N2 в зависимости от операции. Например, следующие вызовы функции приведут к таким результатам:

k/add/  ('-'/5/)   /3/.   ->   '-'/2/ 
k/add/        ()   /2/.   ->      /2/    
k/mul/  ('-'/5/)   /3/.   ->  '-'/15/   
k/mul/     (/2/).         ->      /0/    
k/sub/  ('-'/5/)   /3/.   ->      /8/   
k/sub/        ()   /2/.   ->   '-'/2/

Функция dr осуществляется вызовом

k/dr/ (<N1>) <N2>.    ,

где N1 - делимое, а N2 - делитель. Она возвращает выражение

<Q> (<R>) ,

где Q - частное, а R - остаток. Попытка делить на 0 приводит к аварийному завершению. Знаки частного и остатка определяются следующим образом: сначала производится деление нацело без учета знаков делимого и делителя, а затем частному и остатку приписываются знаки так, чтобы выполнялось соотношение:

N1 = Q*N2 + R

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

k/dr/    (/5/)    /3/.  ->     /1/    (/2/)
k/dr/    (/5/) '–'/3/.  ->  '–'/1/    (/2/)
k/dr/ ('–'/5/)    /3/.  ->  '–'/1/ '–'(/2/)
k/dr/ ('–'/5/) '–'/3/.  ->     /1/ '–'(/2/)

Функция div в отличие от функции dr возвращает только частное. В остальном же подобна ей. Например, следующие вызовы функции приведут к таким результатам:

k/div/    (/5/)    /3/.  ->    /1/
k/div/    (/5/) '–'/3/.  -> '–'/1/
k/div/ ('–'/5/)    /3/.  -> '–'/1/
k/div/ ('–'/5/) '–'/3/.  ->    /1/

Функции p1, m1 имеют 1 аргумент и возвращают соответственно макроцифру, увеличенную на 1 или уменьшенную на 1. Например, следующие вызовы приведут к таким результатам:

k/p1/  '–'/2007/.   ->  '–' /2006/
k/p1/.              ->         /1/
k/m1/     /2007/.   ->      /2006/
k/m1/.              ->      '–'/1/

Функция symb преобразует макроцифру (аргумент) в символьное представление. Например, следующие вызовы функции приведут к таким результатам:

k/symb/  '–'/2007/.  ->  '–2007'
k/symb/.             ->      '0'

Функция numb преобразует цепочку символов (аргумент), являющуюся десятичной записью целого числа в макроцифру этого числа. Например, следующие вызовы функции приведут к таким результатам:

k/numb/  '–2007'.  ->  '–'/2007/
k/numb/      '0'.  ->        /0/

Функции лексического анализа

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

k/first/  /2/  'A'('B')'C'. ->   ('A'('B')) 'C'
k/first/  /5/  'A'('B')'C'. ->     '*A'('B')'C'
k/last/  /2/  'A'('B')'C'.  ->   'A' (('B')'C')
k/last/  /5/  'A'('B')'C'.  ->     'A'('B')'C*'
k/lengw/  'A' () ('A').     -> /3/ 'A' () ('A')
k/lengw/  .                 ->              /0/
k/lengr/  'A' () ('A').     -> /6/ 'A' () ('A')
k/lengr/  .                 ->              /0/
k/multe/  /5/ 'A'.          ->          'AAAAA'
k/multe/  /2/ 'A'('B').     -> 'A'('B')'A'('B')

Функции для работы с символами-метками

Иногда требуется превратить символ-метку в цепочку символов, из которой она состоит, и при этом, если одну и ту же символ-метку превращать в цепочки символов несколько раз, то требуется, чтобы получались одинаковые цепочки. Наоборот, иногда требуется превратить цепочку символов в символ-метку. При этом одинаковые цепочки должны превращаться в одну и ту же символ-метку. Наконец, полученную из цепочки символ-метку иногда требуется зарегистрировать в качестве имени функции. Этим целям служат приведенные в табл. 4.2 функции. В качестве примеров приведем следующие вызовы функции, которые дадут такие результаты:

k/ftochar/  /aaaa3434/.  ->  'aaaa3434'
k/ftochar/  /ABCD/.      ->      'ABCD'
k/chartof/  'aaaa3434'.  ->  /aaaa3434/

   k/chartof/   'ABCD'.   -> /ABCD/
   k/functab/   /func1/.  ->

Примеры программ

Рефал является металингвистическим языком для формализации синтаксиса алгоритмических языков. В этом его основное назначение, но благодаря первичным арифметическим функциям возможна реализация и вычислительных алгоритмов. Мы рассмотрим 2 примера, показывающие возможности Рефала в этих двух направлениях.

Синтаксический анализатор для языка арифметических выражений

Рассмотрим упрощенный язык арифметических выражений, в котором введены всего 2 арифметические операции: сложение (+) и умножение (*), а также переменные, числа и скобки, определяющие порядок вычислений. Синтаксис языка определен следующими формами Бэкуса-Наура (БНФ):

<арифмвыр>       ::= <арифмвыр>+<множитель>| 
                     <множитель>
<множитель>      ::= <множитель>*<первичное>| 
                     <первичное>
<первичное>        ::= (<арифмвыраж>)|<число>| 
                        <имяпеременной>
<число>            ::= <цифра>|<число><цифра> 
<имяпеременной>    ::= <буква>|<имяпеременной><буква>| 
                       <имяпеременной><цифра>
<цифра>            ::= 0|1|2|3|4|5|6|7|8|9
<буква>            ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|
                       S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|
                       p|q|r|s|t|u|v|w|x|y|z

Например, правильным арифметическим выражением является следующее

a+(2+c*d)*(d+(a+c)*2),

а выражение

a+(2+c*d*(d+)(a+c)*2)

не является правильным, так как его часть (d+)(a+c) не является множителем (выражение в первых скобках не является правильным арифметическим выражением - нет множителя после знака '+' и между первым и вторым первичными выражениями в скобках нет знака '*' ).

Необходимо построить для этого языка синтаксический анализатор, который бы проверял вводимое арифметическое выражение и в случае правильности выдавал бы в качестве результата на экран строку "Выражение верно", а в случае ошибочности указывал бы ошибочное место и диагностику ошибки (например, "ошибка: d+ - не имя переменной" ).

Программа анализатора на Рефале будет выглядеть следующим образом:

ANALYZE     START
            ENTRY   ArExpr
            EXTRN   prout, card
ArExpr        = k/pr/ k/арифмвыр/ k/prout/'Введите: '. k/card/...

арифмвыр   R  V1'+'V2  = k/арифмвыр/V1. k/множитель/V2.
              E1       = k/множитель/ E1.
множитель   R V1'*'V2   = k/множитель/V1. k/первичное/V2.
                V1      = k/первичное/ V1.
                        = '?' – пропущен множитель
                      
первичное    '('E1')'   = k/арифмвыраж/ E1.
              S(D)1 E2  = k/число/ S1 E2.
              S(L)1 E2  = k/имяпеременной/ S1 E2.
              V1        = '?'V1 – не первичное выражение
           
число         V(D)1     =
              E1        = '?'E1 – не число
           
имяпеременной   S(L)1 E(LD)2   =
                E1             = '?'E1 – не имя переменной
               
pr              '?' E1       = к/prout/ 'ошибка: ' E1.
                E1           = k/prout/ – является выражением.
                
             END

В этой программе вслед за директивой начала START идет директива ENTRY, определяющая в качестве входа программы функцию ArExpr, и директива EXTRN, определяющая использование внешних модулей с первичными функциями ввода card и вывода prout.

Функция ArExpr, с которой начинается выполнение программы, выводит функцией prout приглашение "Введите: ", затем вводит функцией card строку выражения, производит анализ выражения функцией арифмвыр и, наконец, выводит функцией pr результат синтаксического анализа.

Описание функций арифмвыр, множитель и первичное соответствует БНФ языка арифметических выражений: их рефал-предложения в точности соответствуют альтернативам в правых частях соответствующих БНФ.

С БНФ буква и цифра языка мы не связываем функций программы, так как в Рефале им соответствуют множество L символов букв и множество D символов цифр. Поэтому функции число и имяпеременной определены рефал-предложениями с использованием этих множеств.

В описаниях функций, соответствующих БНФ языка, добавлены в конце рефал-предложения, которые диагностируют соответствующую ошибку и с этой целью помечают диагностику ошибки символом '?', позволяющим функции pr идентифицировать ошибку и вывести диагностику. Второе рефал-предложение функции pr выводит сообщение о верности арифметического выражения, т. е. соответствии с приведенным синтаксисом языка арифметических выражений.

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

Суммирование последовательности чисел

Рассмотрим пример разработки программы суммирования последовательности чисел. Числа вводятся с клавиатуры и суммируются до тех пор, пока не будет введен нуль. В этом случае сумма чисел выдается на экран.

Из постановки задачи следует, что каждое вводимое число должно анализироваться на нулевое значение - признак окончания суммирования и, если оно не нуль, накапливаться в сумме. В качестве начального значения суммы возьмем нуль, а ввод очередного слагаемого будем делать в самой функции суммирования. Таким образом, функция sum суммирования:

Эти 2 действия можно осуществить двумя рефал-предложениями функции, что и делает следующая программа.

SUMMA    START  
         ENTRY   Summ 
         EXTRN   prout, card, numb, symb, add 
Summ  = k/pr/ k/sum/(/0/) k/prout/'Добавьте число '.
                                          k/numb/ k/card/....
sum (S(N)1) /0/    = S1
    (S(N)1) S(N)2  = k/sum/ (k/add/ (S1) S2.)
                             k/prout/'Добавьте число '.
                                          k/numb/ k/card/...
pr  S(N)1          = к/prout/ 'Сумма=' k/symb/ S1.
    E1             = k/prout/ 'ошибка: 'E1.
    
        END

Первичная функция numb преобразует вводимое число из цепочки символов в символ-число, add - добавляет в накапливаемую сумму очередное число, а symb - преобразует полученный результат к выводимой цепочке символов.

Упражнения