73508

Теория языков программирования

Лекция

Информатика, кибернетика и программирование

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

Русский

2014-12-17

114.5 KB

6 чел.

Лекция 1

Введение

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

Однако всем этим схемам присуща общая технологическая цепочка – «лексический анализ → синтаксический анализ → генерация кода → оптимизация кода».

1. Предварительные сведения

1.1. Множества

Атом a.

Множество A.

Атомы являются элементами множества, aA.

Таким образом, множество состоит из элементов (атомов или других множеств): A = {a1, a2, …, an}. Если множество B принадлежит множеству A, то пишут BA.

Атому ничего не принадлежит.

Утверждение #A = n означает, что множество A имеет n элементов. Символ обозначает пустое множество, т.е. множество, в котором нет элементов. При этом атом тоже не имеет элементов, но пустое множество не атом и атом не является пустым множеством.

Один из способов определения множества – определение с помощью предиката. Предикат – это утверждение, состоящее из нескольких переменных и принимающее значение 0 или 1 («ложь» или «истина»). Множество, определяемое с помощью предиката, состоит из тех элементов, для которых предикат истинен.

1.2. Операции и отношения

1.2.1. Операции на множествах

Объединение AB = {x | xA или xB}

(диаграмма)

Пересечение AB = {x | xA и xB}

(диаграмма)

Разность AB = {x | xA и xB}

(диаграмма)

Декартово произведение AB = {(a, b) | aA и bB}

Примеры на  и т.д.

1.2.2. Отношения на множествах

Пусть A и B – множества. Отношением из A в B называется любое подмножество множеств AB.

Если A = B, то отношение задано (определено) на A.

Если R – отношение из A в B и (a, b)R, то пишут aRb.

Пример. Aмножество целых чисел. Отношение L представляет множество {(a, b) | a < b} или a < b (aLb).

Определение. Отношение {(b, a) | (a, b)R} называют обратным к отношению R, т.е. R–1.

Определение. Пусть A – множество, R – отношение на A. Тогда R называют:

1) рефлексивным, если aRa для всех пар из A;

2) симметричным, если aRb влечет bRa для всех a и b из A;

3) транзитивным, если aRb и bRс влекут aRс для a, b, c из A.

Определение. Степень отношения R на A обозначается k и определяется следующим образом:

1) aR1b тогда и только тогда, когда aRb;

2) aRib для i > 1 тогда и только тогда, когда существует такое cA, что aRc и cRi–1b.

Это пример рекурсивного определения:

[aR4baRc1 и c1R3bc1Rc2 и c2R2bc2Rc3 и c3R1b].

Транзитивное замыкание отношения множества R на A (R+) определяется так: аR+b тогда и только тогда, когда aRib для некоторого i  1.

Расшифровка понятия транзитивного замыкания: аR+b, если существует последовательность c1, c2, …, cn, состоящая из 0 или более элементов, принадлежащих A, такая, что aRc1, c1Rc2, …, cn–1Rcn, cnRb. Если n = 0, то аRb.

Рефлексивное и транзитивное замыкание отношения R (R*) на множестве A определяется следующим образом:

 1) aR*a для всех aA;

 2) аR*b, если аR+b;

3) в R* нет ничего другого, кроме того, что содержится в 1) и 2).

Если определить R0, сказав, что aR0b тогда и только тогда, когда a = b, то аR*b тогда и только тогда, когда aRib для некоторого i  0.

Единственное различие между R+ и R* состоит в том, что aR*a истинно для всех aA, но аR+a может быть, а может и не быть истинным.

1.3. Множества цепочек

1.3.1. Цепочки

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

Символ – элемент алфавита (синонимы: буква, знак).

Пример: 01011 – цепочка в бинарном алфавите {0, 1}.

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

Соглашения:

  •  Прописные буквы греческого алфавита – алфавиты.
  •  a, b, c и d – отдельные символы.
  •  t, u, v, w, x, y и z – цепочка символов.

Если цепочку из i символов обозначить aai, тогда a0 = e – пустая цепочка.

Определение. Цепочки в алфавите Σ определяются следующим образом:

1) e – цепочка в Σ;

2) если x цепочка в Σ и aΣ, то xa – цепочка в Σ;

3) y – цепочка в Σ тогда и только тогда, когда она является таковой в силу 1) и 2).

1.3.2. Операции над цепочками

Пусть x, y – цепочки.

  •  Цепочка xy называется сцепленной (конкатенацией). Например, если x = ab и y = cd, то xy = abcd. Для любой цепочки x можно записать, что  = еx = x.
  •  Обращением цепочки x (xR) называется цепочка x, записанная в обратном порядке: x = a1a2an, xR = anan–1a1, eR = e.
  •  Пусть x, y, z – цепочки в некотором алфавите Σ, тогда:

 – x – префикс цепочки xy;

 – y – суффикс цепочки xy;

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

Префикс и суффикс цепочки являются ее подцепочками.

Если x ≠ y, x – префикс (суффикс) цепочки y, то x – собственный префикс (суффикс) цепочки y.

Длина цепочки – это число символов в ней. Если x = a1a2an, то длина цепочки n. Длину цепочки обозначают |x|, например |abc|=3, |e|=0.

1.4. Языки

1.4.1. Определения

Языком в алфавите Σ называют множество цепочек в Σ.

Определение. Через Σ* обозначается множество, содержащее все цепочки в алфавите, включая e.

Пример. Пусть Σ – бинарный алфавит {0,1}, тогда Σ* = {e, 0, 1, 00, 01, 10, 11, 000, …,}.

Каждый язык в алфавите Σ является подмножеством Σ*. Множество всех цепочек в Σ, за исключением e, обозначают Σ+.

Определение. Если язык L таков, что полная цепочка в L не является собственным подмножеством (суффиксом) никакой другой цепочки в L, то L обладает префиксным (суффиксным) свойством.

1.4.2. Операции над языком

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

Определение. Пусть L1 – язык в Σ1, L2 – язык в Σ2. Тогда язык L1L2 называется конкатенацией языков L1 и L2 – это язык {xy | xL1 и yL2}. Итерация языка L обозначается L* и определяется следующим образом:

1) L0 = {e};

2) Ln = LLn–1 для n  1;

3)

Позитивная итерация языка L обозначается L+ – это язык

2. Теория языков программирования

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

Мы определяем язык L как множество цепочек конечной длины в алфавите Σ.

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

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

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

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

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

2.2. Грамматики

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

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

Сердцевину грамматики составляет конечное множество P правил образования, которое описывает процесс порождения цепочек языка. Правило – это просто пара цепочек или элемент множества, иначе говоря, (NΣ)*N(NΣ)*(NΣ)*. Первой компонентой правила является любая цепочка, содержащая хотя бы один нетерминал, а второй компонентой – любая цепочка.

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

Соглашение. Правило (α, β) будем записывать как α→β.

Определение. Грамматикой называется четверка G = (N, Σ, P, S), где

  •  N – конечное множество нетерминальных символов или нетерминалов (иногда называемых вспомогательными символами, синтаксическими переменными или понятиями);
  •  Σ – непересекающееся с N конечное множество терминальных символов (терминалов);
  •  P – конечное подмножество множества (NΣ)*N(NΣ)*(NΣ)*, элемент (α, β) множества P называется правилом (или продукцией) и записывается α→β;
  •  S – выделенный символ из N, называемый начальным (исходным) символом.

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

  S→0A1

  0A→00A1

  Ae

Нетерминальными символами являются A и S, а терминальными – 1 и 0.

Грамматика определяет язык рекурсивным образом. Рекурсивность проявляется в задании особого рода цепочек, называемых вводимыми цепочками грамматики G = (N, Σ, P, S), где

1) S – вводимая цепочка;

2) если αβγ – выводимая цепочка и β→δ содержится в P, то αδγ – тоже выводимая цепочка.

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

Терминология.

Пусть G = (N, Σ, P, S) – грамматика. Введем отношение G на множестве (NΣ)* (φ G Ψ означает Ψ, непосредственно выводимая из φ), которое трактуется следующим образом: если αβγ – цепочка из (NΣ)* и β→δ – правило из P, то αβγ G αδγ.

Транзитивное замыкание отношения G обозначается через G+ и трактуется как Ψ, выводимая из φ нетривиальным образом.

Рефлексивное и транзитивное замыкание отношения G (G*): φG*Ψ – означает Ψ, выводимую из φ.

Далее, если ясно, о какой грамматике идет речь, то индекс G будет опускаться.

Таким образом, L(G) = {w | wΣ*, S*w}. Через k будем обозначать k степень данного отношения. Иначе говоря, α k δ, если существует α0, α1, …, αk, состоящая из k+1 цепочки, для которых α = α0, …, αi–1, αi при  i  k и αk = β. Эта последовательность цепочек называется выводом длины k цепочки β из цепочки α в грамматике G.

Отметим, что α * δ тогда и только тогда, когда α i δ для некоторого i ≥ 0, и α + δ тогда и только тогда, когда α i δ для некоторого i ≥ 1.

Пример. Рассмотрим грамматику G1 из ранее приведенного примера:

S  0A 00A11  0011.

На первом шаге S заменяется на 0A1 в соответствии с правилом S→0A1.

На втором шаге 0A заменяется на 00A1.

На третьем шаге A заменяется на e.

Можно сказать, что

  S 3 0011,

  S + 0011,

  S * 0011,

и что 0011 принадлежит языку L(G1).

Соглашение:

  α→β1

  α→β2

  ……

  α→βn

обозначим α → β1 | β2 | … | βn.

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

(1) a, b, c, d и цифры 0, 1, 2, …, 9 обозначают терминальные символы;

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

(3) U, V, …, Z обозначают либо нетерминалы, либо терминалы;

(4) α, β, …, ω обозначают цепочки, которые могут содержать как терминалы, так и нетерминалы;

(5) u, v, …, z обозначают цепочки, состоящие только из терминалов.

Пример. Пусть G0 = ({E, T, F}, {a, +, *, (, )}, P, E), где P состоит из правил:

  E → E+T | T

  T → T*F | F

  F → (E) | a

Пример вывода в этой грамматике:

  E  E+T

   T+T

   F+T

   a+T

   a+T*F

   a+F*F

   a+a*F

   a+a*a,

т.е. язык G0 представляет собой множество арифметических выражений, построенных из символов a, +, *, ( и ).

2.3. Грамматики с ограничениями

Грамматики можно классифицировать по виду их правил: пусть G = (N, Σ, P, S) – грамматика.

Определение. Грамматика G называется:

1) праволинейной, если каждое правило из P имеет вид AxB или Ax, где A, B  N;

2) контекстно-свободной (или бесконтекстной), если каждое правило из P имеет вид A→α, где AN, α(NΣ)*;

3) контекстно-зависимой (или неукорачивающей), если каждое правило из P имеет вид α→β, |α||β|.

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

Рассмотренный ранее пример (множество арифметических выражений, построенных из символов a, +, * и скобок) является примером контекстно-свободной грамматики.

Заметим, что согласно введенным определениям, каждая праволинейная грамматика – контекстно-свободная грамматика. Контекстно-зависимая грамматика запрещает правило Ae (e-правило).

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

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

2.4. Регулярные множества

2.4.1. Определения

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

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

1) (пустое множество) – регулярное множество в алфавите Σ;

2) {e} – регулярное множество в алфавите Σ;

3) {a} – регулярное множество в алфавите Σ для каждого aΣ;

4) если P и Q – регулярные множества в алфавите Σ, то таковы же и множества:

 а) PQ;

 б) PQ;

 в) P*;

5) ничто другое не является регулярным множеством в алфавите Σ.

Таким образом, множество в алфавите Σ регулярно тогда и только тогда, когда оно либо , либо {e}, либо {a} для некоторого aΣ, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

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

1) – регулярное выражение, обозначающее регулярное множество ;

2) e – регулярное выражение, обозначающее регулярное множество {e};

3) если aΣ, то a – регулярное выражение, обозначающее регулярное множество {a};

4) если p и q – регулярные выражения, обозначающие регулярные множества P и Q, то

 а) (p+q) – регулярное выражение, обозначающее PQ;

 б) pq – регулярное выражение, обозначающее PQ;

 в) p* – регулярное выражение, обозначающее P*;

5) ничто другое не является регулярным выражением.

Принято обозначать p+ для сокращенного обозначения рр*. Расстановка приоритетов:

  •  * (итерация) – наивысший приоритет;
  •  конкатенация;
  •  + (объединение).

Таким образом, 0 + 10* = (0 + (1 (0*))).

Примеры:

1. 01 означает {01};

2. 0* – {0}*;

3. (0+1)* – {0, 1}*;

4. (0+1)* 011 – означает множество всех цепочек, составленных из 0 и 1 и оканчивающихся цепочкой 011;

5. (a+b) (a+b+0+1)* означает множество всех цепочек {0, 1, a, b}*, начинающихся с a или b.

6. (00+11)* ((01+10)(00+11)* (01+10)(00+11)*) означает множество всех цепочек нулей и единиц, содержащих четное число 0 и четное число 1.

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

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

Пусть α, β и γ регулярные выражения, тогда:

1) α + β = β + α

2) * = e

3) α + (β + γ) = (α + β) + γ

4) α(βγ) = (αβ)γ

5) α(β + γ) = αβ + αγ

6) (α + β)γ = αγ + βγ

7) αe = eα = α

8) α = α =

9) α* = α+α*

10) *)* = α*

11) α+α = α

12) α+ = α

2.4.2. Уравнения с регулярными коэффициентами

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

X = aX + b,

где a и b – регулярные выражения. Можно проверить прямой подстановкой, что решением этого уравнения будет a*b:

aa*b + b = (aa* + e)b = a*b,

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

Регулярные множества – множества, определенные регулярными выражениями. Регулярные множества являются языками, порождаемыми праволинейными грамматиками.

Определение. Систему уравнений с регулярными коэффициентами назовем стандартной системой с множеством неизвестных Δ = {X1, X2, …, Xn}, если она имеет вид:

X1 = α10 + α11X1 + α12X2 + … + α1nXn

X2 = α20 + α21X1 + α22X2 + … + α2nXn

………………………………………

Xn = αn0 + αn1X1 + αn2X2 + … + αnnXn

где αij – регулярные выражения в алфавите, не пересекающемся с Δ. Коэффициентами уравнения являются выражения αij.

Если αij = , то в уравнении для Xi нет члена, содержащего Xj. Аналогично, если αij = e, то в уравнении для Xi член, содержащий Xj – это просто Xj. Иными словами, играет роль коэффициента 0, а e – роль коэффициента 1 в обычных системах линейных уравнений.

Алгоритм решения:

Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите Σ и множеством неизвестных Δ = {X1, X2, …, Xn}.

Выход. Решение системы Q.

Метод: Аналог метода решения системы линейных уравнений методом исключения Гаусса.

Шаг 1. Положить i = 1.

Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы записать уравнения для Xi в виде

Xi = αXi + β,

где α – регулярное выражение в алфавите Σ, а β – регулярное выражение вида

β0 + βi+1Xi+1 + … + βnXn,

причем все βi – регулярные выражения в алфавите Σ. Затем в правых частях для уравнений Xi+1, …, Xn заменим Xi регулярным выражением α*β.

Шаг 3. Увеличить i на 1 и вернуться к шагу 2.

Шаг 4. Записать уравнение для Xn в виде Xn = αXn + β, где α и β – регулярные выражения в алфавите Σ. Перейти к шагу 5 (при этом i = n).

Шаг 5. Уравнение для Xi имеет вид Xi = αXi + β, где α и β – регулярные выражения в алфавите Σ. Записать на выходе Xi = α*β, в уравнениях для Xi–1, …, X1 подставляя α*β вместо Xi.

Шаг 6. Если i = 1, остановиться, в противном случае уменьшить i на 1 и вернуться к шагу 5.

Однако следует отметить, что не все уравнения с регулярными коэффициентами обладают единственным решением. Например, если

X = αX + β

является уравнением с регулярными коэффициентами и α означает множество, содержащее пустую цепочку, то X = α*(β + γ) будет решением этого уравнения для любого γ. Таким образом, уравнение имеет бесконечно много решений. В ситуациях такого рода мы будем брать наименьшее решение, которое назовем наименьшей неподвижной точкой. В нашем случае наименьшая неподвижная точка – α*β.


 

А также другие работы, которые могут Вас заинтересовать

69131. Алгоритмічний вибір альтернатив. Вкладеність конструкцій вибору 48 KB
  Під час програмування деяких розгалужень виникає потреба у використанні операторних блоків що розглядатимуться у розділі 3. У цьому ж розділі буде пояснено як орієнтуватися в коді великих програм що містять численну кількість конструкцій вибору та операторних блоків.
69132. Алгоритмічна конструкція повторення. Цикл з передумовою, постумовою, лічильником. Переривання циклу 83.5 KB
  У заголовку циклу зазначається умова завершення циклу а тіло циклу являє собою блок операторів що повторюються. Кожне виконання операторів тіла циклу супроводжується перевіркою умови завершення циклу і називається його ітерацією.
69133. Підпрограми, їх різновиди та способи використання. Процедури та функції користувача. Стандартні процедури та функції 83.5 KB
  Одним із найпростіших і найважливіших застосувань циклічних структур є генерування рекурентних послідовностей. Ефективність розв’язання деяких математичних задач цілком залежить від вибору рекурентної послідовності та способу її обчислення. До таких задач належать, зокрема...
69134. Полевые транзисторы. Их основные параметры и характеристики 44.5 KB
  Различают три основных разновидности транзисторов: Полевой транзистор с управляемым pnпереходом: з затвор с – сток и исток Входная характеристика: Выходная характеристика: МДП-транзисторы металл диэлектрик полупроводник транзисторы с встроенным каналом:...
69135. Транзисторы нового поколения: MOSFET, IGBT, SET 66 KB
  МДП-транзисторы металл диэлектрик полупроводник P=I2 R чем меньше сопротивление канала тем больше потери. Вольтамперные характеристики этих транзисторов близки к характеристикам полевых транзисторов: Входная характеристика...
69136. Тиристоры. Основные параметры и характеристики 41.5 KB
  Включает в себя положительную обратную связь Обратная связь – технологический прием позволяющий передать часть полезного сигнала с выхода устройства на его вход. Различают: положительную обратную связь; отрицательную обратную связь; Положительная обратная связь передает часть...
69137. Датчики и средства индикации. Принцип работы. Основные параметры и характеристики 68 KB
  Основные параметры и характеристики Датчики строятся на базе полупроводниковых приборов и их свойств изменять токи или напряжения в зависимости от их параметров. ТКЕ = 23 мв 0С Такие датчики могут работать от 40 0С до 85 0С G проводимость Простейшие датчики: тока и напряжения.
69138. Аналоговая схемотехника 76 KB
  Аналоговая схемотехника Различают: линейный и нелинейный сигналы. Линейный сигнал синус: Данный сигнал несет информацию по двум параметрам: амплитуда w круговая частота где; От частоты зависит тембр звуки. К импульсным нелинейным сигналам относится...
69139. Усилители 43.5 KB
  Усилитель устройство электронная схема предназначенное для преобразования энергии источника питания в полезный сигнал отдаваемый в нагрузку. УНЧ усилитель низких частот состоит из каскада предварительного усиления и усилителя мощности.