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


 

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

14134. Формування зображення на екрані ПЕОМ. Створення найпростіших лінійних програм 66.5 KB
  Тема уроку: Формування зображення на екрані ПЕОМ. Створення найпростіших лінійних програм Мета уроку: Дати дитині поняття про режими роботи монітору та принципи виведення зображення на екран в цих режимах.Тип уроку: Лекційний з практичними прикладами. Лекційний мате...
14135. Створення найпростіших лінійних програм 27 KB
  Тема уроку: Створення найпростіших лінійних програм Мета уроку: Дати дитині поняття про режими роботи монітору та принципи виведення зображення на екран в цих режимах.Тип уроку: Практична робота. На початку уроку необхідно нагадати дітям правила поведінки в комп'юте
14136. Розвязування задач з лінійними алгоритмами 61 KB
  Тема уроку: Розвязування задач з лінійними алгоритмами Мета уроку: Навчитися розвязувати прості задачі з лінійними алгоритмами. Тип уроку: Практична робота. На початку уроку необхідно нагадати дітям правила поведінки в компютерному класі та правильної роботи за к
14137. Вказівка розгалуження та її опис мовою програмування. Опис умов 40.5 KB
  Тема уроку: Вказівка розгалуження та її опис мовою програмування. Опис умов. Мета уроку: Дати поняття про структурні оператори вказівку розгалуження повну та скорочену форми та поняття про прості та складені умови.Тип уроку: Лекційний з практичними прикладами. Лекц
14138. Запис алгоритмів з використанням вказівки розгалуження мовою програмування 63.5 KB
  Тема уроку: Запис алгоритмів з використанням вказівки розгалуження мовою програмування. Мета уроку: Навчити складати алгоритми з використанням команди розгалуження та записувати їх мовою програмування.Тип уроку: Розбір задач що потребують для свого розв'язання вказ
14139. Запис алгоритмів з використанням вказівки розгалуження мовою програмування 70.5 KB
  Тема уроку: Запис алгоритмів з використанням вказівки розгалуження мовою програмування. Мета уроку: Навчити створювати математичні моделі задач складати алгоритми з використанням команди розгалуження та записувати їх мовою програмування.Тип уроку: Розбір задач що
14140. Запис алгоритмів з використанням вказівки розгалуження мовою програмування 69.5 KB
  Тема уроку: Запис алгоритмів з використанням вказівки розгалуження мовою програмування. Мета уроку: Навчити складати алгоритми з використанням команди розгалуження та записувати їх мовою програмування.Тип уроку: Розбір більш складних задач що потребують для свого р
14141. Вказівка повторення та її опис мовою блок-схем та мовою програмування 48.5 KB
  Тема уроку: Вказівка повторення та її опис мовою блоксхем та мовою програмування. Мета уроку: Дати поняття про вказівку повторення та її використання при розвязуванні задач про типи циклів та їх оформлення мовою програмування Паскаль та мовою блоксхем. Тип уроку: Лек
14142. Використання циклу з параметром для розвязування задач 66.5 KB
  Тема уроку: Використання циклу з параметром для розвязування задач. Мета уроку: Навчити використовувати цикл з параметром для розвязування типових задач. Тип уроку: Практичний. На початку уроку рекомендується провести письмове опитування можна у вигляді диктанту