Понятие языка. Формальное определение языка

В общем случае язык — это заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого естественного или искусственного языка является алфавит, определяющий набор допустимых символов языка.
Алфавит — это счетное множество допустимых символов языка. Будем обозначать это множество символом V. Интересно, что согласно формальному определению, алфавит не обязательно должен быть конечным множеством, но реально все существующие языки строятся на основе конечных алфавитов.
Цепочка символов a является цепочкой над алфавитом V: a(V), если в нее входят только символы, принадлежащие множеству символов V. Для любого алфавита V пустая цепочка l может как являться, так и не являться цепочкой l(V). Это условие оговаривается дополнительно.
Если V — некоторый алфавит, то:
V⁺ — множество всех цепочек над алфавитом V без 1;
V^* — множество всех цепочек над алфавитом V, включая 1.
Справедливо равенство: V* = V+И{l}.
Языком L над алфавитом V: L(V) называется некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. Из этого определения следует два вывода: во-первых, множество цепочек языка не обязано быть конечным; во-вторых, хотя каждая цепочка символов, входящая в язык, обязана иметь конечную длину, эта длина может быть сколь угодно большой и формально ничем не ограничена. Все существующие языки подпадают под это определение. Большинство реальных естественных и искусственных языков содержат бесконечное множество цепочек. Также в большинстве языков длина цепочки ничем не ограничена (например, этот длинный текст — пример цепочки символов русского языка). Цепочку символов, принадлежащую заданному языку, часто называют предложением языка, а множество цепочек символов некоторого языка L(V) — множеством предложений этого языка.
Для любого языка L(V) справедливо: L(V)НV*.
Язык L(V) включает в себя язык L'(V): L'(V)НL(V), если "aОL(V): aОL'(V). Множество цепочек языка L'(V) является подмножеством множества цепочек языка L(V) (или эти множества совпадают). Очевидно, что оба языка должны строиться на основе одного и того же алфавита.
Два языка L(V) и L'(V) совпадают (эквивалентны): L'(V) = L(V), если L'(V)Н L(V) и L(V)НL'(V); или, что то же самое: "aОL'(V): aОL(V) и "bОL(V): bОL'(V). Множества допустимых цепочек символов для эквивалентных языков равны.
Два языка L(V) и L'(V) почти эквивалентны: L'(V)@L(V), если L'(V)И{l} = = L(V)И{l}. Множества допустимых цепочек символов почти эквивалентных языков могут различаться только на пустую цепочку символов.

Способы задания языков. Синтаксис и семантика языка

Итак, каждый язык — это множество цепочек символов над некоторым алфавитом. Но кроме алфавита язык предусматривает также правила построения допустимых цепочек, поскольку обычно далеко не все цепочки над заданным алфавитом принадлежат языку. Символы могут объединяться в слова или лексемы — элементарные конструкции языка, на их основе строятся предложения — более сложные конструкции. И те и другие в общем виде являются цепочками символов, но предусматривают некоторые правила построения. Таким образом, необходимо указать эти правила, или, строго говоря, задать язык.
В общем случае язык можно определить тремя способами:
1.
перечислением всех допустимых цепочек языка;
2.
указанием способа порождения цепочек языка (заданием грамматики языка);
3.
определением метода распознавания цепочек языка.
Первый из методов является чисто формальным и на практике не применяется, так как большинство языков содержат бесконечное число допустимых цепочек и перечислить их просто невозможно. Трудно себе представить, чтобы появилась возможность перечислить, например, множество всех правильных текстов на русском языке или всех правильных программ на языке Pascal. Иногда для чисто формальных языков можно перечислить множество входящих в них цепочек, прибегнув к математическим определениям множеств. Однако этот подход уже стоит ближе ко второму способу.
Например, запись L({0,1}) = {0^{n1n, n > 0} задает язык над алфавитом V = {0,1},} содержащий все последовательности с чередующимися символами 0 и 1, начинающиеся с 0 и заканчивающиеся 1. Видно, что пустая цепочка символов в этот язык не входит. Если изменить условие в этом определении с n > 0 на n і 0, то получим почти эквивалентный язык L'({0,1}), содержащий пустую цепочку.
Второй способ предусматривает некоторое описание правил, с помощью которых строятся цепочки языка. Тогда любая цепочка, построенная с помощью этих правил из символов алфавита языка, будет принадлежать заданному языку. Например, с правилами построения цепочек символов русского языка вы долго и упорно знакомились в средней школе.
Третий способ предусматривает построение некоторого логического устройства (распознавателя) — автомата, который на входе получает цепочку символов, а на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку. Например, читая сейчас этот текст, вы в некотором роде выступаете в роли распознавателя (надеюсь, что ответ на вопрос о принадлежности текста русскому языку будет положительным). Говоря о любом языке, можно выделить его синтаксис и семантику. Кроме того, трансляторы имеют дело также с лексическими конструкциями (лексемами), которые задаются лексикой языка. Ниже даны определения всех этих понятий.
Синтаксис языка — это набор правил, определяющий допустимые конструкции языка. Синтаксис определяет “форму языка” — задает набор цепочек символов, которые принадлежат языку. Чаще всего синтаксис языка можно задать в виде строгого набора правил, но полностью это утверждение справедливо только для чисто формальных языков. Даже для большинства языков программирования набор заданных синтаксических конструкций нуждается в дополнительных пояснениях, а синтаксис языков естественного общения вполне соответствует общепринятому мнению о том, что “исключения только подтверждают правило”.
Например, любой окончивший среднюю школу может сказать, что строка “3 + 2” является арифметическим выражением, а “3 2 +” — не является. Правда, не каждый задумается при этом, что он оперирует синтаксисом алгебры.
Семантика языка — это раздел языка, определяющий значение предложений языка. Семантика определяет “содержание языка” — задает смысл для всех допустимых цепочек языка. Семантика для большинства языков определяется неформальными методами (отношения между знаками и тем, что они обозначают, изучаются семиотикой). Чисто формальные языки лишены какого-либо смысла. Возвращаясь к примеру, приведенному выше, и используя семантику алгебры, мы можем сказать, что строка “3 + 2” есть сумма чисел 3 и 2, а также то, что “3 + 2 = 5” — это истинное выражение. Однако изложить любому ученику синтаксис алгебры гораздо проще, чем ее семантику, хотя в случае алгебры семантику как раз можно определить формально.
Лексика — это совокупность слов (словарный запас) языка. Слово или лексическая единица (лексема) языка — это конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Иначе говоря, лексическая единица может содержать только элементарные символы и не может содержать других лексических единиц.
Лексическими единицами (лексемами) русского языка являются слова русского языка, а знаки препинания и пробелы представляют собой разделители, не образующие лексем. Лексическими единицами алгебры являются числа, знаки математических операций, обозначения функций и неизвестных величин. В языках программирования лексическими единицами являются ключевые слова, идентификаторы, константы, метки, знаки операций; в них также существуют и разделители (запятые, скобки, точки с запятой и т. д.).

Цепочки символов. Операции над цепочками символовЦепочкой символов (или строкой) называют произвольную упорядоченную конечную последовательность символов, записанных один за другим. Понятие символа (или буквы) является базовым в теории формальных языков и не нуждается в определении.
Далее цепочки символов будем обозначать греческими буквами: a, b, g.
Цепочка символов — это последовательность, в которую могут входить любые допустимые символы. Строка, которую вы сейчас читаете, является примером цепочки, допустимые символы в которой — строчные и заглавные русские буквы, знаки препинания и символ пробела. Но цепочка — это необязательно некоторая осмысленная последовательность символов. Последовательность “аввв..аагрьь ,..лл” — тоже пример цепочки символов.
Цепочка символов — это упорядоченная последовательность символов. Это значит, что для цепочки символов имеют значение три фактора: состав входящих в цепочку символов, их количество, а также порядок символов в цепочке. Поэтому цепочки “а” и “аа”, а также “аб” и “ба” — это различные цепочки символов. Цепочки символов a и b равны (совпадают), a = b, если они имеют один и тот же состав символов, одно и то же их количество и одинаковый порядок следования символов в цепочке.
Количество символов в цепочке называют длиной цепочки. Длина цепочки символов a обозначается как |a|. Очевидно, что если a = b, то и |a| = |b|.
Основной операцией над цепочками символов является операция конкатенации (объединения или сложения) цепочек.
Конкатенация (сложение, объединение) двух цепочек символов — это дописывание второй цепочки в конец первой. Конкатенация цепочек a и b обозначается как ab. Выполнить конкатенацию цепочек просто: например, если a = аб, а b = вг, то ab = абвг.
ВНИМАНИЕ
Так как в цепочке важен порядок символов, то очевидно, что для операции конкатенации двух цепочек символов важно, в каком порядке записаны цепочки. Иными словами, конкатенация цепочек символов не обладает свойством коммутативности, то есть в общем случае $ a и b такие, что ab № ba (например, для a = аб и b = вг: ab = абвг, а ba = вгаб и ab № ba).
Также очевидно, что конкатенация обладает свойством ассоциативности, то есть (ab)g = a(bg). Любую цепочку символов языка можно представить как конкатенацию составляющих ее частей — разбить цепочку на несколько подцепочек. Такое разбиение можно выполнить несколькими способами произвольным образом. Например, цепочку g = абвг можно представить в виде конкатенации цепочек a = аб и b = вг (g = ab), а можно — в виде конкатенации цепочек u = а и w = бвг (g = uw). Чем длиннее исходная цепочка, тем больше вариантов разбиения ее на составляющие подцепочки.
Если некоторую цепочку символов разбить на составляющие ее подцепочки, а затем заменить одну из подцепочек на любую произвольную цепочку символов, то в результате получится новая цепочка символов. Такое действие называется заменой, или подстановкой, цепочки. Например, возьмем все ту же цепочку g = абвг, разобьем ее на три подцепочки: a = а, w = б и b = вг (g = awb), и выполним подстановку цепочки u = аба вместо подцепочки w. Получим новую цепочку g’ = аабавг (g’ = aub). Любая подстановка выполняется с помощью разбиения исходной цепочки на подцепочки и операции конкатенации.
Можно выделить еще две операции над цепочками:
Обращение цепочки — это запись символов цепочки в обратном порядке. Обращение цепочки a обозначается как a^R. Если a = “абвг”, то a^R = “гвба”. Для операции обращения справедливо следующее равенство " a,b: (ab)R = b^Ra^R.
Итерация (повторение) цепочки n раз, где nОN, n > 0 — это конкатенация цепочки самой с собой n раз. Итерация цепочки a n раз обозначается как aⁿ. Для операции повторения справедливы следующие равенства " a: a^{1 = a}, a^{2 = aa}, a^{3 = aaa}, … и т. д. Итерация цепочки символов определена и для n = 0 — в этом случае результатом итерации будет пустая цепочка символов.
Пустая цепочка символов — это цепочка, не содержащая ни одного символа. Пустую цепочку здесь везде будем обозначать греческой буквой l (в литературе ее иногда обозначают латинской буквой e или греческой e). Для пустой цепочки справедливы следующие равенства:
1.|1| = 0 2."a: la = al = a 3.l^R = l 4."n і 0: lⁿ = 1 5."a: a⁰ = 1

2. Понятие грамматики.

Грамматика — это описание способа построения предложений некоторого языка. Иными словами, грамматика — это математическая система, определяющая язык.
Фактически, определив грамматику языка, мы указываем правила порождения цепочек символов, принадлежащих этому языку. Таким образом, грамматика — это генератор цепочек языка. Она относится ко второму способу определения языков — порождению цепочек символов.
Грамматику языка можно описать различными способами. Например, грамматика русского языка описывается довольно сложным набором правил, которые изучают в начальной школе. Для некоторых языков (в том числе для синтаксических конструкций языков программирования) можно использовать формальное описание грамматики, построенное на основе системы правил (или продукций).
Правило (или продукция) — это упорядоченная пара цепочек символов (a,b). В правилах важен порядок цепочек, поэтому их чаще записывают в виде a ® b (или a ::= b). Такая запись читается как “a порождает b” или “b по определению есть a”.
Грамматика языка программирования содержит правила двух типов: первые (определяющие синтаксические конструкции языка) довольно легко поддаются формальному описанию; вторые (определяющие семантические ограничения языка) обычно излагаются в неформальной форме. Поэтому любое описание (или стандарт) языка программирования обычно состоит из двух частей: вначале формально излагаются правила построения синтаксических конструкций, а потом на естественном языке дается описание семантических правил.

Принцип рекурсии в правилах грамматики Особенность рассмотренных выше формальных грамматик в том, что они позволяют определить бесконечное множество цепочек языка с помощью конечного набора правил (конечно, множество цепочек языка тоже может быть конечным, но даже для простых реальных языков это условие обычно не выполняется). Приведенная выше в примере грамматика для целых десятичных чисел со знаком определяет бесконечное множество целых чисел с помощью 15 правил.
В такой форме записи грамматики возможность пользоваться конечным набором правил достигается за счет рекурсивных правил. Рекурсия в правилах грамматики выражается в том, что один из нетерминальных символов определяется сам через себя. Рекурсия может быть непосредственной (явной) — тогда символ определяется сам через себя в одном правиле, либо косвенной (неявной) — тогда то же самое происходит через цепочку правил.
В рассмотренной выше грамматике G непосредственная рекурсия присутствует в правиле: <чс> ® <чс><цифра>, а в эквивалентной ей грамматике G' — в правиле: T ® TF.
Чтобы рекурсия не была бесконечной, для участвующего в ней нетерминального символа грамматики должны существовать также и другие правила, которые определяют его, минуя его самого, и позволяют избежать бесконечного рекурсивного определения (в противном случае этот символ в грамматике был бы просто не нужен). Такими правилами являются <чс> ® <цифра> — в грамматике G и T ® F — в грамматике G'.
В теории формальных языков более ничего сказать о рекурсии нельзя. Но чтобы полнее понять смысл рекурсии, можно прибегнуть к семантике языка — в рассмотренном выше примере это язык целых десятичных чисел со знаком. Рассмотрим его смысл.
Если попытаться дать определение тому, что же является числом, то начать можно с того, что любая цифра сама по себе есть число. Далее можно заметить, что любые две цифры — это тоже число, затем — три цифры и т. д. Если строить определение числа таким методом, то оно никогда не будет закончено (в математике разрядность числа ничем не ограничена). Однако можно заметить, что каждый раз, порождая новое число, мы просто дописываем цифру справа (поскольку привыкли писать слева направо) к уже написанному ряду цифр. А этот ряд цифр, начиная от одной цифры, тоже в свою очередь является числом. Тогда определение для понятия “число” можно построить таким образом: “число — это любая цифра либо другое число, к которому справа дописана любая цифра”. Именно это и составляет основу правил грамматик G и G' и отражено в правилах <чс> ® <цифра> | <чс><цифра> и T ® F | TF (вторая строка правил). Другие правила в этих грамматиках позволяют добавить к числу знак (первая строка правил) и дают определение понятию “цифра” (третья строка правил). Они элементарны и не требуют пояснений.
Принцип рекурсии (иногда его называют “принцип итерации”, что не меняет сути) — важное понятие в представлении о формальных грамматиках. Так или иначе, явно или неявно рекурсия всегда присутствует в грамматиках любых реальных языков программирования. Именно она позволяет строить бесконечное множество цепочек языка, и говорить об их порождении невозможно без понимания принципа рекурсии. Как правило, в грамматике реального языка программирования содержится не одно, а целое множество правил, построенных с помощью рекурсии.

Не нашли, что искали? Воспользуйтесь поиском по сайту: