Материал: Волченков Логическое программирование язык пролог 2015

test3("весеннего"). test4("индиго").

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

Анализ основы – это «сбор» всех оставшихся букв в один список методом входящей рекурсии.

Процедуру поиска в словаре fid/4 можно взять из кода 7.1. После отработки целевых утверждений

будут возвращены следующие значения переменной Res:

Res = morf(osnova(красн), okonch(pril:pad(именит): chislo(множ), ые))

Res = morf(osnova(распрекрасн), okonch(pril:pad(родит): rod(жен), ой))

Res = morf(osnova(весенн), okonch(pril:pad(родит): rod(муж), его))

Res = morf(osnova(индиго), okonch(void))

101

3.Синтаксический анализ кодов программ для упрощённой модели языка программирования операторного типа

Наш последний пример синтаксического анализатора взят из книги Л. Стерлинг, Э. Шапиро «Искусство программирования на языке Пролог» [7, гл. 23].

Речь пойдет о возможности использования Пролога для написания компиляторов традиционных языков программирования операторного типа (таких, например, как Паскаль). Сразу же может возникнуть следующий вопрос: «Какой смысл использовать для этой цели тихоходный Пролог?»

Ответить на этот вопрос можно так.

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

Во-вторых, даже в наше время «компиляторы» на Прологе могут служить прототипами будущих реальных систем. В силу наглядности, естественности и лаконичности Пролога в задачах символьного преобразования, его изначальной нацеленности на эффективный синтаксический анализ с широким использованием backtracking'а программирование всех этапов компиляции становится очень быстрым и нетрудоёмким делом. А прототип компилятора можно использовать для исследования его принципиальных возможностей, выявления изъянов и недостатков.

Компиляция программы, написанной на языке высокого уровня (здесь мы рассмотрим очень упрощённый вариант Паскаля – «учебный» язык PL) – это символьное преобразование текста этой программы в объектный код – программу на машинном языке. Компиляция обычно содержит несколько этапов: лексический и синтаксический анализ, генерацию кода, ассемблирование и, наконец, вывод объектной программы из абсолютной объектной структуры.

102

Продемонстрируем лишь один из указанных этапов – синтаксический анализ, так как именно он имеет непосредственное отношение к теме лекции.

На вход синтаксического анализатора поступает результат лексического анализа текста на языке PL – так называемый список лек-

сем (tokens).

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

program factorial; begin

read value; count := 1; result := 1;

while count < value do begin

count := count + 1; result := result * count end;

write result

end

program test1; begin

write x + y - z/2 end

program test2; begin

if a > b then max := a else max := b end

Эти списки таковы:

L1 = [program, factorial, ';', begin, read, value, ';', count, ':=', 1, ';', result, ':=', 1, ';', while, count, '<', value, do, begin, count, ':=', count, '+', 1, ';', result, ':=', result, '*', count, end, ';', write, result, end]

103

L2 = [program, test1, ';', begin, write, x, '+', y, '-', z, '/', 2, end]

L3 = [program, test2, ';', begin, if, a, '>', b, then, max, ':=', a, else, max, ':=', b, end]

Синтаксический анализатор, преобразующий списки такого рода в структуры, поступающие на вход генератора кода, представлен

следующим кодом:

Код 7.6

an_plprogram(ResStructure) --> [program], an_identifier(_), [';'], an_statement(ResStructure).

an_statement((S;Ss)) -->

[begin], an_statement(S), an_rest(Ss).

an_rest((S;Ss)) -->

[';'], an_statement(S), an_rest(Ss). an_rest(void) --> [end].

%Анализ операторов: присваивания (:=),

%условного (if then else),

%цикла с условием (while do), ввода и вывода. an_statement(assign(X, E)) -->

an_identifier(X), [':='], an_expr(E). an_statement(if(T, S1, S2)) -->

[if], an_test(T),

[then], an_statement(S1), [else], an_statement(S2). an_statement(while(T, S)) -->

[while], an_test(T), [do], an_statement(S).

an_statement(read(X)) --> [read], an_identifier(X). an_statement(write(X)) -->

[write], an_expr(X).

%Анализ "псевдоарифметических" выражений. an_expr(X) --> an_constant(X).

an_expr(expr(Op, X, Y)) -->

104

an_constant(X), an_arithmetic_op(Op), an_expr(Y).

% Анализ "констант" - идентификаторов и целых чисел an_constant(name(X)) -->

an_identifier(X). an_constant(number(X)) -->

an_integer(X).

an_identifier(X) -->

an_arithmetic_op(Op) --> [Op], {member(Op,['+','-','*','/'])}.

an_comparison_op(Op) --> [Op],

{member(Op,['=','<>','>','>=','<','<='])}.

В результате анализа трех приведенных выше списков лексем получаются следующие три структуры:

1)read(value); assign(count, number(1)); assign(result, number(1)); while(compare('<', name(count), name(value)), (assign(count, expr('+', name(count), number(1))); assign(result, expr('*', name(result), name(count))); void)); write(name(result)); void

2)write(expr('+', name(x), expr('-', name(y), expr('/', name(z), number(2))))); void

3)if(compare('>', name(a), name(b)), assign(max, name(a)), assign(max, name(b))); void

105