В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 14
Текст из файла (страница 14)
Если нет –добавляем имя в таблицу имен (добавление аналогично добавлению массива длины 1), послечего ведем себя так же, как если бы запись былаconst <адрес переменной>pushЕсли встретилась операция – дописываем: для операции +addЛекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год44для –subдля *mulдля /divдля []addpush(то есть вычислить адрес a[2] как a + 2 и извлечь значение из соотв. ячейки памяти)Легко видеть, что результатом будет код, осуществляющий вычисление выражения.Результат выражения будет последним элементом, оставшимся в стеке после окончаниявычислений.Теперь обратимся к левой части. Согласно грамматике, там стоит <lvalue>. Если это<имя> - и оно есть в таблице имен, то находим по таблице имен адрес переменной идописываем в код.
Если имени в таблице нет – добавляем имя в таблицу имен (добавлениеаналогично добавлению массива длины 1), после чего ведем себя так же, как если бы записьбылаconst <адрес переменной>popЕсли это <имя>[<выражение>] – то дописываем код для вычисления <выражения>,находим запись в таблице имен для <имени> (здесь запись должна быть обязательно,причем запись, в которой отмечено, что данное имя задает массив – вообще, более точно, втаблице имен хранятся тройки: имя переменной – тип переменной – адрес переменной, дляпростоты тип был опущен) а затем в конец – командуconst <адрес переменной>addpopВ конец программы записываем командуstopВот мы и получили полностью работоспособный компилятор. Покажем на примере, какпроходит разбор.dim a[3]b = 45 + 2a[2] = b + a[1]*3Будет разобрано: первая строчка – даст запись в таблице имен a – 0вторая строчка – выражение даст в постфиксной записи 45 2 +const 45const 2addв таблицу имен будет добавлено имя b – 3 и дописан кодconst 3popтретья строчка – выражение дает в постфиксной записи b a 1 [] 3 * + и кодconst 3pushconst 0pushconst 1pushaddpushconst 3muladdЛекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год45при разборе lvalue будет вначале вычислено 2const 2затем значение из стека будет записано в a[2]const 0addpopВ конец программы будет дописаноstopПолученная программа в целом:constconstaddconstpopconstpushconstpushconstpushaddpushconstmuladdconstconstaddpopstop4523301320Можно убедиться, что эта программа работает корректно.Псевдокод для компиляции оператора присваивания: //Серега, сам реши, кудадобавить и надо ли.Будем использовать следующие функции:oooooooooесть_входные_символыадрес(вход: строка) //возвращает адрес переменной с таким именемвыделить_очередную_лексему(выход: строка) /*возвращает тип лексемы, встроку пишет саму лексему. Типы лексем:o NAME (имя переменной);o CNST (константа);o ADD, SUB, MUL, DIV (арифметические действия);o L_RNDBR, R_RNDBR (круглые скобки);o L_SQBR, R_SQBR (квадратные скобки);o LET (присваивание).*/value(вход: строка) //возвращает значение константыдобавить_код(вход: код) //добавляет код в выходную последовательностьпроцессорных командудалить_последний_кодотложить_операцию(вход: лексема) //откладывает операцию, соответствующуюлексеме, в стек разбораобработать_лексему(вход: лексема) //самая главная процедурасвернуть_стек_разбора(вход: лексема)С учетом этих функций псевдокод будет выглядеть так:компилировать_присваивание(){Лекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год46тип_лексемы lex;строка str;обработать_лексему(L_RNDBR, NULL);while(есть_входные_символы){lex=выделить_очередную_лексему(str);обработать_лексему(lex, str);}обработать_лексему(R_RNDBR, NULL);//утверждение: стек разбора пустдобавить_код(pop);}Опишем некоторые функции:обработать_лексему(lex, str){адрес adr;switch(lex){case NAME:adr=адрес(str);добавить_код(const);добавить_код(adr);добавить_код(push);break;case CNST:добавить_код(const);добавить_код(value(str));break;case L_RNDBR:отложить_операцию(L_RNDBR);break;case R_RNDBR:свернуть_стек_разбора(R_RNDBR);//утверждение: на вершине стека разбора L_RNDBRудалить_вершину_стека_разбора;break;case ADD, SUB, MUL, DIV:свернуть_стек_разбора(lex);отложить_операцию(lex);break;case LET://утверждение: последний код есть pushудалить_последний_код;break;case L_SQBR://утверждение: последний код есть pushудалить_последний_код;отложить_операцию(L_SQBR);break;case R_SQBR:свернуть_стек_разбора(R_SQBR);//утверждение: на вершине стека разбора L_SQBRудалить_вершину_стека_разбора;добавить_код(add);добавить_код(push);break;}}свернуть_стек_разбора(lex)Лекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год47{тип_лексемы oper;while(свертка_возможна(lex)){oper=взять_на_стеке_разбора;switch(oper){case ADD:добавить_код(add);break;case SUB:добавить_код(sub);break;case MUL:добавить_код(mul);break;case DIV:добавить_код(div);break;}}}Функция свертка_возможна фактически проверяет приоритеты по следующей таблице (1 –свертка возможна, 0 – невозможна, _ – ситуация не встречается (точнее, если онавстретилась, то произошла ошибка)):lex (новая лексема)oper+ - * / ( ) [ ](вершина + 1 1 0 0 _ 1 _ 1стека)- 1 1 0 0 _ 1 _ 1* 1 1 1 1 _ 1 _ 1/ 1 1 1 1 _ 1 _ 1( 0 0 0 0 _ _ _ _) _ _ _ _ _ _ _ _[ 0 0 0 0 _ _ _ _] _ _ _ _ _ _ _ _Для полностью корректной работы компиляции присваивания остается лишь добавитьвыдачу сообщений об ошибках при невыполнении выделенных жирно утверждений.Рассмотрим теперь следующий момент – компиляцию переходов (условных ибезусловных). Без переходов получаемая программа будет строго последовательной и«неинтересной», добавление всего лишь одной команды условного перехода уже позволяетреализовывать практически любую программу (любую, поддающуюся написанию на C,например).
Действительно, такие команды как if , for, while – основаны на командахусловного перехода.Синтаксис: по ходу компилируемой программы могут встречаться метки, обозначаемыетак:<имя_метки>:безусловный переход к метке обозначается так:goto <имя_метки>а условный – так:if(<выражение>) goto <имя_метки>Условный переход совершается, если значение выражения отлично от нуля.В процессоре же существуют две соответствующие команды: jmp <адрес> и jne<адрес>. Jmp переходит по адресу без всяких условий, а jne – только если на вершине стекане 0.Лекции по ЭВМ. Конспект. Лектор В.Д.
Валединский.Группа 208, 3 семестр, 2002 год48В процессе компиляции этот самый <адрес> надо как-то найти. Для этого компиляторзаводит специальную таблицу меток с их именами и адресами. Однако с такой таблицейможно скомпилировать только переход на метку, лежащую в программе раньше самогоперехода. Поэтому в таблице заводят еще и третий столбец – ссылки на метку. Встретивпереход на еще не зарегистрированную метку, компилятор сохраняет номер строки в«ссылках», а в выходной код вставляет шаблон для перехода – строку jmp 0 (Это нужно,чтобы длина кода оставалась неизменной). Встретив саму метку, компилятор дописывает ееадрес в таблицу и заменяет им нули во всех шаблонах. Если же он ее так и не встретил, то,очевидно, произошла ошибка.Компиляция условного перехода несколько сложнее.
Для начала нужно вычислитьвыражение, т.е. вставить код для его вычисления в выходной код. После этого в выходнойкод вставляется команда jne <адрес>, а после этого нужно еще удалить вершину стека (ведьв ней лежит значение выражения, которое нам больше не нужно). Имеющимися средствамимы этого сделать не можем, поэтому нужна специальная команда, либо модификация jne.3. Базовые принципы функционирования вычислительныхсистем3.1. Общая архитектура вычислительной системыСовременная архитектура вычислительных систем основана на идеологии общей шины.Существует некоторая общая среда передачи данных – общая шина, к которой подключеныразличные устройства. Как правило, выделяют шину данных, адресную шину и шинууправления. По шине данных, как легко понять из названия, передаются собственно данные,адресная шина используется для передачи адреса данных (например, при передаче данныхот процессора в оперативную память по шине данных передается, что записать в память, апо шине адреса – куда записать).
Шина управления является «вспомогательной» – по нейпередаются служебные сигналы, определяющие, что в данный момент передается по шине,состояние шины и т.д. Эти шины могут и не быть физически разделены (хотя в современныхсистемах чаще всего так не делается – скажем так, «параллельно» передаются данные,адреса, служебная информация – каждая по своей физической шине, но в последнее времяявно наметилась тенденция к переходу к «последовательной» передаче данных, например,вначале передаются данные, затем адрес – т.н. мультиплексирование, хотя без выделенияхотя бы части шины управления пока обойтись не удается). Кроме того, еще со времен 486ых процессоров общая шина неоднородна: отдельные ее участки работают по-разному, и кним подключаются разные устройства.
Типичная схема современной x86-архитектурывыглядит следующим образом:Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год49чипсет«южный мост»клавиатураконтроллерPS/2 PS/2мышьUSBустройстваCOM и LPTустройстваUSB контроллерUSBUARTCOM/LPT контроллер(RS232 и др.)PCI платырасширенияконтроллерPCI PCIшиначипсетачипсет«северныймост»шинапамятиконтроллерпамятиоперативнаяпамятьAGP видеокартаAGPконтроллерконтроллерпроцессорнойшиныпроцессоршинапроцессораконтроллержесткогодискаUATA / SCSI / SATAжесткий дискИз-за неоднородностей общей шины (о шинах – см.
чуть далее) используютсяспециальные устройства – контроллеры, осуществляющие передачу данных между шинами.Обычно большую часть контроллеров группируют в т.н. чипсет; чипсет обычно разделен нанесколько ключевых микросхем (по традиции их обычно называют мостами, хотя, скажем,Intel во всех последних чипсетах использует термин «хаб»), одна из микросхем отвечает завысокоскоростные шины, связывающие ключевые компоненты системы (процессор, память,видеокарта – «северный мост»), другая – за периферийные («южный мост»).Общий принцип передачи данных по шине – данные передаются строго дискретно,синхронизируясь со специальным тактовым сигналом.
Происходит это примерно так: вначальный момент времени шина находится в неактивном состоянии, данные по ней непередаются. Затем на шину поступает сигнал от тактового генератора – и в этот момент пошине передается один пакет данных, по окончании сигнала шина возвращается в исходноесостояние (1 бит в последовательном интерфейсе, больше в параллельном, в шинахDDR/Rambus/EV-6 используется передача данных в момент, когда поступил тактовыйсигнал, и в момент, когда тактовый сигнал пропал). Тактовые сигналы поступают на шину сопределенной частотой и имеют прямоугольную форму. Все сказанное иллюстрируетрисунок:0 01 01 11110 00данныетактовые сигналыпример показывает процесс передачи последовательности бит 101111001000.Лекции по ЭВМ. Конспект. Лектор В.Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
