Развитие формальных грамматик. Примеры построения грамматик
При создании формальных языков необходимо выбрать множество базовых знаков для формирования лексем, указать множество синтаксических правил написания выражений и предложений, согласовать множество семантических правил для интерпретации их значений. Подобно естественным языкам, грамматики формальных языков организованы в виде иерархии синтаксических конструкций, формирующих лексемы и последовательности лексем - выражения и предложения. Элементы нижнего уровня образованы знаками базового набора и формируют слова или лексемы формального языка. Элементы следующих уровней, образованные цепочками лексем и/или синтаксических переменных, формируют выражения формального языка. Элементы самого верхнего уровня, образованные цепочками выражений, формируют предложение. Так как языки программирования являются формальными языками, то все последующие обсуждения будем сопровождать примерами на этих языках.
Множество базовых знаков, используемых в языках программирования, опирается на 26 строчных и прописных букв латинского алфавита, на 10 арабских цифр и на 26 специальных символов, имеющих фиксированное значение (знаки препинания, арифметических действий, сравнения и т.п.).
Множество синтаксических правил, по которым строят синтаксически правильные выражения и предложения программы, определяет содержание грамматики языка программирования.
Для формирования модели грамматики обозначим элементарные лексические единицы языка строчными буквами латинского алфавита. Знаки этого множества называют терминальными (от лат. terminus - предел,конец). Множество терминальных символов обозначим знаком V T . Это множество называют также словарем или лексикой языка. Множество V T - счетно, но не конечно, т.к. всегда можно добавить новую лексему для какой-либо синтаксической переменной.
Элементарными лексическими единицами большинства языков программирования являются:
значения идентификаторов констант, переменных, программ, процедур, функций и т.п. в виде последовательности букв латинского алфавита и цифр, начинающейся обязательно с буквы;
<служебные слова>: := AND ½ ARRAY ½ BEGIN ½ CASE ½ CONS ½ DIV ½ DOWNTO ½ DO ½ ELSЕ ½ END ½ FILE ½ FOR ½ FUNCTION ½ GOTO ½ IF ½ IN ½ LABEL ½ MOD ½ NIL ½ NOT ½ OF ½ OR ½ PACKED ½ PROCEDURE ½ PROGRAM ½ RECORD ½ REPEAT ½ SET½ THEN ½ TO ½ TYPE ½ UNTIL ½ VAR ½ WHILE ½ WITH ;
<специальные символы>: := + ½ - ½ * ½ / ½ = ½ < ½ > ½ <= ½ >= ½ [ ½ ] ½ (½) ½ _ ½:= ½ " ½ " ½ . ½ , ½: ½ ; ½ ¹ ½# ½$ ;
десятичные числа без знака.
В выражениях и предложениях формального языка, cодержащих лексемы и синтаксические переменные, лексемы всегда заключены в кавычки. Например, "BEGIN", "NOT", AND" и др.
Для обозначения синтаксических переменных введем прописные буквы латинского алфавита. Знаки этого множества называют нетерминальными. Обозначим множество нетерминальных символов знаком V N .
Множество V N - счетно и конечно.
Элементарными синтаксическими переменными для языка программирования являются:
<блок > :: = <блок-операторов>½<блок-процедуры>½<блок-функции>½...;
<заголовок > ::= <заголовок-программы>½<заголовок-процедуры>½
<заголовок-функции>½...;
<идентификатор > ::= <идентификатор-программы>½<идентификатор-
переменной>½...;
<оператор > ::= <оператор-присваивания>½<оператор-ЕСЛИ>...;
<операция > ::= <операция-сложения>½<операция-умножения>
½<операция-отношения>½...;
и другие синтаксические переменные.
В языке Паскаль всего около 240 синтаксических переменных.
В выражениях и предложениях формального языка, содержащих синтаксические переменные, их заключают в угловые скобки. Например, "PROGRAM" <идентификатор-программы> ";" "BEGIN" <блок-операторов> "END" и др.
Объединение символов двух множеств V T и V N представляет множество символов формального языка, т.е.
V = V T ÈV N . (2)
Цепочки символов формального языка могут содержать различное количество терминальных и/или нетерминальных символов. Поэтому множество правильных цепочек может быть записано так:
Если каждый элемент множества V* обозначить строчной буквой греческого алфавита, то множество V* можно описать перечислением его элементов:
V* = { a ; b ; g ;... } (4)
Например,
a:= "PROGRAM"<идентификатор-программы>";"<блок>".";
b:= "CONST" <определение-константы> "; " ;
g:= "(" <идентификатор> { " , " <идентификатор> } ") " ;
где знак ":=" означает: "...присвоить значение...". Цепочка a ÎV* содержит пять символов множества V, цепочка b ÎV* - три символа и цепочка g Î V* - не менее трех символов, т.к. в языках программирования знак "{ .. }" означает многократное повторение выражения, заключенного в фигурные скобки, включая нуль раз.
Конструкция программы на любом языке программирования состоит, как правило, из двух частей: заголовка - <заголовок-программы> и тела программы - <блок>. В заголовке программы, начинающемся служебным словом "PROGRAM", ей присваивается имя (идентификатор), вслед за которым в круглых скобках задается перечень идентификаторов тех файлов, через которые программа взаимодействует с внешним миром. В теле программы должны следовать в определенном порядке разделы меток, констант, типов, переменных, процедур, функций и операторов. Так как разделы, предшествующие разделу операторов, носят описательный характер, то каждый из них может быть пустой цепочкой, а раздел операторов является основным и должен присутствовать в любой программе. Поэтому в последующих объяснениях <блок> содержит только описание операторов, т.е. исполняет функции <блока-операторов>.
Синтаксические правила формальной грамматики можно рассматривать как элементарные операторы подстановки, которые, будучи примененными в определенной последовательности к исходной цепочке терминальных и/или нетерминальных символов, порождают правильные цепочки этих же символов. Поэтому эти правила часто называют правилами подстановки или продукциями.
Продукцию или правило подстановки записывают так:
где a - левая часть правила,
b - правая часть правила.
Если правил несколько,то их необходимо индексировать:
p i: a i::= b i , где i = 1;2;3;... (6)
Левая часть правила не может быть пустой цепочкой и всегда содержит один или несколько нетерминальных символов, т.е.
a ÎV* \ e, где e - пустая цепочка. (7)
Правая часть правила может содержать пустые цепочки и не содержать нетерминальных символов, т.е.
b ÎV * или b ÎV*\ V N . (8)
Пример 3 . Пусть даны несколько правил языка программирования Паскаль:
<программа> ::= <заголовок-программы> " ; "<блок>" . ";
<заголовок-программы> ::= "PROGRAM"<идентификатор-программы>;
<блок> ::= <раздел-операторов> | ...;
<раздел-операторов> ::= "BEGIN" <оператор> " END" ;
<оператор> ::= <оператор-присваивания> |...;
<оператор-присваивания> ::= <переменная> " := " <выражение>;
<выражение> ::= <терм> <операция-сложения> <терм> ;
<терм> ::= <множитель> <операция-умножения> <множитель>;
<множитель> ::= <переменная> ;
<переменная> ::= <идентификатор-переменной> ;
<операция-сложения> ::= " + " | " - " | "OR";
<операция-умножения> ::= " x " | " / " | "DIV" | "MOD" |"AND".
Синтаксической переменной <идентификатор-программы> присвоим какое-либо значение (например, "ALGEBRA"), т.е.
<идентификатор-программы>::= "ALGEBRA".
Cинтаксической переменной <идентификатор-переменной> также присвоим какое-либо значение, начинающееся с буквы (например," i "), т.е.
<идентификатор-переменной> ::= " i ".
Последовательность использования правил подстановки в процессе формирования цепочки терминальных и/или нетерминальных символов называют выводом. Поэтому эти же правила часто называют правилами вывода. Для указания процесса вывода используют знак "=>".
Выводы бывают левосторонние и правосторонние. При левостороннем выводе продукцию применяют к самому левому нетерминальному символу цепочки, а при правостороннем - к самому правому.
Пример 4 . а) Для начального символа <программа> (пример 3) исполнить левосторонний вывод:
<программа> => <заголовок-программы> ";" <блок> "." => "PROGRAM" <идентификатор-программы> ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <раздел-операторов> "." => <оператор> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <оператор-присваивания> "END" "." => ."PROGRAM" "ALGEBRA" ";" "BEGIN" <переменная> ":= " <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <идентификатор-переменной> ":=" <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" " i " ":=" <выражение> "END" "." => ..
b) Для начального символа <программа> (пример 3) исполнить правосторонний вывод:
<программа> => <заголовок-программы> ";" <блок> "." => <заголовок-программы> ";" <раздел-операторов> "." => <заголовок-программы> ";" "BEGIN" <оператор> "END" "." => <заголовок-программы> ";" "BEGIN" <оператор-присваивания> "END" "." => <заголовок-программы> ";" "BEGIN" <переменная> ":=" <выражение> "END" "." => ...
Cинтаксической переменной <выражение> может быть любое арифметическое, алгебраическое или логическое выражение. Так как содержание этого выражения не определено, то оба вывода остановились на этой синтаксической переменной. Остальные члены предложения <программа> представлены элементарными лексическими единицами текста программы.,
Пример 5 . Для cинтаксической переменной <выражение> (пример 3) выполнить левосторонний вывод:
<выражение> => <терм><операция-сложения><терм>=> <множитель> <операция-умножения><множитель><операция-сложения><терм> => <переменная><операция-умножения><множитель><операция-сложения> <терм>=> <идентификатор-переменной><операция-умножения> <множитель> <операция-сложения><терм> => "i" <операция-умножения> <множитель><операция-сложения><терм> => "i" "x" <множитель><операция-сложения><терм> => "i" "x" <переменная><операция-сложения><терм> => "i" "x" <идентификатор-переменной><операция-сложения><терм> => "i" "x" "i" <операция-сложения><терм> => "i" "x" "i" "+" <терм> => "i" "x" "i" "+" <множитель><операция-умножения><множитель> => "i" "x" "i" "+" <переменная> <операция-умножения><множитель> => "i" "x" "i" "+" <идентификатор-переменной><операция-умножения> <множитель> => "i" "x" "i" "+" "i" <операция-умножения> <множитель> => "i" "x" "i" "+" "i" "x" <множитель> "i" "x" "i" "+" "i" "x" <переменная> => "i" "x" "i" "+" "i" "x"<идентификатор-переменной> => "i" "x" "i" "+" "i" "x" "I".
Имя начальной синтаксической переменной языка, для которой дано множество правил вывода называют начальным символом и обозначают буквой J. Роль начального символа может исполнять любая синтаксическая переменная. Для текста программы начальной синтаксической переменной является <программа>. Для части текста программы - выражения - начальной синтаксической переменной является <выражение>.
Итак, модель формальной грамматики может быть описана совокупностью четырех основных компонент:
G = á V T ; V N ;J ; P ñ , (9)
где V T = { a;b;c;... } - терминальные символы;
V N = { A;B;C;...} - нетерминальные символы;
JÎ Vn - начальный символ;
P = { p i |i = 1; 2; 3; ... } - синтаксические правила.
Множество правильных цепочек терминальных символов представляет выражения и предложения формального языка данной формальной грамматики L(G) :
L (G) = { a , b , g ,...½ a , b , g Î V *\ VN }. (10)
Текст программы, ограниченный разделителем ".", называют предложением, а часть текста, ограниченную разделителем ";" , - выражением.
Если для начального символа дана цепочка терминальных и/или нетерминальных символов, то формальная грамматика позволяет установить, является ли эта цепочка правильной, и, в случае положительного ответа, выяснить структуру этой цепочки. Такая грамматика называется распознающей. Например, синтаксический анализатор компилятора проверяет текст исходной программы и, в случае положительного ответа, транслирует его на язык вычислительной машины. Для такого анализатора должны быть разработаны правила разбора текста программы.
Если для начального символа не дана цепочка терминальных и/или нетерминальных символов или дана ее часть, то формальная грамматика оказывает помощь в построении синтаксически правильной цепочки терминальных символов с указанием ее состава и структуры. Такая грамматика называется порождающей.
Грамматика формальная
Формальная грамматика или просто грамматика в теории формальных языков - способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавитa . Различают порождающие и распознающие (или аналитические ) грамматики - первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет.
Термины
Порождающие грамматики
Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.
Итак, грамматика определяется следующими характеристиками:
Вывод
Выводом называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены некоторой подстроки по одному из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.
Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.
Типы грамматик
Терминальный алфавит:
Σ ={"0","1","2","3","4","5","6","7","8","9","+","-","*","/","(",")"}.Нетерминальный алфавит:
{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }
1. ФОРМУЛА ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА ЧИСЛО (формула есть число) 3. ФОРМУЛА (ФОРМУЛА) (формула есть формула в скобках) 4. ЗНАК + | - | * | / (знак есть плюс или минус или умножить или разделить) 5. ЧИСЛО ЦИФРА (число есть цифра) 6. ЧИСЛО ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1 или... 9)
Начальный нетерминал:
ФОРМУЛА
Вывод :
Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.
ФОРМУЛА (ФОРМУЛА) (ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + 5 ) (ФОРМУЛА + 5) (ЧИСЛО + 5) (ЧИСЛО + 5) (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) (1 ЦИФРА + 5) (1 ЦИФРА + 5) (1 2 + 5)Аналитические грамматики
Порождающие грамматики - не единственный вид грамматик, однако наиболее распространенный в приложениях к программированию. В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом , а любая контекстно-свободная грамматика - с помощью автомата со стековой памятью . Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.
Источники
- Гладкий А. В. Формальные грамматики и языки. - М.: Наука, 1973.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений . - Новосибирск: НГУ. - 1995. - 112 с.
- Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник / Под ред. А.А.Ляпунова и О.Б.Лупанова. - М.: Мир, 1965.
Wikimedia Foundation . 2010 .
Смотреть что такое "Грамматика формальная" в других словарях:
- (в лингвистике) логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным… … Большая советская энциклопедия
грамматика формальная - В лингвистике: логическая система, или исчисление, задающая некоторое множество (правильных) цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого алфавитом или основным (терминальным)… … Словарь лингвистических терминов Т.В. Жеребило
Грамматика формальная - В лингвистике: логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным (терминальным)… … Общее языкознание. Социолингвистика: Словарь-справочник
Грамматика (от греч. γράμμα «запись»), как наука, есть раздел языкознания, изучающий грамматический строй языка, закономерности построения правильных осмысленных речевых отрезков на этом языке (словоформ, синтагм, предложений, текстов). Эти … Википедия
Есть раздел языкознания, изучающий грамматический строй языка, закономерности построения правильных осмысленных речевых отрезков на этом языке (словоформ, синтагм, предложений, текстов). Эти закономерности грамматика формулирует в виде общих… … Википедия
ФОРМАЛЬНАЯ ГРАММАТИКА. Грамматика, последовательно проводящая принцип изучения только форм языка и исключающая из своего состава все явления, не обозначенные формами языка. Ф. Г. противополагается т. н. логической (название неточное) грамматике,… … Литературная энциклопедия
Генеративная лингвистика … Википедия
У этого термина существуют и другие значения, см. Грамматика (значения). Грамматика (др. греч. γραμματική от γράμμα «буква») как наука является разделом языкознания, который изучает грамматический строй языка, закономерности построения… … Википедия
См. грамматика формальная (в статье грамматика) … Словарь лингвистических терминов
В общем случае язык представляет собой бесконечное множество, а бесконеч- ные объекты даже задать трудно: их невозможно задать простым перечислением эле- ментов. Любой конечный механизм задания языка называется грамматикой.
Формальный язык представляет собой множество цепочек в некотором конеч- ном алфавите. К формальным языкам можно отнести искусственные языки для обще- ния человека с машиной – языки программирования.
Для задания описания формального языка необходимо, во-первых, указать ал- фавит, т. е. совокупность объектов, называемых символами (или буквами), каждый из которых можно воспроизводить в неограниченном количестве экземпляров (подобно обычным печатным буквам или цифрам), и, во-вторых, задать формальную граммати- ку языка, т. е. перечислить правила, по которым из символов строятся их последова- тельности, принадлежащие определяемому языку, – правильные цепочки.
Правила формальной грамматики можно рассматривать как продукции (прави- ла вывода), то есть элементарные операции, которые, будучи применены в опреде- ленной последовательности к исходной цепочке (аксиоме), порождают лишь пра- вильные цепочки. Сама последовательность правил, использованных в процессе по- рождения некоторой цепочки, является ее выводом. Определенный таким образом язык представляет собой формальную систему.
По способу задания правильных цепочек формальные грамматики разделяются на порождающие и распознающие. К порождающим относятся грамматики языка L,
по которым можно построить любую «правильную» цепочку с указанием ее структу- ры и нельзя построить ни одной неправильной цепочки. Распознающая грамматика языка L – это грамматика, позволяющая установить, правильна ли произвольно вы- бранная цепочка и, если она правильна, то выяснить ее строение. Распознающая грам- матика задает критерий принадлежности произвольной цепочки данному языку.
Формальные грамматики широко применяются в лингвистике и программиро-
вании в связи с изучением естественных языков и языков программирования.
Автоматные и лингвистические модели строятся на базе теории формальных грамматик, основы которой были заложены в работах Н. Хомского. Основными объ- ектами, с которыми имеет дело эта теория, являются символы, представляющие собой базовые элементы какого-либо непустого множества А любой природы, а также це- почки, построенные из этих элементов. Множество А называют также алфавитом.
Символы будем обозначать строчными буквами латинского алфавита, а цепоч- ки – в виде ffghhh, которые будем считать ориентированными слева направо. Цепочки будем обозначать также специальными символами – прописными буквами латинско- го алфавита или греческими буквами, например: = ffg, В = аbbа. Введем в рассмот- рение пустую цепочку , не содержащую ни одного символа.
Длиной цепочки будем называть число символов, входящих в эту цепочку.
Длина цепочки обозначается следующим образом:
| | = | ffg | = 3;
| В | = | аbbа| = 4;
Конкатенацией двух цепочек Х и Y называется такая цепочка Z, которая полу- чается непосредственным слиянием цепочки Х, стоящей слева, и цепочки Y, стоящей справа. Например, если X = ffg, Y = ghh, то конкатенация Х и Y – это цепочка Z = ffgghh. Обозначим операцию конкатенации символом о. Свойства этой операции
можно записать следующим образом:
1) свойство замкнутости:
о: А* × А* → А*;
2) свойство ассоциативности:
(∀Х ∈ А*, Y ∈ A*, Z ∈ A*) [(X o Y) o Z = X o (Y o Z)],
где через А* обозначено множество всех возможных цепочек (разумеется, бес- конечное), составленных из конечного множества А базовых элементов (символов) словаря, включая пустую цепочку ; символ х обозначает операцию декартова произ- ведения двух множеств; а X, Y, Z – произвольные цепочки, принадлежащие А*.
Рассмотрим пару (А*, 0). С учетом перечисленных свойств операции о эта пара представляет собой полугруппу с единичным элементом или моноид. Полугруппой в алгебре называют только множество (в данном случае А*), снабженное всюду опре- деленной ассоциативной операцией.
Цепочка может принадлежать или не принадлежать языку L. Любое множество цепочек L ≤ А* (где А* – моноид), называется формальным языком, если это мно- жество цепочек определено на алфавите А.
Пример 1. Пусть А – множество букв русского алфавита. Тогда множество це- почек, составленных из пяти букв, представляет собой формальный язык L1. Другой пример языка, определенного на том же алфавите – множество L2 пятибуквенных
слов русского языка, которые можно разыскать в орфографическом словаре. Оче-
видно L2 ⊂ L1, так как многие цепочки языка L1 не являются русскими словами.
Пусть В и С – некоторые подмножества множества А*.
Произведением множеств В и С называется множество D цепочек, являю-
щихся конкатенацией цепочек из В и С, т. е.
D = { X o Y | X ∈ B, Y ∈ C}.
Обозначается произведение следующим образом: D = ВC.
Рассмотрим алфавит А. Обозначим множество, состоящее из , через А0. Опре-
делим степень алфавита как Аn = An-1 A для каждого n ≥ 1.
Нетрудно показать, что множество всех возможных цепочек алфавита
Такое множество называют итерацией алфавита А. Усеченной итерацией ал-
фавита А называют
Если X и Y – цепочки множества А*, то цепочку Х называют подцепочкой це-
почки Y, когда существуют такие цепочки U и V из А*, что
При этом, если U – пустая цепочка, то подцепочку Х называют головой цепоч-
ки Y, а если V – пустая цепочка, то Х называют хвостом цепочки Y.
Конкатенация двух цепочек X и Y обозначается ХоY или XY. Рассмотрим пары цепочек (P1, Q1), (P2, Q2), ..., (Pn, Qn) из А* х А*. Соотношениями Туэ будем называть правила, согласно которым любой це-
почке X = U Pi V из множества А* будет ставиться в соответствие цепочка Y = U Qi V, из того же множества А* (i = 1, 2, ..., n) и наоборот. Эти соотношения приводят к так называемым ассоциативным исчислениям.
Если цепочка Y получается из цепочки Х однократным применением одного соотношения Туэ (т. е. заменой подцепочки Pi на подцепочку Qi), будем говорить, что Х и Y являются смежными цепочками.
Цепочка Хn соотносима с цепочкой Х0, если существует последовательность цепочек
Х0, Х1, ..., Хn ,
такая, что Х i-1 и Хi являются смежными цепочками.
Пример 2. Пусть А – множество букв русского алфавита, на котором опреде-
лим соотношение Туэ, заключающееся в праве замены любой одной буквы слова на любую другую. Тогда в последовательности цепочек МУКА, МУЗА, ЛУЗА, ЛОЗА, ПОЗА, ПОРА, ПОРТ, ТОРТ, две любые соседние цепочки являются смежными, а це- почки МУКА и ТОРТ являются соотносимыми в смысле заданных соотношений.
Введение соотношений Туэ позволяет выделить среди множества языков опре- деленные их классы, которые используются при построении автоматно- лингвистических моделей самого различного типа.
Соотношения Туэ являются двусторонними, если цепочка Х является смежной по отношению к цепочке Y, и наоборот, цепочка Y является смежной по отношению к
цепочке Х. Более интересными, с точки зрения теории формальных грамматик, явля-
ются соотношения, в которых введено направление.
В этом случае их называют полусоотношениями Туэ или продукциями и обо-
значают следующим образом:
(Р1 → Q1), (P2 →Q2), ..., (Pn → Qn).
В том случае, когда имеется набор продукций, говорят, что цепочка Y непо-
средственно порождается из цепочки Х, и обозначается как Х ⇒ Y, если существуют такие цепочки U и V, что
X = U Pi V, Y = U Qi V,
а (Рi → Qi) – продукция из данного набора.
Говорят также, что Х порождает Y.
Если существует последовательность цепочек Х0, Х1, ..., Хn такая, что для каж-
дого i = 1, 2, ..., n
Х i-1 ⇒ X i ,
то говорят, что Хn порождается из Х0 (Х0 порождает Хn), и обозначают как Х0 ⇒ * Xn. .
Грамматики Хомского соответствуют формальным комбинаторным схемам,
являющимся полусистемами Туэ, в основу которых положены полусоотношения Туэ
ВВЕДЕНИЕ………… ………………………………….…………….4
Глава 1. ЯЗЫКИ И ГРАММАТИКИ. ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ И КЛАССИФИКАЦИЯ ………………………………………………………………………………6
1.1. Понятие грамматики языка. Обозначения……………………………………………7
1.2. Классификация грамматик по Хомскому………………………..…………………13
1.3. Техника построения КС- и А- грамматик…………………………………………..16
1.4. Синтаксические деревья вывода в КС-грамматиках. Представление
А-грамматик в виде графа состояний. Неоднозначность грамматик……………..19
1.5. Синтаксический анализ А-языков…………………………………………………..23
Упражнения……………………………………………………………………………….29
Глава 2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ .……………………………….….…………32
Глава 3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ …………….35
3.1. Автоматные грамматики и конечные автоматы…………………………………….35
3.2.Эквивалентность недетерминированных и детерминированных А-грамматик…… 36
Упражнения………………………………………………………………………………… 41
Глава 4. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КОНТЕКСТНО-СВОБОДНЫХ
И АВТОМАТНЫХ ГРАММАТИК ………………………………………………..….42
4.2. Исключение тупиковых правил из грамматик………………………………………46
4.3. Обобщенные КС-грамматики и приведение грамматик к удлиняющей форме…….48
4.4. Устранение левой рекурсии и левая факторизация………………………………..…52
Упражнения………………………………………………………………………………….53
Глава 5. СВОЙСТВА АВТОМАТНЫХ И КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ …55
5.1. Общий вид цепочек А-языков и КС-языков………………………………………..55
5.2. Операции над языками………………………………………………………………….59
5.2.1. Операции над КС-языками………………………………………………………59
5.2.2. Операции над А-языками………………………………………………………62
5.2.3. Операции над К-языками………………………………………………………66
5.3. Выводы для практики…………….………………………………………………….67
5.4. Неоднозначность КС-грамматик и языков…………………………………………71
Упражнения…………………………………………………………………………....…74
Глава 6. СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-языков ……………………………...……...75
6.1. Методы анализа КС-языков. Грамматики предшествования………………….…75
6.2. Грамматики предшествования Вирта……………………………………………...77
Грамматики предшествования Флойда…….……………………………………...79
Функции предшествования…………………………………………………………81
Упражнения………………………………………………………………………………84
Глава 7. ВВЕДЕНИЕ В СЕМАНТИКУ ……………………………………………………….85
7.1. Польская инверсная запись….……………………………………………………...85
7.2. Интерпретация ПОЛИЗа……………………………….………………………..….87
7.3. Генерирование команд по ПОЛИЗу………………………………….…………....89
7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ………..……….91
7.5. Атрибутные грамматики……………………………………………………………97
Упражнения……………………………………………………………………………..100
Глава 8. ОСНОВНЫЕ ФАЗЫ КОМПИЛЯЦИИ ……………………………………...……100
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ …………………………………………………………………………………105
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ……………………………………………………….…….…115
Введение
Лингвистика - наука о языке. Математическая лингвистика - наука, занимающаяся формальными методами построения и изучения языков.
Теория формальных грамматик - раздел математической лингвистики, включающий способы описания формальных грамматик языков, построение методов и алгоритмов анализа принадлежности цепочек языку, а также алгоритмов перевода (трансляции) алгоритмических языков на язык машины.
Импульсом к созданию и совершенствованию этой теории послужило развитие вычислительной техники и, как следствие, необходимость в средствах общения человека с ЭВМ. Во всех применениях ЭВМ должна понимать какой-либо язык, на котором пользователь может сообщить ей алгоритмы решения задач и исходные данные. Каждая ЭВМ имеет собственный язык машинных команд, представляемых в двоичном коде и отражающих отдельные операции процессора. На первых этапах развития вычислительной техники программисты общались с ЭВМ именно на этом примитивном языке, но человек не способен хорошо мыслить в категориях цифрового языка машины. Автоматизация программирования привела к созданию вначале языков ассемблера, а затем и алгоритмических языков высокого уровня, перевод с которых на родной машинный язык был поручен самой ЭВМ. Программы такого перевода называются трансляторами .
С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) - специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс: пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть, необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать, как создаются языки и их программная поддержка.
Чтобы объяснить язык машине, необходимо четко представлять, как он устроен и как мы его понимаем. Задумавшись над этим, мы увидим, что не знаем, как мы понимаем наш родной язык. Процесс этого понимания подсознателен, интуитивен. Но чтобы создать транслятор, необходимо иметь алгоритм перевода текста в те действия, которые этот текст требует выполнить, а это, в свою очередь, требует формализации языка . Задачи формализации языка и решает математическая лингвистика. Естественные языки слишком сложны, и формализовать их полностью пока не удается. Алгоритмические языки, напротив, уже создаются в расчете на формализацию. Теория формальных языков - это наиболее развитая ветвь математической лингвистики, представляющая по сути методику объяснения языка машине. Прежде чем рассматривать определения, модели и методы этой теории, рассмотрим некоторые понятия на примерах из естественных языков.
Язык – это множество предложений (фраз), построенных по определенным правилам.
Грамматика - свод правил, определяющих принадлежность фразы языку.
Любой язык должен удовлетворять свойствам разрешимости и однозначности.
Язык разрешим , если за конечное время можно определить, что фраза или предложение принадлежит языку. Язык однозначен , если любая фраза понимается единственным образом.
Основными разделами грамматики являются синтаксис и семантика.
Синтаксис - свод правил, определяющих правильность построения предложений языка.
Семантика - свод правил, определяющих семантическую или смысловую правильность предложений языка.
Предложение может быть синтаксически верным и семантически неверным.
Синтаксис обычно упрощается тем, что не все фразы языка обязаны иметь смысл. Зачастую трудно понять смысл футуристов или речь некоторых политиков. В этой связи интересен пример академика Л.В.Щербы: «Глокая куздра штеко будланула бокра и кудрячит бокренка». Это фраза на русском языке, так как её можно разобрать по членам предложения, но смысл её неясен.
Синтаксический анализ фразы можно записать в виде дерева грамматического разбора. Узлы дерева, такие как подлежащее, сказуемое, группа подлежащего, предложение соответствует синтаксическим понятиям, а листья – это слова, из которых строится предложение. Обрубив в дереве часть листьев и ветвей, мы получим сентенциальную форму (выводимую цепочку).
<предложение>
Природу неоднозначности фразы можно объяснить на примере все того же дерева разбора для фразы «Мать любит дочь».
Эта фраза двусмысленна, так как имеет два варианта синтаксического разбора. Синтаксическая неоднозначность напрямую влечет неоднозначность семантическую. Но можно предложить и примеры синтаксически однозначных фраз, которые могут быть не поняты из-за неоднозначного смысла слов. Напомним, что алгоритмический язык должен быть однозначным.
Формальный язык – это математическая абстракция, возникшая как обобщение обычных лингвистических понятий естественных языков. Теория формальных языков изучает в основном синтаксис языков и является фундаментом синтаксически управляемых процессов перевода, к которому можно отнести трансляцию, ассемблирование и компиляцию. Основы этой теории были заложены американским математиком Н. Хомским в конце 50-х начале 60-х годов и до настоящего времени продолжают развиваться вместе с развитием вычислительной техники. Остановимся на основных элементах этой теории.
Алгоритм был ранее определен как алфавитный оператор с конечной системой правил преобразования. Для записи входных, промежуточных и выходных слов используется некоторый алфавит. Каким-то образом должны быть описаны и правила преобразования. Очевидно, для этого требуется некоторый язык. Пригоден ли для описания алгоритма обычный разговорный язык?
Любой естественный язык возникал как средство общения людей. Именно по этой причине ему присущи такие особенности как:
· изменчивость, которая состоит в непостоянстве словарного состава языка;
· неоднозначность трактовки фраз различными людьми;
· избыточность, о чем шла речь в главе «Кодирование символьной информации».
Перечисленные особенности не позволяют применить естественный язык для записи алгоритма, поскольку одним из свойств алгоритма является его детерминированность, т.е. однозначность выполнения шагов любым исполнителем. Наиболее простой путь преодоления нежелательных свойств естественных языков - построение языков искусственных со строгим синтаксисом и полной смысловой определенностью - такие языки получили название формальных.
В любом языке - естественном или искусственном - можно выделить две составляющие: синтаксис и семантику. Синтаксис (грамматика языка) - это совокупность правил, согласно которым строятся допустимые в данном языке конструкции. Семантика - смысловая сторона языка - она соотносит единицы и конструкции языка с некоторым внешним миром, для описания которого язык используется.
Для описания формального языка необходим другой язык, с помощью которого будут создаваться языковые конструкции. Описываемый формальный язык называется языком-объектом, а язык, средствами которого производится описание - метаязыком. Метаязык должен обеспечивать как описание структурных единиц языка и правил объединения их в допустимые предложения, так и содержательную (смысловую) сторону языковых конструкций.
Любая грамматика начинается с указания алфавита, т.е. набора символов, посредством которого строятся конструкции языка.
Синтаксис формального языка задается некоторой системой правил (порождающей системой), которая из небольшого набора исходных конструкций порождает все допустимые их комбинации, т.е. язык образуется как множество разрешенных правилами сочетаний исходных конструкций. Кроме этого, синтаксис содержит формулировку условия, которое выполняется для законченных конструкций языка и не выполняется в противном случае.
Помимо синтаксиса устанавливается система правил, позволяющих конструкциям языка придать смысл - эти правила образуют семантику языка.
Формальная грамматика - система правил, описывающая множество конечных последовательностей символов формального алфавита.
Конечные цепочки символов называются предложениями формального языка, а само множество цепочек - языком, описываемым данной грамматикой.
Набор синтаксических правил формального языка аналогичен системе подстановок, используемых в нормальных алгоритмах Маркова. Вывод в данной порождающей грамматике есть последовательность цепочек, в которой любая, начиная со второй, получается из предыдущей применением какого-либо правила вывода.
Формальная грамматика задается упорядоченной четверкой {T , N, S, Р }, где Т и N - непересекающиеся конечные множества, образующие алфавит или словарь порождаемого формального языка; Т называется множеством (словарем) терминальных символов; N - множеством (словарем) нетерминальных (вспомогательных) символов. S - начальный (выделенный) вспомогательный символ из множества N. Р - набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного символа, имеющие вид g → h, где g и h - цепочки, состоящие как из терминальных, так и нетерминальных символов.
Подстановки работают следующим образом: если в преобразуемой цепочке есть слово g , то оно заменяется словом h. Единственное ограничение на вид подстановок состоит в том, что слово g не может состоять только из терминальных символов. Это означает, что получение на некотором шаге цепочки, состоящей только из терминальных символов, свидетельствует о прекращении процесса порождения - эта цепочка является правильной, завершенной конструкцией порождаемого языка. Подстановки Р могут применяться к трансформируемой цепочке в произвольном порядке.
