Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Билет №3 Грамматики , классификация языков по Хомскому , способы описания синтаксиса языков программирования.

Синтаксис.

Существует множество различных способов описания синтаксиса языков программирования. Если язык состоит из конечного числа строк, то его определение может быть сделано перечислением всех его элементов. Так как все языки программирования содержат бесконечное число строк, то требуется найти способ представления бесконечного числа строк конечным образом.

Рассмотрим примеры описания бесконечного числа строк символов.

Пример1. Язык который состоит из произвольного количества символа x

Может быть определен в виде выражения { x ⁿ | n>0 }, где n - целое, а

умножение здесь трактуется как конкатенация.

Пример2. Язык который состоит из произвольного количества

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

символов y. Этот язык определяется в виде выражения

{ x ^m y ⁿ | m,n>0 }, где m,n - целые.

Пример 3. Если язык определить в виде выражения

{ x ^m y ⁿ | m,n ³ 0 }, то допустимыми являются строки вида

xxx (при n=0),уууу (при m=0), а также пустая строка (при m=0, n=0), которую будем обозначать <>.

Пример 4. Язык, определенный в примере 3, можно переопределить

по другому: x ^* y ^*, где символ "* " (звездочка Клини) обозначает, что предшествующий ему элемент, используется нуль или большее число раз (представление с помощью языка регулярных выражений).

Пример 5. Выражение вида xx ^* yy ^* определяет язык, каждая строка которого содержит как минимум по одному элементу x и y.

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

{ A..Z }, { 0..9 }, { А..Я } и т.п..

Регулярными выражениями являются:

1) пустая строка (<>);

2) любой элемент из алфавита.

Далее, если P и Q - регулярные выражения, то регулярными являются

выражения:

3) PQ (Q следует за P);

4) P | Q (P или Q);

5) P ^* (нуль или большее число вхождений P).

Несмотря на компактность и удобство регулярных выражений, далеко

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

с помощью грамматик.

Грамматика определяется в виде четверки объектов (A_T, A_N,P,S), где

A_T - алфавит терминальных символов, A_N - алфавит нетерминальных символов, P - множество продукций (или правил вывода) вида a -> b,

где a - левая часть, а b - правая часть продукции, S - начальный символ (аксиома или символ предложения) грамматики, являющийся элементом множества A_N (SÎ A_N). При этом имеют место следующие соотношения: A_T Ç A_N = Æ,a Î A^* , b Î A^* , A = A_T È A_N (A^* определяет строки, состоящие из нуль или более повторений символов из A). Особенностью начального символа S является то, что с него начинается генерация любой строки языка.

Грамматика используется для генерации строк символов языка начиная с аксиомы грамматики, последовательно применяя правила подстановки (продукции) и заменяя нетерминал последователь-

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

В дальнейшем для обозначения терминальных символов будем использовать строчные буквы, или, в некоторых случаях слова, состоящие только из строчных букв (x, y, if, then, else и т.п.). Для обозначения нетерминальных символов будем использовать заглавные буквы (X,Y, S и т.п.). Аксиому грамматики будем обозначать буквой S.

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

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

Пример 6. Грамматикой для языка { x ⁿ y ⁿ | n>0 }, строки которого состоят из одного или более символов x, после чего следует такое же количество символов y, является G₁= ({ x, y }, { S }, P, S), где множество продукций P определяется как: S -> xSy, S -> xy.

Пример7. Грамматикой для языка { x ^m y ⁿ |m, n³ 0 }, строки которого состоят из нулевого числа или более символов x, после чего следует нулевое число или более символов y, является

G₂= ({ x, y }, { S, B }, P, S), где множество продукций P определяется как:

S -> xS

S -> yB

S -> x

S -> y

S -> <>

B -> yB

B -> y.

Например, строка xxyyy может быть сгенерирована грамматикой G₂

с помощью серии подстановок S=> xS => xxS => xxyB => xxyyB => xxyyy,

называемой порождением. Каждая из строк, входящая в порождение,

называется сентенциальной формой, а последняя сентенциальная форма, состоящая только из терминальных символов, называется

предложением языка. Выражение вида a => b, где a, b - сентенциаль-ные формы означает, что строка b получена из строки a посредством одного порождения. Выражение вида a =^*> b означает, что строка b порождается из строки a за нуль или более шагов. Выражение вида

a =⁺> b означает, что строка b порождается из строки a за один или более шагов. Условимся в дальнейшем обозначать порождения вида

B -> yB, B -> y как B -> yB | y.

Для классификации грамматик и языков было введено понятие иерархии Хомского. Хомский определил четыре класса грамматик, которые были названы грамматиками 0-го, 1-го, 2-го и 3-го типов.

К 0-му типу относятся все грамматики без ограничений на типы продукции. Грамматики 0-го типа называют еще рекурсивно-

- перечислимыми грамматиками.

Грамматики, все продукции которых ограничены соотношением

| a | £ | b | (то есть длина строки a, исчисляемая количеством входящих символов, не может быть больше длины строки b), называ-ются грамматиками 1-го типа, или по другому контекстно-

- зависимыми.

Если контекстно-зависимую грамматику ограничить условием,

которое предусматривает наличие в левой части каждой продукции только одного единственного нетерминального символа, то мы получаем грамматику 1-го типа, или по другому контекстно-свободную грамматику.

Для определения 3-го типа грамматик, или так называемых регулярных грамматик, введем сначала ряд вспомогательных определений.

Грамматика называется праволинейной, если каждая ее продукция имеет вид A-> a либо A-> bC. Соответственно грамматика называется леволинейной, если каждая ее продукция имеет вид A-> a либо A-> Cb.

Грамматика называется регулярной (грамматикой 3-го типа), если она является только праволинейной или только левоволинейной.

Замечание. В контекстно-свободных грамматиках разрешим

использование продукций вида a -> <>, где a -нетерминальный символ (хотя строго говоря эта продукция не разрешена даже в контекстно-

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

Классификация Хомского является иерархической в том смысле, что

все грамматики 3-го типа являются грамматиками 2-го, все грамматики

2-го типа являются грамматиками 1-го, а все грамматики 1-го типа -

- грамматиками 0-го типа.

Соответственно, мы можем определить иерархию языков

основываясь на порождающих их грамматиках, то есть языки 3-го типа, языки 2-го типа и т.п.. Однако необходимо иметь в виду, что существуют языки, например 3-го типа, которые определяются грамматикой 2-го типа, и в то же время существует эквивалентная грамматика 3-го типа для порождения этого языка (в этом случае она обязательно должна существовать, поскольку речь идет о языке 3-го типа).

Например язык вида { x ^m y ⁿ |m, n³ 0 } (этот пример уже рассматривался выше). Этот язык можно сгенерировать следующими продукциями:

S->XY

X->xX

X-> <>

Y->yY

Y-> <>

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

следующими ниже продукциями 3-го типа.

S -> xS

S -> yB

S -> x

S -> y

B -> yB

B -> y

S -> <>

В разработке компиляторов широко используются контекстно-

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

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

A -> Ab

B -> cB

C -> dCf.

Это - примеры так называемой прямой рекурсии, при которой нетерминальный символ из левой части продукции входит и в правую часть. В первом случае имеем левую рекурсию (нетерминал слева),

во втором - правую рекурсию (нетерминал справа), в третьем - среднюю

рекурсию (нетерминал располагается и не слева и не справа).Следует

отметить, что кроме прямой рекурсии существует еще понятие

косвенной (непрямой) рекурсии. Например: A -> Bc, B -> Cd, C -> Ae. Поскольку существует простой алгоритм преобразования косвенной рекурсии в прямую (этот алгоритм мы здесь не рассматриваем), далее мы не будем рассматривать косвенную рекурсию.

Теперь мы можем сформулировать важное утверждение, на основе которого можно будет определить, является ли генерируемый язык регулярным: если грамматика не содержит средней рекурсии, то

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

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

Левое порождение определяется как порождение, на каждом шаге которого заменяется крайний левый нетерминал сентенциальной

формы.

Правое порождение определяется как порождение, на каждом шаге которого заменяется крайний правый нетерминал сентенциальной

формы.

Рассмотрим в качестве примера язык вида { x ^m y ⁿ |m, n > 0 }, определяемый следующими продукциями:

S -> XY

X -> xX

X -> x

Y - >yY

Y -> y

Строка xxxyy может быть сгенерирована одним из двух порождений:

1) S => XY => xXY => xxXY => xxxY => xxxyY => xxxyy

2) S => XY => XyY => Xyy => xXyy => xxX yy => xxxyy.

Первое порождение является левым, а второе - правым.

Порождение можно выразить по другому - через синтаксическое дерево (дерево синтаксического разбора).

Например порождение S =>XY=>xXY=>xXyY=>xxXyY=>xxXyy=>xxxyy

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

S

X Y

x X y Y

x X y

x

Рис. 3.1.1-1. Пример синтаксического дерева.

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

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

Многие компиляторы создаются на основе однозначных грамматик, однако при разработке компиляторов в ряде случаев возникают неоднозначные грамматики, для которых однако чаще всего находятся методы устранения неоднозначности. Неоднозначные языки, для которых не существует однозначной грамматики, обычно не

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

Билет №4 Лексический анализ. Основные понятия.

Лексический анализ выполняет формирование символов языка на основе так называемых лексем, к числу которых принадлежат следующие элементы языка.

1) Ключевые слова языка (if, then, else, while,do, var, integer и т.п).

2) Идентификаторы (custom, x1,y1, name и т.п)

3) Константы (14, 13.06, 'abc' и т.п.).

4) Последовательности знаков (<=, <>,>=, и т.п.).

2) Знаки пунктуации ({ } [ ] …,; и т.п).

Лексемы преобразуются в неделимые символы языка, которые в дальнейшем используются на фазах синтаксического и

семантического анализов. Кроме этого лексический анализатор осуществляет обработку пробелов, удаление комментариев и некоторые другие действия, необходимые для подготовки текста программы к последу-ющим фазам. При формировании символов языка лексический анализатор не учитывает их последовательность, то есть как правило не работает с контекстом. Например, если в программе на языке PASCAL появится некорректная конструкция вида if b while P вместо if b then P, лексический анализатор не обнаружит никакой ошибки.

Для фазы лексического анализа наиболее удобным средством описания символов являются регулярные выражения. Например, идентификатор можно представить в виде буква(буква | цифра)^*.

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

- ключевые слова разрешено использовать в качестве

идентификаторов;

- интерпретация некоторых последовательностей лексем носит

контекстно-зависимый характер.

Например в языке FORTRAN можно использовать конструкцию вида

IF(K) =1, которую можно интерпретировать как присвоение значения

K-ому элементу массива с именем IF. Однако распознавание именно

такой интерпретации может быть выполнено только по достижению конца строки, поскольку может появиться конструкция IF(K) 1,2,3, интерпретируемая как оператор IF. Другим неудобством языка FORTRAN с точки зрения лексического анализа является воможность использования внутренних пробелов при обозначении

идентификаторов. Конструкция DO 7 K=1,5 определяет оператор цикла. В то же время, пока не считан символ запятой, начало строки можно спутать с идентификатором DO 7 K.

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

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

образом.

Билет №5 Задача синтаксического анализа. Основные понятия,канонические формы, используемые в синтаксическом анализе (префиксный и постфиксный способы представления выражений)

Первоочередной задачей синтаксического анализа является

нахождение порождения (если оно существует) конкретного предложения языка с использованием данной грамматики.

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

Если анализируемое предложение не принадлежит языку,

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

Нисходящий синтаксический анализ (top-down parsing) предусматривает построение синтаксического дерева, начиная

с вершины (символа предложения) с развертыванием дерева в направлении предложения языка.

Восходящий синтаксический анализ (bottom-up parsing)

предусматривает построение синтаксического дерева, начиная

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

Префиксная и постфиксная записи выражений.

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

перед генерацией кода являются префиксная и постфиксная записи.

Для пояснения рассмотрим выражение вида a+b*c+d/e-f. Такая запись выражения называется инфиксной, что означает расположение знака

бинарной операции между операндами. Интерпретация и

соответственно анализ такого выражения в общем случае носит

неодназначный характер. Для устранения неодназначности

используется приоритет операций. Анализ основывается на

представлении выражения в древовидной форме следующего вида:

-

+ f

+ /

a * d e

b c

Рис. 3.4.4-1. Пример древовидного представления выражения.

Каждая промежуточная вершина этого дерева помечена знаком

соответствующей операции, а дуги, исходящие из данной вершины,

ведут к операндам.

Теперь, начиная с вершины (сверху вниз) и придерживаясь

левоориентированного пути, обойдем это дерево, попутно выписывая

в строку все встречающиеся символы. В результате получим выражение

вида - + + a * b c / d e f, представляющее префиксную запись.

Отличительная собенность префиксной записи заключается в том, что

каждый знак операции предшествует своим операндам.

Постфиксная запись получается "зеркальным отображением "

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

выше выражения постфиксная запись имеет вид f e d / c b * a + + -.

Отличительной собенностью постфиксной записи является то, что

каждый знак операции записывается после операндов. Постфиксная

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

в ней все знаки выполняемых операций располагаются в порядке

убывания приоритетов.

Последнее означает, что первая встретившаяся операция при

просмотре выражения слева направо выполняется первой, вторая встретившаяся - второй и т.п.. Для вычисления постфиксной записи используется классический алгоритм с использованием стека. Алгоритм

основывается на просмотре символов выражения слева направо и вы-

полнении соответствующих действий в зависимости от назначения

символа (знак операции, символ операнда или символ конца строки).

Таким образом алгоритм в процессе просмотра выражения может

находиться в одном из следующих состояний.

1. Считываемый символ является операндом. В этом случае

значение операнда заносится в стек.

2. Считываемый символ является знаком операции. Выполняется

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

из стека. Извлеченные из стека операнды соответственно удаляю-

тся из стека и в стек заносится результат выполнения операции.

3. Считываемый символ определяет конец строки. Алгоритм завер-

шает свою работу. В стеке остается единственный элемент,

определяющий результат вычисления выражения.

Билет №6 Определение семантики языков программирования на основе средств логического программирования. Определения базисных операторов на языке исчисления предикатов.

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

Методы описания семантики как правило принадлежат к одному из

перечисленных ниже классов.

Денотационная семантика основывается на функциональных вычислениях, определяющих операции в языке в виде отображений

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

Аксиоматическая семантика основывается на исчислении

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

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