nC1DMY1V3A

гола-60), являются нормальные формы Бэкуса, сокращенно обозначают БНФ – бэкусова нормальная форма или бэкуса-науровская форма (по имени авторов Джона Бэкуса и Петера Наура). Формы Бэкуса-Наура используются, прежде всего, для представления в сжатом и компактном виде строго формальных правил написания основных конструкций конкретного языка программирования.

В форме Бэкуса-Наура используются два класса объектов [5]: основные символы языка программирования; имена конструкций описываемого языка, или так называемые, металингвистические переменные.

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

< >.

Каждая форма описывает правила построения конструкций языка и состоит из двух частей. В левой находится металингвистическая переменная, обозначающая соответствующую конструкцию. Далее следует связка ::=, означающая «определяется как» или «есть». В правой части формулы указывается один или несколько вариантов построения конструкции, определяемой в левой части. Варианты правой части формулы разделяются связкой |, имеющей смысл «или».

Пример БНФ для определения десятичного целого числа:

1.< десятичное целое число > ::= < число без знака >| + < число без знака > | — < число без знака >

2.< число без знака > ::= < цифра > | < число без знака >< цифра >

3.<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

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

Пример, число –57 выводится по указанным выше формулам следующим образом:

1.< десятичное целое число >

2.–< число без знака >

3.–< число без знака >< цифра >

4.–< число без знака > 7

5.–< цифра > 7

6.–57

Формы Бэкуса-Наура представляют формальное описание языка и указывают на возможность использования математических средств для системного описания и исследования языков программирования. Использование математического аппарата как основы для синтаксического анализа в трансляторах далее получило развитие в разнообразных методах синтаксического анализа, основанных на теории формальных языков и грамматик.

10

Вопросы и задания для контроля к теме 1

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

2.Что понимается под терминами «исходная программа» и «объектная программа».

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

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

5.Опишите результат работы лексического блока.

6.Опишите результат работы синтаксического блока.

7.Опишите варианты взаимодействия блоков в процессе трансляции.

8.Дайте определение синтаксиса языка.

9.Дайте определение семантики языка.

10.Укажите цель применения нормальных форм Бекуса-Наура.

11.Укажите основные элементы записи формул БНФ.

12.Постройте вывод целых чисел –2, 71, –654, используя формулы БНФ, описанные в параграфе.

11

Тема 2. Основы теории формальных языков и грамматик

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

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

Основные термины и определения теории формальных грамматик

[3].

Определение 2.1. Символ (или буква) – это простой неделимый знак. Множество символов образует алфавит.

Алфавиты являются множествами, и поэтому к ним можно применять теоретико-множественные обозначения. В частности, если А и В такие алфавиты, что А В, то будем говорить, что А является подалфавитом В.

Определение 2.2. Цепочка – упорядоченная последовательность символов алфавита.

Введем соглашение: в тексте для обозначения символов будем использовать строчные буквы латинского алфавита: a, b, c, d и т.д., для обозначения алфавита – прописные буквы латинского алфавита: A, B, C, D и т.д., для обозначения цепочек – строчные буквы греческого алфавита: , ,

, , , , и т.д.

Основные формы записи цепочек.

Пусть А – алфавит, тогда цепочки одинаковой длины являются элементами множества: Аn = А А ... А и записываются в виде: а1 а2 ... аn, а не (а1, а2, ..., аn), как это принято для обозначения элементов декартового произведения множеств.

Пример, на алфавите А={a, b} при n=3 получим следующее множе-

ство цепочек Аn ={aaa, aab, abb, aba, baa, bba, bab, bbb}.

Символ также является цепочкой для случая n = 1.

Цепочка может и не иметь символов, тогда это – пустая цепочка, которая имеет специальное обозначение – . При этом не является символом, то есть А. Пустая цепочка является очень важным элементом теории формальных языков, она участвует во многих построениях и выводах.

Цепочки можно называть также словами.

Определение 2.3. Множество всех возможных цепочек над алфавитом А называют замыканием А и обозначают А*, так что

A*=A0 U A1 U ... = U Аn , здесь А0 = { }, А1 = А.

n=0

Еще множество А* называют итерацией алфавита А.

12

Определение 2.4. Множество непустых цепочек над алфавитом А называется усеченной итерацией алфавита А и определятся как:

A+ =A* \ { } = U Аn

через | | и равна числу букв в , при этом | |= 0.

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

конкатенацией.

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

Если цепочки состоят из повторяющихся букв, то применяются сокращенные обозначения, чтобы показать, что цепочку нужно рассматривать как произведение символов алфавита. Поэтому, например, с помощью символа х А можно образовать цепочки = х0, хх= х2, ххn-1= хn и т.д. Такой же подход используется для обозначения повторяющихся цепочек: например, цепочку хухух можно записать как х(ух)2или (ху)2х, при этом символы ( ) А.

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

Определение 2.5. Совокупность цепочек называется языком. Формально язык L над алфавитом А – это множество цепочек из А*, поэтому

L A*.

Теория формальных грамматик занимается описанием, распознаванием и переработкой языков. Она позволяет ответить на ряд прикладных вопросов. Например, может ли язык распознаваться быстро и просто; принадлежит ли данный язык определенному классу; существуют ли алгоритмы, которые давали бы ответ на вопросы типа: «Принадлежит ли цепочка языку L?» и т.д.

В общем случае существуют два основных способа описания отдельных языков (классов языков):

спомощью порождающей процедуры;

спомощью распознающей процедуры.

13

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

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

При построении трансляторов используются оба эти способа: грам-

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

Порождающая грамматика

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

Определение 2.6. Формальной порождающей грамматикой называ-

ется четверка G = <N, T, S, P>, где

Т – конечное непустое множество символов, называемых терминальными символами (терминалами);

N – конечное непустое множество символов, называемых нетерми-

называются правилами подстановки или продукциями [1].

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

Нетерминалы представляют собой синтаксические переменные, которые обозначают множества строк. Эти элементы помогают в определении языка, порождаемого грамматикой, и являются аналогом металингвистических переменных в формулах БНФ.

Терминалы и нетерминалы различаются формой записи: нетерминалы заключаются в угловые скобки < >.

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

14

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

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

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

Формальная порождающая грамматика позволяет не только описать некоторый язык, но и лежит в основе процесса распознавания этого языка: проверки правильности построения предложений языка в соответствии с его синтаксисом.

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

Если такой алгоритм существует, то язык называется распознавае-

мым.

Если при этом число шагов алгоритма распознавания зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык на-

зывается легко распознаваемым.

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

Наиболее важные классы таких языков были определены в рамках классификации, предложенной в 1959 г. американским лингвистом Н.Хомским (классификация по Хомскому). Он предложил классифицировать формальные языки по типу правил порождающих их грамматик [5].

15

Практического применения грамматики, относящиеся только к классу 0, не имеют в силу своей сложности.

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

грамматика с такими правилами называется контекстной грамматикой или грамматикой непосредственно составляющих (НС-грамматика).

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

также, например, для проверки орфографии в текстовых редакторах. Языки, порождаемые грамматиками этого класса, называют контек-

стно-зависимыми.

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

Класс 2. Все порождающие правила грамматики имеют вид: <А> , где <А> – нетерминальный символ, – непустая цепочка из T N. Замена нетерминала <А> на строку происходит без учета контекста, поэтому грамматики этого класса называют контекстно-свободными (КСграмматиками), такое же название имеют порождаемые этими грамматиками языки.

Если допустить, что (T N)*, т.е. возможна пустая подстановка вместо нетерминала <А>, то грамматика называется укорачивающей КСграмматикой (УКС-грамматика). Доказано, что по любой УКС-грамматике можно построить почти эквивалентную КС-грамматику, т.е. порождающую тот же язык, что и исходная грамматика, за исключением пустой цепочки.

16

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

Класс 3. Все порождающие правила имеют вид: <А> b<В> и <А> b, где <А>,<В> N, b T, то есть правая часть правила является или единичным терминалом, за которым следует единичный нетерминал, или единичным терминалом. Языки класса 3 называют автоматными или регулярными языками, а порождающие их грамматики – автоматными грамматиками (А-грамматики). А-грамматики используются в основном на этапе лексического анализа для описания простейших конструкций языка таких, как константа, идентификатор и т.п.

Пример: грамматика G = <N, T, S, P> описывает язык арифметических выражений с переменными а, b, с и знаками +, –.

N = {<S>}, Т = {а, b, с,+, –}, S={<S>}

Данная грамматика по виду своих правил относится к классу 2 – контексно-свободных грамматик, при этом не противоречит и формам правил классов 1 и 0, но, не может быть отнесена к классу 3. Таким образом, класс грамматики определяется по максимальному уровню, формам правил которого она соответствует.

Языки, порождаемые грамматиками разных классов, образуют следующую иерархию. Если язык L(G) регулярный, то он контекстносвободный. Если язык L(G) контекстно-свободный, то язык L(G) – НСязык. Если язык L(G) – НС-язык, то он язык класса 0.

Вопросы и задания для контроля к теме 2

1.Дайте определение терминам: символ, алфавит, цепочка, язык.

2.Пусть задан алфавит А={x, y, z}. Постройте множество Аn , n=2.

3.Укажите разницу между множествами, обозначаемыми символами А* и А+ .

4.Пусть заданы цепочки =000111, =10000, =00001. Перепишите данные цепочки, используя сокращенные обозначения для повторяющихся символов.

17

5.Постройте конкатенацию цепочек =, если =aba, =bab, и запишите результат в краткой форме, используя сокращенные обозначения для повторяющихся символов.

6.Пусть язык задан множеством L={1n 0m ,m>n>0}. Приведите примеры цепочек, принадлежащих данному языку. Пустая цепочка принадлежит данному языку?

7.Пусть язык задан множеством L={1n,n≥0} {0n,n≥0}. Приведите примеры цепочек, принадлежащих данному языку. Пустая цепочка принадлежит данному языку?

8.Назовите два основных способа описания отдельных языков.

9.Назовите множества, участвующие в определении формальной порождающей грамматики.

10.Определите назначение аксиомы грамматики (начального нетерминала).

11.Дайте определение языка, порождаемого заданной грамматикой.

12.Какой язык считается легко распознаваемым?

13.Сколько уровней включает классификация формальных порождающих грамматик по Холмскому?

14.Какой вид правил подстановки соответствует классу контекстносвободных грамматик (КС-грамматик)?

15.Назовите основное назначение КС-грамматик.

16.Какой вид правил подстановки соответствует классу автоматных грамматик (А-грамматик)?

17.Как называется язык, порождаемый А-грамматикой.

18.С какой целью можно использовать А-грамматики.

19.Опишите иерархию языков в соответствии с порождающими их классами грамматик.

18

Тема 3. Контекстно-свободные грамматики

Контекстно-свободные грамматики (КС-грамматики) традиционно используют в реализации синтаксического блока компилятора. КСграмматика позволяет описать синтаксические правила входного языка, на котором пишутся тексты исходных программ.

Уточним определение 2.6 формальной порождающей грамматики, используя форму правил, соответствующую классу 2 в классификации по Хомскому.

Определение 3.1. КС-грамматикой называется четверка G = <N, T, S, P>, где

Т – конечное непустое множество терминальных символов (или терминалов);

N – конечное непустое множество терминальных символов (или нетерминалов), T N = ;

S – стартовый символ (аксиома) грамматики G (или начальный нетерминал грамматики G), S N;

Р – конечное множество правил подстановки вида: <A> , где

влевой части <A> – единичный нетерминал;

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

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

Каждому синтаксическому правилу языка соответствует правило подстановки (продукция) грамматики.

Пример. Рассмотрим формальную грамматику G с начальным нетерминалом <S>:

1.<S> a<A><B>c

2.<S> ε

3.<A> c<S><B>

4.<A> <A>b

5.<B> b<B>

6.<B> a

Использование правила 5 для подстановки в некоторую цепочку, состоящую из терминальных и нетерминальных символов, записывается следующим образом:

a<A><B>5c a<A>b<B>c

19