Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Алёшин А.В. Теория языков программирования и методы трансляции - файл 1.doc


Алёшин А.В. Теория языков программирования и методы трансляции
скачать (1088.5 kb.)

Доступные файлы (1):

1.doc1089kb.16.11.2011 04:20скачать

содержание
Загрузка...

1.doc

  1   2   3   4   5   6   7   8   9   ...   13
Реклама MarketGid:
Загрузка...

ЛЕКЦИЯ № 3 ТЕОРИЯ ЯЗЫКОВ И ФОРМАЛЬНЫХ ГРАММАТИК




3.1 Способы определения языков



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

Существует два основных способа определения языков:

– механизм порождения или генератор;

– механизм распознавания или распознаватель.

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

Неформально язык ^ L - это множество цепочек конечной длины в алфавите T. Механизм порождения позволяет описать языки с помощью системы правил, называемой грамматикой. Цепочки (предложения) языка строятся в соответствии с этими правилами. Достоинство определения языка с помощью грамматик в том, что операции, производимые в ходе синтаксического анализа и перевода, можно делать проще, если воспользоваться структурой, предписываемой цепочкам с помощью этих грамматик.

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

^

3.2 Формальные грамматики



Грамматикой называется четверка


G = (N, T, P, S), (3.1)


где N - конечное множество нетерминальных символов

(нетерминалов),

T - множество терминалов (не пересекающихся с N),

S - символ из N, называемый начальным,

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

Множество правил ^ Р описывает процесс порождения цепочек языка. Элемент pi = (, ) множества Р называется правилом (продукцией) и записывается в виде   . Здесь и - цепочки, состоящие из терминалов и нетерминалов. Данная запись может читаться одним из следующих способов:

– цепочка порождает цепочку ;

– из цепочки выводится цепочка .

Таким образом, правило P имеет две части: левую, определяемую, и правую, подставляемую. То есть правило pi - это двойка (pi1, pi2), где p i1 = - цепочка, содержащая хотя бы один нетерминал, pi2 = произвольная, возможно пустая цепочка ( - цепочка).

Если цепочка содержит pi1, то, в соответствии с правилом pi, можно образовать новую цепочку , заменив одно вхождение pi1 на pi2. Говорят также, что цепочка выводится из в данной грамматике.

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

– терминалы обозначаются буквами a,b,c,d или цифрами 0,1, ...,9;

– нетерминалы обозначаются буквами A, B, C, D, S (причем нетерминал S - начальный символ грамматики);

– буквы U, V, ..., Z используются для обозначения отдельных терминалов или нетерминалов;

– через , , ... обозначаются цепочки терминалов и нетерминалов;

– u, v, w, x, y, z - цепочки терминалов;

– для обозначения пустой цепочки (не содержащей ни одного символа) используется знак ;

– знак «» отделяет левую часть правила от правой и читается как «порождает» или «есть по определению». Например, A cd, читается как «A порождает cd».

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


Пример грамматики G1:


G1 = ({A, S}, {0, 1}, P, S), (3.2)


где P:

1. S 0A1;

2. 0A 00A1;

3. A  .

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

Язык L(G), порождаемый грамматикой G, - это множество терминальных цепочек, порождаемых грамматикой G.

Введем отношение G непосредственного вывода на множестве , которое записывается следующим образом:


 G(3.3)


Данная запись читается: непосредственно выводима из для грамматики G = (N, T, P, S) и означает: если  – цепочка из множества и    – правило из Р, то  G .

Через G+ обозначим транзитивное замыкание (нетривиальный вывод за один и более шагов). Тогда  G+ читается как: выводима из нетривиальным образом.

Через G* обозначим рефлексивное и транзитивное замыкание (вывод за ноль и более шагов). Тогда  G* означает: выводима из .

Пусть K – k-я степень отношения . То есть, если  K, то существует последовательность 0 1 2 3 ... k из к+1 цепочек


 = 0, 1, ... i - 1  i, 1 ≤ i ≤ k и k = (3.4)


Пример выводов для грамматики G1:


S 0A1 00A11 0011; (3.5)


S 1 0A1; S 2 00A11; S 3 0011; (3.6)


S + 0A1; S + 00A11; S + 0011; (3.7)


S * S; S * 0A1; S * 00A11; S * 0011, (3.8)


где 0011  L(G1).


^

3.3 Грамматики с ограничениями на правила



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

праволинейной, если каждое правило из Р имеет вид:


A  xB или A  x, (3.9)


где A, B - нетерминалы,

x - цепочка, состоящая из терминалов;

контекстно-свободной (КС) или бесконтекстной, если каждое правило из Р имеет вид: A  , где A N, а   , то есть является цепочкой, состоящей из множества терминалов и нетерминалов, возможно пустой;

контекстно-зависимой (КЗ) или неукорачивающей, если каждое правило из P имеет вид:   , где ||  ||. То есть, вновь порождаемые цепочки не могут быть короче, чем исходные, а, значит, и пустыми (другие ограничения отсутствуют);

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


Пример праволинейной грамматики:


G2 = ({S,}, {0,1}, P, S), (3.10)


где P:

1. S 0S;

2. S 1S;

3. S  ,

определяет язык {0, 1}*.


Пример КС-грамматики:


G3 = ({E, T, F}, {a, +, *, (,)}, P, E), (3.11)


где P:

1. E T;

2. E E + T;

3. T F;

4. T T * F;

5. F (E);

6. F a.

Данная грамматика порождает простейшие арифметические выражения.


Пример КЗ-грамматики:


G4 = ({B, C, S}, {a, b, c}, P, S), (3.12)


где P:

1. S aSBC;

2. S abc;

3. CB BC;

4. bB bb;

5. bC bc;

6. cC сc,

порождает язык { an bn cn }, n ≥ 1.


Примечание 1. Согласно определению каждая праволинейная грамматика является контекстно-свободной.


Примечание 2. По определению КЗ-грамматика не допускает правил: А  , где - пустая цепочка. Т.е. КС-грамматика с пустыми цепочками в правой части правил не является контекстно-зависимой. Наличие пустых цепочек ведет к грамматике без ограничений.


Соглашение. Если язык L порождается грамматикой типа G, то L называется языком типа G.


Пример: L(G3) - КС язык типа G3.


Наиболее широкое применение при разработке трансляторов нашли КС-грамматики и порождаемые ими КС-языки. В дальнейшем при изучении КС-языков будут рассматриваться только полезные для нас с практической точки зрения (теория языков весьма обширна и для детального ее изучения необходимо много времени). Для получения углубленных знаний рекомендуется обратиться к фундаментальной монографии Ахо и Ульмана [14].
  1   2   3   4   5   6   7   8   9   ...   13



Скачать файл (1088.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru