Проектирование трансляторов

характеризуется алфавитом, лексикой, семан-

тикой и синтаксисом.


┌──────────── ПРЕДЛОЖЕНИЕ ───────────┐

│ │ │ │

│ │ │ │

ОПРЕДЕЛЕНИЕ ПОДЛЕЖАЩЕЕ СКАЗУЕМОЕ ДОПОЛНЕНИЕ

│ │ │ │

голодный верблюд съел колючку


В самом общем виде в состав транслятора должны входить сле-

дующие блоки:

- Лексический анализ;

- Синтаксический анализ;

- Семантический анализ;

- Синтез программы на промежуточном языке;

- Оптимизация программы;

- Синтез объектной программы.


Лексический анализ реализуется с помощью лексического анали-

затора (сканера). ЛА выделяет лексемы из транслируемого сообще-

ния и заменяет их на символы языка. В процессе анализа могут воз-

никать ошибки.

Лексемы могут быть следующих классов:

- разделители;

- арифметические операции: + - / *;

- ключевые слова: for, begin, end, do, to, step;

- идентификаторы.


Синтаксический анализатор распознает синтаксис языка (струк-

туру).


Семантический разбор - это программа или группа программ,

занимающаяся распознаванием смысла сообщения.


Синтез программы - программа, которая занимается генерацией

программы на промежуточном языке.


Оптимизация программы - синтез программы в виде объектного

кода.


ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЯ ГРАММАТИКИ:

Грамматика - упорядоченная четверка G = (Vт, Vn, P, S), S C

Vn, множества терминальных Vt и нетерминальных Vn символов, грам-

матических правил P, начальный нетерминальный символ S или аксио-

ма.

Правила P непосредственно определяют процесс вывода. Хом-

ский ввел 4 класса грамматик:


1. Автоматная грамматика: символы, которые встречаются в ле-

вой части правил называются нетерминалами, они образуют множес-

тво нетерминальных символов Vn; символы, которые входят в множес-

тво Vт, называются терминалами. Нетерминалы и терминалы вместе

образуют словарь V.


V = Vn U Vт

U ::= N, U ::= WN

N C Vт, U,W C Vn


На базе автоматной грамматики строятся конечные или беско-

нечные автоматы, использующиеся для сканирования или синтаксичес-

кого анализа.


2. Контекстно-свободная грамматика:


U ::= u ; U C Vn , u C V

│ │

цепочка строка состоит из

исходного термин. и нетерм.

текста символов

(нетерм.)


Строка u сворачивается в U вне зависимости от контекста.


3. Контекстно-зависимые грамматики:


x U y ::= xuy

U C Vn; x,y,u C V


4. Грамматика без ограничения на правила вывода:


V ::= u u C V*, V C V*


Грамматика, которая позволяет разбирать арифметические выра-

жения:


<выражение>::= <терм>│

<выражение>+<терм>│

<выражение>-<терм>


<терм> ::= <множество>│

<терм>*<множество>│

<терм>/<множество>


<множество> ::= (<выражение>)│ i


i - идентификатор


Алфавит языка - это некоторое непустое конечное множество

элементов, называемых символами.

Всякая конечная последовательность символов языка называет-

ся цепочкой.

Пустая цепочка - цепочка, не содержащая ни одного символа.

Ее длина равна 0.

Множества цепочек в алфавите обычно обозначаются заглавными

буквами.


Х = mABCn

│ │

голова хвост


xy - конкатенация цепочек x, y. х - голова, у - хвост цепоч-

ки z=xy.

Произведение АВ двух множеств цепочек А и В:


AB = { xy │ x C A, y C B }


Степень цепочки: x^0 - "", x^N = x^(N-1)*x


V* - рефлексивно-транзитивное замыкание (итерация).

V+ - транзитивное замыкание (усеченная итерация).

Бесконечные множества:


V* = V^0 U V^1 U ... U V^N U ...


Формальное описание строки:


V*={z │ z = "",z = xU}, z,x C V*, U C V - любой символ из V.


Строка x непосредственно порождает y относительно P (x->y),

когда существуют строки u, w, (возможно пустые) такие, что x=uVw,

y=uzw, V ::= z C P.


Строка x порождает y относительно P (x=>y), когда сущес-

твует последовательность строк x0, x1, x2, ... xN, такая, что

x=x0, y=xN, xI-1 -> xI (I=1,2,...,N).


Язык - некоторое множество предложений:

Lg = { x │ x C Vt*, S => x }.


Порождение (либо свертывание) строк Lg можно представить в

виде дерева. Терминальные символы не порождают новых символов,

нетерминальные - порождают. Иначе терминальные символы - это те,

на которых образуются конструкции Lg.


Cентенциальная форма: S => x, х C V+.


Предложение - цепочка терминальных символов, выведенных из

аксиомы: { x │ S => x, x C Vt* }


Пусть w=xuy - сентенциальная форма. Тогда u - фраза для U C

Vn, если S => xUy и U => u. Простая фраза - если U -> u.


Основа - самая левая простая фраза. Существуют леворекурсив-

ные и праворекурсивные грамматики. Различные грамматики могут по-

рождать один и тот же L. Мы можем генерировать синтаксически пра-

вильные сообщения.


<предложение>::=<определение><подлежащее><сказуемое><дополнение>

<определение>::=<голодный>│<большой>

<подлежащее>::=<верблюд>│<слон>│ ...

<сказуемое>::=<съел>│<взял>│ ...

<дополнение>::=<колючку>│<ветку>│ ...


Используя функции порождения строк относительно синтаксиса

этого языка, можно генерировать строки, формально принадлежащие

этому языку, правильные синтаксически, но неверные семантически (

Пример - Глоклая куздра бодланула куздренка).


G1 и G2 эквивалентны, если порождаемые ими языки Lg1 и Lg2

равны. Эквивалентные преобразования грамматик могут быть ис-

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


Однозначная грамматика - если существует только одно дерево

вывода для каждого предложения Lg.


Разбор или синтаксический анализ сентенциальной формы - это

построение вывода и, возможно, синтаксического дерева для нее.

Существуют методы как нисходящего, так и восходящего разбо-

ра (относительно движения по синтаксическому дереву).


Непосредственный вывод xUy -> xuy называют каноническим, ес-

ли u C Vt*. Вывод w=>v канонический, если все непосредственные

выводы в нем канонические.

Сентенциальная форма, имеющая канонический вывод - канони-

ческая сентенциальная форма.


Свертывание будем называть проходом или анализом. В дальней-

шем будем считать, что в процессе анализа считывание входного

текста происходит слева направо, а свертывание начинается с той

самой левой части строки, которая может быть свернута без допол-

нительного анализа последующего текста. Такое свертывание будем

называть каноническим.


Отношения


->, => - символы отношений между цепочками.

Пара цепочек (c,d) принадлежит отношению R, если выполняет-

ся cRd.


Отношение P включает R, если из (c,d) C R следует (c,d) C Р.


Отношение, обратное R - R^(-1).


Рефлексивное отношение - при справедливости сRc.

Например: i <= i - рефлексивное, а i < i - не рефлексивное

отношение.


Транзитивное отношение R - если выполняется aRb, bRc => aRc.


Произведение R,P: cRPd - если существует е, такое что cRe и ePd.


Итерация R - (обозначается R*): aR*b - когда a=b или aR+b.


Ограничения, накладываемые на грамматику G:

- нет правил вида U ::= U;

- S=>xUy, U=>t, t C Vt* - приведенная грамматика;


Пример. G - язык арифметических выражений.

S ::= E

E ::= T

E ::= E+T

T ::= P

T ::= T*P

P ::= (E)

P ::= I


ЛЕКЦИЯ 3


АНАЛИЗ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ

С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ


Будем рассматривать каноническое свертывание контекстно-сво-

бодных (КС) языков. Нахождение эффективных методов свертывания -

одна из важнейших задач в теории построения трансляторов. В рас-

сматриваемых алгоритмах анализа входного текста, написанного на

КС-языке, используются отношения предшествования между каждой па-

рой соседних символов строки.

Рассмотрим подробнее отношения предшествования: пусть Si и

Sj - символы языка L (Si,Sj С V). Если в некоторой строке языка

они могут быть записаны рядом (...SiSj...), то между ними могут

существовать только три отношения.


1. В строке ...SiSj... свертываемая часть строки начинается

└──┘

с символа Sj, то есть Sj - самый левый символ свертываемой под-

строки. Если при этом Si не является последним символом другой

строки свертываемой подстроки, то будем говорить, что Si предшес-

твует Sj. Запишем это условие в виде Si < Sj.


2. В строке ...SiSj... символы Si и Sj входят в одну и ту

└────┘

же свертываемую часть строки.Этот факт запишем в виде Si = Sj и

будем говорить, что Si и Sj входят в одно и то же свертывание.


3. В строке ...SiSj... свертываемая часть строки кончается

└──┘

символом Si, то есть Si - самый правый символ свертываемой части

строки. Это условие запишем в виде Si > Sj и будем говорить, что

Sj следует за Si.


Отношения <, =, > назовем отношениями предшествования. Отно-

шения предшествования обычно записываются в виде матрицы, стол-

бцы и строки которой соответствуют символам словаря V. На пересе-

чении i-ой строки и j-го столбца записывается отношение предшес-

твования между символами Si и Sj. Элементами матрицы являются

знаки <, =, > или пусто. Последний случай означает, что символы

Si и Sj ни в одной строке языка не могут стоять рядом.

В дальнейшем будет введено формальное определение отношений

предшествования и дан алгоритм их определения.

Сейчас же мы рассмотрим алгоритм анализа программы, разрабо-

танный Виртом и Вебером.

Достоинство этого алгоритма заключается в том, что он сни-

мает дополнительное ограничение на грамматику языка, и допускает,

чтобы в правилах грамматики два нетерминальных символа стояли ря-

дом. Но и в этом алгоритме требуется, чтобы между каждой парой

символов языка существовало не более одного отношения предшество-

вания и в множестве синтаксических правил не было двух одинако-

вых правых частей, т.е. правил, у которых правые части одинаковы,

а левые - разные.

Алгоритм основан на каноническом свертывании, т.е. на выде-

лении самой левой свертываемой части строки. Блок-схема алгорит-

ма показана на рис. 1 (@ - символ начального (конечного) ограни-

чителя входного анализируемого текста; не входит в алфавит языка).


┌────────────────────────────────┐

│ ^

┌─────┴───┬─┐ │

┌───────┬─┐ │ i:=i+1 │2│ │

│ i:=1 │1│ │ └─┤ │

│ └─┤ │ j:=i │ │

│ k:=2 │ │ │ │

│ │ │ R :=L │ │

│ R :=@ │ │ i k │ │

│ i │ │ │ │

└────┬────┘ │ k:=k+1 │

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: