Метод Рутисхаузера Первыми транслирующими программа - страница 5

^ 2.6Польская запись. Алгоритм Бауэра-Замельзона
Результат синтаксического анализа – дерево грамматического разбора – представляют в виде таблицы или обратной польской записи.

Польская запись (в честь польского математика Лукасевича, предложившего этот вид записи выражений) представляет собой последовательность команд двух типов:

  1. КI, где I – идентификатор операнда – выбрать число по имени I и заслать его в стек операндов;

  2. K, где  – операция – выбрать два верхних числа из стека операндов, произвести над ними операцию  и занести результат в стек операндов.

Рассмотрим алгоритм Бауэра-Замельзона, по которому осуществляется представление выражений в виде польской записи.

^ Алгоритм Бауэра-Замельзона. Грамматика, описывающая правила записи арифметических выражений, относится к классу грамматик операторного предшествования, т. е. порядок следования терминальных символов (знаков операций), однозначно определяет порядок выделения троек, причем нетерминальные символы (имена операндов) на этот порядок не влияют.

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

Согласно алгоритму Бауэра-Замельзона разбор выражения и формирование польской записи выполняется в два этапа:

  1. разбор выражения и построение эквивалентной польской записи;

  2. выполнение (или трансляция) польской записи.

При этом используется два стека: стек операций – на первом этапе и стек операндов – на втором этапе.

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

а) если символ – операнд, то вырабатывается команда КI,

б) если символ – операция, то выполняются действия согласно таблице 11:


Таблица 11 – Таблица генератора

\

+

*

(

)





I

I

I

?

Вых

+

II

I

I

IV

IV

*

IV

II

I

IV

IV

(

I

I

I

III

?






Обозначения:

? - ошибка;

 - верхний символ в стеке операций;

 - текущий символ.


Операции:

I – заслать  в стек операций и читать следующий символ;

II – генерировать K , заслать  в стек операций и читать следующий символ;

III – удалить верхний символ из стека операций и читать следующий символ;

IV – генерировать K и повторить с тем же входным символом.

На этапе выполнения польская запись читается слева направо и выполняется.

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

Пример. Построить тройки для выражения (a+b*c)/d.

  1. Построение польской записи:

^ Стек операций

Символ

Действие

Команда



(

I




► (

a




Ka

► (

+

I




► ( +

b




Kb

► ( +

*

I




► ( + *

c




Kc

► ( + *

)

IV

K*

► ( +

)

IV

K+

► (

)

III






/

I




► /

d




Kd

► /



IV

K/





Конец




В результате получаем:

Ka Kb Kc K* K+ Kd K/ или abc*+d/

  1. Выполнение операций:

^ Стек операндов

Команда

Тройка



Ka




a

Kb




a b

Kc




a b c

K*

T1= b*c

a T1

K+

T2= a+T1

T2

Kd




T2 d

K/

T3= T2/d

T3









^ 3Распределение памяти
После распознавания конструкций и определения таблиц переменных, именованных констант и временных переменных осуществляют распределение памяти под эти данные и программы. При этом могут использоваться разные типы распределения памяти.

Различают:

  1. статическое;

  2. автоматическое;

  3. управляемое;

  4. базированное.

Статическое распределение памяти выполняется:

а) во время компиляции – для подпрограмм и для инициализированных переменных;

б) во время компоновки – для неинициализированных переменных.

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

Управляемое распределение памяти выполняется во время выполнения программы специальными подпрограммами, например, new и delete.

Базированное распределение памяти выполняется во время выполнения программы из выделенного буфера. Доступ к такой памяти осуществляется через вычисляемые адреса.

Кроме этого, различают:

  1. локальную память;

  2. глобальную память.

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

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

Mov AX,

Add AX,

Mov AX,

В такой последовательности команд выполняется подстановка адресов операндов и результата.

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

Все способы оптимизации можно разделить на две группы:

  1. машинно-независимая оптимизация;

  2. машинно-зависимая оптимизация.

Машинно-независимая оптимизация включает:

а) исключение повторных вычислений одних и тех же операндов;

б) выполнение операций над константами во время трансляции;

в) вынесение из циклов вычисления величин, не зависящих от параметров циклов;

г) упрощение сложных логических выражений и т. п.

Машинно-зависимая оптимизация включает:

а) исключение лишних передач управления типа «память-регистр»;

б) выбор более эффективных команд т. п.

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

Литература

  1. Д. Грис. Конструирование компиляторов для цифровых вычислительных машин – М.: Мир, 1975. – 544 с.

  2. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты. Пер. с англ. – М.: «Вильямс», 2003.

  3. В. Дж. Рейуорд–Смит. Теория формальных языков. Вводный курс. – М.: Радио и связь, 1988. – 128 с.


0102880102617487.html
0103021962515847.html
0103095334428561.html
0103214468337785.html
0103340892372262.html
http://utp.deutsch-service.ru/documentauksnvt.html
http://udo.deutsch-service.ru/documentaqyvsll.html
http://regb.deutsch-service.ru/2256980563561564.html
http://regm.deutsch-service.ru/2773843228253817.html
http://say.deutsch-service.ru/documentaezgpth.html
http://rehc.deutsch-service.ru/4621777836680382.html
http://regm.deutsch-service.ru/3032384671399105.html
http://refx.deutsch-service.ru/1709797950735905.html
http://refh.deutsch-service.ru/0070481207909153.html
http://regs.deutsch-service.ru/3855906429106613.html
http://wao.deutsch-service.ru/documentbbrxouz.html
http://rejj.deutsch-service.ru/9582885836090761.html
http://reil.deutsch-service.ru/7996728391180485.html
http://tfo.deutsch-service.ru/documentalrfwub.html
http://rvq.deutsch-service.ru/documentadvjuzx.html
http://refr.deutsch-service.ru/1259656158445655.html
http://uhn.deutsch-service.ru/documentaruftob.html
http://wbw.deutsch-service.ru/documentbbxnlsj.html
http://rejf.deutsch-service.ru/9749249894559305.html
http://twq.deutsch-service.ru/documentaplfxhp.html
http://reih.deutsch-service.ru/7614877092999761.html
http://sgu.deutsch-service.ru/documentaggokcn.html
http://thg.deutsch-service.ru/documentambubmf.html
http://tow.deutsch-service.ru/documentansfliv.html
http://sjr.deutsch-service.ru/documentagwtdlp.html
http://rgi.deutsch-service.ru/documentaammaon.html
http://regc.deutsch-service.ru/1814239127659063.html
http://waz.deutsch-service.ru/documentbbtmwub.html
http://uei.deutsch-service.ru/documentardeyfx.html
http://rejf.deutsch-service.ru/9678924538519381.html
http://refv.deutsch-service.ru/1630386819399095.html
http://regd.deutsch-service.ru/2362031229639400.html
http://reie.deutsch-service.ru/7039913393929058.html
http://vlc.deutsch-service.ru/documentayglomj.html
http://usl.deutsch-service.ru/documentauesqpd.html
http://regn.deutsch-service.ru/3236046804369117.html
http://rur.deutsch-service.ru/documentadpnimz.html
http://udi.deutsch-service.ru/documentaqwxpev.html
http://urb.deutsch-service.ru/documentatwxeqr.html
http://regx.deutsch-service.ru/4181383203686860.html
http://twd.deutsch-service.ru/documentapidult.html
http://uil.deutsch-service.ru/documentarzonnt.html
http://umz.deutsch-service.ru/documentaszzskf.html
http://rpa.deutsch-service.ru/documentacjxxzt.html
http://reix.deutsch-service.ru/9013110618834856.html
http://refy.deutsch-service.ru/2121344914261265.html
http://vcd.deutsch-service.ru/documentawixoib.html
http://rejf.deutsch-service.ru/9510865953929510.html
http://rgf.deutsch-service.ru/documentaalewdl.html
http://refx.deutsch-service.ru/1447960827392054.html
http://rehn.deutsch-service.ru/5657085533355433.html
http://ukn.deutsch-service.ru/documentaslonyv.html
http://twt.deutsch-service.ru/documentaplebyv.html
http://rejc.deutsch-service.ru/9180179284474211.html
http://reid.deutsch-service.ru/6921718780591450.html
http://thm.deutsch-service.ru/documentamcjttp.html
http://refl.deutsch-service.ru/0740746727638160.html
http://ubt.deutsch-service.ru/documentaqnyvkr.html
http://reib.deutsch-service.ru/6837066693540574.html
http://wml.deutsch-service.ru
http://rvj.deutsch-service.ru/documentadumcdl.html
http://regl.deutsch-service.ru/2889958053618319.html
http://tic.deutsch-service.ru/documentamgcoar.html
http://regi.deutsch-service.ru/2774276684235853.html
http://regc.deutsch-service.ru/1877089706476940.html
http://whg.deutsch-service.ru/documentbdczxhp.html
http://reif.deutsch-service.ru/6804594622306761.html
http://vqq.deutsch-service.ru/documentazmyklt.html
http://rgn.deutsch-service.ru/documentaaodgvh.html
http://run.deutsch-service.ru/documentadocrvt.html
http://rehz.deutsch-service.ru/6521573310160603.html
http://regy.deutsch-service.ru/4479650771610656.html
http://deutsch-service.ru/0138430384244860.html
http://slg.deutsch-service.ru/documentahgazxp.html
http://unj.deutsch-service.ru/documentatctcxl.html
http://regv.deutsch-service.ru/3947221526351822.html
http://vfj.deutsch-service.ru/documentaxakjtp.html
http://regt.deutsch-service.ru/4048050833292959.html
http://vbd.deutsch-service.ru/documentawbmbgj.html
http://refx.deutsch-service.ru/1535547108116238.html
http://tri.deutsch-service.ru/documentaoghumr.html
http://reht.deutsch-service.ru/6194313623005231.html
http://rejc.deutsch-service.ru/9201750055580581.html
http://reip.deutsch-service.ru/8045053807424419.html
http://regj.deutsch-service.ru/3033948932620288.html
http://shk.deutsch-service.ru/documentagjngqb.html
http://refj.deutsch-service.ru/0710630974880532.html
http://rzo.deutsch-service.ru/documentaermouj.html
http://vty.deutsch-service.ru/documentbaeuedt.html
http://rehm.deutsch-service.ru/5784326521272467.html
http://reis.deutsch-service.ru/8472821621950220.html
http://tjg.deutsch-service.ru/documentammtumb.html
http://vaw.deutsch-service.ru/documentawaqatt.html
http://vua.deutsch-service.ru/documentbagsiwv.html
http://vyb.deutsch-service.ru/documentbbcthin.html
http://tji.deutsch-service.ru/documentamntncr.html
http://reih.deutsch-service.ru/7554361985684137.html
http://rejm.deutsch-service.ru/9974426635326071.html
http://reid.deutsch-service.ru/7028571980737488.html
http://srj.deutsch-service.ru/documentaiopxfl.html
http://regn.deutsch-service.ru/3272876822431285.html
http://ucb.deutsch-service.ru/documentaqpjrzt.html
http://tfc.deutsch-service.ru/documentalpvxwj.html
http://regq.deutsch-service.ru/3358096740681681.html
http://refu.deutsch-service.ru/1616044520728515.html
http://refy.deutsch-service.ru/1964361626640773.html
http://refg.deutsch-service.ru/0153655736148870.html
http://rehd.deutsch-service.ru/4626364364229279.html
http://syc.deutsch-service.ru/documentakbfgmr.html
http://vjr.deutsch-service.ru/documentaxzfdbt.html
http://reiu.deutsch-service.ru/8493213789490228.html
http://rehi.deutsch-service.ru/5045782681070450.html
http://vzl.deutsch-service.ru
http://regz.deutsch-service.ru/4508985584304809.html
http://refm.deutsch-service.ru/0558893268338255.html
http://sfz.deutsch-service.ru/documentagcouib.html
http://reho.deutsch-service.ru/5745094654949155.html
http://regy.deutsch-service.ru/4414551254664683.html
http://reji.deutsch-service.ru/9545486817832108.html
http://refz.deutsch-service.ru/1937899313124883.html
http://refx.deutsch-service.ru/1647163409550382.html
http://regp.deutsch-service.ru/3566356915442574.html
http://regd.deutsch-service.ru/2463162716812579.html
http://vlq.deutsch-service.ru/documentaykfyej.html
http://rehs.deutsch-service.ru/6098632666652004.html
http://rehd.deutsch-service.ru/4659952307748996.html
http://regy.deutsch-service.ru/4339438191084896.html
http://regm.deutsch-service.ru/2867796938291074.html
http://sbu.deutsch-service.ru/documentafdncnp.html
http://vcz.deutsch-service.ru/documentawnexhh.html
http://refp.deutsch-service.ru/1122147184674478.html
http://slg.deutsch-service.ru/documentahfyliv.html
http://tqf.deutsch-service.ru/documentanzntor.html
http://rejb.deutsch-service.ru/9465578774999364.html
http://reji.deutsch-service.ru/9604301233550396.html
http://rege.deutsch-service.ru/2424791999887971.html
http://reip.deutsch-service.ru/7999248135318023.html
http://tpu.deutsch-service.ru/documentanyasub.html
http://tuo.deutsch-service.ru/documentaoyxqjp.html
http://rehx.deutsch-service.ru/6473797229103968.html
http://regw.deutsch-service.ru/3619888278588294.html
http://ttc.deutsch-service.ru/documentaopwtwj.html
http://reff.deutsch-service.ru/0384252366971957.html
http://tqk.deutsch-service.ru/documentaoanqqr.html
http://udy.deutsch-service.ru/documentaragkpd.html
http://ubd.deutsch-service.ru/documentaqjsyxl.html
http://wid.deutsch-service.ru/documentbdiiikn.html
http://swh.deutsch-service.ru/documentajrcopt.html
http://sry.deutsch-service.ru/documentaisayht.html
http://rehb.deutsch-service.ru/4083924299857613.html
http://regn.deutsch-service.ru/3245318579861171.html
http://reis.deutsch-service.ru/8386885676011040.html
http://reif.deutsch-service.ru/7094182128787952.html
http://trb.deutsch-service.ru/documentaofbgir.html
http://wbu.deutsch-service.ru/documentbbybhen.html
http://rqh.deutsch-service.ru/documentacqsevp.html
http://rejh.deutsch-service.ru/9855091518762657.html
http://swc.deutsch-service.ru/documentajpssqz.html
http://rtp.deutsch-service.ru/documentadjqror.html
http://rng.deutsch-service.ru/documentacabgxt.html
http://refs.deutsch-service.ru/1166537589931025.html
http://uli.deutsch-service.ru/documentaspvgqz.html
http://reii.deutsch-service.ru/7582801289088890.html
http://sfh.deutsch-service.ru/documentafxoaxl.html
http://rehf.deutsch-service.ru/4722220240410462.html
http://regw.deutsch-service.ru/3685183575303936.html
http://rehi.deutsch-service.ru/5270473805339498.html
http://reij.deutsch-service.ru/7383363676235528.html
http://rejg.deutsch-service.ru/9920953635412163.html
http://rehb.deutsch-service.ru/4241261129927953.html
http://uzk.deutsch-service.ru/documentavrqwqj.html
http://refv.deutsch-service.ru/1702806639465672.html
http://slk.deutsch-service.ru/documentahgvztx.html
http://uoe.deutsch-service.ru/documentatgysaj.html
http://regu.deutsch-service.ru/3880142204547980.html
http://regd.deutsch-service.ru/2518436416127206.html
http://reih.deutsch-service.ru/7511319931199399.html
http://uqe.deutsch-service.ru/documentatsbgzh.html
http://refk.deutsch-service.ru/0467386570260776.html
http://refy.deutsch-service.ru/2248724581852940.html
http://regm.deutsch-service.ru/2789355701085257.html
http://rega.deutsch-service.ru/1969998560150728.html
http://vju.deutsch-service.ru/documentaxzbpjd.html
http://suu.deutsch-service.ru/documentajimehl.html
http://sdw.deutsch-service.ru/documentafpzxun.html
http://tfe.deutsch-service.ru/documentalprtwr.html
http://refs.deutsch-service.ru/1234111830832009.html
http://rejg.deutsch-service.ru/9564433273561676.html
http://rein.deutsch-service.ru/8116936706506780.html
http://tsu.deutsch-service.ru/documentaopoxsr.html
http://regk.deutsch-service.ru/3062880615049226.html
http://rqa.deutsch-service.ru/documentacoworh.html
http://refz.deutsch-service.ru/2129665053562814.html
http://wis.deutsch-service.ru/documentbdlhsgf.html
http://rehq.deutsch-service.ru/5646261545174759.html
http://tnc.deutsch-service.ru/documentanigfsb.html
http://rehk.deutsch-service.ru/5378620266557460.html
http://reha.deutsch-service.ru/4372389273605463.html
http://reji.deutsch-service.ru/9928090294743686.html
http://uaw.deutsch-service.ru/documentaqjbmtt.html