Государственный комитет Российской Федерации
по высшему образованию
Самарский муниципальный комплекс непрерывного образования
“Университет Наяновой”
М. А. Шамашов теория формальных языков. Грамматики и автоматы
Учебное пособие
Самара
1996
УДК 519.682:681.142
Теория формальных языков. Грамматики и автоматы. Учебное пособие./
М.А.Шамашов. Самара: Самарский муниципальный комплекс непрерывного
образования “Университет Наяновой”, 1996, 91 с.
Материал, изложенный в данном пособии, в течении целого ряда лет использовался при чтении курсов лекций на факультете информатики Самарского аэрокосмического университета и математическом факультете университета Наяновой. Пособие освещает основные концепции, методы и алгоритмы теории формальных языков - науки, изучающей математические модели языков и имеющей практическую ориентацию на конструирование программной поддержки интеллектуальных языковых интерфейсов для общения человека с ЭВМ в самых различных областях науки и техники.
Пособие, в первую очередь, ориентировано на студентов, изучающих информатику и компьютерные науки, и специалистов, связанных с задачами проектирования системного и прикладного программного обеспечения автоматизированных систем самой различной ориентации. Рекомендуется в качестве учебника для использования в учебном процессе специальностей "Прикладная математика и компьютерные науки", "Автоматизированные системы обработки информации и управления", "Автоматизированные информационные системы", "Программное обеспечение вычислительных и автоматизированных систем". Выполнено на кафедре "Прикладной математики и компьютерных наук" университета Наяновой.
Ил. 38. Библ. 15 наим.
Печатается по решению редакционно-издательского совета Самарского муниципального комплекса непрерывного образования “Университет Наяновой”
ПРЕДИСЛОВИЕ
Данное пособие задумано как первая часть учебника для одно- или двухсеместрового курса по теории формальных языков и основ построения трансляторов. В пособии освещена та часть математической теории формальных языков и автоматов, которая лежит в основе построения синтаксически управляемого перевода и компиляции. Большая часть идей и методов, рассматриваемых в пособии, почерпнута автором из целого ряда фундаментальных переводных монографий, большинство которых в настоящее время являются библиографической редкостью. Эти материалы в первоисточниках зачастую слишком объемны, сложны и потребовали глубокого осмысления и серьезной переработки.
Математические понятия теории автоматов и формальных грамматик излогаются строго, но автор счел возможным опустить или схематизировать доказательства целого ряда теорем из-за ограниченных рамок пособия и стремления сделать его доступным широкому кругу читателей, включающих не только математиков, но и студентов технических университетов. Автор считает, что концепции теории формальных грамматик и автоматов служат прекрасной основой не только для обучения основам вычислимости и построения компиляторов, но и для реальной разработки предметно-ориентированных языков. Так, основываясь на этой теории, автор в 1988 году реализовал универсальный символьный процессор, различные модификации которого до сих пор используются при создании предметно-ориентированных языков и обучении.
Пособие рассчитано на студентов, ранее не знакомых с математической лингвистикой и теорией автоматов, поэтому каждое определение или теорема снабжена примерами. В конце большинства разделов даются контрольные вопросы и упражнения, которые могут использоваться при проведении практических занятий, лабораторных работ на ЭВМ, зачетов и экзаменов.
Разделы этого пособия возникли как конспекты курсов лекций, которые в течении ряда лет читаются автором в Самарском аэрокосмическом университете и университете Наяновой. Хочется поблагодарить слушателей, чьи критические замечания, вопросы и недоумевающие взгляды заставляли неоднократно перерабатывать курс. Автор благодарит своих коллег В.В.Куликова, Л.Ф.Штернберга и М.А.Кораблина, совместная работа с которыми способствовала его специализации в теоретических, учебно-методических и практических аспектах данной области знаний.
ВВЕДЕНИЕ
Теория формальных языков - это раздел математической лингвистики, изучающей математические модели языков. Импульсом к созданию и совершенствованию этой теории послужило развитие вычислительной техники и, как следствие, необходимость в средствах общения человека с ЭВМ. Во всех применениях ЭВМ должна понимать какой-либо язык, на котором пользователь может сообщить ей алгоритмы решения задач и исходные данные. Каждая ЭВМ имеет собственный язык машинных команд, представляемых в двоичном коде и отражающих отдельные операции процессора. На первых этапах развития вычислительной техники программисты общались с ЭВМ именно на этом примитивном языке, но человек не способен хорошо мыслить в категориях цифрового языка машины. Автоматизация программирования привела к созданию вначале языков ассемблера, а затем и алгоритмических языков высокого уровня, перевод с которых на родной машинный язык был поручен самой ЭВМ. Программы такого перевода называются трансляторами.
С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) - специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс, - пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать как создаются языки и их программная поддержка. Хочется надеяться, что предлагаемое пособие станет Вашим первым шагом в познании этой области.
Чтобы объяснить язык машине необходимо четко представлять как он устроен и как мы его понимаем. Задумавшись над этим, мы увидим, что не знаем, как мы понимаем наш родной язык. Процесс этого понимания подсознателен, интуитивен. Но чтобы создать транслятор, необходимо иметь алгоритм перевода текста в те действия, которые этот текст требует выполнить, а это в свою очередь требует формализации языка. Задачи формализации языка и решает математическая лингвистика. Естественные языки слишком сложны и формализовать их полностью пока не удается. Алгоритмические языки, напротив, уже создаются в расчете на формализацию. Теория формальных языков - это наиболее развитая ветвь математической лингвистики, представляющая по сути методику объяснения языка машине. Прежде чем рассматривать определения, модели и методы этой теории, рассмотрим некоторые понятия на примерах из естественных языков.
Язык - это множество предложений (фраз), построенных по определенным правилам. Грамматика - это и есть те самые правила, которые определяют предложения языка. Язык должен быть разрешимым, то есть должен существовать алгоритм, который за конечное число шагов (конечное время) может определить, принадлежит фраза языку или нет. На алгоритмический язык накладывается также требование однозначности,- любая его фраза должна быть понята единственным образом, не допускать двоякого толкования. Разрешим ли русский язык? Да, так как мы каким-то образом определяем, сказана фраза по русски или нет. Но он неоднозначен и на нем трудно описывать алгоритмы.
В языке можно выделить синтаксис и семантику. Синтаксис определяет принадлежность фраз языку, а семантика - их смысл. Синтаксис обычно упрощается тем, что не все фразы языка обязаны иметь смысл. Зачастую трудно понять смысл стихов футуристов или речей некоторых политиков. В этой связи интересен пример академика Л.В.Щербы: "Глокая куздра штеко будланула бокра и кудрячит бокренка". Это фраза на русском языке, ее можно разобрать по членам предложения, но смысл ее не ясен. Между синтаксисом и семантикой нет четкой грани. Семантика, также как и синтаксис, накладывает ограничения на фразы языка, чтобы сделать их осмысленными. Однако, можно так изменить синтаксис, чтобы бессмысленные фразы просто не принадлежали языку.
Мы узнаем принадлежность фразы языку, основываясь на интуиции, но для этого можно применить и правила грамматики. Синтаксический анализ фразы можно записать в виде дерева грамматического разбора. Узлы дерева, такие как подлежащее, сказуемое, группа подлежащего, предложение соответствуют синтаксическим понятиям, а листья - это слова из которых состоит предложение. Обрубив в дереве часть листьев и ветвей мы получим сентенциальную форму (выводимую цепочку).
Природу неоднозначности можно объяснить на примере все того же дерева разбора для фразы “Мать любит дочь” (см. рис. 1).
Эта фраза двусмысленна, так как имеет два варианта синтаксического разбора. Синтаксическая неоднозначность напрямую влечет неоднозначность семантическую. Но можно предложить и примеры синтаксически однозначных фраз, которые могут быть не поняты из-за неоднозначного смысла слов. Напомним, что алгоритмический язык должен быть однозначным.
Формальный язык - это математическая абстракция, возникшая как обобщение обычных лингвистических понятий естественных языков. Теория формальных языков изучает в основном синтаксис языков и является фундаментом синтаксически управляемых процессов перевода, к которому можно отнести трансляцию, ассемблирование и компиляцию. Основы этой теории были заложены американским математиком Н.Хомским в конце 50-х, начале 60-х годов и до настоящего времени продолжают развиваться вместе с развитием вычислительной техники. Остановимся на основных элементах этой теории.
