Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

R 1

12. Построить регулярную грамматику, порождающую цепочки в алфавите
{a, b}, в которых символ a не встречается два раза подряд.

13. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc.

L = {a²ⁿ b^m c^2k | m=n+k, m>1}.

14. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите { a, ( , ),  }. Сбалансированную цепочку  определим рекуррентно: цепочка  сбалансирована, если

1.  не содержит скобок,

2.  = (₁) или = ₁ ₂, где ₁ и ₂ сбалансированы.

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

L = {aⁿ cb^m caⁿ | n, m>0}.

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

L = {1ⁿ 0^m 1^p | n+p>m; n, p, m>0}.

17. Дана грамматика G. Определить ее тип; язык, порождаемый этой грамматикой; тип языка.

G: S  0A1

0A  00A1

A  

18. Дан язык L = {1³ⁿ⁺² 0ⁿ | n>=0}. Определить его тип, написать грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки 1111111100.

19. Привести пример грамматики, все правила которой имеют вид
A  Bt, либо A  tB, либо A  t, для которой не существует эквивалентной регулярной грамматики.

20. Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики для

1. L1L2

2. L1 * L2

3. L1^*

Замечание: L = L1 * L2 - это конкатенация языков L1 и L2, т.е.L = {  |   L1,   L2}; L = L1^* - это итерация языка L1, т.е. объединение {}  L1  L1*L1  L1*L1*L1  ...

21. Написать КС-грамматику для L={_i 2 _i+1^R | i  N, _i=(i)₂ - двоичное представление числа i, ^R - обращение цепочки }. Написать КС-грамматику для языка L^* (см. задачу 20).

22. Показать, что грамматика

E  E+E | EE | (E) | i

неоднозначна. Как описать этот же язык с помощью однозначной грамматики?

23. Показать, что наличие в КС-грамматике правил вида

1. A  AA | 

2. A  AA | 

3. A  A | A | 

где , ,   (VTVN)^*, A  VN, делает ее неоднозначной. Можно ли преобразовать эти правила таким образом, чтобы полученная эквивалентная грамматика была однозначной?

*24. Показать, что грамматика G неоднозначна. Какой язык она порождает? Является ли этот язык однозначным?

G: S  aAc | aB

B  bc

A  b

25. Дана КС-грамматика G={VT, VN, P, S}. Предложить алгоритм построения множества

X={A  VN | A  }.

26. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G).

27. Написать приведенную грамматику, эквивалентную данной.

a) S  aABS | bCACd b) S  aAB | E

A  bAB | cSA | cCC A  dDA | 

B  bAB | cSB B  bE | f

C  cS | c C  cAB | dSD | a

D  eA

E  fA | g

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

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

30. Доказать, что нециклическая КС-грамматика порождает конечный язык.

Замечание: Нетерминальный символ A  VN - циклический, если в грамматике существует вывод A  ₁A₂. КС-грамматика называется циклической, если в ней имеется хотя бы один циклический символ.

31. Показать, что условие цикличности грамматики (см. задачу 30) не является достаточным условием бесконечности порождаемого ею языка.

32. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой, содержащей хотя бы один эффективный циклический символ, бесконечен.

Замечание: Циклический символ называется эффективным, если A  A, где |A| > 1; иначе циклический символ называется фиктивным.

ЭЛЕМЕНТЫ ТЕОРИИ ТРАНСЛЯЦИИ

Введение.

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

• лексический анализ

• синтаксический анализ

• семантический анализ

• генерация внутреннего представления программы

• оптимизация

• генерация объектной программы.

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

В этом разделе мы рассмотрим некоторые методы, используемые для построения анализаторов (лексического, синтаксического и семантического), язык промежуточного представления программы, способ генерации промежуточной программы, ее интерпретации. Излагаемые алгоритмы и методы иллюстрируются на примере модельного паскалеподобного языка ( М-языка ). Все алгоритмы записаны на Си.

Информацию о других методах, алгоритмах и приемах, используемых при создании трансляторов, можно найти в [1, 2, 3, 4, 5, 8].

Описание модельного языка

P  program D1; B

D1  var D {,D}

D  I {,I}: [ int | bool ]

B  begin S {;S} end

S  I := E | if E then S else S | while E do S | B | read (I) | write (E)

E  E1 [ = | < | > | != ] E1 | E1

E1  T {[ + | - | or ] T}

T  F {[ * | / | and ] F}

F  I | N | L | not F | (E)

L  true | false

I  C | IC | IR

N  R | NR

C  a | b | ... | z | A | B | ... |Z

R  0 | 1 | 2 | ... | 9

Замечание:

1. запись вида {} означает итерацию цепочки , т.е. в порождаемой цепочке в этом месте может находиться либо , либо , либо , либо  и т.д.

2. запись вида [  |  ] означает, что в порождаемой цепочке в этом месте может находиться либо , либо .

3. P - цель грамматики; символ  - маркер конца текста программы.

Контекстные условия:

1. Любое имя, используемое в программе, должно быть описано и только один раз.

2. В операторе присваивания типы переменной и выражения должны совпадать.

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

4. Операнды операции отношения должны быть целочисленными.

5. Тип выражения и совместимость типов операндов в выражении определяются по обычным правилам; старшинство операций задано синтаксисом.

В любом месте программы, кроме идентификаторов, служебных слов и чисел, может находиться произвольное число пробелов и комментариев вида {< любые символы, кроме } и  >}.

True, false, read и write - служебные слова (их нельзя переопределять, как стандартные идентификаторы Паскаля).

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

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

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

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

Напомним, что грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A  Bt либо A  t, где A  VN, B  VN, t  VT.

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

Для грамматик этого типа существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):

(1) первый символ исходной цепочки a₁a₂...a_n заменяем нетерминалом A, для которого в грамматике есть правило вывода A  a₁ (другими словами, производим "свертку" терминала a₁ к нетерминалу A)

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал a_i исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B  Aa_i (i = 2, 3,.., n);

Это эквивалентно построению дерева разбора методом "снизу-вверх": на каждом шаге алгоритма строим один из уровней в дереве разбора, "поднимаясь" от листьев к корню.

При работе этого алгоритма возможны следующие ситуации:

(1) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу S. Это означает, что исходная цепочка a₁a₂...a_n  L(G).

(2) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка a₁a₂...a_n  L(G).

(3) на некотором шаге не нашлось нужной свертки, т.е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала a_i исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B  Aa_i. Это означает, что исходная цепочка a₁a₂...a_n  L(G).

(4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки, т.е. в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями, и поэтому непонятно, к какому из них производить свертку. Это говорит о недетерминированности разбора. Анализ этой ситуации будет дан ниже.

Допустим, что разбор на каждом шаге детерминированный.

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

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

Например, для грамматики G = ({a, b, }, {S, A, B, C}, P, S), такая таблица будет выглядеть следующим образом:

Знак "-" ставится в том случае, если для пары "терминал-нетерминал" свертки нет.

Но чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) - неупорядоченного ориентированного помеченного графа, который строится следующим образом:

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

(2) соединяем эти состояния дугами по следующим правилам:

a) для каждого правила грамматики вида W  t соединяем дугой состояния H и W (от H к W) и помечаем дугу символом t;

б) для каждого правила W  Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t;

Диаграмма состояний для грамматики G (см. пример выше):

Алгоритм разбора по диаграмме состояний:

(1) объявляем текущим состояние H;

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом. Состояние, в которое мы при этом попадаем, становится текущим.

При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям, которые возникают при разборе непосредственно по регулярной грамматике):

(1) прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S. Это означает, что исходная цепочка принадлежит L(G).

(2) прочитана вся цепочка; на каждом шаге находилась единственная "нужная" дуга; в результате последнего шага оказались в состоянии, отличном от S. Это означает, что исходная цепочка не принадлежит L(G).

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

(4) на некотором шаге работы алгоритма оказалось, что есть несколько дуг, выходящих из текущего состояния, помеченных очередным анализируемым символом, но ведущих в разные состояния. Это говорит о недетерминированности разбора. Анализ этой ситуации будет приведен ниже.

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

Характеристики

Список файлов книги