Основные понятия и определения. по дисциплине Системное программное обеспечение

Введение

Описание языков.

Л Е К Ц И Я № 2

по дисциплине Системное программное обеспечение

Тема: «Формальные модели грамматик. Построение таблиц идентификаторов»

Цель:

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

План:

1. Описание языков.

2. Организация таблиц символов компилятора.

Литература:

1. А.В. Гордеев, А.Ю. Молчанов «Системное программное обеспечение»,

С.-П.: Питер 2001г. 736с.

2. Волкова И.А., Руденко Т.В. «Формальные грамматики и языки.

Элементы теории трансляции», М.: МГУ 1999 г. 62с.

1. О.В. Газина и др. «Системное программное обеспечение», Севастополь: СНУЯЭиП, 2010
2. А.Ахо, Дж.Ульман Теория синтаксического анализа, перевода и компиляции. - Т. 1,2. М., Мир, 1979.
3. А.Ю. Молчанов «Системное программное обеспечение. Лабораторный практикум» - С.-П.: Питер 2005г.

При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.

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

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

Сегодня мы рассмотрим некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Будут введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков – грамматиками.

Рассмотрим предложение «The big elephant ate the peanut» («Большой слон съел орех»). Если мы знаем английский, то поймем, что это предложение английского языка. Его можно изобразить в виде схемы (рисунок 1). Такая схема называется синтаксическим деревом. Оно описывает синтаксис, или структуру, предложения, разлагая его на составные части.

Для того чтобы описать структуру, мы использовали новые символы – «синтаксические единицы» или «синтаксические классы», такие как <предложение>, <сказуемое>. Эти символы заключаются в угловые скобки < >, чтобы отличить их от слов самого языка. Основываясь на знании правил грамматики, можно составить неформальное синтаксическое дерево для любого простого английского предложения. Однако для того, чтобы иметь возможность механически разбирать предложение, мы должны дать точные формальные правила, которые описывают структуру предложений. Для этой цели создается метаязык, т.е. некий язык, на котором можно описывать другие языки. Описание синтаксиса, составленное с помощью такого языка, называют грамматикой языка.

Метаязык, который используется в теории компиляторов, впервые был предложен Хомским для описания естественных языков.

Еще раз рассмотрим предложение «The big elephant ate the peanut». Как видно из рисунка 1 <предложение> состоит из <подлежащее>, за которым следует <сказуемое>. Если сократить фразу «может состоять из», заменив ее символом::=, то наша грамматика могла бы содержать, например, такие правила:

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

<подлежащее>::= <артикль> <прилагательное> <существительное>

<артикль>::= the

<прилагательное>::= big

Рисунок 1

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

<глагол>::= ate

<прямое дополнение>::= <артикль> <существительное>

<существительное>::= peanut

<существительное>::= elephant

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

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

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

Таким образом, мы заменяем синтаксическую единицу на одну из цепочек, из которых она может состоять. Повторим процесс. Возьмем одну из синтаксических единиц в цепочке <подлежащее> <сказуемое>, например <подлежащее>; найдем правило, где <подлежащее> находится слева от::=, и заменим <подлежащее> в исходной цепочке на соответствующую цепочку, которая находится справа от::=.

Это дает

<подлежащее> <сказуемое> Þ <артикль> <прилагательное> <существительное> <сказуемое>

Символ «Þ» означает, что один символ слева от Þ в соответствии с правилом грамматики заменяется цепочкой, находящейся справа от Þ. Полный вывод предложения будет таким:

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

Þ <артикль> <прилагательное> <существительное> <сказуемое>

Þ the <прилагательное> <существительное> <сказуемое>

Þ the big <существительное> <сказуемое>

Þ the bigelephant <сказуемое>

Þ the bigelephant <глагол> <прямое дополнение>

Þ the bigelephant ate <прямое дополнение>

Þ the bigelephant ate <артикль> <существительное>

Þ the bigelephant ate the <существительное>

Þ the bigelephant ate the peanut

Этот вывод предложения запишем сокращенно, используя новый символ «Þ+»

<предложение> Þ+ the bigelephant ate the peanut

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

Из семи правил

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

<подлежащее>::= We

<подлежащее>::= He

<подлежащее>::= I

<сказуемое>::= ran

<сказуемое>::= sat

<сказуемое>::= ate

мы можем образовать целых девять предложений!

We ran He ran I ran

We ate He ate I ate

We sat He sat I sat

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

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

Алфавит - это конечное множество символов.

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

Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита. Цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ e.

Более формально цепочка символов в алфавите V определяется следующим образом:

e - цепочка в алфавите V; (1)

если a - цепочка в алфавите V и a - символ этого алфавита, то aa - цепочка в алфавите V; (2)

b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2). (3)

Если a и b - цепочки, то цепочка ab называется конкатенацией ( или сцеплением) цепочек a и b.

Например, если a = ab и b = cd, то ab = abcd. Для любой цепочки a всегда ae = ea = a.

Обращением ( или реверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки a будем обозначать a^R.

Например, если a = abcdef, то a^R = fedcba. Для пустой цепочки: e = e^R.

N-ой степенью цепочки a (будем обозначать aⁿ) называется конкатенация n цепочек a.

a⁰ = e; aⁿ = aa^n-1 = a^n-1a.

Длина цепочки - это число составляющих ее символов.

Например, если a = abcdefg, то длина a равна 7. Длину цепочки a будем обозначать | a |. Длина e равна 0.

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

Обозначим через V^* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e. Например, если V={0,1}, то V^* = {e, 0, 1, 00, 11, 01, 10, 000, 001, 011,...}.

Обозначим через V⁺ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e. Следовательно, V^* = V⁺ È {e}.

Ясно, что каждый язык в алфавите V является подмножеством множества V^*.

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

Декартовым произведением A ´ B множеств A и B называется множество {(a,b) | a Î A, b Î B}.

/Прямое или декартовое произведение двух множеств — множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств. Данное понятие употребляется не только в теории множеств, но также в алгебре, топологии и прочих разделах математики благодаря тому, что прямое произведение часто наследует структуры (алгебраические, топологические и т. д.), существующие на перемножаемых множествах./

Порождающая грамматика G - это четверка (VT, VN, P, S), где

VT - алфавит терминальных символов (терминалов),

VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT,
P - конечное подмножество множества (VT È VN)⁺ ´ (VT È VN)^*; элемент (a, b) множества P называется правилом вывода и записывается в виде a ® b,

S - начальный символ (цель) грамматики, S Î VN.

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

a ® b₁ a ® b₂... a ® b_n

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

a ® b₁ | b₂ |...| b_n.

Каждое b_i , i = 1, 2,...,n, будем называть альтернативой правила вывода из цепочки a.

Пример грамматики: G1 = ({0,1}, {A,S}, P, S), где P состоит из правил

S ® 0A1

0A ® 00A1

A ® e

Цепочка b Î (VT È VN)^* непосредственно выводима из цепочки a Î (VT È VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим a ® b), если a = x₁gx₂, b = x₁dx₂, где x₁, x₂, d Î (VT È VN)^*, g Î (VT È VN)⁺ и правило вывода g ® d содержится в P.
Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.

Цепочка b Î (VT È VN)^* выводима из цепочки a Î (VT È VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим a Þ b), если существуют цепочки g₀, g₁,..., g_n (n>=0), такие, что a = g₀ ® g₁ ®... ® g_n= b.
Последовательность g₀, g₁,..., g_n называется выводом длины n.

Например, S Þ 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S ® 0A1 ® 00A11 ® 000A111. Длина вывода равна 3.

Языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) = {a Î VT ^* | S Þ a}. Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.

Например, L(G1) = {0ⁿ1ⁿ | n>0}.

Цепочка a Î (VT È VN)^*, для которой S Þ a, называется сентенциальной формой в грамматике G = (VT, VN, P, S).

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

Дата добавления: 2014-01-13