Реферат Програма обчислення виразів
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Реферат на тему:
Програма обчислення виразів
Програма буде розроблятися із застосуванням так званого методу послідовних уточнень – коли задача розбивається на підзадачі, розв'язання яких перекладається на підпрограми. Програма розв'язання задачі має досить просту структуру та містить виклики цих підпрограм. Далі розробляються підпрограми для розв'язання підзадач, у яких виділяються свої підзадачі. Для їх розв'язання розробляються відповідні підпрограми тощо.
Таким чином, програма та її складові частини не записуються одразу, а розробляються послідовним їх уточненням. У процесі розробки можливі повернення до підпрограм, розроблених раніше, та їх уточнення. Зауважимо, що в цьому процесі окремі частини програми можуть розроблятися одночасно різними програмістами.
Алгоритм обчислення значення виразу в його інфіксній формі уточнимо програмою, у тіло якої запишемо лише виклики двох підпрограм. Перша з них уточнює алгоритм побудови ЗПЗ, друга – алгоритм обчислення значення за ЗПЗ.
В обох алгоритмах неважко виділити операції, які виконуються над послідовністю та магазином лексем – додавання елементів, їх вилучення тощо. Нехай усі ці операції разом із необхідними означеннями, зокрема, типу послідовності лексем 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.