Реферат на тему:

Програма обчислення виразів

Програма буде розроблятися із застосуванням так званого методу
послідовних уточнень – коли задача розбивається на підзадачі,
розв’язання яких перекладається на підпрограми. Програма розв’язання
задачі має досить просту структуру та містить виклики цих підпрограм.
Далі розробляються підпрограми для розв’язання підзадач, у яких
виділяються свої підзадачі. Для їх розв’язання розробляються відповідні
підпрограми тощо.

Таким чином, програма та її складові частини не записуються одразу, а
розробляються послідовним їх уточненням. У процесі розробки можливі
повернення до підпрограм, розроблених раніше, та їх уточнення.
Зауважимо, що в цьому процесі окремі частини програми можуть
розроблятися одночасно різними програмістами.

Алгоритм обчислення значення виразу в його інфіксній формі уточнимо
програмою, у тіло якої запишемо лише виклики двох підпрограм. Перша з
них уточнює алгоритм побудови ЗПЗ, друга – алгоритм обчислення значення
за ЗПЗ.

В обох алгоритмах неважко виділити операції, які виконуються над
послідовністю та магазином лексем – додавання елементів, їх вилучення
тощо. Нехай усі ці операції разом із необхідними означеннями, зокрема,
типу послідовності лексем Sqlx, зібрано в модулі Sllx. Використання
цього модуля укажемо в програмі, а його розробка залишається вправою.

Крім модуля Sllx, у програмі використовується модуль Glx. У ньому мають
міститится всі означення, необхідні для читання виразу «з зовнішнього
світу». Це читання буде здійснюватися багаторазовим викликом підпрограми
getlx читання чергової лексеми виразу. Розробку цього модуля
представлено в підр. 20.9–20.10.

Побудову ЗПЗ оформимо функцією ipllx, з якої повертається значення true,
якщо в процесі читання виразу не було якихось помилок, і false у
противному разі. Побудована послідовність запам’ятовується в змінній
Llx. Значення виразу обчислюється за виконання виклику функції llxval і
друкується. Отже, програма має вигляд:

program calcul ( input, output );

uses Glx, Sllx;

var Llx : Sqlx;

function ipllx … end;

function llxval … end;

begin

if ipllx( Llx )

then writeln( llxval( Llx ) )

end.

Розробка функцій ipllx і llxval розкривається в наступних двох
підрозділах.

Уточнення алгоритму побудови ЗПЗ

Напишемо функцію ipllx читання та побудови ЗПЗ виразу, з якої
повертається ознака відсутності помилок у виразі. Зробимо уточнення
постановки задачі: будемо вважати, що вхідні вирази не містять імен
змінних, а елементарними позначеннями операндів є лише числові сталі.

Читання чергової лексеми виразу задається функцією getlx із модуля Glx,
в якому також означено типи Tlx і Ttlx лексем та їхніх різновидів.

Вважатимемо, що модуль Sllx містить усе необхідне для роботи з
послідовністю та магазином лексем, які подаються змінними типів Sqlx і
Stlx відповідно. Ініціалізація порожніх послідовності та магазина
задається процедурами із заголовками відповідно

procedure initl( var Llx : Sqlx );

procedure inits( var Slx : Stlx );

запис лексеми в магазин – процедурою із заголовком

procedure push( var Slx : Stlx; lx : Tlx );

вилучення лексеми з магазина та повернення її типу – функцією

function pop( var Slx : Stlx; var lx : Tlx) : Ttlx;

добування лексеми з верхівки магазина без вилучення та повернення її
типу – функцією

function gett(Slx : Stlx; var lx : Tlx ) : Ttlx;

додавання лексеми в кінець списку –

procedure put( var Llx : Sqlx; lx : Tlx ).

Крім того, функція prior задає обчислення пріоритетів лексем.

Читання чергової лексеми задається в модулі Glx функцією getlx,
заголовок якої

function getlx(var lx : Tlx) : boolean;

з її виклику повертається ознака наявності чергової лексеми та сама
лексема за допомогою параметра-змінної.

Розроблювана функція ipllx матиме одну особливість. Після того, як вираз
прочитано, в магазині ще можуть залишитися знаки операцій; за алгоритмом
вони записуються у вихідну послідовність. У цій функції весь вхідний
вираз штучно «береться в дужки». Перед його читанням у магазин
записується відкриваюча дужка, що відмічає його дно. В кінці магазин
лексем обробляється так, ніби на вході з’явилася закриваюча дужка, тобто
всі знаки до відкриваючої дужки виштовхуються та копіюються у вихідну
послідовність.

function ipllx ( var Llx : Sqlx ) : boolean;

var Slx : Stlx; lx, lx1 : Tlx;

lt : Ttlx; ok : boolean;

begin

initl( Llx ); inits( Slx );

ok := true;

lx.stl := par; lx.prt := ‘(‘;

push( Slx, lx);

while (getlx( lx ) and ok) do

case lx.stl of

con : put(Llx, lx);

par : case lx.prt of

‘(‘ : push( Slx, lx);

‘)’ : while pop(Slx, lx1) <> par do

put( Llx, lx1);

end;

ops : begin

lt := gett( Slx, lx1);

while ( lt = nam ) or

( ( lt = ops ) and (prior(lx1.sig) >= prior(lx.sig) ) do

begin

lt := pop( Slx, lx1);

put( Llx, lx1);

lt := gett( Slx, lx1)

end;

push( Slx, lx)

end;

nam : push( Slx, lx)

else ok := false

end; {case та while}

if ok then

while pop( Slx, lx1) <> par do

put(Llx, lx1);

ipllx := ok

end;

Ця підпрограма має суттєвий недолік. Справа в тім, що вона не задає
структурного, або синтаксичного, аналізу вхідного ланцюжка символів.
Наприклад, недопустима вхідна послідовність лексем «1 2 3 + *» буде
прочитана та оброблена як інфіксний вираз, за ним буде створено ЗПЗ «1 2
3 * +», а далі обчислено значення 7, що не має ніякого змісту.

Поняття, необхідні для аналізу структури виразів, розглядаються в
розділі 21.

Похожие записи