73508

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

Лекция

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

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

Русский

2014-12-17

114.5 KB

7 чел.

Лекция 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 = α*(β + γ) будет решением этого уравнения для любого γ. Таким образом, уравнение имеет бесконечно много решений. В ситуациях такого рода мы будем брать наименьшее решение, которое назовем наименьшей неподвижной точкой. В нашем случае наименьшая неподвижная точка – α*β.


 

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

33347. Общие принципы формирования многоканальных линий связи (МКЛС) 20.02 KB
  Для унификации многоканальных систем связи за основной или стандартный канал принимают канал тональной частоты канал ТЧ обеспечивающий передачу сообщений с эффективно передаваемой полосой частот 300.11 приведена структурная схема наиболее распространенных систем многоканальной связи. Структурная схема систем многоканальной связи Реализация сообщений каждого источника а1t а2t.
33348. Принципы формирования МКЛС с частотным разделением сигналов (ЧРК) 33.83 KB
  Частотное разделение сигналов Функциональная схема простейшей системы многоканальной связи с разделением каналов по частоте представлена на Рис. ФN спектры gK канальных сигналов занимают соответственно полосы частот 1 2 . Проследим основные этапы образования сигналов а также изменение этих сигналов в процессе передачи Рис.
33349. Принципы формирования МКЛС с временным разделением каналов (ВРК) 25.94 KB
  Временное разделение каналов Принцип временного разделения каналов ВРК состоит в том что групповой тракт предоставляется поочередно для передачи сигналов каждого канала многоканальной системы Рис. Принцип временного разделения каналов В зарубежных источниках для обозначения принципа временного разделения каналов используется термин Time Division Multiply ccess TDM. Для этого один из каналов занимают под передачу специальных импульсов синхронизации.
33350. Особенности построения цифровых многоканальных систем передачи. Плезиохронная цифровая иерархия (ПЦИ). Cинхронная цифровая иерархия 72.37 KB
  Особенности построения цифровых систем передачи Основной тенденцией развития телекоммуникаций во всем мире является цифровизация сетей связи предусматривающая построение сети на базе цифровых методов передачи и коммутации. Это объясняется следующими существенными преимуществами цифровых методов передачи перед аналоговыми. Представление информации в цифровой форме позволяет осуществлять регенерацию восстановление этих символов при передаче их по линии связи что резко снижает влияние помех и искажений на качество передачи информации.
33351. Виды и тенденции развития направляющих систем электросвязи (НСЭ) 90.94 KB
  Тенденции развития направляющих систем электросвязи НСЭ Построение сети базируется на направляющих средах передачи рис. В направляющие среды передачи входят вся номенклатура действующих металлических кабелей связи волоконнооптические кабели воздушные линии волноводы линии поверхностной волны высоковольтные линии электропередачи электрофицированные железные дороги радиорелейные линии и спутниковые линии. Направляющими системами передачи НСП имеющими первостепенное значение при построении сетей электросвязи являются электрические...
33352. Металлические кабели и их основные параметры 42.52 KB
  проводников К линиям связи предъявляются следующие основные требования: осуществление связи на практически требуемые расстояния; пригодность для передачи различных видов сообщений как по номенклатуре так и по пропускной способности; защищенность цепей от взаимных влияний и внешних помех а также от физических воздействий атмосферных явлений коррозии и пр. В простейшем случае проводная ЛС физическая цепь образуемая парой металлических проводников. По конструкции и взаимному расположению проводников различают симметричные СК и...
33353. Волоконно-оптические кабели и их основные параметры 13.74 KB
  Многомодовое волокно со ступенчатым изменением показателя преломления диаметр сердечника 40 100 мкм. Многомодово волокно с плавным изменение показателя преломления диаметр сердечника 40 100 мкм. Одномодовое волокно диаметр сердечника 5 15 мкм. В одномодовом кабеле используется центральный проводник очень малого диаметра соизмеримый с длинной волной света от 5 до 10 мкм.
33354. Общие сведения о радиолиниях связи. Основные понятия и определения. Классификация диапазонов радиочастот и радиоволн. Особенности распространения радиоволн метрового и миллиметрового диапазонов 18.21 KB
  Классификация диапазонов радиочастот и радиоволн. Особенности распространения радиоволн метрового и миллиметрового диапазонов. Классификация диапазонов радиочастот и радиоволн. Радиосвязь вид электросвязи осуществляемый с помощью радиоволн.
33355. Обеспечение дальности связи. Радиорелейные, тропосферные и спутниковые линии (системы) передачи (связи). Магистральные кабельные линии (системы) передачи 64.86 KB
  Радиорелейные тропосферные и спутниковые линии системы передачи связи. Магистральные кабельные линии системы передачи. Радиолинии передачи 6. Радиорелейные линии передачи Радиолиния передачи в которой сигналы электросвязи передаются с помощью наземных ретрансляционных станций называется радиорелейной линией передачи.