Теория компиляторов-1. Л.71 Классическая теория компиляторов Лекция 7. - презентация

1 Теория компиляторов-1. Л.71 Классическая теория компиляторов Лекция 7

2 Теория компиляторов-1. Л.72 ИНТЕРПРЕТАТОРЫ Интерпретатор – это программа, которая транслирует исходную программу на языке высокого уровня во внутреннее представление; выполняет (интерпретирует) программу, представленную на этом внутреннем языке. Интерпретаторы хороши для обучения (когда большая часть времени уходит на отладку) и для тех языков, в которых много времени уходит на работу системных п/программ (работа с матрицами, базами данных и т.п.). Достоинства интерпретаторов простота (не надо реализовывать генерацию объектного кода); удобство и простота отладки программ – все внутренние структуры нам доступны (прежде всего – это доступ к таблице символов в любой момент времени), легки трассировка, отслеживание обращений к меткам и переменным и т.п.; возможность включения интерпретируемых выражений в процессе выполнения программы (самомодификация программы). => Интерпретаторы наиболее часто применяются при разработке новых и сложных языков. Недостатки интерпретаторов Малая, "по определению", скорость выполнения программы Для устранения этого недостатка приходится платить упрощением синтаксиса языка, т.е. его грамматики.

3 Теория компиляторов-1. Л.73 Аргументы Наиболее эффективной формой внутреннего представления программы для интерпретатора является ПФ записи. Основной частью интерпретатора является переключатель CASE: while TRUE do begin case gettype(P[n]) of operand: Push(S,P[n]); operator: arg1 := Pop(); arg2 := Pop(); arg2); else: error(); endcase n := n+1 end Проблема представления в стеке аргументов различных типов данных. 4 типа аргументов: константы, имена, адреса переменных, указатели.

4 Теория компиляторов-1. Л.74 Хранение операндов 1. Различать типы данных, используя аналогию с байт-кодом. Либо хранить аргумент, предваряя его элементом, указывающим тип. 2.Тип элемента можно держать в таблице имен, и тогда в польской форме мы будем хранить лишь адреса. Необходим механизм проверки типов и соответствующих функций конвертирования: cvPV (pointer to value) – конвертация указателя в значение; cvPA (pointer to address) – конвертация указателя в адрес; cvAV (address to value) – конвертация адреса в значение. Для увеличения эффективности выполнения программы можно заранее вставлять в ПФ процедуры конверсии типов.

5 Теория компиляторов-1. Л.75 Виды интерпретаторов 1. Интерпретатор, как самостоятельная программа, что зачастую создает некоторые проблемы, связанные с мобильностью программного обеспечения (один исполняемый файл удобнее пары – исходный текст программы плюс интерпретатор). 2. "Скрытые" или "неявные" интерпретаторы. Формируется исполняемый файл, содержащий в себе как непосредственно интерпретатор, так и исходный текст программы. Внешне мы имеем исполняемый модуль, который, занимается интерпретацией. 3. Виртуальные машины

6 Теория компиляторов-1. Л.76 КОМПИЛЯТОРЫ КОМПИЛЯТОРОВ КК – система, позволяющая создавать компиляторы. КК – это некий инструментарий программиста, помогающий создавать компиляторы. Автоматизация рутинных процедур. Имея регулярную грамматику лексической структуры можно, автоматически сгенерировать сканер в виде КА. Имея грамматику синтаксической структуры, можно написать универсальную процедуру синтаксически управляемого перевода (или создать универсальный МП-автомат). Для этого потребуется некоторое описание двух грамматик – грамматики для сканера и грамматики для синтаксического анализатора. Это описание можно хранить в некотором файле. Тогда получим специальный входной язык – язык описания компилятора.

7 Теория компиляторов-1. Л.77 Пример автомата ; Конфигурация распознающего автомата ; Входной алфавит sD = " " sL = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЬЪЮЯабвгдеёжзийклмнопрстуфхцчшщыэьъюя/_"; sN = "Н" sC = "Ч" sMinus = "-" sLsk = "(" sRsk = ")" sZpt = "," sEol = "#" sSpace = " " sPoint = "." # ; Состояния s, q1, n1, n2, n3, n4 terminate, error # ; Начальное состояние S # ; Терминальные состояния terminate, error # ; Переходы S sN -> q1clr, dreset, acc S sC -> q2clr, dreset, acc S sD -> n3clr, dreset, acc S sL -> n3clr, dreset, acc S sEol -> terminate S sZpt -> S S sSpace -> S q1 sLsk -> n1 clr, set_nch q1 sZpt -> SADD q1 sEol -> S ADD, ungetch q1 sZpt -> S ADD, ungetch q1 sD -> n3 acc q1 sL -> n3 acc q2 sLsk -> n1 clr, set_ch q2 sZpt -> SADD q2 sEol -> S ADD, ungetch q2 sZpt -> S ADD, ungetch q2 sD -> n3 acc q2 sL -> n3 acc n1 sD -> n1acc n1 sL -> n1acc n1 sMinus -> n2set_n1, clr n2 sD -> n2acc n2 sL -> n2acc n2 sRsk -> Sset_n2, ADD n3 sD -> n3acc n3 sL -> n3acc n3 sZpt -> Sset_n1, set_n2, ADD n3 sEol -> Sset_n1, set_n2, ADD, ungetch n3 sMinus -> n4 set_n1 ; Опасное место: игнорирование точки n3 sPoint -> n3 n4 sD -> n4acc n4 sL -> n4acc n4 sZpt -> Sset_n2, ADD, ungetch n4 sEol -> Sset_n2, ADD, ungetch # q1clr, dreset, acc S sC -> q2clr, dreset, acc S sD -> n3clr, dreset, acc S sL -> n3clr, dreset, acc S sEol -> terminate S sZpt -> S S sSpace -> S q1 sLsk -> n1 clr, set_nch q1 sZpt -> SADD q1 sEol -> S ADD, ungetch q1 sZpt -> S ADD, ungetch q1 sD -> n3 acc q1 sL -> n3 acc q2 sLsk -> n1 clr, set_ch q2 sZpt -> SADD q2 sEol -> S ADD, ungetch q2 sZpt -> S ADD, ungetch q2 sD -> n3 acc q2 sL -> n3 acc n1 sD -> n1acc n1 sL -> n1acc n1 sMinus -> n2set_n1, clr n2 sD -> n2acc n2 sL -> n2acc n2 sRsk -> Sset_n2, ADD n3 sD -> n3acc n3 sL -> n3acc n3 sZpt -> Sset_n1, set_n2, ADD n3 sEol -> Sset_n1, set_n2, ADD, ungetch n3 sMinus -> n4 set_n1 ; Опасное место: игнорирование точки n3 sPoint -> n3 n4 sD -> n4acc n4 sL -> n4acc n4 sZpt -> Sset_n2, ADD, ungetch n4 sEol -> Sset_n2, ADD, ungetch #">

8 Теория компиляторов-1. Л.78 Грамматика XQL ; ГРАММАТИКА XQL ::=, ;if C then P1 else P2 endif ;P1: ::= ?'ELSE' :push.L2.push.1.push.BR.do.L1 ;P2: ::= ?'ENDIF' :do.L2 ::= ?','..'ELSE'..'ENDIF'... ; ::= STOP :push.0.push.EXIT ::= EXIT :push.0.push.EXIT ::= QUIT :push.0.push.EXIT ::= BR BRZ SICAFIL ELIST EXECUTE STARTSELECT STARTFROM STARTWHERE ; ::= FOR FROM TO DO ENDFOR ::= IF THEN ELSE ENDIF ::= ?'THEN' :push.L1.push.2.push.BRZ ; ::= WRITE :push.1.push.WRITE ::= WRITELN :push.1.push.WRITELN ::= READ :push.1.push.READ ::= SYSTEM :push.1.push.SYSTEM ::= = :push.2.push.= ::=, ::= ?',' :push.0.push.ELIST.push.0.push.SICAFIL ::= :push.0.push.ELIST ::= ?' ' :push.0.push.SELECT ::= :push.0.push.SELECT ::= SELECT :push.0.push.STARTSELECT.push.0.push.SICAFIL ::= FROM :push.0.push.STARTFROM.push.0.push.SICAFIL ::= WHERE :push.0.push.STARTWHERE.push.0.push.SICAFIL ; АРИФМЕТИЧЕСКОЕ ВЫРАЖЕНИЕ ::= ?'LIKE'..'AND'..'OR'..'EQ'..'>'..'>='..'.' '..'.'+'..'- '..'*'..'/'..')' ;БИНАРНЫЕ ОПЕРАЦИИ НИЗКОГО ПРИОРИТЕТА ::= ?'*'..'/'.. :push.2.push. ::= ?'*'..'/'.. :push.2.push.= ?'*'..'/'.. :push.2.push.>= ::= ?'*'..'/'.. :push.2.push.< ::= > ?'*'..'/'.. :push.2.push.> ::= EQ ?'*'..'/'.. :push.2.push.EQ ::= OR ?'*'..'/'.. :push.2.push.OR ::= AND ?'*'..'/'.. :push.2.push.AND ::= LIKE ?'*'..'/'.. :push.2.push.LIKE ::= NOT ?'*'..'/'.. :push.1.push.NOT ::= - ?'*'..'/'.. :push.1.push.~ ::= - ?'*'..'/'.. :push.2.push.- ::= + ?'*'..'/'.. :push.2.push.+ ::= ?'*'..'/'.. ::= / :push.2.push./ ::= * :push.2.push.* ::= ?']'. ::= ( ) :push.2.push.CALL ::= [ ] :push.0.push.] ::= ?'='..'('.. !push.I ::= ( )