Cистемное программирование учебное пособие – элементы теории компиляции


LA (1) -грамматики. Леворакурсивные и расширенные продукции

Неформально можно определить LA (1) -грамматики, как такую, что является контестном-свободной и позволяет выбирать необходимую для развертывания продукцию по первым символом еще не распознанной части слова. «LA (1)» обозначает предложение «L ook A head 1 symbol», то есть «посмотреть вперед на 1 символ».

Правило вида A Av называется ливорекурсивним.Если в грамматике есть продукции A Av | u, где u е — пустая строка), то грамматика — не LA (1) -грамматики, но ее можно превратить в LA (1) -грамматики.

С помощью правил A Av | u выводятся слова из множества {u, uv, uvv …}, которая задается регулярным выражением uv * или u {v}.Записи v * и {v} означают, что цепочка v может повторяться сколько угодно раз или ни разу.

Продукции с регулярными выражениями в правой части называются

расширенными, как и грамматики с такими продукции.

Вместо продукций A Av | u запишем расширенную продукцию A u {v}.Правила вида A u {v} уже удовлетворяют условиям LA (1) — грамматик.

построим эквивалентную

G ({E, T, F}, {a, * , (,)}, P, E)

рас-

Рену грамматику G 0, записав вместо продукций P продукции P1:

P: E E + T | T, T T * F | F, F (E) | a P 1: E T {+ T}, T F {* F}, F (E) | a

Грамматика G — это LA (1) -грамматики. К такой грамматики можно применить метод рекурсивного спуска. Каждое правило расширенной грамматики G можно изобразить с помощью синтаксической диаграммы.

синтаксические диаграммы

Синтаксической диаграммой [2] называется ориентированный граф с двумя фиксированными вершинами: входная вершина, из которой выходит одна дуга, и конечная вершина, в которую входит одна дуга.Дуги графа могут быть замеченными терминальными и нетерминальный символами.

Вид синтаксической диаграммы для правила B , где B N, — регулярное выражение в алфавите N T, можно определить рекурсивно:

  1. Если L = a, a є T, то диаграмма имеет вид:
  1. imageРис.10.
  2. Если L=A, AєN, то диаграмма имеет вид:imageРис.11.
  3. Если L=1|2|…|n, де і –регулярные выражения, то диаграмма имеет вид:imageРис.12.
  4. Если L=12n, де і – регулярные выражения, то диаграмма имеет вид:

    -

    *

    *

    Рис.13.

  5. Если =1 , де 1 регулярные выражения, то диаграмма имеет вид:

image

Если задана расширена грамматика, то ей соответствует набор диаграмм, по одной диаграмме на каждое правило, соответствующий одному нетерминалу.

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

Синтаксический анализатор распознавания выражений

Методом рекурсивного спуска построим синтаксический анализатор, распознающий язык грамматики

G ({E, T, F}, {a, * , (,)}, P 1, E)

С продукцией P 1: E T {+ T}, T

F {* F}, F (E) | a.Для этого каждое правило расширенной грамматики представим с помощью синтаксической диаграммы.

Синтаксическая диаграмма нетерминала E (правило E T {+ T}):

image

age

Рис.15.

Синтаксическая диаграмма нетерминала T (правило T F {* F}):

image

Рис.16.

Синтаксическая диаграмма нетерминала F (правило F (E) | a):

image

Рис.17.

Для каждого правила по синтаксической диаграмме напишем одноименную функцию.

Здесь по синтаксических диаграммах запрограммировано метод

рекурсивного спуска. Сначала вызывается функция E (), которая соответствует главному нетерминалу, далее из нее вызывается функция Т (), которая соответствует понятию «слагаемое». Она, в свою очередь обращается к «множителя» (функция F ()), а то, применяя косвенную рекурсию, — снова к функции E ().

Если на вход данной программы подать некоторое цепочку, то программа, проанализировав его, даст ответ, принадлежит цепочка языке грамматики G 0.

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

Построение синтаксического анализатора математических формул

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

Интерпретатор формул должен

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

    Запуск процесса вычисления

    Для запуска процесса вычисления формулы используется функция calculate с двумя параметрами: входной строку, в которой задается формула по правилам, принятым в языке Basic, и значение переменной х. Если переменная в строке с формулой не используется, то второй параметр можно опустить.

    // стартовая программа

    double calculate (char * line, double x = 0)

    {

    var_value = x; // глобальная переменная (значение переменной х Error = 0; // глобальная переменная (наличие ошибок)

    // запись входной строки в входной поток cin cin = * new istream (100, line)

    get_token (); // лексический анализ (считывание лексемы) double result = expr (); // синтаксический анализ (вычисления) if (Error) return 0; // анализ ошибок

    else return result;

    }

    void main () // пример основной программы

    {

    // результат, очевидно, равна 1 cout << «Result =»

    << calculate ( «sin (x) ^ 2 + cos (x) ^ 2», 23.4567) << << endl;

    // результат равен 15

    cout << «Result =» << calculate ( «sqrt (x ^ 2) ^ 3-3 * (1 + x)», 3) << endl; cout << «Result =» << calculate ( «- ((23.4-0.1) ^ 2) ^ 3») << endl; cout << «Result =» << calculate ( «sin (-0.0123) / 219999») << endl; cout << «Result =» << calculate ( «- 123.123E-10») << endl;

    }

лексический анализ

Задача лексического анализа заключается в последовательном считывании символов и составлении из них лексемы, с которой работают уже функции более высокого уровня — функции синтаксического анализатора. Входная строка записан в стандартный входной поток C ++ cin. Лексический анализатор читает символы из потока и передает информацию о следующей лексему синтаксическому анализатору.

В программе используются такие глобальные переменные:

enum token_value // типы лексем

{

VAR, // переменная х NUMBER, // число PLUS, // знак «+»

MINUS, // знак ‘-‘

MUL, // знак ‘*’

DIV, // знак ‘/’

LP, // знак ‘(‘

RP, // знак ‘)’

FUNC, // имя функции

POW, // знак «^» (возведение в степень) END // признак конца строки

};

token_value curr_tok; // текущая лексема double var_value = 0 // значение переменной х

double number_value; // значение последнего числа int function_code; // код последней функции int Error; // флажок ошибки

Функцию лексического анализа выполняют подпрограммы

token_value get_token (); // функция получения текущей лексемы token_value function (); // сканирования имени функции

Функция получения текущей лексемы

token_value get_token ()

{

// Пропуск пробелов и проверка окончания цепочки do {

if (!cin.get (ch)) return curr_tok = END;

} While isspace (ch);

if (isdigit (ch) || ch == ‘.’) // лексема типа NUMBER

{Cin.putback (ch); cin >> number_value;

return curr_tok = NUMBER;}

switch (ch) {// определение типа других лексемы case ‘x’: return curr_tok = VAR;

case ‘*’: return curr_tok = MUL; case ‘/’: return curr_tok = DIV; case ‘+’: return curr_tok = PLUS; case ‘-‘: return curr_tok = MINUS; case ‘^’: return curr_tok = POW; case ‘(‘: return curr_tok = LP; case ‘)’: return curr_tok = RP; default: // лексема типа FUNC if (isalpha (ch))

{

cin.putback (ch); return function ();

}

return error ( «неверная лексема»)

}

}

Функция определения имени функции и ее кодирование

token_value function ()

{

char func_name [20]; char * p = func_name, ch;

// накопления строки с ыменем

while (cin.get (ch) && isalnum (ch)) * p ++ = ch;

// возврат во входной поток лишнего символа cin.putback (ch);

* P = ‘\ 0’; // признак конца имени функции

// определение конкретной функции и установки ее кода if (!strcmp (func_name, «sqrt»)) function_code = 1; else if (!strcmp (func_name, «sin»)) function_code = 2; else if (!strcmp (func_name, «cos»)) function_code = 3; else return error (strcat ( «неизвестная функция:» func_name)) return curr_tok = FUNC;

}

Обработка ошибок

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

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

В приведенном выше коде происходило обращение к функции error (), которая в качестве параметра получает строку с описанием ошибки, состоялась. К этой функции мы будем обращаться и с синтаксического анализатора. Она выводит сообщение об ошибке и устанавливает значение переменной Error = 1. Эту переменную необходимо будет анализировать при получении результата. Поскольку, если произошла ошибка результаты анализатора являются неверными, необходимо изменить входной строку и повторить запуск.

Функция обработки ошибок

// выводит ошибку и прекращает считывания лексем token_value error (char * s)

{

Error = 1; // глобальная переменная cerr << «Ошибка:» << s << endl; return curr_tok = END;

}

синтаксический анализ

Структуру математической формулы определим с помощью конткстно-свободной грамматики, которую превратим в LA (1) -грамматики.

Грамматика анализатора имеет вид G = (N, T, P, EXPR), где множество нетерминальных символов задается так:

N = {EXPR, TERM, PRIM, POW}

а множество терминальных символов —

T = {+, -, /, *, ^, (,), FUNC, VAR, NUMBER, END}.

    • Напомним, что терминальные символы распознаются на этапе лексического анализа и в программе значки:
      • VAR — переменная х;
      • NUMBER — действительное число;
      • PLUS — знак «+»;
      • MINUS — знак «-«;
      • MUL — знак ‘*’;
      • DIV — знак ‘/’;
      • LP — знак ‘(‘;
      • RP — знак ‘)’;
      • FUNC — имя функции (sin, cos или sqrt)
      • POW — знак «^» (возведение в степень)
      • END — признак конца строки.

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

Правило: EXPR -> TERM {+ TERM | -TERM}

image

Рис.18.

Правило: TERM -> POW {/ POW | * POW}

image

Рис.19. Правило: POW -> PRIM {^ PRIM}

image

Рис. 20.

правило:

PRIM -> NUMBER | VAR | -PRIM | (EXPR) | FUNC (EXPR) | END

image

Рис.21.

Каждому нетерминалу грамматики соответствует своя функция с именем, которое совпадает с нетерминалом, но пишется строчными буквами. Каждая из функций вызывает другие функции (с более высоким приоритетом). Терминальные символы (например, END, NUMBER, +) распознаются лексическим анализатором (функция get_token ()). Нетерминальные символы распознаются функциями синтаксического анализатора expr (), term () pow () и prim (). Как только оба операнда выражения или вложенного выражения стали известны, он вычисляется.

Для всех функций синтаксического анализатора предполагается, что функция get_token () уже была вызвана, и поэтому в глобальной переменной curr_tok хранится следующая лексема, подлежащая анализу. Это позволяет анализатору заглядывать на одну лексему вперед. Каждая функция анализатора всегда читает на одну лексему больше, чем нужно для распознавания того правила, для которого она

вызывалась. Каждая функция анализатора вычисляет «свой» выражение и возвращает его результат.

Функция обработки операций типа сложения

Функция expr () обрабатывает сложение и вычитание. Она состоит из одного цикла, в котором распознанные термы добавляются или вычитаются. Отметим, что выражение вида 21-3 + 42 исчисляются как (21-3) +42, что определяется правилами грамматики.

double expr () {

double left = term ();

while (curr_tok == PLUS || curr_tok == MINUS) if (curr_tok == PLUS) {get_token (); left + = term ();}

else {get_token (); left — = term ();}

return left;

}

Функция обработки операций типа умножения

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

double term () {

long double left = pow ();

while (curr_tok == MUL || curr_tok == DIV) if (curr_tok == MUL)

{

else

get_token (); left * = pow ();

}

{

get_token ();

long double d = pow ();

if (d == 0) return error ( «деление на 0») left / = d;

}

return left;

}

Функция обработки операции возведения в степень

Функция pow () отвечает за вычисления степени. Она работает с первичными нетерминалами, то есть вызывает функцию prim () для получения операндов. А также проверяет на допустимость значений операндов и в случае ошибки сообщает об этом.

double pow ()

{Double left = prim (); while (curr_tok == POW)

{

get_token (); long double p = prim ();

if ((left == 0) && (p == 0)) left = 1;

else

if ((left <= 0) && ((int) p!= P)) return

error ( «при пiднесеннi в степень x ^ y x <= 0 а y-никак целое») else

if ((left == 0) && (p <0)) return

error ( «при пiднесеннi в степень x ^ yx = 0 a y <0»); else

left = pow (left, p)

}

return left;

}

Функция обработки первичного (primary)

Функция prim (), который обрабатывает первичное, во многом похожа на функции expr (), term () i pow (). Это самый низкий уровень рекурсивного спуска, то есть в этой функции вычисляются выражения наивысшего приоритета: возвращаются значения чисел и переменных, вычисляются значения функций и т.д. При этом ведется контроль над допустимыми значениями аргументов функций.

double prim () {

switch (curr_tok) {

case NUMBER: get_token ();

return number_value; case VAR: get_token ();

return var_value; case MINUS: get_token (); return -prim ();

case LP:

{

get_token (); double e = expr (); if (curr_tok!= RP)

return error ( «отсутствует)»)

get_token (); return e;

}

case FUNC:

{

get_token (); if (curr_tok!= LP)

return error ( «отсутствует («); get_token ();

double e = expr (); if (curr_tok!= RP)

return error ( «отсутствует)») get_token ();

switch (function_code)

{

{Case 1: {if (e> = 0) return sqrt (e) else return error ( «аргумент <0»);}

case 2: return sin (e) case 3: return cos (e)

}

}

case END: return 0;

default: return error ( «отсутствует переменная или число»);

}

}

Построение интерпретатора языка программирования SPL

Неформальное описание языка SPL

В качестве примера применения основных методов компиляции рассмотрим написанный на языке С интерпретатор, созданный для реализации простой универсального языка программирования высокого уровня SPL [2].

Формальное описание синтаксиса языка задается с помощью формальных грамматик и будет рассматриваться далее.

Алфавит языка SPL образуют:

  • буквы латинского алфавита;
  • десятичные цифры;
  • символы + — * /% = () ,; \ T \ n и пробел.Из символов состоят лексемы — минимальные цепочки, имеют самостоятельное содержание.

    Идентификатором является последовательность букв и цифр, начинающаяся с буквы.Числом без знака — последовательность цифр. С позиций синтаксиса языка все идентификаторы одинаковые и образуют лексему, что обозначается через IDEN.

    Аналогично целые числа без знака образуют лексему NUMB. Оды- надцать специальных идентификаторов задают служебные слова:

    if, while, return, print, read, begin, end, int, const, then, do.

    Символы \ t, \ n и пробел допустимые в каждом месте программы, за исключением идентификаторов и чисел без знака; в процессе обработки программы они не принимаются во внимание. Знаки операций +, -, *, /,% и разделители ‘(‘, ‘)’, ‘,’, ‘; образуют отдельные лексемы.

    Язык SPL имеет только цели скалярные данные: константы (идентификаторы, числа) и переменные. Переменные могут быть такими: глобальными (областью действия их есть вся программа и память для них выделяется статически) и локальными (областью их действия является функция, где они определяются, а память для них выделяется динамически). Выражения строятся из констант, переменных и имен функций с применением круглых скобок и знаков целочисленных операций +, -, *, /,%.

    Выражения задаются так: v, c, (е 1), f (е 1, е 2, …, е n), е 1 + е 2, е первые 2, е 1 * е 2, е 1 / е 2, е 1% е 2, + е 1 — е 1, где v переменная, с константа, f — идентификатор функции, е 1, е 2, …, е п — выражения.

    В языке SPL являются операторы:

    • присвоение v = е;
    • условный if e then sp end;
    • цикла while e do sp end;
    • возвращение return e;
    • печати print e;
    • введение read v;(V означает переменную, e — выражение, sp — список операторов).В условном операторе и в операторе цикла sp выполняется, если значение выражения e больше нуля — ему соответствует истинность; значению e 0 соответствует ошибочность.Программа состоит из функций и описания глобальных переменных и констант, которые должны быть описаны к их использованию. Описания задаются в виде

      int v1, v2, …, vl;

      const с1 = n1, c2 = n2, …, ck = nk;

      где c1 c2, …, ck идентификаторы констант, n1 n2, …, nk — число, v1, v2, …, vl, — идентификаторы переменных. Имя одной функции — main, с этой функции начинается выполнение программы.

      Функция может зависеть от параметров и описывается так:

      f (p1, p2, …, pn) begin

      dcl spop

      end

      Здесь f — идентификатор функции, p1, p2, …, pn различные идентификаторы формальных параметров, spop — список операторов, dcl — описание локальных констант и переменных. Параметры передаются только по значению. Допускаются прямая и косвенная рекурсии.

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

      Функция может возвращать значение или оператором return e в место вызова, или изменением значений глобальных переменных. Программа заканчивает работу, если достигнут конец end какой-либо функции и при исполнении не встретился оператор return, или если в функции main встретится оператор return е — тогда значение выражения е печатается.

      Пример: SPL-программы для вычисления максимума двух введенных чисел с демонстрацией использования функции max ().

      Файл VAR1.SPL

      main () begin

      int x, y;

      read x; read y; print max (x, y)

      end

      max (a, b) begin

      if ab then return a end; if ba then return b end; return a

      end

      Пример Следующая программа вычисляет результат возведения в степень значения а с неотъемлемым показателем степени b,

      показывая возможности передачи параметров функции main () и использование оператора return e в функции main ().

      Файл VAR2.SPL

      main (a, b) begin

      int z; z = 1; while b do

      if b% 2 then z = z * a end; a = a * a; b = b / 2;

      end; return z

      end

      состав интерпретатора

      Разработаем интерпретатор для SPL, состоящий из фаз:

      • лексического анализа (файл lexan.cpp)
      • синтаксического анализа (syntax. cpp)
      • интерпретации (inter.cpp)
      • работы с таблицами (table.cpp).Описания типов данных, используемых помещенные в файле protot.h. Там же описано прототипы функций.Используются вспомогательные файлы:
      • error.cpp — содержит функции сообщений об ошибках;

      • printrez.cpp — печать в файлы созданных таблиц и объектной программы.

        Для вызова интерпретатора надо вызвать файл spl.exe с параметром — именем файла, где записана spl-программа. Интерпретатор последовательно проводит лексический, синтаксический анализы, генерирует объектный код, а затем его выполняет. Если в SPL-программе есть ошибки, то интерпретатор работает до первой обнаруженной ошибки, выдает сообщение об ошибке с номером ошибочной строки и заканчивает работу.

        Если приведенные выше SPL-программы записаны соответственно в файлах VAR1.SPL и VAR2.SPL, то результатом работы интерпретатора с исходными данными 3 и 4 на дисплее:

        > SPL VAR2. SPl> SPL.EXE VAR1. SPl

        2> 3 4 1> 3

        81 1> 4

        4

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

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

image

Рис.22.

Ниже записано главный файл Spl.cpp с функцией main ().

      • лексический анализ

        В процессе лексического анализа различаются лексемы:

  • служебные слова if, while, return, print, read, begin, end, int, const, then, do;кодируемые соответственно константами IFL, WHILEL, RETRL, PRITL, READL, BEGINL, ENDL, INTL, CONSTL, THENL, DOL;
  • знаки операций и разделители, закодированные литерально константами ‘+’, ‘-‘, ‘*’, ‘/’, ‘%’, ‘=’, ‘(‘, ‘)’, ‘,’, ‘; ;
  • целое без знака с кодом NUMB;
  • идентификатор с кодом IDEN;
  • конец файла с кодом EOF.В процессе лексического анализа определятся глобальные переменные:
  • lex — тип (номер) распознанной лексемы;

  • lvalnumber — значение лексемы, если lex = NUMB — целое число;

  • lvalword — значение лексемы, если lex = IDEN — указатель на элемент в таблице идентификаторов TNM;

  • nst — номер строки программы, содержит лексему.

    Заголовочный файл protot.h, который подключается к функциям лексического анализа, содержит прототипы функций, структуры и др, в частности, там описано константы, которые определяют лексемы:

    enum {IFL = 257, WHILEL, RETRL, PRITL, READL, BEGINL, ENDL, INTL, CONSTL, THENL, DOL, NUMB, IDEN

    };

    Файл Lехan.сpp содержит функции лексического анализа:

    • get () — введение с файла PF наступноi лексемы в lex и при необходимости — в lvalnumber и lvalword;

    • number () — введение лексемы число;

    • word () — введение лексемы идентификатор или

ключевое слово.

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

файл Lехan.сpp

Функция add () осуществляет поиск и при необходимости вводит иден- тификатор в таблицу TNM. Массив TNM содержит цепочки букв, которые задают все разные идентификаторы, которые встречаются в начальной программе. Так, массив для программы VAR1.SPL содержит 6 цепочек: «main», «x», «y», «max», «a», «b» и указатель ptn первого свободного элемента массива TNM [400]:

main \ 0x \ 0y \ 0max \ 0a \ 0b \ 0

0 5 7 9 13 15 ptn

Описание функции add () и таблицы TNM, расположен в файле table.cpp, имеет вид:

файл Тable.cpp

char TNM [400], * ptn = TNM; // Таблица TNM

// add — поиск и добавление в TNM iдентiфiкатора nm char * add (char * nm)

{

char * p;

for (p = TNM; p <ptn; p + = strlen (p) +1) if (strcmp (nm, p) == 0) return p;

if ((ptn + = strlen (nm) 1)> TNM + 400) error1 ( «переполнения TNM»)

return (strcpy (p, nm))

}

синтаксический анализ

Формальный синтаксис языка SPL

Синтаксис языка SPL описывается расширенными грамматиками с использованием символов [] в регулярных выражениях в правых частях правил. Если r — регулярное выражение, задает множество R, то [r] — регулярное выражение для множеств R {e}, где e — пустая строка.

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

Нетерминалами есть последовательности букв PROG, DCONST, DVARB, DFUNC, CONS, PARAM, BODY, STML, STAT, EXPR, TERM, FACT,

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

Полный синтаксис языка SPL выглядит грамматики G = (N, T, P, PROG), где множества

нетерминалов N = {PROG, DCONST, DVARB, DFUNC, CONS, PARAM, BODY, STML, STAT, EXPR, TERM, FACT, FCTL}

терминалов T = {ifl, whilel, retrl, pritl, readl, beginl, endl, intl, constl, thenl, dol, numb, iden, eof, ‘+’, ‘-‘, ‘*’, ‘/’, ‘% ‘,’ = ‘,’ ( ‘,’) ‘,’, ‘,’; }

а правила грамматики P задаются так:

  • PROG -> (DCONST | DVARB | DFUNC) * eof программа
  • DCONST -> constl CONS ( ‘,’ CONS) * ‘; описание констант
  • CONS -> iden ‘=’ [ ‘+’ | ‘-‘] numb константа в описании
  • DVARB -> intl iden ( ‘,’ iden) * ‘; описание переменных
  • DFUNC -> iden PARAM BODY описание функций
  • PARAM -> ‘(‘ [iden ( ‘,’ iden) *] ‘)’ список параметров
  • BODY -> beginl (DCONST | DVARB) * STML endlтело функции
  • STML -> STAT ( ‘; STAT) * список операторов
  • STAT-> ifl EXPR thenl STML endl оператор| whilel EXPR dol STML endl| retrl EXPR | pritl EXPR | readl iden | iden ‘=’ EXPR
  • EXPR -> [ ‘+’ | ‘-‘] TERM (( ‘+’ | ‘-‘) TERM) * выражение
  • TERM -> FACT (( ‘*’ | ‘/’ | ‘%’) FACT) * слагаемое
  • FACT -> «(» EXPR ‘)’ | numb | iden [ ‘(‘ [FCTL] ‘)’] множитель
  • FCTL -> EXPR ( ‘,’ EXPR) * список аргументовЭта грамматика является LA (1) -грамматики и позволяет делать синтаксический анализ с помощью синтаксических диаграмм. В разрабатываемом интерпретаторе синтаксический анализ ведется до обнаружения первой ошибки, после чего печатается сообщение и работа завершается. В процессе анализа используется функция exam (lх), которая проверяет, имеет ли следующая лексема код lх. Если так, то вводится следующая лексема, а если нет, то анализ завершается после обнаружения ошибки:

    extern int nst, lvalnumber, lex; extern char * lvalword;

    void exam (int lx)

    {

    if (lx!= Lex) error4 ( «% d: ошибка синтаксиса», nst) get ();

    return;

    }

    Процедуры синтаксического анализа (по одной на каждый нетерминал) размещаются в файле syntax.cpp, куда входит также функция exam (). Все функции используют функцию get () лексического анализа и глобальные переменные lex, nst, lvalword, lvalnumber.

    По каждому правилу стоит определенное понятие языка SPL. Первые шесть правил грамматики определяют структуру объявлений в языке SPL. Все остальные описывают структуру операторов и выражений.

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

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

анализ объявлений

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

Правило: PROG -> (DCONST | DVARB | DFUNC) * eof

image

Рис.23.

// prog — программа; анализ и завершения обработки void prog (void)

{

while (lex!= EOF) switch (lex)

{

case CONSTL: dconst (); break; case INTL: dvarb (); break; case IDEN: dfunc (); break;

default: error4 ( «% d: ошибка синтаксиса», nst)

}

return; }

Правило: DCONST -> constl CONS ( ‘,’ CONS) * ‘;

image

Р ис.24.

// dcons — описание констант void dconst (void)

{

do

{Get (); cons (); }

while (lex == ‘,’);

exam ( ‘;’); return;

}

Правило: CONS -> iden ‘=’ [ ‘+’ | ‘-‘] numb

image

Рис.25.

// cons — константа в описании void cons (void)

{

exam (IDEN) exam ( ‘=’);

if (lex == ‘+’ || lex == ‘-‘) get (); exam (NUMB)

return;

}

Правило: DVARB -> intl iden ( ‘,’ iden) * ‘;

image

Р ис.26.

// dvard — описание переменных void dvarb (void)

{

do

{Get (); exam (IDEN) }

while (lex == ‘,’);

exam ( ‘;’); return; }

Правило: DFUNC -> iden PARAM BODY

image

Рис.27.

// dfunc — описание функций void dfunc (void)

{

get (); param (); body (); return;

}

Правило: PARAM -> ‘(‘ [iden ( ‘,’ iden)] ‘)’

image

Рис.28.

// param — список параметров void param (void)

{

exam ( ‘(‘)

if (lex!= ‘)’)

{

exam (IDEN) while (lex == ‘,’)

{Get (); exam (IDEN) }

}

exam ( ‘)’); return;

}

Анализ операторов и выражений

Правило: BODY -> beginl (DCONST | DVARB) * STML endl

image

Рис.29.

// body — тело функции void body (void)

{

exam (BEGINL) while (lex == CONSTL || lex == INTL)

if (lex == INTL) dvarb (); else dconst ();

stml (); exam (ENDL) return;

}

Правило: STML -> STAT ( ‘; STAT) *

image

Рис.30.

// stml — список операторов void stml (void)

{

stat (); while (lex == ‘;’)

{Get ();

stat (); } Return;

}

Правило: STAT-> ifl EXPR thenl STML endl

| whilel EXPR dol STML endl

| retrl EXPR | pritl EXPR | readl iden | iden ‘=’ EXPR

image

Рис.31.

// stat — оператор void stat (void)

{

switch (lex)

{

case IFL: get (); expr (); exam (THENL) stml (); exam (ENDL) break;

case WHILEL: get (); expr (); exam (DOL) stml (); exam (ENDL) break;

case RETRL: get (); expr (); break; case PRITL: get (); expr (); break; case READL: get (); exam (IDEN) break;

case IDEN: get (); exam ( ‘=’); expr (); break; default: error4 ( «% d: ошибка синтаксиса», nst)

}

return;

}

Правило: EXPR -> [ ‘+’ | ‘-‘] TERM (( ‘+’ | ‘-‘) TERM) *

image

Рис.32.

// expr — выражение void expr (void)

{

if (lex == ‘+’ || lex == ‘-‘) get (); term (); while (lex == ‘+’ || lex == ‘-‘)

{Get (); term (); } Return;

}

Правило: TERM -> FACT (( ‘*’ | ‘/’ | ‘%’) FACT) *

image

Рис.33.

// term — слагаемое void term (void)

{

fact ();

while (lex == ‘*’ || lex == ‘/’ || lex == ‘%’)

{Get (); fact (); } Return; }

Правило: FACT -> «(» EXPR ‘)’ | numb | iden [ ‘(‘ [FCTL] ‘)’]

image

Рис.34.

// fact — множитель void fact (void)

{

switch (lex)

{

case IDEN: get (); if (lex == ‘(‘)

{Get (); if (lex!= ‘)’) Fctl (); exam ( ‘)’);} break;

case ‘(‘: get (); expr (); exam ( ‘)’); break; case NUMB: get (); break;

default: error4 ( «% d: ошибка синтаксиса», nst)

}

return; }

Правило: FCTL -> EXPR ( ‘,’ EXPR) *

image

Рис.35.

// fctl — список аргументов void fctl (void)

{

expr ();

while (lex == ‘,’) {get (); expr (); } Return; }

  • интерпретация

    SPL-процессор

    В процессе синтаксического анализа будет не только проверяться синтаксис SPL-программы. Далее синтаксический анализ будет дополнен генерацией промежуточного кода.

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

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

    SPL-процессор имеет:

    1. память SPL-программы, моделируется глобальными данными:

      • массив TCD (таблица кода)
      • adrnm — адрес главной программы, точка входа в главную программу;

      • cpnm — количество параметров главной программы;

      • cgv — количество глобальных переменных

    2. память данных, моделируется стеком st, где содержатся значения всех данных в процессе интерпретации. Используются указатели (индексы массивов):
      • t — вершины стека st;

      • sp — начало области локальных данных функции (записи активации);

      • p — текущей команды в TCD.

    Поскольку каждая функция в SPL имеет локальные переменные и допускается рекурсия, то необходимо динамическое выделение памяти в стеке st при вызове функции, а при возвращении — ее освобождения.

    При вызове каждой функции, main включительно, в стеке st выделяется запись активации этого вызова, куда заносятся:

    1. значение фактических параметров р 1, р 2, …, р n;
    2. количество параметров n;
    3. адрес возврата в TCD (адрес команды вызова)
    4. адрес предварительной записи активации в стеке (откуда произошла вызов функции);
    5. локальные и временные данные, используемые при исчислении этого вызова функции.

    В любой момент выполнения SPL-программы доступными являются глобальные переменные, которые записаны в начале стека. Обращаться к ним можно: st [k], k = 0,1, …, cgv-1;

    Доступны также локальные данные, которые находятся в верхнем записи активации:

    • параметры, расположенные «ниже» sp, имеют смещение k <0;

    • локальные переменные, расположенные «выше» sp, имеют смещение k> 0.

      Индекс последнего элемента, включенного в стек, равна t. Адрес возврата из main () равен -2.

      Адресация локальных переменных происходит так: st [sp + k]. Смещение для данных вычисляется при обработке описаний в SPL-

      программе; смещение могут быть такими:

    • для n фактических параметров: — (n + 2), …, 4, 3;
    • для локальных данных: 1,2,3, …;
    • для глобальных переменных: 0,1,2, …

      Пусть в программе последовательно вызываются функции main, р0, р1 а функция р1 имеет вид:

      p1 (x, y, z) begin int v, w;

      … end

      Тогда стек St будет включать в себя

      • область глобальных данных, содержащая сgv элементов;
      • записи активации для функций main, p0, р1.

При обработке описаний функции p1 () будут вычислены смещение

x   5, y   4; z   3; v1, w2.

В файл protot.h, кроме кодов лексем, рассмотренных выше, является описание кодов операций и структура команды SPL-процессора:

enum {OPR = 1, LIT, LDE, LDI, STE, STI, CAL, INI, JMP, JMC};

typedef struct {

int code; // код операции int opd; // операнд

} Cmd; cmd TCD [300];

Промежуточный код создается в процессе синтаксического анализа в массиве TCD типа cmd:

TCD [и] = {f, a}, где f = TCD [i] .cod, a = TCD [i] .opd.

Действия задаются кодами операций:

OPR — выполнить операцию а над вершиной стека; LIT — скачать в стек константу a;

LDE, LDI — записать в стек значение глобальной (локальной) переменной со смещением a;

STE, STI — запомнить значение вершины стека в глобальной (локальной) переменной со смещением а;

CAL — вызвать функцию с точкой входа a; INI — увеличить t на a (выделение памяти);

JMP — осуществить безусловный переход на команду a;

JMC — выполнить условный переход на команду a, если верхний элемент стека меньше или равен нулю (этот элемент изымается из стека).

В команде с кодом OPR допустимые операции:

а = 1 — ввести в стек число с stdin;

а = 2 — вывести верхнее значение из стека в stdout;

а = 3, …, 7 — выполнить над двумя верхними элементами стека операцию +, -, *, /,%;

а = 8 — изменить знак верхнего элемента стека;

а = 9 — вернуться в функции (результат размещается в верхнем элементе стека)

а = 10 — остановить выполнение SPL-программы.

При возвращении из функции main () печатается результат и происходит присвоение p = — 1, при завершении остановкой (достигли end в функции) происходит присвоение p = -2.

Выполнение SPL-программы

Все функции, которые выполняют SPL-программы, размещаются в файле inter.cpp.

  • interp () начинает и завершает выполнение SPL-программы, а также осуществляет общее управление;

  • comman () — выполняет текущую команду TCD [p];

  • operat (а) — операцию OPR a;

  • push (а) — заносит значение a в стек;

  • read () — вводит число из stdin в стек.

файл Inter.cpp

Генерация промежуточного кода

Алгоритм создания промежуточного кода SPL-программы

Операторы языка SPL переводятся в промежуточный код по такому принципу:

  • константа или число v со значением val — в {LIT val};
  • глобальная переменная d со смещением а — в {LDE a};
  • локальная переменная или параметр d со смещением а — в {LDI a};
  • вызов функции f (e1, e2, …, en) с точкой входа b — в последовательность команд<e1> <e2> … <en> {LIT n} {CAL b}

    где <e i> — результат перевода выражения e i;

  • выражение е переводится в <e> {OPR 8};
  • выражение e 1 op e 2 (где op — одна из операций +, -, *, /,%) — в последовательность <e 1> <e 2> {OPR a}, где a = 3, 4, 5, 6, 7
  • оператор присваивания d = е, где d — переменная со смещением апереводится в код<e> {STE a} — для глобальной переменной d,«е» {SТИ а} — для локальной переменной d.
  • оператор ввода read d заменяется на{OPR 1} {STE a} — для глобальной переменной,{OPR l} {STI a} — для локальной переменной.
  • оператор print е переводится в код<E> {OPR 2}
  • оператор return e в код<E> {OPR 9}
  • оператор if e then s end переводится в код<e> {JMC l} <s> l:,где l — номер следующей команды по <s>.
  • оператор цикла while е do s end превращается в код

    lb <е> {JMC l} <s> {JMP lb} l:,

    где lb — номер первой команды <e>, l — номер команды, следующей за {JMP lb}.

  • описание функции вида f (p1, p2, …, pk) begin dcl s end, где

p1, p2, …, pk — параметры,

dcl — описание локальных переменных,

s — список операторов функций; переводится в фрагмент промежуточного кода

b {INI l} <s> {OPR 10}

где

b — номер первой команды функции f (bточка входа в f),

l — количество локальных переменных в dcl,

<S> — код, соответствующий список операторов s.

Если при выполнении операторов s НЕ встретится

оператор return, то выполняется команда остановки

{OPR 10}.

Далее будет запрограммировано процесс генерации промежуточного кода. Причем, для каждой программы этот код будет записываться таблицу кода TCD. Посмотреть созданный код можно в файле f.asm.

Приведем пример созданного промежуточного кода по приведенному алгоритму (мистиме файла f.asm) для Spl-программы, которая выводит максимальное из двух чисел, если числа не равны:

Начальная Spl-программа

промежуточный код

main () begin

int x, y; read x; read y;

if xy then print x end; if yx then print y end

end

0:

8

2

|

INI

2

1:

1

1

|

OPR

1

2:

6

1

|

STI

1

3:

1

1

|

OPR

1

4:

6

2

|

STI

2

5:

4

1

|

LDI

1

6:

4

2

|

LDI

2

7:

1

4

|

OPR

4

8:

10

11

|

JMC

11

9:

4

1

|

LDI

1

10:

1

2

|

OPR

2

11:

4

2

|

LDI

2

12:

4

1

|

LDI

1

13:

1

4

|

OPR

4

14:

10

17

|

JMC

17

15:

4

2

|

LDI

2

16:

1

2

|

OPR

2

17:

1

10

|

OPR

10

Операции промежуточного кода представлены сначала в числовом виде, а затем — с использованием мнемоники, определенной в файле protot.h:

enum {OPR = 1, LIT, LDE, LDI, STE, STI, CAL, INI, JMP, JMC};

Работа с таблицами

В процессе анализа SPL — программы создаются такие таблицы:

  • TNM — таблица идентификаторов, создается во время лексического анализа;
  • TCD — таблица кода, содержит промежуточный код, создается во время синтаксического анализа и используется (выполняется) при интерпретации промежуточного кода
  • TOB — таблица данных, создается частично при синтаксическом анализе (существует своя таблица TOB для каждой функции SPL — программы). В таблице данных TOB задается вид каждого из данных (константа, глобальная или локальная переменная) и значения (константы, смещение глобальной переменной относительно «дна» или локальной переменной относительно sp)
  • TFN — таблица функций, создается во время синтаксического анализа. В таблице функций TFN для каждой функции на- водятся количество параметров и адрес точки входа в TCD.

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

Глобальная переменная out указывает тип данных (Оut = 1 означает глобальные данные, а Оut = 0 — локальные данные).

Элемент таблицы ООО имеет следующую структуру (этот тип описано в файле protot.h):

typedef struct

{

char * name; int what; int val;

} Odc;

Компонента ООО [i] .name — задает указатель имени данного в таблице имен TNM, ООО [i] .val -значение константы или смещение переменной, ООО [i] .what — тип данных

1, константа ООО [i] .what = 2, глобальная переменная

3, локальная переменная.

При работе с таблицей ООО используются такие данные из файла

Динамику положений pto и ptol перед анализатором списков внутри функции и после анализа списков внутри функций можно изобразить так:

image

image

глобальные описания Рис.37. анализ локальных описаний

Функция findob (nm) осуществляет поиск описания объекта с именем nm

в ООО:

// findob — поиск элемента данных nm в таблице TOB odc * findob (char * nm)

{

odc * p;

for (p = pto-1; p> = TOB; p—) if (nm == p-> name) return p;

error2 ( «% s: не описано», nm) return p;

}

В таблицу TFN внесена информация обо всех функциях SPL — программы. Описание структуры элемента TFN содержится в файле «protot.h» и имеет вид:

typedef struct

{

char * name; // имя функции в TNM

int isd; // количество параметров функции

int cpt; / * Или описана функция (isd = 1-функция описана, isd = 0 — функция не описана) * /

int start; / * Задает адрес точки входа для описанной функции, или указатель цепи вызовов для обратного заполнения для неописанной функции * /

} Fnd;

На рисунке показана ситуация, когда есть три вызова неописанной функции с именем ABC и k параметрами.

image

Рис.38.

В работе с таблицей TFN используются функции:

  • newfn (nm, df, cp, ps) — добавление нового элемента в TFN,

    nm — имя функции, df — или описана функция, cp-

    количество параметров, ps — точка входа;

  • findfn (nm) — поиск в TFN описания функции с именами nm;

  • eval (nm, cp) — обработка вызова функции nm с количеством параметров cp:

  • defin (nm, cp, ad) — обработка описания функции nm с количеством параметров cp и точкой входа ad;

  • fmain () — завершение работы с TFN, поиска неописанных функций и функции main.

    файл Тable.cpp

Расширение анализа описаний

Таблица ООО и TFN заполняется при обработке описаний. Выполняют эту работу дополнены функции prog () cons () (dconst () без изменений), dvarb () dfunc () param (). Функция param () возвращает значение, равное количеству формальных параметров; функция body () — адрес точки входа в TCD. Модифицированная часть файла syntax.cpp, который был рассмотрен выше, замечено так: // +++.

файл Syntax.cpp

// prog — программа; анализ и завершения обработки void prog (void)

{

fnd * p; // +++ while (lex!= EOF)

switch (lex)

{

case CONSTL: dconst (); break; case INTL: dvarb (); break; case IDEN: dfunc (); break;

default: error4 ( «% d: ошибка синтаксиса», nst)

}

p = fmain (); // +++

adrnm = p-> start; // +++

cpnm = p-> cpt; // +++ return;

}

// cons — константа в описании; анализ и формирование void cons (void)

{

char * nm = lvalword; int s; // +++

exam (IDEN) exam ( ‘=’);

s = (lex == ‘-‘? 1: 1); // +++

if (lex == ‘+’ || lex == ‘-‘) get (); newob (nm, 1, s * lvalnumber) // +++ exam (NUMB)

return;

}

// dvard — описание переменных: анализ и формирование void dvarb (void)

{

do

{

get ();

newob (lvalword, (out? 2: 3), (out? cgv ++: ++ clv)) // +++ exam (IDEN)

}

while (lex == ‘,’);

exam ( ‘;’); return;

}

// dfunc — описание функций: анализ и формирование void dfunc (void)

{

char * nm = lvalword; int cp, st; // +++ get ();

out = 0 // +++

cp = param (); // +++

st = body (); // +++

out = 1; // +++

// Печать таблицы ООО для функции tabzm (nm) pto = ptol; // +++

defin (nm, cp, st) // +++ return;

}

// param — список параметров: анализ и формирование int param (void) // +++

{

odc * p; int cp = 0 // +++ exam ( ‘(‘)

if (lex!= ‘)’)

{

newob (lvalword, 3, ++ cp) // +++ exam (IDEN)

while (lex == ‘,’)

{

get ();

newob (lvalword, 3, ++ cp) // +++ exam (IDEN)

}

}

exam ( ‘)’);

for (p = ptol; p <pto; p ++) // +++ p-> val- = cp + 3; // +++ return cp; // +++

}

В конце функции param () происходит корректировка смещений переменных параметров функции, смещение уменьшается на (cp + 3), образуются нужны смещения.

Так, при обработке описания

p1 (x, y, z) begin int v, w;

… end

будут вычислены такие смещения (часть таблицы TOB):

к image после корректировки

Рис.39.

Расширение анализа операторов и выражений

Расширение синтаксического анализа операторов и выражений связано с формированием промежуточного кода TCD. Меняются все функции, кроме stml (). Функция fctl () возвращает как результат число, равное количеству фактических параметров в вызове. Модифицированные части программ, которые уже рассматривались при синтаксическом анализе, генерируют промежуточный код (через // +++ замечено добавлены фрагменты программы).

файл Syntax.cpp

  • Лабораторная работа «Элементы компиляции»

    задания

    Ознакомиться с интерпретатором для языка SPL, разобрать коды следующих программ:

    • лексический анализ (файл lexan.cpp)
    • синтаксический анализ (syntax. cpp)
    • интерпретатор (inter.cpp)
    • работа с таблицами (table.cpp)
    • типы данных и прототипы функций (protot.h).
  1. Создать и отладить программу на языке SPL по заданному варианту.
  2. Провести лексический анализ созданной SPL-программы (построить таблицы идентификаторов и лексем).
  3. Провеcти грамматический разбор методом рекурсивного спуска одного оператора созданной SPL-программы.
  4. Проанализировать объектную программу (построить стек ST, моделирует память данных и поставить в соответствие операторам созданной SPL-программы фрагменты промежуточного кода).

Пример выполнения лабораторной работы

Условие: Написать SPL-программу для вычисления результата возведения числа x в степень y (y — неотъемлемый показатель).

  1. создание кода

    main () begin

    int x, y; read x; read y;

    print exp (x, y)

    end exp (a, b) begin

    int z; z = 1;

    while b do

    if b% 2 then z = z * a end; a = a * a;

    b = b / 2 end; return z

    end

  2. лексический анализ

    Таблица идентификаторов (массив TNM) нашей программы содержит 7 цепочек: «main», «x», «y», «exp», «a», «b», «z» и указатель ptn первого свободного элемента.

    Таблица идентификаторов

    main \ 0x \ 0y \ 0exp \ 0a \ 0b \ 0z \ 0

    0 5 7 9 13 15 17 ptn

    Таблица лексем

строка

лексема

Тип лексемы

значение лексемы

1

main

IDEN = 269

TNM + 0

1

(

‘(‘ = 40

1

)

‘)’ = 41

2

begin

BEGINL = 262

3

int

INTL = 264

3

x

IDEN = 269

TNM + 5

3

,

‘,’ = 44

3

y

IDEN = 269

TNM + 7

3

;

‘; = 59

4

read

READL = 261

4

x

IDEN = 269

TNM + 5

4

;

‘; = 59

5

read

READL = 261

5

y

IDEN = 269

TNM + 7

5

;

‘; = 59

6

print

PRITL = 260

6

exp

IDEN = 269

TNM + 9

6

(

‘(‘ = 40

6

x

IDEN = 269

TNM + 5

6

,

‘,’ = 44

6

y

IDEN = 269

TNM + 7

6

)

‘)’ = 41

7

end

ENDL = 263

9

exp

IDEN = 269

TNM + 9

9

(

‘(‘ = 40

9

a

IDEN = 269

TNM + 13

9

,

‘,’ = 44

9

b

IDEN = 269

TNM + 15

9

)

‘)’ = 41

10

begin

BEGINL = 262

11

int

INTL = 264

11

z

IDEN = 269

TNM + 17

11

;

‘; = 59

12

z

IDEN = 269

TNM + 17

12

=

‘=’ = 61

12

1

NUMB = 268

1

12

;

‘; = 59

13

while

WHILEL = 258

13

b

IDEN = 269

TNM + 15

13

do

DOL = 267

14

if

IFL = 257

14

b

IDEN = 269

TNM + 15

14

%

‘%’ = 37

14

2

NUMB = 268

2

14

then

THENL = 266

14

z

IDEN = 269

TNM + 17

14

=

‘=’ = 61

14

z

IDEN = 269

TNM + 17

14

*

‘*’ = 42

14

a

IDEN = 269

TNM + 13

14

end

ENDL = 263

14

;

‘; = 59

15

a

IDEN = 269

TNM + 13

15

=

‘=’ = 61

15

a

269

TNM + 13

15

*

‘*’ = 42

15

a

269

TNM + 13

15

;

‘; = 59

16

b

269

TNM + 15

16

=

‘=’ = 61

16

b

269

TNM + 15

16

/

‘/’ = 47

16

2

NUMB = 268

2

17

end

ENDL = 263

17

;

‘; = 59

18

return

RETRL = 259

18

z

269

TNM + 17

19

end

ENDL = 263

Грамматический разбор методом рекурсивного спуска

  1. Проведем грамматический разбор одного оператора программы, а именно оператора: if b% 2 then z = z * a endimageРис.40.

    Здесь использовано правила расширенной грамматики, которые можно применить для формирования дерева разбора. Прямоугольниками обозначены нетерминалы, а овалами или кругами — терминальные символы (лексемы). Листья дерева — терминальные символы. Путь к письмам обозначено пунктиром. Корень дерева — нетерминал STAT, обозначающий понятие «оператор».

    Если надо построить дерево разбора всей программы, то надо начинать с нетерминала PROG, обозначающий понятие «программа».

  2. Анализ промежуточного кода

Стек St содержит

две записи активации для функций main () i exp ():

Рис.41.

варианты заданий

  1. Дано натуральное число n. Есть ли оно палиндромом (то есть его зеркальное отражение совпадает с ним самим. Например, 2552).
  2. Дано натуральное число n. Содержит оно три одинаковые цифры?
  3. Дано натуральное число n. Есть ли в нем повторение цифр?
  4. Доказать, что произвольную денежную сумму n> 7 руб. Выплатить купюрами по 3 руб. и 5 руб. Найти цели aib, что n = 3a + 5b.
  5. Данные натуральные числа n и m. Получить сумму m последних цифр числа n.
  6. Дано натуральное число n. Входит цифра 3 в запись числа n. Переставить первую и последнюю цифры числа n.
  7. Напечатать все числа, которые меньше n и делятся на m, затем те — которые делятся на m — 2, m — 4, …, делятся на 2.
  8. Перевести число n из системы счисления с основанием k в систему счисления с основанием i (2 i 10, 2 k 10).

  9. Дано целое m> 1. Получить больше k, при котором m <4k <2m.
  10. Напечатать все двусмысленные простые числа.
  11. Найти все натуральные числа, не превышающие заданного n и делятся на каждую из своих цифр.
  12. Для заданного натурального числа n цифр в числе и количество разрядов.

    (N 10000)

    вычислить сумму

  13. Дано натуральное число i — основание системы счисления

    (2 i 10).

    Ввести два числа в этой системе счисления (проверить это). Составить и отнять их в заданной системе счисления.

  14. Найти наименьшее общее кратное двух натуральных чисел.
  15. Из заданного натурального числа n изъять цифры 0 и получить представление полученного числа в троичной системе счисления.
  16. Задано натуральные числа а, в (a b).Получить все простые числа p,

    удовлетворяющие неравенство a p b.

  17. Задано натуральное число n. Выяснить, есть ли среди цифр n, n + 1, …, 2n числа близнецы, то есть простые числа, разница между которыми равно двум.
  18. Найти натуральное число от 1 до 10000 с максимальной суммой делителей.
  19. Для заданного натурального числа n выяснить, делится ли оно на каждую из своих цифр, кроме нуля.
  20. Разложить заданное натуральное число n на простые множители.
  21. Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением самого себя. Например, число 6 — совершенное, поскольку 6 = 1 + 2 + 3. Для заданного натурального числа n получить все совершенные числа, меньше n.
  22. Последовательность чисел Фибоначчи,

    u 0, u 1, u 2,

    образуется

    законом:

    u 0, u 1 1, u i u i 1 u i 2 (i = 2,3, …).Ввести число n> 1.

    получить числа

    u 0, u 1, u 2, u n.

  23. Ввести целое положительное число. Определить количество единиц в двоичном представлении числа.
  24. Получить в порядке возрастания n первых натуральных чисел, не делятся ни на один из цифр 2,3,5.
  25. Найти наибольший общий делитель двух натуральных чисел.
  26. Дано целое число k (1 k 180). Определить, какая цифра находится в k -тий позиции последовательности 1011121314 … 9899, в которой вписаны подряд все двузначные числа.
  27. Дано натуральное число k. Определить k-ю цифру в последовательности 110100100010000100000 …, в которой выписаны подряд степени 10.
  28. Ввести натуральное число k. Определить k — ту цифру последовательности 12345678910111213 … в которой выписаны подряд все натуральные числа.
  29. Для заданного натурального числа n получить его представления в двоичной системе счисления.
  30. Дано натуральное число n. Определить, входит цифра 7 в запись числа n 2 1.
  31. Ввести целое положительное десятичное число. Определить количество троекв восьмеричном представлении числа.
  32. Данные натуральные числа n (в троичной системе счисления) и m (в пятилетней системе счисления). Определить, они равны.
  33. Данные натуральные числа n и m. n и m — являются множествами цифр. Найти объединение и пересечение этих множеств.
  34. Данные натуральные числа n и m. n и m — являются множествами цифр. Найти разницы множеств nm и mn, а также дополнения множеств n и m множеству всех цифр.
  35. Данные натуральные числа n и m. Напечатать третью цифру после десятичной запятой числа n / m.
  36. В заданном числе переставить цифры так, чтобы они образовывали невозрастающая последовательность.

Использованная литература

  1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. т. 1. Синтаксический анализ, М .: Мир, 1978.- 489с.

  2. Проценко В.С., Чаленко П.И. Элементы компиляции: Учебное пособие.-М .: УМК ВО, 1988.- 55 с.

  3. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов.- М .: Мир, 1979.- 654 с.

  4. Хантер Р. Проектирование и конструирование компиляторов. М .: Финансы и статистика, 1984.- 232 с.

  5. Бек Л. Введение в системное программирование. М .: Мир, 1988.-448 с.

  6. Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. — M .: Издательский дом «Вильямс», 2001.- 768 c.

  7. Хопкрофт Джон, Мотвани Раджив, Ульман Джефри. Введение в теорию автоматов, языков и вычислений.-M .: Издательский дом «Вильямс», 2002.- 528 c.

  8. Сопронюк Т.М., Сопронюк А.Ю. Использование сервера автоматизации MS EXCEL для организации символьных вычислений в средах VB

    .NET и DELPHI // Третья Международная научно-практическая конференция «Спецпроект: анализ научных исследований»: Сборник научных трудов. — Днепропетровск: ПГАСА, 2007. — С.101-102.

    Интернет-ресурсы

  9. http://se.math.spbu.ru/Courses/dotNETCompilerEngineering/Lectures/ — (С.Петербургского государственный университет)

  10. http://ermak.cs.nstu.ru/trans/ — Е.Л.Романов. Основы построения трансля- торов (Новосибирский государственный технический университет)

  11. http://www-db.stanford.edu/~ullman/ialc.html — Introduction to Automata Theory, Languages, and Computation (Stanford University)

  12. http://www.codenet.ru/progr/alg/cons/001.php — В.А.Серебряков.Лекции по конструированию компиляторов (Московский государственный университет)

  13. http://www.math.spbu.ru/user/mbk/TUTORY/LT.html — Б.К. Мартыненко.Языки и трансляции (С.Петербургского государственный университет)

  14. http://www.eltech.ru/misc/edu/INDEX.HTM — В.С.Фомичев. Формальные языки, грамматики и автоматы

  15. http://www.codenet.ru/progr/alg/cmp/intro.php — Основы компиляции

  16. http://www.softcraft.ru/translat/lect/content.shtml — Основы разработки трансляторов

  17. http://directory.google.com/Top/World/Russian/Компьютеры/Программи- рование / Компиляторы /

  18. http://softcraft.ru/auto.shtml — Автоматы в программировании.

[Всего голосов: 4    Средний: 5/5]

Читать  Конспект лекций Паскаль для 1 курса заочного отделения – Методические рекомендации к выполнению контрольных работ