Метод Рутисхаузера Первыми транслирующими программа - страница 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://reiy.deutsch-service.ru/8984427712229265.html
http://tvp.deutsch-service.ru/documentapelryf.html
http://regw.deutsch-service.ru/3860569465275834.html
http://reiw.deutsch-service.ru/8983543571586712.html
http://regu.deutsch-service.ru/4065324371764496.html
http://rehc.deutsch-service.ru/4916600025876224.html
http://refs.deutsch-service.ru/1165143114402827.html
http://ruj.deutsch-service.ru/documentadofamr.html
http://reib.deutsch-service.ru/7238845404368524.html
http://tax.deutsch-service.ru/documentakramur.html
http://tkr.deutsch-service.ru/documentamvazdp.html
http://refw.deutsch-service.ru/1654829536565185.html
http://regr.deutsch-service.ru/3194713667560770.html
http://refz.deutsch-service.ru/1829332592963227.html
http://reil.deutsch-service.ru/7887208464999748.html
http://umf.deutsch-service.ru/documentasvzphp.html
http://vxp.deutsch-service.ru/documentbbaeauz.html
http://sdj.deutsch-service.ru/documentafnhfav.html
http://refp.deutsch-service.ru/1288057172398605.html
http://rehu.deutsch-service.ru/5926236392264851.html
http://rehx.deutsch-service.ru/6732868742843176.html
http://regy.deutsch-service.ru/4390182619845352.html
http://ufq.deutsch-service.ru/documentarkzdqf.html
http://rehp.deutsch-service.ru/5519919593197593.html
http://rehs.deutsch-service.ru/6262909747437995.html
http://sor.deutsch-service.ru/documentahzjbef.html
http://refs.deutsch-service.ru/1296565619756729.html
http://regy.deutsch-service.ru/4298585152556619.html
http://regb.deutsch-service.ru/2041684604606272.html
http://wko.deutsch-service.ru/documentbdvyrkz.html
http://reji.deutsch-service.ru/9875942591597860.html
http://whn.deutsch-service.ru/documentbdeokof.html
http://refx.deutsch-service.ru/1792973786460126.html
http://swv.deutsch-service.ru/documentajufwnh.html
http://sfm.deutsch-service.ru/documentafytinh.html
http://ukg.deutsch-service.ru/documentaskihfd.html
http://refq.deutsch-service.ru/1196371796046956.html
http://regm.deutsch-service.ru/2869307625651891.html
http://reiq.deutsch-service.ru/8488712405827338.html
http://tdf.deutsch-service.ru/documentalevfsr.html
http://wal.deutsch-service.ru/documentbbqclyv.html
http://rehf.deutsch-service.ru/4733124319514207.html
http://reiy.deutsch-service.ru/8662576534347196.html
http://reih.deutsch-service.ru/7369634474542133.html
http://reii.deutsch-service.ru/7540474349779862.html
http://reft.deutsch-service.ru/1479131385123520.html
http://reht.deutsch-service.ru/6252180525818134.html
http://regh.deutsch-service.ru/2425023900982994.html
http://reir.deutsch-service.ru/8494615386523617.html
http://utx.deutsch-service.ru/documentaumwepd.html
http://win.deutsch-service.ru/documentbdjtaof.html
http://regv.deutsch-service.ru/3992741372047510.html
http://ter.deutsch-service.ru/documentalmblfl.html
http://regg.deutsch-service.ru/2363486507640756.html
http://refv.deutsch-service.ru/1475226801100372.html
http://rfk.deutsch-service.ru/documentaahkyhd.html
http://reit.deutsch-service.ru/8315977944097989.html
http://regi.deutsch-service.ru/2978686509060107.html
http://rehr.deutsch-service.ru/6302593535207237.html
http://ufh.deutsch-service.ru/documentarhxvmv.html
http://regb.deutsch-service.ru/1861455347111342.html
http://swq.deutsch-service.ru/documentajsvltx.html
http://rehp.deutsch-service.ru/5509509785101018.html
http://rejj.deutsch-service.ru/9775169001955395.html
http://refw.deutsch-service.ru/1584917643899326.html
http://reff.deutsch-service.ru/0003289696310396.html
http://rehc.deutsch-service.ru/4830410421018240.html
http://rhe.deutsch-service.ru/documentaarbxkz.html
http://utz.deutsch-service.ru/documentaunknjl.html
http://sbs.deutsch-service.ru/documentafdyjkz.html
http://vek.deutsch-service.ru/documentawuvaej.html
http://vkc.deutsch-service.ru/documentayawkuz.html
http://reji.deutsch-service.ru/9763602029704083.html
http://reho.deutsch-service.ru/5632116528729782.html
http://scy.deutsch-service.ru/documentafkdfjt.html
http://rehj.deutsch-service.ru/5405720716761258.html
http://reho.deutsch-service.ru/5483393559486622.html
http://refy.deutsch-service.ru/1996513712404793.html
http://rkr.deutsch-service.ru/documentabkjmvx.html
http://txv.deutsch-service.ru/documentaprkrtx.html
http://deutsch-service.ru/0353713566237191.html
http://sas.deutsch-service.ru/documentaeyyajp.html
http://vos.deutsch-service.ru/documentazbmvtx.html
http://whz.deutsch-service.ru/documentbdhdrbt.html
http://refp.deutsch-service.ru/1131259577449876.html
http://regl.deutsch-service.ru/2759699513017355.html
http://regm.deutsch-service.ru/2890955494905638.html
http://wfp.deutsch-service.ru/documentbctxxfd.html
http://ups.deutsch-service.ru/documentatppspt.html
http://refj.deutsch-service.ru/0871051582938372.html
http://vop.deutsch-service.ru/documentazaaguz.html
http://usv.deutsch-service.ru/documentaugxvgz.html
http://ttf.deutsch-service.ru/documentaorbjsr.html
http://regr.deutsch-service.ru/3280836801935851.html
http://rehb.deutsch-service.ru/4311000025712974.html
http://rejc.deutsch-service.ru/9360206835211001.html
http://reft.deutsch-service.ru/1553956667965540.html
http://regf.deutsch-service.ru/2279925189157763.html
http://rehm.deutsch-service.ru/5658688209132371.html
http://rehi.deutsch-service.ru/5224834002332760.html
http://wew.deutsch-service.ru/documentbcpklyn.html
http://uhb.deutsch-service.ru/documentarrzpsj.html
http://sqq.deutsch-service.ru/documentaikrgov.html
http://rehw.deutsch-service.ru/6572566740264164.html
http://refg.deutsch-service.ru/0228899013589287.html
http://reim.deutsch-service.ru/7847087914673381.html
http://wbx.deutsch-service.ru/documentbbzjwpd.html
http://riw.deutsch-service.ru/documentabazair.html
http://ugq.deutsch-service.ru/documentarqaiwn.html
http://reid.deutsch-service.ru/7113331901254996.html
http://reip.deutsch-service.ru/7881202879943237.html
http://uwp.deutsch-service.ru/documentavcmksn.html
http://reji.deutsch-service.ru/9716402214696845.html
http://rehc.deutsch-service.ru/4699408821034782.html
http://wgb.deutsch-service.ru/documentbcvrnph.html
http://wld.deutsch-service.ru/documentbdzxyir.html
http://reha.deutsch-service.ru/4327876919470686.html
http://rehg.deutsch-service.ru/4725604515002035.html
http://rehu.deutsch-service.ru/6249112584941934.html
http://szt.deutsch-service.ru/documentakkoyhl.html
http://wbq.deutsch-service.ru/documentbbwpmyb.html
http://rehy.deutsch-service.ru/6669457932137660.html
http://regi.deutsch-service.ru/2969690591293012.html
http://reia.deutsch-service.ru/6486814708813155.html
http://refi.deutsch-service.ru/0150456858426020.html
http://reih.deutsch-service.ru/7401595230172973.html
http://refo.deutsch-service.ru/1190115342768306.html
http://reft.deutsch-service.ru/1783990923462682.html
http://uzq.deutsch-service.ru/documentavurlnt.html
http://vks.deutsch-service.ru/documentayedvft.html
http://ugz.deutsch-service.ru/documentarrqkbp.html
http://rehc.deutsch-service.ru/4714375315461914.html
http://reft.deutsch-service.ru/1729715375453613.html
http://reff.deutsch-service.ru/0297604290693551.html
http://tmz.deutsch-service.ru/documentaniqhnt.html
http://refg.deutsch-service.ru/0123283162245070.html
http://regn.deutsch-service.ru/3243608247176872.html
http://reir.deutsch-service.ru/8150097823527764.html
http://uyi.deutsch-service.ru/documentavnajmv.html
http://vkr.deutsch-service.ru/documentayevcyb.html
http://uni.deutsch-service.ru/documentatbreov.html
http://rehe.deutsch-service.ru/4565816204091658.html
http://rxh.deutsch-service.ru/documentaeemcmr.html
http://ryo.deutsch-service.ru/documentaelbuzp.html
http://reib.deutsch-service.ru/7150416910824424.html
http://saq.deutsch-service.ru/documentaexckfh.html
http://refl.deutsch-service.ru/0610664093442664.html
http://rege.deutsch-service.ru/2308106665595064.html
http://regy.deutsch-service.ru/4250607509505371.html
http://uoy.deutsch-service.ru/documentatkrzpp.html
http://refr.deutsch-service.ru/1013249713722629.html
http://vrh.deutsch-service.ru/documentazpigll.html
http://tev.deutsch-service.ru/documentalnuazh.html
http://uyj.deutsch-service.ru/documentavmavhp.html
http://twv.deutsch-service.ru/documentapmejkb.html
http://rejb.deutsch-service.ru/9107163067262726.html
http://slj.deutsch-service.ru/documentahgkvvl.html
http://uhg.deutsch-service.ru/documentartcitl.html
http://reiy.deutsch-service.ru/8936472562955601.html
http://wdb.deutsch-service.ru/documentbcgavqf.html
http://tee.deutsch-service.ru/documentaljvnhp.html
http://refk.deutsch-service.ru/0569789924689390.html
http://rejh.deutsch-service.ru/9842969146679648.html
http://reik.deutsch-service.ru/7603681581403828.html
http://vgy.deutsch-service.ru/documentaxjjsij.html
http://smm.deutsch-service.ru/documentahnsven.html
http://reho.deutsch-service.ru/5856397073629637.html
http://rehq.deutsch-service.ru/5674382257626441.html
http://regt.deutsch-service.ru/4023820991116050.html
http://rego.deutsch-service.ru/3467210727072573.html
http://toz.deutsch-service.ru/documentantbusf.html
http://reii.deutsch-service.ru/7524735307038829.html
http://rehj.deutsch-service.ru/5242900202633162.html
http://refi.deutsch-service.ru/0098811477054564.html
http://ubz.deutsch-service.ru/documentaqptgnh.html
http://vqp.deutsch-service.ru/documentazmrgbp.html
http://ufi.deutsch-service.ru/documentarialob.html
http://rgr.deutsch-service.ru/documentaanoksv.html
http://umy.deutsch-service.ru/documentaszovwb.html
http://ttq.deutsch-service.ru/documentaotvzhp.html
http://suo.deutsch-service.ru/documentajhqfhh.html
http://wch.deutsch-service.ru/documentbcbljcz.html
http://rehl.deutsch-service.ru/5415792500691321.html
http://regx.deutsch-service.ru/4385462904488094.html
http://refq.deutsch-service.ru/0925100962285265.html
http://regh.deutsch-service.ru/2491246341020972.html
http://ulc.deutsch-service.ru/documentaspkyxl.html
http://regk.deutsch-service.ru/2804349359417650.html
http://rego.deutsch-service.ru/3243171157852573.html
http://udc.deutsch-service.ru/documentaqvfdwj.html
http://sfy.deutsch-service.ru/documentagbtkcn.html
http://rehk.deutsch-service.ru/5121163752855414.html
http://vgw.deutsch-service.ru/documentaxircpl.html
http://vbd.deutsch-service.ru/documentawbjubx.html
http://rjs.deutsch-service.ru/documentabeusbh.html
http://tkf.deutsch-service.ru/documentamskagf.html
http://regh.deutsch-service.ru/2378538346785506.html
http://regc.deutsch-service.ru/2208914219009707.html
http://rnn.deutsch-service.ru/documentacaxaab.html
http://refo.deutsch-service.ru/1116189316357341.html