Языки и порождающие их грамматики

До начала двадцатого века существовали только разговорные языки. При этом под языком понималось средство общения между людьми. В настоящее время под языком понимается любое средство общения.

Большинство искусственных языком используют при построении предложений формальные, т.е. независимые от смысла, правила. Такие языки называются формальными.

С формальными грамматиками мы сталкиваемся, когда составляем программу для ЭВМ на одном из языков высокого уровня. Другим примером может быть описание объекта, который обрабатывается программой или программной системой: описание карьера или блока ЭВМ, проектируемого цеха или системы управления технологическим процессом.

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

Прежде всего необходимо вести понятие формального языка. Языком называют множество слов в заданном алфавите. Этот алфавит конечен, его принято называть основным или терминальным. Обозначим его как V. Все слова языка должны подчиняться заданному множеству правил. Это множество правил образует грамматику языка. В формаль-ном языке число этих правил конечно и чаще всего небольшое. Этим лавным образом формальный язык отличается от естественного языка,

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

 Таким образом, формальные языки имеют следующие особенности:

· независимость синтаксических правил от смысла;

· строгость правил и отсутствие исключений;

· конечное число правил.

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

Пример 1. Рассмотрим язык, содержащий всевозможные десятичные целые числа. Для него алфавитом будет множество V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -, +}.

Пример 2. Пусть язык содержит всевозможные идентификаторы языка Паскаль. Его алфавитом будет множество V = {0,1, ¼ , 9, a, b, c, ¼, Z}.

Пример 3. Рассмотрим алфавит языка, содержащего всевозможные команды языка Паскаль. В его алфавит будут входить идентификаторы Паскаля, имена меток, специальные слова, типа DO, GOTO, IF, ENDIF и т.п.

Система правил, в соответствии с которыми можно строить «правиль-ные» последовательности «букв», представляет собой синтаксис языка.

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

Вторым аспектом является семантика языка. Слово «семантика» происходит от древнегреческих слов «Sema» – «знак, знамение» и «SemanticoS» — «обозначающий».

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

Проверка семантической правильности фразы языка невозможна в рамках грамматики языка, необходимо связать фразы языка с миром, который этот язык описывает. Рассмотрим в качестве примера фразы русского языка с однородными членами предложения. Формально пред-ложения «шел снег» и «шли студенты» можно объединить в одно пред-ложение «шли два студента и снег». Но с точки зрения семантики пред-ложение неверное, так как слово «шел» имеет разный смысл для снега и человека. 

Третьим аспектом является прагматика языка. Оно произошло от древнегреческих слов «pragma» — «дело, действие» и «pragmateia» — «деятельность».

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

Прагматика является скорее социально-философской дисциплиной, которой мы касаться не будем.

Язык можно задать тремя способами:

1) перечислением всех допустимых слов языка;

2) определением метода распознавания слов языка;

3) указанием способа порождения слов (заданием грамматики языка).

Первый способ на практике не применяется, так как большинство языков содержит бесконечное число слов и перечислить, например, множество всех правильных программ на языке PaScal невозможно. Можно, правда, некоторые простые формальные языки перечислить, прибегая к математическим определениям множеств. Например, запись L={{0, 1}={0n 1n , n≥1}} задает язык, содержащий всевозможные двоичные слова, содержащие одинаковое количество символов 0 и 1. Однако этот способ стоит ближе к третьему способу.

Второй способ предусматривает построение некоторого устройства –распознавателя, который на входе получает цепочку символов, и на выходе выдаёт ответ, принадлежит или нет она заданному языку. (Читая этот текст, мы выступаем в роли распознавателя).

Третий способ предполагает описание грамматики языка.

Символы языка будем далее обозначать строчными буквами латинского алфавита, например, V={a,b,c,d}. Рассмотрим, как в формальных языках задаются правила.

Для описания правил вводится множество вспомогательных символов. Эти символы называют ещё нетерминальными. Они образуют вспомогательный (нетерминальный) алфавит языка, который обозначим как N. Если элементы из N записаны как слова (т.е. состоят из более чем одного символа), то их принято заключать в угловые скобки. Обозначим символы нетерминального языка строчными буквами латинского алфа-вита. Например, N={A,B,C}. Ясно, что множества V и N не пересекаются.

Пример 4. Для языка из примера1 в качестве вспомогательных символов могут быть приняты слова {<число>, <знак>, <цифра>, <модуль>}.

Один из нетерминальных символов принят для обозначения того, что является словом языка. Для примера1 это будет слово <число>, для примера 3 –слово <команда>. этот символ принято называть целью языка или его аксиомой. Обозначим его как S.

Объединим два алфавита V и N и обозначим его как U.

Тогда правила формального языка можно описать в виде
p: j®m, где j и m некоторые слова из алфавита U, причём слово j содержит хотя бы один символ вспомогательного словаря.

Множество правил обозначим как P={p1, p2, ¼pr}.

Символ стрелка трактуется как "заменить".

Пример 5. Для языка из примеров 1 и 4 правила могут иметь вид. p1: <число> ®<знак> <модуль>,
 p2: <знак>®+,
p3: <знак>®-,
p4:<модуль>®<цифра>,
p5:<модуль> ®<цифра><модуль>,
p6:<цифра>®0,
p7:<цифра>®1,
¼,
p14:<цифра>®9.

Для приведённого примера правилу p1 сопоставляется фраза: символ <число> заменить двумя символами - <знак> и <модуль>.

Если слева от стрелки в нескольких правилах стоят одинаковые слова, то эти правила можно объединить. При этом справа слова объединяются через символ | (читается как ИЛИ). Так в последнем примере правила с 6 по 14 можно представить одним правилом

p6: <цифра> ®0 | 1 |2 |3 |4 |5 |6 | 7 | 8 | 9 . (читается как "нетерминал <цифра > заменить на 1, или 2, или 3, или ¼, или 9").

Иногда в формальных грамматиках для описания правил используют символ «::=», который трактуется как « это есть». Такая запись называется нотацией Бекуса-Наура.

Если записать p2 в виде нотации Бекуса-Наура

p2: <число>::<знак ><модуль>

то этой записи будет соответствовать фраза: «<число> это есть <знак> и <модуль>.

Одним из первых языков программирования высокого уровня, описанным формально через нотации Бекуса-Наура (то есть полно и строго), был АЛГОЛ. Язык ФОРТРАН, который появился немного раньше АЛГОЛА, был описан на естественном (английском) языке, и это описание было не строгим.

 

 

5.2. Примеры фрагментов описаний в языках
программирования.

 

Рассмотрим несколько примеров формального описания в языке Си.

Пример 1. Описание унарных операций — — и + +.

G=<Vт,Vн, P,S>;

V={0-9, A-Z, a-Z, + +, — — };

Vн={<выражение>, <имя переменной>, <оператор>, <цифра>, <буква>, <слово>};

S≡<выражение>;

P:

<выражение>®<оператор> <имя переменной>;

<выражение>® <имя переменной> <оператор>;

<имя переменной>::=<буква>;

<имя переменной>::=<буква> <слово>;

<слово>::= <буква> <слово>;

<слово>::=<цифра> <слово>;

<слово>::=<цифра>;

<слово>::=<буква>;

<буква>::=A½B½¼½Z;

<буква>::=a½b½¼½Z;

<цифра>::=0½1½¼½9;

<оператор>::= — —;

<оператор>::= + +.

 

 

Пример 2. Доступ к члену класса или структуры.

G=<Vт,Vн, P,S>;

Vт={0-9, A-Z, a-Z, . , ® };

Vн={<выражение>, <имя переменной>, оператор, <цифра>, <буква>, <слово>};

S≡<выражение>;

P:

<выражение>::= <имя переменной>оператор <имя переменной>;

<имя> ::= <буква>;

<имя> ::= <буква> <слово>;

<слово> ::= <буква> <слово>;

<слово> ::= <цифра> <слово>;

<слово> ::= <цифра>;

<слово> ::= <буква>;

<буква> ::= A½B½¼½Z;

<буква> ::= a½b½¼½Z;

<цифра> ::= 0½1½¼½9;

<оператор> ::= ®;

<оператор> ::= .

 

Пример 3. Для цикла с предусловием while.

G=<Vт,Vн, P,S>;

Vт={while, ( ), 0-9, A-Z, a-Z, +, —, =, >, < , !=, ==, >=, <=};

Vн={<цикл>, <условное_выражение>, <имя переменной>, <оператор>, <цифра>, <буква>, <слово>, <число>, <операнд>, <знак>, <мантисса>};

S≡<цикл>;

P:

<цикл>::= while( <условное_выражение>);

<условное_выражение> ::= <операнд><оператор><операнд>;

<операнд> ::= <число>½ <знак><число>;

<операнд> ::= <имя переменной>;

<число> ::= <цифра>½<цифра><число>;

<число>::= <цифра>.<мантисса>;

<мантисса>::= <цифра><мантисса>;

<мантисса>::= <цифра>;

<имя переменной>::= <буква>;

<имя переменной>::= <буква><слово>;

<слово> ::=<буква>½<буква><слово>½<цифра> ½<цифра><слово>;

<слово> ::=;

<знак> ::= +½—;

<оператор> ::= <½>½> =½<=½!=½==;

<буква> ::= A½B½¼½Z½a½b½¼½Z;

<цифра> ::=0½1½¼½9.

 

Порождающая грамматика

Одна из задач, которая решается в формальных языках, заключается в выявлении множества слов, которые могут быть построены с помощью данной грамматики. Чаще решается обратная задача: для заданного языка построить грамматику, которая порождает этот язык. Такие грамматики называются порождающими. Пример решения такой задачи рассмотрены выше (пример 5). При этом необходимо определить алфавиты V, N, описать множество правил P. Если алфавит V определяется однозначно из вида слов языка, то алфавит N можно определить по-разному. В примере 5 можно не определять понятие <знак>, тогда правила p1, р2 и p3 заменятся двумя правилами

 p1: <число> ::= + <модуль>,
 p2: <число> ::= - <модуль>.

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

Порождающая грамматика G = (V, N, S, P) позволяет выводить (порождать) цепочки языка из некоторой начальной цепочки с помощью заданных правил замены (подстановки). Вывод — это пошаговый процесс, в котором из цепочки, полученной на предыдущем шаге, путем применения правил замены можно получить новую цепочку.

Правило вывода записывают в виде: a ® b.

Цепочку a называют левой частью правила вывода, а цепочку b — правой.

Цепочка a должна содержать вхождение хотя бы одного символа нетерминального алфавита N.

Буквы терминального алфавита называют терминальными символами (терминалами), а нетерминального алфавита — нетерминальными символами (нетерминалами). Любую цепочку в терминальном (нетерминальном) алфавите называют терминальной (нетерминальной) цепочкой.

Пример. Четверка G = ({a,b}, {S, A, B}, S, {S ® aAB, aA ® aB, S ® bb, B ® aB}) задает грамматику с терминальным алфавитом V = {a,b}, нетерминальным алфавитом N = {S, A, B}, аксиомой S и множеством правил вывода P = {S ® aAB, aA ® aB, S ® bBb, B ® aB, B ® bb}.

Цепочка d непосредственно выводима в грамматике G из цепочки g, если существуют такие цепочки s и r и такое правило вывода a ® b из P, что g = sar (т. е. существует вхождение левой части правила вывода в цепочку g), а d = sbr.

Говоря другими словами, непосредственная выводимость подразумевает получение цепочки d из цепочки g за одно применение какого-либо правила вывода.

В вышеприведенном примере цепочка aAB непосредственно выводима из цепочки S, а цепочка aB — из цепочки aA.

Цепочка d выводима в грамматике G из цепочки g (обозначим как g ├ d), если найдутся такие слова a0 = g, a1, a2, …, an = d, что a0├ a1 ├…├ an.

Выводом в грамматике G называют саму последовательность слов a0 = g, a1, a2, …, an = d, таких, что a0 ├ a1 ├ a2 ├ … ├ an..
В вышеприведенном примере цепочка aAaB выводима из цепочки S.

Выводом же будет цепочка слов S ├ aAB ├ aAaB.

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

Язык, порождаемый грамматикой G, — это множество L(G) всех терминальных цепочек, выводимых из аксиомы грамматики:

L(G) = {x: S ├ x, x Î V+}.

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

Для сокращения записи правил с одинаковой левой частью примем следующее соглашение: вместо записи A ® a1, A ® a2, …, A ® an  будем писать A ® a1 ê, a2 ê … ê an.

Пример. Рассмотрим грамматику, моделирующую простейший фрагмент русского языка. Терминальными символами данной грамматики являются некоторые слова русского языка, а нетерминальными — грамматические категории: «предложение», «подлежащее», «сказуемое».

G1 = (V={землекоп, корабль, оркестр, играет, копает, плывет}, N={<предложение>, <подлежащее>, <сказуемое>}, S=<предложение>, P1).

Множество правил вывода P1 имеет вид:

{<предложение> ® <подлежащее> <сказуемое>,

<подлежащее> ® землекоп ê корабль ê оркестр,

<сказуемое> ® играет ê копает ê плывет}.

Первое правило вывода можно толковать следующим образом: «предложение — это подлежащее, за которым следует сказуемое».

Второе правило вывода означает: «подлежащее — это или “землекоп” или “корабль” или “оркестр”».

Третье правило вывода означает: «сказуемое — это или “играет” или “копает” или “плывет”».

Построим какой-нибудь вывод в грамматике G1:

<предложение> ├ <подлежащее> <сказуемое> ├ корабль < сказуемое > ├ корабль играет.

Отметим, что «смысл» (семантика) выводимой цепочки нас не интересует. Так что корабль может играть, оркестр плыть и т. д.

Таким образом, грамматику можно рассматривать как систему определений некоторых «понятий». Выделяется самое общее понятие — аксиома. В данном примере это <предложение>. Оно сводится к менее общим понятиям — нетерминалам. В конечном итоге получаем «конкретные объекты» – терминальные цепочки.

Пример. Рассмотрим грамматику G = (V, N, S, P), у которой

V = {a, b, c, Ú, Ù, Ø, (, )},

N = {I},

S = {I},

P = {I ® (I Ú I)

I ® (I Ù I)

I ® ØI

I ® a

I ® b

I ® c}.

Эта грамматика описывает язык булевых формул с переменными a, b, c и логическими операциями Ú, Ù, Ø. Выведем в данной грамматике формулу

f = (ā Ù b Ú c) Ù (a Ú b).

(I) ® (I Ù I) ® ((I Ú I) Ù I)) ® (((I Ù I) Ú I) Ù I) ® (((I Ù I) Ú I) Ù (I Ú I)) ®

® (((ØI Ù I) Ú I) Ù (I Ú I)) ® (((Øa Ù I) Ú I) Ù (I Ú I)) ® (((Øa Ù b) Ú I) Ù (I Ú I)) ®

® (((Øa Ù b) Ú c) Ù (I Ú I)) ® (((Øa Ù b) Ú c) Ù (a Ú I)) ® (((Øa Ù b) Ú c) Ù (a Ú b)).

Следует отметить, что хотя порождающая грамматика и описывает процесс порождения цепочек языка L(G), но описание это не является алгоритмическим. В грамматике отсутствует одно из основных свойств алгоритма — детерминированность. То есть не фиксируется конкретный порядок применения правил подстановки. Так, в рассмотренном выше примере после цепочки (I Ù I) мы могли перейти не к цепочке ((I Ú I) Ù I)), а к цепочке (I Ù (I Ú I)).

 

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться: