Формальные языки и грамматики

12. Лекция: Формальные языки и грамматики Рассматриваются основные сведения о формальных и естественных языках, грамматиках, типах грамматик, грамматическом анализе, переводе с языков, типах трансляторов. Математический язык как форма выражения научного знания использовался еще в древности при решении практических задач. Большую роль в развитии математики как языка – метаязыка наук – сыграла математическая логика, аксиоматизировавшая ряд теории, изучившая их логику, внутреннюю структуру. Развитие информатики, особенно таких ее разделов, как теория формальных языков, грамматик, структур, алгоритмических языков и методов трансляции баз данных и знаний и других приводит к развитию, углублению, формализации и структурированию предметов наук. В свою очередь, появилась возможность моделирования языковых структур, формализации, структурирования ряда языков общения, анализа и построения различного рода текстов и словарей, в том числе – их автоматического построения. Язык , определенный с помощью алфавита (над алфавитом) X = {x1, x2, ... , xn} , – это некоторая устная, звуковая, письменная или иная форма выражения слов над X, включая синтаксис – правила образования структур из слов и словосочетаний, семантику – правила проверки правильности, смысловой однозначности и совместимости синтаксических конструкций языка, состоящих из лексем. Для устных языков (общения) нужна и фонетика – правила произношения составных частей предложения, то есть фонем. Язык как коммуникативный аппарат должен иметь определяющие конструкции слов над данным алфавитом, грамматические правила образования предложений из слов и соотнесения этих предложений тем явлениям и процессам, которые они описывают, или синтаксическим и семантическим правилам. Пример. В частности, семантика изучает связи вида: "знак, структура знаков значение объект"; синтаксис – связи вида: "знак, структура знаков объект". Основные функции любого языка – отображение, передача, сжатие, хранение, актуализация информации с помощью сообщений на этом языке. Пример. Запишем более кратко, сжато, точно (формализованно) факт "целое число x делится на целое число y без остатка". На математическом языке это будет иметь вид "Число x кратно числу y". Факт, что числа x, y – целые, уже можно специально, как выше, не оговаривать, так как математическое понятие кратности это уже предполагает (аксиома). Запишем еще более кратко и формализованно на алгоритмическом языке Паскаль: "x mod y = 0". Здесь уже условие кратности область изменения аргументов не нужно оговаривать – они декларированы в языке Паскаль (в описаниях типов и операции mod). Языки бывают естественного происхождения (например языки общения) и искусственного происхождения или формальные языки , разрабатываемые для общения человека с автоматом (компьютером) либо для описания и получения знаний. Пусть X – некоторый алфавит, X = {x1, x2, ... , xn} , а S(X) – множество слов над алфавитом X, тогда S(X) – бесконечное и счетное множество. Формальный язык L(X) – произвольное подмножество S(X). Формальный язык использует естественный язык как лексическую форму оформления входящих в него абстрактных объектов, как метаязык или язык для описания синтаксиса другого языка. Описываемый метаязыком язык в этом случае называется объектным языком (по отношению к метаязыку). Формальная грамматика G состоит из совокупностей: T = {t1, t2, ... , tk} – множество терминальных символов языка или множество основных понятий языка; N = {n1, n2, ..., nm} – множество нетерминальных символов языка или вспомогательных понятий, обозначений конкретных классов слов, например, глаголов или предлогов, причем во множестве N содержится n0 – начальный символ из N; P = {p1, p2, ..., pq} – система подстановок (продукции) слов вида в слова или замен всех слов s1(x) в рассматриваемой системе соотношений на слова вида s2(x) . Язык (множество слов S(X)) задается грамматикой G(S) – структурой правил, которые позволяют порождать все слова и только их. Грамматический анализ – процесс редукции к нетерминальному символу или слову. Множество – словарь грамматики G. Правила вывода – это непустое множество правил вида , где , а "" – отношение вида "левое (можно) заменить на правое". Слово выводимо из слова с помощью правила , если , . Последовательность называется выводом g из f, если fi+1 выводимо из fi для всех . Признаком завершения процесса (последовательности) вывода является отсутствие слова, выводимого из g. Пример. Опишем элементы естественного, например, русского языка в терминах формальных грамматик. Алфавит языка X = {А, а, Б, б, ... , Я, я, ., ,, :, ;, ., !, ?, ", ", (, )}, T={<корни>, <приставки> и т.д.}, N = {предложение, подлежащее, сказуемое, глагол, местоимение и т.д.}, n0 = "предложение" . Например, пусть Т = {арбуз, банан, красный, греет, загорает, бок}, N = {сказуемое, подлежащее, определение, дополнение, группа подлежащего, группа сказуемого}, n0 = {предложение} , P = {p1: предложение (группа подлежащего), (группа сказуемого ), p2: группа подлежащего (определение)(подлежащее) , p3: группа сказуемого (сказуемое) (дополнение) , p4: определение "красный" , p5: подлежащее "арбуз" , p6: подлежащее "банан" , p7: сказуемое "греет" , p8: дополнение "банан" , p9: дополнение "бок"} . Тогда справедливы следующие выводы: предложение (группа подлежащего)(группа сказуемого) (определение) (подлежащее) (группа сказуемого) (определение) (подлежащее) (сказуемое) (дополнение) "красный" (подлежащее) (сказуемое )(дополнение) "красный арбуз" (сказуемое) (дополнение) "красный арбуз греет" (дополнение) "красный арбуз греет бок". Таким образом, мы по формальным правилам построили предложение естественного языка. Различают четыре основных типа формальных грамматик. Грамматика типа 0 (G–0) – грамматика, в которой нет ограничений на правила вывода (то есть в правиле вывода , f и g – любые). Грамматика типа 1 (G–1) – грамматика, в которой содержатся правила вида , где n – нетерминальный символ , f1 , f2 , w – цепочки из словаря W. Грамматика типа 2 (G–2) – грамматика, в которой допустимы лишь правила вида . Грамматика типа 3 (G–3) имеет правила вида , либо , где . Грамматики типа G–0 называются свободными, типа G–1 – контекстно-зависимыми, типа G–2 – контекстно-свободными, типа G–3 – регулярными или автоматными. Выражение, записанное на метаязыке с помощью конечного (счетного) числа операций и операндов, называется регулярным выражением. В формальных грамматиках рассматриваются три основные проблемы: 1. проблема вхождения – построить алгоритм, который для каждого задаваемого слова выясняет, принадлежит ли оно языку, допускаемому данной грамматикой; 2. проблема анализа – построить алгоритм, который для каждого слова, допускаемого данной грамматикой, строит вывод этого слова; 3. проблема оценки сложности алгоритма вывода (вычислений). Если первые две задачи – более "грамматического" характера, то третья задача – более "алгоритмического" характера. С появлением компьютеров повысились требования к точности и структурированности алгоритма. Для этих целей разрабатываются алгоритмические языки . Это формальный язык, формализованный язык, так как он включает в себя и математическую символику, например, числа, знаки операций, переменные, выражения и др. Алгоритмический язык – средство записи алгоритмов для исполнения, изучения логики алгоритма. Основное отличие алгоритмического языка от языка программирования (хотя их часто отождествляют) состоит в том, что последний предназначен для записи и исполнения алгоритмов в виде, понятном и исполнимом ЭВМ. Основные атрибуты языка алгоритмического (программирования): 1. константы – постоянные величины (числовые, символьные, логические); 2. символы – знаки, имеющие различные коды при переводе; 3. идентификаторы – имена, именования различных объектов алгоритма; 4. переменные – для именования изменяемых величин, параметров; 5. метки – именования различных частей, участков алгоритмов; 6. процедуры – функционально завершенные именованные части алгоритма; 7. описания – соглашения о типе, характере, структуре используемых данных и стандартизации представления (описания) данных; 8. комментарии – пояснения к различным участкам алгоритма; 9. операторы – команды преобразования используемых, получаемых данных или изменения порядка их выполнения; 10. выражения – записи, образуемые из постоянных, переменных и знаков операций и являющиеся источниками значений; сюда отнесем и функции стандартные (встроенные), с которыми можно оперировать, как и с переменными, в соответствии с их атрибутами. Любые математические выражения записываются на алгоритмических языках по правилам не только математики, но и этого языка. Пример. На алгоритмическом языке Паскаль математическое выражение будет записано в виде y = exp(x*ln(2)) + 3*sin(x – 4/5))*ln(x + sqrt(x + 5)). Пример. Выражению Паскаля w = sqrt(sqr(b + c) + 2/a*x/c) соответствует математическое выражение вида . Вычисление значений выражений на алгоритмическом языке происходит в соответствии с принятым в языке старшинством операций. Пример. Найдем b = ln(ехр(5)) + min(max(3,2),6) + mod(15,4)*int(1.99). Результат равен: b = 5 + min(3,6) + 3*1 = 5 + 3 + 3 = 11. Первые ЭВМ поставлялись без программного обеспечения, и программисту приходилось описывать в программе все необходимое для ее работы. Разработка первых алгоритмических языков (например ForTran) упростила программирование, увеличила число людей, решающих на компьютере свои задачи без привлечения программистов, положила начало двум основным направлениям в программировании: прикладному и системному программированию, а затем и третьему – инструментальному программированию. Прикладной программист (обычно на языках программирования высокого уровня) разрабатывает программы решения конкретных естественнонаучных задач. Системный программист (обычно на языках программирования низкого уровня) разрабатывает программы автоматизации процесса написания и отладки прикладных программ, распределения ресурсов между прикладными программами, управления процессом прохождения таких прикладных программ на ЭВМ, например разрабатывает ОС. Язык считается тем более высокого уровня, чем более он близок к языку естественному, и считается тем более низкого уровня, чем он ближе к языкам, реализуемым аппаратно, машинным. Охарактеризуем эти уровни алгоритмических языков: • языки запросов (непроцедурные языки) предназначены для осуществления диалога с некоторым пакетом прикладных программ, — это языки имитационного моделирования, в частности язык SLAM и др.; • языки высокого уровня (проблемно-ориентированные языки) предназначены для решения определенного, но достаточно широкого класса задач, например, вычислительного характера или обработки текстов (символов) — это, к примеру, языки FORTRAN, BASIC, LISP и др.; • ассемблеры (семейство языков), предназначены для укрупнения и символической (мнемонической) записи машинных команд; • языки микроопераций (языки разработки микропрограмм) — собственно говоря, это и есть языки машинных операций. Языки по типу их использования и сферам применения можно делить условно на следующие типы (это – не полная их классификация): 1. языки процедурные; 2. языки непроцедурные; 3. языки функционального программирования; 4. языки моделирования; 5. языки аналитических преобразований; 6. языки эвристические; 7. языки описания, представления объектных языков или метаязыки. Возможно и такое деление языков (отражающее характер их использования): 1. метаязыки, языки описания других языков; 2. языки описания, формулирования задач; 3. языки описания технологии, сценариев решения задач; 4. языки описания, разработки программ решения задач (или кодирования алгоритмов, часто вычислительного характера); 5. языки описания, представления знаний (фреймовые языки); 6. языки описания, представления данных; 7. языки описания, формулировки решений задач. В мире разработано несколько тысяч языков различного назначения. Пример. Отметим следующие языки, которые оказали наибольшее влияние и преемственность в развитии языков программирования: • ФОРТРАН, язык научно-технических расчетов, разработан в 1955 году фирмой IBM; • АЛГОЛ, язык вычислительного характера, разработан в 1960 году Международным комитетом ученых; • БЕЙСИК, простой язык для начинающих, разработан в 1965 году в Дортмунде; • ПАСКАЛЬ, разработан в качестве языка учебного и исследовательского характера в 1969 году в Цюрихе Н. Виртом; • СИ, разработан лабораторией BELL (США, 1972 г.) в качестве языка поддержки и программирования ОС UNIX; • ПРОЛОГ, язык логического программирования, разработан Колмероэ в 1971-1973 годах; • ПИТОН (ПАЙТОН), разработан в начале 1990-х годов Гвидо ван Россумом и является простым объектно-ориентированным языком, расширяемым, совершенствуемым пользователями; • JAVA – язык, ориентированный на сеть Интернет и серверы WWW; рассмотрим этот язык подробнее ниже; • HTML, предложен Тимом Бернерсом-Ли в 1989 году в качестве поддержки WWW-документов. ЭВМ может исполнять программы, написанные на ее машинном языке, в машинных кодах. Для перевода с других языков на машинный язык составляется специальная программа, называемая транслятором . Алгоритм (программа на языке программирования) преобразуется в корректную последовательность команд и данных, загружаемых в память ЭВМ и выполняемых в ней аппаратно. Чем выше уровень используемого при составлении программы исходного языка, тем больше работ по трансляции программы. Транслятор переводит программу с исходного языка программирования на машинный язык загрузки ее в память и исполнения. Существует два основных режима трансляции: компиляция и интерпретация. При интерпретации перевод на язык машины и выполнение каждой команды исходной программы осуществляется последовательно, покомандно, а полученная машинная программа пригодна только для одноразового решения задачи; данные вводятся при этом по мере трансляции. При компиляции до выполнения программы осуществляется полный перевод всей программы на машинный язык ЭВМ, затем полученная программа редактируется и загружается со всеми необходимыми для выполнения транслированной программы программами ОС в память ЭВМ и получается так называемый загрузочный модуль. Загрузочный модуль пригоден для многократного использования без повторной трансляции. Пример. Язык Бейсик имеет трансляторы различного типа. Например, в среде TurboBasic (TBasic) – транслятор-интерпретатор, а в среде QuickBasic (QBasic) – транслятор-компилятор. Программа для TBasic интерпретируется по циклу: "ввод команды – перевод команды на внутренний машинный язык – ввод данных для данной команды – исполнение". Программа для QBasic компилируется по циклу: "перевод всех команд программы на внутренний язык – исправление ошибок в программе – ввод данных для программы – исполнение всей программы".