Теория формальных грамматик 1ч

Государственный комитет Российской Федерации
по высшему образованию

Самарский муниципальный комплекс непрерывного образования
“Университет Наяновой”








М. А. Шамашов


ТЕОРИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ.
ГРАММАТИКИ И АВТОМАТЫ

Учебное пособие








Самара
1996
УДК 519.682:681.142

Теория формальных языков. Грамматики и автоматы. Учебное пособие./
М.А.Шамашов. Самара: Самарский муниципальный комплекс непрерывного
образования “Университет Наяновой”, 1996, 91 с.

Материал, изложенный в данном пособии, в течении целого ряда лет использовался при чтении курсов лекций на факультете информатики Самарского аэрокосмического университета и математическом факультете университета Наяновой. Пособие освещает основные концепции, методы и алгоритмы теории формальных языков - науки, изучающей математические модели языков и имеющей практическую ориентацию на конструирование программной поддержки интеллектуальных языковых интерфейсов для общения человека с ЭВМ в самых различных областях науки и техники.
Пособие, в первую очередь, ориентировано на студентов, изучающих информатику и компьютерные науки, и специалистов, связанных с задачами проектирования системного и прикладного программного обеспечения автоматизированных систем самой различной ориентации. Рекомендуется в качестве учебника для использования в учебном процессе специальностей "Прикладная математика и компьютерные науки", "Автоматизированные системы обработки информации и управления", "Автоматизированные информационные системы", "Программное обеспечение вычислительных и автоматизированных систем". Выполнено на кафедре "Прикладной математики и компьютерных наук" университета Наяновой.
Ил. 38. Библ. 15 наим.

Печатается по решению редакционно-издательского совета Самарского муниципального комплекса непрерывного образования “Университет Наяновой”



ПРЕДИСЛОВИЕ

Данное пособие задумано как первая часть учебника для одно- или двухсеместрового курса по теории формальных языков и основ построения трансляторов. В пособии освещена та часть математической теории формальных языков и автоматов, которая лежит в основе построения синтаксически управляемого перевода и компиляции. Большая часть идей и методов, рассматриваемых в пособии, почерпнута автором из целого ряда фундаментальных переводных монографий, большинство которых в настоящее время являются библиографической редкостью. Эти материалы в первоисточниках зачастую слишком объемны, сложны и потребовали глубокого осмысления и серьезной переработки.
Математические понятия теории автоматов и формальных грамматик излогаются строго, но автор счел возможным опустить или схематизировать доказательства целого ряда теорем из-за ограниченных рамок пособия и стремления сделать его доступным широкому кругу читателей, включающих не только математиков, но и студентов технических университетов. Автор считает, что концепции теории формальных грамматик и автоматов служат прекрасной основой не только для обучения основам вычислимости и построения компиляторов, но и для реальной разработки предметно-ориентированных языков. Так, основываясь на этой теории, автор в 1988 году реализовал универсальный символьный процессор, различные модификации которого до сих пор используются при создании предметно-ориентированных языков и обучении.
Пособие рассчитано на студентов, ранее не знакомых с математической лингвистикой и теорией автоматов, поэтому каждое определение или теорема снабжена примерами. В конце большинства разделов даются контрольные вопросы и упражнения, которые могут использоваться при проведении практических занятий, лабораторных работ на ЭВМ, зачетов и экзаменов.
Разделы этого пособия возникли как конспекты курсов лекций, которые в течении ряда лет читаются автором в Самарском аэрокосмическом университете и университете Наяновой. Хочется поблагодарить слушателей, чьи критические замечания, вопросы и недоумевающие взгляды заставляли неоднократно перерабатывать курс. Автор благодарит своих коллег В.В.Куликова, Л.Ф.Штернберга и М.А.Кораблина, совместная работа с которыми способствовала его специализации в теоретических, учебно-методических и практических аспектах данной области знаний.

ВВЕДЕНИЕ

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

13 EMBED Word.Picture.6 1415

1. ЯЗЫКИ И ГРАММАТИКИ. ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ
И КЛАССИФИКАЦИЯ

Вначале дадим ряд определений.

Алфавит - это непустое конечное множество элементов. Элементы алфавита называются символами

Всякая конечная последовательность символов алфавита называется цепочкой. Так a, b, c, ab, aaca - цепочки в алфавите A = {a,b,c}.

Допустим существование пустой цепочки ( , не содержащей ни одного символа.

Важен порядок символов в цепочке. Цепочка ab отличается от ba.

Длина цепочки ((( равна количеству символов в цепочке. Так (a(=1, (abc(=3, ( ( (=0.

Если ( и (- цепочки, то их конкатенацией (( является цепочка, полученная путем дописывания символов цепочки ( вслед за символами цепочки ( . Например, если ((ab, ((bc, то ((( abbc и ((( bcab. Поскольку ( - цепочка, не содержащая символов, то в соответствии с правилами конкатенации для любой цепочки ( можно записать
(((((((.

Обращением цепочки ( (обозначается ( R ) называется цепочка (, записанная в обратном порядке, т.е. если ( = a1...an , где все ai - символы, то (R= an... a1. Кроме того, ( R=( .

Если ( ( (( - цепочка, то ( - голова (префикс), а ( - хвост (суффикс) цепочки (. При этом, ( - правильная голова, если (- не пустая цепочка (( ( (), ( - правильный хвост, если ( ( (. Таким образом, если ( ( abc, то ( , a, ab и abc - головы (, и все они, кроме abc, - правильные головы.

Иногда удобнее и нагляднее писать
( ((( вместо ((,
если нас не интересует ( - остальная часть цепочки. Три точки "(((" будут обозначать любую возможную цепочку, включая пустую.

Языком L в алфавите A называется множество цепочек в A.
Это определение подходит почти для любого языка. Языки Паскаль, С, Модула-2, английский и русский охватываются этим понятием.

Рассмотрим простые примеры языков в алфавите A.
Пустое множество ( - это язык. Множество { ( }, содержащее только пустую цепочку, также является языком.
Заметим, что ( и { ( } - это два разных языка.

Обозначим через A( множество, содержащее все цепочки в алфавите A, включая (.
Например, если A бинарный алфавит {0,1}, то
A( = { ( , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, ...}.

Каждый язык в алфавите A является подмножеством множества A(. Множество всех цепочек в A, за исключением (, обозначим A +, то есть A(= A+ ( (.

Формально цепочку в алфавите A можно определить следующим образом:
1). ( - цепочка в A,
2). если ( цепочка в A и a ( A, то (a - цепочка в A ((a ( A(),
3). ( - цепочка в A, тогда и только тогда, когда она является таковой в силу 1) или 2).

Цепочку, состоящую из i символов a будем обозначать a i, то есть a0=(, a1= a, a2= aa, a3= aaa и т.д.

Итак язык L - это некоторое множество цепочек в некотором алфавите A. Как описать этот язык. Если L состоит из конечного числа цепочек, то самый очевидный способ состоит в составлении списка всех цепочек этого языка. Однако, для большинства языков нельзя или нежелательно устанавливать верхнюю границу длины самой длинной цепочки. Следовательно приходится рассматривать язык, содержащий сколь угодно много цепочек. Очевидно, их нельзя описать перечислением цепочек. Мы хотим, чтобы описание языка было конечным (имело конечный объем), хотя сам язык может быть и бесконечным. Известно несколько методов такого описания. Один из основных состоит в использовании порождающей системы, называемой грамматикой.
В грамматике, определяющей язык L, используется два конечных непересекающихся множества: множества терминальных символов (терминалов) ( и множества нетерминалов (. Из терминалов образуются слова (цепочки) языка L, а нетерминалы - суть синтаксические понятия (синтаксические единицы) языка, служащие для порождения (вывода) слов языка L. Сердцевину же грамматики составляет конечное множество продукций образования (правил вывода) (, которые описывают процесс порождения цепочек языка. Правило - это просто пара цепочек, а точнее элемент декартового произведения:
(( ( ()( ( (( ( ()( ( (( ( ()(.
Иначе говоря, первым компонентом правила служит любая цепочка, содержащая хотя бы один нетерминал, а вторая - любая цепочка из терминалов и нетерминалов, включая ( . Правила обычно записывают в виде
( ( (
или
( ::= (
что означает ( порождает (состоит из) (.

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

В последующем, если не оговорено дополнительно, используем следующие обозначения. Грамматику языка обозначим через G, возможно с индексом, или G(S). Язык L, определяемый грамматикой G, обозначим L(G). Терминальные символы обозначим малыми буквами, а нетерминалы - прописными, или в виде текста в угловых скобках, например, <нетерминал>. Цепочки будем обозначать греческими буквами. Если в грамматике встречаются правила с одинаковыми левыми частями
( ::=(1
( ::=(2
..........
( ::=(n ,
то будем писать
( ::=(1((2( ... ((n
в виде одного правила, имеющего ряд альтернатив в правой части. Правило вида
( ::=( (((
можно представить
( ::=( [( ]
где [(]-факультативный (необязательный) элемент. Последние обозначения используются в системе записи метаязыка Хомского, которая носит название Бэкусовой нормальной формы (БНФ) или формы Бэкуса-Наура. Она была предложена Д.Бэкусом в 1959 году и впервые применена П.Науром для описания языка Алгол-60. Напомним, что метаязыком называется язык, который используется для описания других языков.
Рассмотрим ряд грамматик и обсудим алгоритм порождения, применяемый для вывода цепочек языка.

Пример 1.1.
<предложение>::=<подлежащее><группа сказуемого>
<подлежащее>::=мать(отец
<группа сказуемого>::=<сказуемое><дополнение>
<сказуемое>::=любит(обожает(боготворит
<дополнение>::=сына(дочь (

Если имеется множество правил, то ими можно воспользоваться для того, чтобы вывести или породить цепочку (предложение) по следующей схеме. Начнем с начального символа грамматики - <предложение>, найдем правило, в котором <предложение> слева от ::= , и подставим вместо <предложение> цепочку, которая расположена справа от ::=, т.е.
<предложение> ( <подлежащее> <группа сказуемого>
Таким образом, мы заменяем синтаксическое понятие на одну из цепочек, из которых оно может состоять. Повторим процесс. Возьмем один из нетерминалов в цепочке <подлежащее> <группа сказуемого>, например <подлежащее>; найдем правило, где <подлежащее> находится слева от ::=, и заменим <подлежащее> в исходной цепочке на соответствующую цепочку, которая находится справа от ::=. Это дает
<подлежащее> < группа сказуемого > ( мать < группа сказуемого >
Символ "(" означает, что один символ слева от ( в соответствии с правилом грамматики заменяется цепочкой, находящейся справа от (. Полный вывод одного предложения будет таким:
<предложение> ( <подлежащее> <группа сказуемого>
( мать < группа сказуемого >
( мать <сказуемое> <дополнение>
( мать любит <дополнение>
( мать любит сына
Этот вывод предложения запишем сокращенно, используя новый символ (+
<предложение> (+ мать любит сына
На каждом шаге можно заменить любой нетерминал. В приведенном выше выводе всегда заменялся самый левый из них.
Вывод, на каждом шаге которого заменяется самый левый нетерминал сентенциальной формы называется левым (левосторонним) выводом. Существует и часто используется также правый (правосторонний) вывод, который получается, если в сентенциальной форме заменять всегда самый правый нетерминал.
Обратите внимание на то, что предложенная грамматика используется для описания многих предложений. Девять правил грамматики, если считать каждую альтернативу за отдельное правило, а так оно и есть, определяют двенадцать предложений (цепочек) языка:
мать любит сына мать обожает сына мать боготворит сына
мать любит дочь мать обожает дочь мать боготворит дочь
отец любит сына отец обожает сына отец боготворит сына
отец любит дочь отец обожает дочь отец боготворит дочь
Одно из назначений грамматики как раз и состоит в том, чтобы описывать все цепочки языка с помощью приемлемого числа правил. Это особенно важно, если учесть, что количество предложений в языке, чаще всего, бесконечно.
Рассмотрим еще один пример полезной грамматики

Пример 1.2. Грамматики целого числа без знака содержат следующие 13 правил
(1) <число>::=<чс> S ( A
(2) <чс>::=<цифра><чс> A ( AB
(3) <чс>::=<цифра> A ( B
(4) <цифра>::=0 B ( 0
(5) <цифра>::=1 B ( 1
(6) <цифра>::=2 B ( 2
(7) <цифра>::=3 B ( 3
(8) <цифра>::=4 B ( 4
(9) <цифра>::=5 B ( 5
(10) <цифра>::=6 B ( 6
(11) <цифра>::=7 B ( 7
(12) <цифра>::=8 B ( 8
(13) <цифра>::=9 B ( 9
Заметим, что грамматики G(<число>) и G(S) определяют один и тот же язык и отличаются только именами нетерминалов и вторым правилом (

А теперь продолжим наши определения.

Пусть G - грамматика. Будем говорить, что цепочка ( непосредственно порождает цепочку (, и обозначим
( ( (,
если для некоторых цепочек ( и ( можно написать
( ( (((
( ( (((
где
(((( (
правило грамматики G. Будем также говорить, что ( непосредственно выводима из ( или что ( непосредственно приводится (редуцируется, сворачивается) к ( .

Цепочки ( и (, конечно, могут быть пустыми. Следовательно, для любого правила A(( грамматики G имеет место A ( ( . На рис. 1.1 даны некоторые примеры непосредственных выводов для грамматики G(<число>) из примера 1.2 и обозначений предыдущего определения.

Будем говорить, что ( порождает ( или ( приводится к ( и записывать ( (+ (, если существует последовательность непосредственных выводов
( ( (0 ( (1 ( (2 ( ((( ( (n ( (,
где n>0. Эта последовательность называется выводом длины n. Будем писать ( (( (, если ( (+ ( или ( ( (.

13 EMBED Word.Picture.6 1415
Если просмотреть все строки рис 1.1 то мы получим
<число> ( <чс> ( <цифра> <чс> ( 2 <чс> ( 2 <цифра> ( 25
Таким образом, <число> (+ 22 и длина вывода равна 5. (Если длина вывода известна можно записывать в явном виде <число> (5 22 )
Заметим, что пока в цепочке есть хотя бы один нетерминал, из нее можно вывести новую цепочку, Однако если нетерминальные символы отсутствуют, то вывод завершен. Неслучайно "терминалом" (terminal - заключительный, конечный) называют символ, который не встречается в левой части ни одного из правил. Исключение составляют нетерминалы-тупики, которые будут рассмотрены в разделе 4.2.
Попробуем еще раз определить язык.

Пусть G(S) = {(,(,(,S} - грамматика. Цепочка ( называется сентенциальной формой, если ( выводима из начального символа S, т.е. если
S(((.
Цепочка языка - это сентенциальная форма, состоящая только из терминалов.
Язык L(G(S)) - это множество цепочек:
L(G)={ ( (S((( и ((((}
т.е. язык - это подмножество множества всех терминальных цепочек ( (.

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

Пусть G(S) - грамматика. И пусть ( (((( - сентенциальная форма. Тогда ( называется фразой сентенциальной формы ( для нетерминального символа U, если S (( (U( и U (+ (; и далее, ( называется простой фразой, если S (( (U( и U ( (.

Тот факт, что U (+ (, вовсе не означает, что ( является фразой сентенциальной формы (((; необходимо также иметь S (( (U(. Значит ли в примере 1.2, что <чс> является фразой сентенциальной формы 1 <чс>, если существует правило <число>::=<чс> ? Конечно, нет, поскольку невозможен вывод цепочки 1 <число> из начального символа грамматики <число>. Каковы же фразы сентенциальной формы 1 <чс> ? Имеет место вывод
<число> ( <чс> ( <цифра><чс> ( 1<чс>
Таким образом,
(1) <число> (( <чс> и <чс> (+1<чс>
(2) <число> (( <цифра><чс> и <цифра> (+1
Следовательно, 1<чс> и 1 - фразы, простой же фразой будет только 1.
В дальнейшем мы часто будем говорить о самой левой простой фразе сентенциальной формы, которая называется основой.
Грамматики G(<число>) и G(S) из примера 1.2 описывают бесконечный язык, т.е. язык, состоящий из бесконечного числа цепочек. Это обусловлено тем, что правило <чс>::=<цифра><чс> (A(AB) содержит <чс> (A) и в левой, и в правой частях, т.е. в некотором смысле символ <чс> (A) сам себя определяет.

В общем случае, если U (+...U..., то говорят, что грамматика рекурсивна по отношению к U. Если U (+ U..., то имеет место левая рекурсия, а если U (+...U, то - правая рекурсия. Соответствующие правила называют лево- (право)рекурсивными. Если язык бесконечен, то определяющая его грамматика должна быть рекурсивной.
Ниже представлен пример грамматики, которая включает правило с двухсторонней рекурсией.

Пример 1.3. Грамматика идентификатора, то есть последовательности из одного или более символов, начинающейся с буквы, и содержащей буквы и цифры в качестве возможного продолжения
S ( AB
A ( a A ( b
.............................
A ( y A ( z
B ( BB B ( (
B ( A B ( 0
..............................
B ( 9. (

1.1. Синтаксические деревья и неоднозначность

Рассмотрим грамматику c правилами вывода
(1.1.1)
B ( B+B(B(B(V(C
V ( a(b(c(... x(y(z
C ( 0(1(2(...8(9
и вывод цепочки b+a(9
(1.1.2) B(B+B(B+B(B(V+B(B(V+V(B(V+V(C(b+V(C(b+a(C(b+a(9
Такая запись не очень удобна, так как по ней трудно определить в какой части сентенциальной формы проводилась замена и какой нетерминал породил тот или иной символ. Более наглядна запись в виде дерева вывода или синтаксического дерева, представленного на рис 1.2 (a).
Для того чтобы понять что выведено, применяем левый обход дерева. Идем от корня по крайней левой ветви, дойдя до терминала (конца ветви), выписываем его, возвращаемся до ближайшего разветвления и идем по самой левой из тех, которые еще не пройдены. Если все ветви данного узла уже исчерпаны, возвращаемся к предыдущему разветвлению, если оно есть. Продолжая таким образом, получим в результате b+a(9. Кроме вывода (1.1.2) по данному дереву можно получить целую серию выводов, например,
(1.1.3) B(B+B(B+B(B(B+B(C(V+V(9(B+V(9(B+a(C(V+a(C(b+a(9
Заметим, что эти выводы отличаются лишь порядком применения правил и что синтаксическое дерево и грамматика не определяют точный порядок вывода. На каждом шаге вывода имеется некоторый произвол в выборе заменяемого нетерминала. На данном этапе эти различия порядка для нас несущественны и мы считаем выводы эквивалентными, если им соответствует одно и то же дерево. Более важным здесь является то, что цепочка b+a(9 в данной грамматике имеет два дерева вывода (рисунки 1.2 (а) и (б)). Сентенциальная форма B+B(B имеет два синтаксических дерева и две основы: B+B и B(B. Грамматика неоднозначна и при разборе сентенциальной формы можно выбрать любую из основ. Нельзя сказать, что выполняется раньше: умножение или сложение. Из рис. 1.2 (б) следует, что b+a(9 имеет два подвыражения b+a и 9, хотя по смыслу необходимо иметь подвыражения b и a(9.

13 EMBED Word.Picture.6 1415
Цепочка, порождаемая грамматикой, неоднозначна, если для ее вывода существует более одного синтаксического дерева. Грамматика неоднозначна, если она порождает неоднозначные цепочки, в противном случае она однозначна.
Здесь речь идет о неоднозначной грамматике, а не языке. Изменяя неоднозначную грамматику можно получить однозначную грамматику для того же самого языка. Ниже приведена однозначная грамматика арифметических выражений
(1.1.4) (врж( ( (терм( (( (терм( (( (терм( ((врж( ( (терм( ((врж( ( (терм(
(терм( ( (множ( ((терм( ( (множ( ((терм( ( (множ(
(множ( ( ((врж(( ( i ( k
В этой грамматике i - любой идентификатор (имя переменной), а k - любая константа. Единственное дерево вывода для выражения i+i(k представлено на рис. 1.3. (a). В соответствии с предложенной грамматикой, эта, да и все остальные цепочки, порождаемые грамматикой (1.1.4) однозначны.
Определим теперь, что в выражении i+i(k должно выполняться раньше: сложение или умножение. Операндами для +, согласно дереву, является (врж(, из которого выводится i, и (терм(, порождающий i(k. Это означает, что умножение должно выполняться первым и образовать (терм( для сложения; следовательно, умножение предшествует сложению. Сделать наоборот можно используя только скобки, как показано на рис. 1.3 (б). Грамматику арифметических выражений (1.1.4) следует предпочесть грамматике (1.1.1) ввиду ее однозначности и учета приоритета операций.

1.2. Классификация грамматик по Хомскому

В 1956 году Н.Хомским было предложено классифицировать грамматики по виду их правил, по ограничениям, накладываемым на правила.

Грамматика G по Хомскому - это традиционная четверка множеств
G = ((, (, (, S),
где ( - множество нетерминалов, ( - множество терминалов, ( - множество продукций, S - аксиома грамматики.
13 EMBED Word.Picture.6 1415
Грамматика G называется грамматикой типа 3, регулярной, праволинейной или автоматной грамматикой (А-грамматикой), если каждое правило из ( имеет вид:
A ( xA (праволинейное правило)
или
A ( x (заключительное правило)
где A ( (, x ( (.

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

Грамматика G называется грамматикой типа 2, бесконтекстной или контекстно - свободной (КС- ) грамматикой если ее правила имеют вид:
A ( (,
где A ( (, ( ( (((() (.

То есть в каждом правиле такой грамматики имеет место единственный нетерминал слева и произвольная цепочка из терминалов и нетерминалов справа, возможно и пустая. Замена A на ( в сентециальной форме не зависит от того, в каком окружении, в каком контексте находится A.

Грамматика G называется грамматикой типа 1, контекстной, нормальных составляющих (НС- ) или контекстно - зависимой (КЗ- ) грамматикой если ее правила имеют вид:
(A( ( (((,
где A ( (, (, ( ( (((()*( и ( ( (((()+, то есть в каждом правиле нетерминал A в контексте ( и ( заменяется на непустую цепочку ( в том же контексте.

Грамматика G называется грамматикой типа 0, грамматикой с фразовой структурой или рекурсивно перечислимой грамматикой, если ее правила имеют вид:
(((,
где на левую и правую части правил не наложено никаких ограничений. (

Нетрудно заметить, что грамматики типа i одновременно являются грамматиками типа i -1. Исключение составляют укорачивающие КС (УКС) - грамматики, то есть грамматики, содержащие аннулирующие правила типа
A ( (
которые не являются КЗ-грамматиками.

Язык, определяемый грамматикой типа i называется языком типа i.

Из примеров 1.2 и 1.3 следует, что языки чисел и идентификаторов являются КС-языками (тип 2).
Тот факт, что язык определяется грамматикой типа i, еще не означает, что его нельзя породить менее мощной грамматикой типа i+1. Например, КС- грамматика с правилами
S(AS ( (
A ( 0 ( 1
порождает язык {0,1}*, который конечно же можно определить А-грамматикой
S ( 0S ( 1S ( (
Рассмотрим ряд примеров грамматик. В большинстве случаев мы опускаем описания множеств (, (, S в силу их очевидности и ограничиваемся множеством правил грамматики (.

Пример 1.4. Автоматная грамматика идентификатора.
S ( aA ( bA ( cA (...( yA ( zA
A ( aA ( bA ( cA (...( yA ( zA ( 0A ( 1A (... ( 8A ( 9A
A ( a ( b ( c ( ... ( y ( z ( 0 ( 1 (... ( 8 ( 9.
Данная грамматика имеет на самом деле 72 правила, но для краткости часть из них заменена многоточием. (

Пример 1.5. Грамматика типа 0 для цепочек вида x n y n z n, где n > 0.
(1) S ( xyASz
(2) S ( Q
(3) yAQ ( Qy
(4) yAx(xyA
(5) xQ(x
Покажем, что данная грамматика порождает цепочки x n y n z n и никаких других.
1). Новые символы порождаются только первым правилом. При этом получается одинаковое количество символов x, y и z, символы z в нужном месте и порядке. То есть применяя n раз правило (1) получим вывод:
S ( xyASz ( xyAxyASzz (( (xyA) n Sz n.
2). После применения правила (2) дальнейшее порождение новых символов невозможно. Получаем (xyA) n Sz n ( (xyA) n Qz n.
3). Правила (3) и (4) применяются поочередно. При этом А устраняется правилом (3), когда правее него в сентенциальной форме нет х. Получаем
(xyA) n Qz n = (xyA) n-1 xyAQz n ( (xyA) n-2 xyAxQyz n ( ( xyA) n-2 xxyAQyz n (
(xyA) n-3 xyAxxQyyz n ( (xyA) n-3 xxyAxQyyz n ( (xyA) n-3 xxxyAQyyz n (+ x n Qy n z n
4). x n-1 xQy n z n ( x n y n z n
Применить правило (5) можно только на последнем шаге, в противном случае в цепочке останутся нетерминалы A. (

Пример 1.6. КЗ-грамматика для цепочек x n y n z n, где n>0.
(1) S ( xYz
(2) Yz ( XYYzz
(3) YX ( YA
(4) YA ( XA
(5) XA ( XY
(6) xX ( xx
(7) Y ( y
Здесь правила (3) - (5) заменяют правило YX ( XY, относящееся к типу 0. Взяв дополнительный нетерминал A, мы получили три КЗ-правила. Рассмотрим вывод цепочки x3y3z3 по этой грамматике.
S ( xYz ( xXYYzz ( xXYXYYzzz ( xXYAYYzzz ( xXXAYYzzz ( xXXYYYzzz (
xxXYYYzzz ( xxxYYYzzz ( xxxyYYzzz ( xxxyyYzzz ( xxxyyyzzz = x3y3z3. (

Что можно сказать о выделенных классах грамматик и языков в целом? Идеальной с теоретической и практической точек зрения являются А-грамматики и языки. Но их класс слишком узок. Даже язык арифметических выражений не является A языком. Тем не менее, теория автоматных языков повсеместно используется при построении трансляторов. Класс языков типа 0, напротив, очень широк и неразрешим в общем случае. Все остальные языки (тип 1 - тип 3), которые обобщенно называют контекстными, разрешимы. Для них существуют алгоритмы, определяющие принадлежность или непринадлежность цепочек языку за конечное число шагов.

Теорема 1.1. Любой контекстный язык разрешим.

Доказательство. Для любого контекстного языка L существует порождающая его грамматика G в удлиняющей форме, у которой для всех правил вывода ((( выполняется условие (( (( (( (. (Доказательство этого факта будет дано в разделе 4.5.) В общем случае для контекстной грамматики без аннулирующих правил выполняется условие ((( ( (((.) Возьмем анализируемую терминальную цепочку (. Длина исследуемой цепочки должна быть конечной. Тогда если ( ( L, то существует вывод S ( (1 ( (2 ( ... ( ( n-1 ( ( n ( (, то есть вывод S (n (, где ((( ( n, так как каждый шаг вывода удлиняет цепочку не менее, чем на единицу. Число выводов с длиной не более n конечно. Поэтому достаточно проверить выводится ли ( одним из них. Если ( совпадает с одной из терминальных цепочек, выводимых по заданной грамматике G, не более чем за n шагов, то ( ( L(G), если нет - ( ( L(G). (

Неразрешимость языков типа 0 выводят их из рассмотрения в данном курсе,- нет смысла изучать языки для которых невозможно определить принадлежность цепочки. Прочие же языки, как следует из теоремы 1.1 могут представлять практический интерес. В дальнейшем мы подробно рассмотрим теорию А- и КС- языков, нашедших широкое распространение при проектировании трансляторов.

1.3. Техника построения КС- и А- грамматик

Приобретение навыков в компактном описании языков в виде грамматик и автоматов являются одними из главных задач данной части курса. Задачу можно поставить так: задан вид цепочек языка, требуется описать их с помощью порождающей грамматики.
Контекстно-свободную грамматику строить проще, общий подход ее построения состоит в пошаговой детализации. Разбиваем цепочку на компоненты и вводим нетерминалы, отражающие их суть. Каждую компоненту, полученную на предыдущем шаге, разбиваем на подкомпоненты и т.д., пока не дойдем до терминалов. Для примера рассмотрим такую своеобразную "цепочку", как пассажирский поезд.

Пример 1.7. КС-грамматика пассажирского поезда.
( поезд ( ( ( локомотив ( ( вагоны(
( локомотив ( ( паровоз(тепловоз(электровоз
( вагоны ( ( (вагон( ((вагон( (вагоны(
( вагон ( ( купейный(плацкартный(общий(СВ(ресторан
Здесь терминалами мы считаем объекты типа "электровоз", "ресторан" и т.п., хотя могли спуститься и до стоп-крана и колесных пар. (

Отметим еще раз, что для получения цепочки типа "один или много (", где количество ( не ограничено сверху необходимо использовать рекурсивные правила:
( один или много ( ( ( ( ((( один или много ( (
или
( один или много ( ( ( ( (( один или много ( ((
или
( один или много ( ( ( ( (( один или много ( (( один или много ( (

Пример 1.8. КС-грамматика действительного числа, то есть цепочек от полного представления числа, типа -123.567Е-21, до вырожденных: 0. или .1, т.е. в этом числе обязательна точка и хотя бы одна цифра в целой или дробной части. Терминалами здесь являются знаки - " + " и " - ", цифры от "0" до "9", десятичная точка - "." и символ "E". То есть ( ( {+, - , 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, . , E}. В цепочке ( число ( можно выделить следующие основные компоненты: знак числа, целую часть, точку - "." , дробную часть, символ "E", знак порядка и само значение порядка. Отдельные компоненты или их группы могут отсутствовать. При таком разложении "." и "E" - терминалы, а все остальное нетерминалы, требующие дальнейшей декомпозиции. Так ( целая часть ( - это одна цифра или несколько цифр, а ( знак ( - "+" или "- ". Нетрудно видеть, что знаки числа и порядка ничем не отличаются друг от друга и для них можно ограничиться одним понятием - знак. С точки зрения синтаксиса нет разницы и между целой частью, дробной частью и порядком и их вполне можно определить одно через другое. В результате имеем грамматику:
(1) ( число ( ( ( знак (( целая часть ( .( дробная часть ( Е ( знак ( ( порядок (
(2) ( число ( ( ( целая часть ( . ( дробная часть ( Е ( знак ( ( порядок (
(3) ( число ( ( ( знак ( . ( дробная часть ( Е ( знак ( ( порядок (
(4) ( число ( ( ( знак ( ( целая часть ( . Е ( знак ( ( порядок (
(5) ( число ( ( ( знак ( ( целая часть ( . ( дробная часть ( Е ( порядок (
(6) ( число ( ( ( знак ( ( целая часть ( . ( дробная часть (
(7) ( число ( ( . ( дробная часть ( Е ( знак ( ( порядок (
(8) ( число ( ( ( целая часть ( . Е ( знак ( ( порядок (
(9) ( число ( ( ( целая часть ( . ( дробная часть ( Е ( порядок (
(10) ( число ( ( ( знак ( ( целая часть ( . Е ( порядок (
(11) ( число ( ( ( знак ( . ( дробная часть ( Е ( порядок (
(12) ( число ( ( ( целая часть ( . ( дробная часть (
(13) ( число ( ( ( знак (. ( дробная часть (
(14) ( число ( ( ( знак ( ( целая часть ( .
(15) ( число ( ( ( целая часть ( . Е ( порядок (
(16) ( число ( ( . ( дробная часть ( Е ( порядок (
(17) ( число ( ( ( целая часть ( .
(18) ( число ( ( . ( дробная часть (
(19) ( целая часть ( ( ( цифра ( ( целая часть (
(20) ( целая часть ( ( ( цифра (
(21) ( дробная часть ( ( ( целая часть (
(22) ( порядок ( ( ( целая часть (
(23) ( цифра ( ( 0
(24) ( цифра ( ( 1
(25) ( цифра ( ( 2
. . . . . . .
(32) ( цифра ( ( 9
(33) ( знак ( ( +
(34) ( знак ( ( -
Используя БНФ (альтернативу и факультатив), эти 34 правила можно переписать в виде:
( число ( ( [( знак (]( целая часть (.[(дробная часть (][Е[( знак (]( порядок (](
[( знак (][( целая часть (].( дробная часть ( [Е [( знак (] ( порядок (]
( целая часть ( ( ( цифра ( [( целая часть (]
( дробная часть ( ( ( целая часть (
( порядок ( ( ( целая часть (
( цифра ( ( 0(1(2(3(4(5(6(7(8(9
( знак ( ( +(- (

Техника построение А-грамматик определяется видом их правил, где в правой части первым должен стоять терминал. Для формирования таких правил просматриваются исходные цепочки, выписываются терминалы, которые можно встретить на очередном шаге, и вводятся нетерминалы, описывающие остаток цепочки. Созданные нетерминалы детализируются точно также как и исходный, то есть просматривается остаток цепочки и т.д.

Пример 1.9. Автоматная грамматика действительного числа.
Число может начинаться с "+" или "-" и тогда оставшуюся часть числа резонно назвать числом без знака. Число также может начаться любой цифрой (0 - 9) и остаток цепочки будет тем же числом без знака. Наконец число может начаться десятичной точкой "." и остаток такой цепочки уже иной. Если число без знака может в качестве продолжения содержать цифры и должно завершиться той же точкой, то после точки идет фрагмент цепочки, который точки уже не содержит. Есть смысл назвать этот фрагмент дробной частью и порядком. Рассуждая аналогичным образом мы получим А-грамматику, где использованы следующие сокращения для имен нетерминалов: чис - число, чбз - число без знака, дчп - дробная часть и порядок, пор - порядок, пбз - порядок без знака
( ч ( ( +( чбз ((-( чбз ((0( чбз ((1( чбз ((...(9( чбз ((.( дчп (
( чбз ( ( 0( чбз ((1( чбз ((...(9( чбз ((.( дчп ((.
( дчп ( ( 0( дчп ((1( дчп ((...(9( дчп ((0(1(...(9(E( пор (
( пор ( ( +( пбз ((-( пбз ((0( пбз ((1( пбз ((...(9( пбз ((0(1(...(9
( пбз ( ( 0( пбз ((1( пбз ((...(9( пбз ((0(1(...(9
Данная грамматика допускает порождение совсем уж вырожденных цепочек, типа "-." или ".Е1", т.е. цепочек без целой и дробной частей. На данном этапе проигнорируем этот факт, чтобы не усложнять грамматику. (

1.4. Представление А - грамматики в виде графа состояний.
Недетерминированные и детерминированные А - грамматики

Наглядным способом представления А-грамматики является граф состояний (переходов). Вершины этого графа соответствуют нетерминалам и из вершины A в вершину B проводится дуга, помеченная терминалом a, если в грамматике существует правило
A ( aB.
Добавим еще одну дополнительную заключительную вершину F и проведем дуги
13 EMBED Word.Picture.6 1415
если в грамматике присутствует заключительное правило A ( b, а само это правило будем записывать A ( bF, получив тем самым модифицированную А-грамматику.
Заметим, что каждому выводу в А-грамматике будет соответствовать путь по графу состояний из начальной вершины S в вершину F. Граф А-грамматики действительного числа из примера 1.9 представлен на рисунке 1.5 (a).
13 EMBED Word.Picture.6 1415

А-грамматика числа, рассмотренная в примере 1.9, является недетерминированной, то есть в ней существует такой нетерминал A и терминал a, для которых существует несколько нетерминалов B, таких что выполняются правила A ( aB. Например, модифицированная А-грамматика числа, что отчетливо видно на рис. 5.1 (а), содержит правила ( чбз ((.( дчп ( и ( чбз ((.F или ( дчп ( ( 0( дчп ( и ( дчп ( ( 0F. Это нежелательно с точки зрения построения программ синтаксического анализа.
А-грамматика называется детерминированной, если для любого A ( ( (A ( F) и любого a ( ( существует не более одного B ( (, для которого выполняется правило A ( aB.
А-грамматика называется вполне детерминированной, если для любого A(( (A ( F) и любого a ( ( существует единственное B ( (, для которого выполняется правило A ( aB.
В разделе 3 будет показано, что любую недетерминированную А-грамматику можно свести к детерминированной. Пока же, для того чтобы перейти к реализации программ синтаксического анализа А-языков, что является основной частью лабораторных работ на ЭВМ в данной части курса, отметим, что на практике всегда используется специальный символ - ограничитель цепочки. Это либо нулевой байт, либо символ конца файла и т.п.
Если, например, считать, что число из примера 1.9 завершается символом “;”, то детерминированная А-грамматика числа строится элементарно. Граф состояний для этого случая представлен на рис. 1.5 (б). Нетерминалы ( чбз1 (, ( дчп1 (, ( пбз1 ( добавлены здесь для того, чтобы исключить возможность формирования числа без целой и дробной части и без числа порядка после символа ”E”. Вполне детерминированная форма должна включать, кроме того “ошибочный” нетерминал < Ош > и правила типа ( чбз ( ( +( Ош ( или ( дчп ( ( .( Ош ( и т.п. То есть для тех A( ( (A ( F) и a ( (, для которых в модифицированной детерминированной А-грамматике нет правил A ( aB, необходимо для формирования вполне детерминированной формы добавить правила A ( aE, где E ( <Ош> - “ошибочная” вершина.

1.5. Синтаксический анализ автоматных языков

Задача этого раздела - дать общую схему построения программ синтаксического анализа А-языков и привести примеры их реализации. В дальнейшем мы рассмотрим большую группу полезных свойств А-грамматик и А-языков, которые, конечно же, должны использоваться Вами на практике. Автор счел необходимым привести данный раздел как можно раньше, предваряя этот материал, с тем, чтобы Вы могли совмещать изучение теории и ее использование в практической работе на ЭВМ. В данном курсе она будет сводиться к разработке и отладке программ синтаксического анализа с элементами семантики для предложенных Вам языков. Описание вариантов языков дано в Приложении.
Блок-схема алгоритма и программа, анализирующая принадлежность цепочки заданному А-языку, строиться тривиально по графу состояний А-грамматики. Каждой вершине графа, кроме заключительной и “ошибочной”, соответствует блок выбора очередного символа анализируемой цепочки. Каждому ребру, точнее пометке ребра, блок анализа символа с последующим переходом к тому или иному блоку выбора. Каждому пути по графу соответствует путь по блок-схеме и программе. Рассмотрим несколько приемов построения таких программ на примере анализа числа, граф А-грамматики которого представлен на рис. 1.5 (б). В качестве языка программирования используется подмножество языка C.

Пример 1.10. Фрагмент анализатора с GO TO.
Оператор безусловного перехода goto не рекомендуется использовать при программировании. В свое время он даже отсутствовал в ряде языков и я здесь вовсе не собираюсь призвать Вас повсеместно его применять. Ниже будут приведены примеры реализации структурных программ анализа. Тем не менее, использование goto яснее всего отражает связь программы анализа и А-грамматики или графа состояний. Для того чтобы подчеркнуть эту связь, имена меток в приведенной ниже программе получены транслитерацией имен нетерминалов с рис. 1.5 (б).
.........
char s, str[100]; /* анализируемая строка */
int i;
.........
int analiz(void)
{ i=0;
chis: s=str[i]; if (s==+’ || s==-’) goto chbz;
if (s>=0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·>=0’ && s<=9’) goto pbz1;
goto Osh;
pbz: i++; s=str[i];
if (s>=0’ && s<=9’) goto pbz1;
goto Osh;
pbz1: i++; s=str[i];
if (s>=0’ && s<=9’) goto pbz1;
if (s==;’) goto F;
Osh: printf(“\n Цепочка не принадлежит языку \n”);
return 0;
F: printf(“\n Цепочка принадлежит языку \n”);
return 1; }
.........
В рассмотренном примере, кроме использования goto есть и еще один существенный недостаток,- не идентифицируются ошибки. (

Пример 1.11. Фрагмент анализатора с перечислимым типом и переключателем.
.........
enum State {chis, chbz, chbz1, dchp, dchp1, por, pbz, pbz1, osh, F} sta;
char s, str[100]; int i;
.........
int analiz(void)
{
i=0; sta=chis;
while (sta != F && sta != osh)
{
s=str[i]; i++;
switch (sta)
{
case chis: {
if (s==+’ || s==-’) sta=chbz;
else if (s>=0’ && s<=9’) sta=chbz1;
else if (s==.’) sta=dchp;
else { printf(“\n Ошибка в начале числа \n”); sta=osh; }
break; }
case chbz: {
if ((s>=0’ && s<=9’) sta=chbz1;
else if (s==.’) sta=dchp;
else { printf(“\n Ошибка в целой части числа \n”); sta=osh; }
break; }
case chbz1: {
if ((s>=0’ && s<=9’) sta=chbz1;
else if (s==.’) sta=dchp1;
else { printf(“\n Ошибка в конце целой части числа \n”); sta=osh; }
break; }
case dchp: {
if ((s>=0’ && s<=9’) sta=dchp1;
else { printf(“\n Ошибка в дробной части числа \n”); sta=osh; }
break; }
case dchp1: {
if ((s>=0’ && s<=9’) sta=dchp1;
else if (s==E’) sta=por;
else if (s==;’) sta=F;
else { printf(“\n Ошибка в конце дробной части числа \n”); sta=osh; }
break; }
case por: {
if (s==+’ || s==-’) sta=pbz;
else if (s>=0’ && s<=9’) sta=pbz1;
else { printf(“\n Ошибка в значении порядка числа \n”); sta=osh; }
break; }
case pbz: {
if ((s>=0’ && s<=9’) sta=pbz1;
else { printf(“\n Ошибка в значении порядка числа \n”); sta=osh; }
break; }
case pbz1: {
if ((s>=0’ && s<=9’) sta=pbz1;
else if (s==;’) sta=F;
else { printf(“\n Ошибка в конце числа \n”); sta=osh; }
break; }
}
}
if (sta==F) printf(“\n Число без ошибок \n”);
return (sta==F);
}
.........
Сообщения об ошибках здесь несколько расплывчаты, но это уже дело вкуса. (

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

Пример 1.12. Синтаксический анализатор числа с получением его значения.
#include

double rez; /* результат */
char st[80]; /* анализируемая строка */

/* Процедура анализа цифры */
int Dig(char d)
{
return (d>=0’ && d<=9’);
}
/* Процедура анализа числа */
int RealNumber(double *r)
{
double c, /* текущее значение числа */
z, /* знак числа */
p, /* знак порядка */
g; /* текущий множитель для формирования дробной части */
int cd; /* признак наличия целой или дробной части */
int i, j; char s;

c=0; z=1; p=10; j=0; g=0.1; cd=0; i=0; s=st[i];

if (s==-’) { z=-1; s=st[++i]; } /* знак “- “*/
else if (s==+’) s=st[++i];
while (Dig(s)) { c=c*10+(s-48); cd=1; s=st[++i]; } /* формируем целую часть */
if (s != .’) return 1; /* нет “.” */ s=st[++i];
while (Dig(s)) { c=c+((s-48)*g); g=g*0.1; cd=1; s=st[++i]; } /* дробная часть */
if (s==E’)
{ s=st[++i];
if (s==-’) p=0.1; /* отрицательный порядок */
else
{ if (Dig(s)) j=s-48; /* первая цифра порядка */
else if (s != +’) return 2; /* не то, что надо после “E” */
}
s=st[++i]; while (Dig(s)) { j=j*10+(s-48); s=st[++i] } /* значение порядка */
}
if (s != ;’) return 3; /* отсутствует ; */
if (!cd) return 4; /* отсутствуют цифры в целой и дробной части */
c=c*z; for(i=0;i *r=c; return 0; /* нормальное завершение */
}

main()
{ printf(“\n Тест анализатора действительного числа. Для завершения \n”);
printf(“тестирования на предложение ввести число’ введите пустую строку \n”);
for (;;)
{ printf(“\n введите число \n”);
gets(st);
if (st[0] == \0’) break; /* Строка пуста - конец теста */

switch (RealNumber(&rez))
{
case 0:
{ printf(“\n Успешная трансляция. Результат = %30.15f \n”, rez); break; }
case 1:
{ printf(“\n Ошибка, ожидается точка (.’). \n”); break; }
case 2:
{ printf(“\n Ошибка в значении порядка \n”); break; }
case 3:
{ printf(“\n Ошибка, ожидается ;’ \n”); break; }
case 4:
{ printf(“\n Ошибка, в числе отсутствуют целая и дробная части \n”); break; }
}
} return 0;
} (

Упражнения.

1.1. Дайте определение грамматике. Перечислите классы грамматик по Хомскому и дайте их определения. Как определить, содержит ли язык, порождаемый грамматикой, бесконечное число цепочек?

1.2. Что общего в А- и КС- грамматиках? Какие грамматики являются частным случаем других грамматик?

1.3. Постройте КС- и А- грамматики для цепочек вида x n y m z k, где n,k ( 0 и m ( 0. Покажите деревья вывода цепочк xxxyyz, xxzzz и xyz по полученной КС-грамматике.

1.4. Приведите граф состояний для A-грамматики из упр. 1.3. Введите признак конца цепочки, например символ “;”, и преобразуйте граф к детерминированной форме. Напишите программу синтаксического анализа цепочек x n y m z k, в качестве семантики подсчитайте количество x, y и z.

1.5. Постройте КС-грамматику, A-грамматику и граф состояний для цепочек состоящих из одного или нескольких, идущих без разделения блоков. Каждый блок начинается с единственной буквы и содержит в качестве продолжения от одной до трех цифр.

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

1.7. Постройте КС-грамматику, детерминированную А-грамматику и граф состояний для языка индексов ФОРТРАНа. При построении грамматики терминалами считать { a b c ...y z 0 1 2...8 9 ( ) + - ( }. Индексы ФОРТРАНа - это ограниченное арифметическое выражение, заключенное в круглые скобки. Ниже перечислены все возможные варианты этих индексов: (И) (К) (К*И) (И+К) (И-К) (К*И+К) (К*И-К), где И - идентификатор, а К - целая константа без знака.

1.8. Напишите процедуру анализа идентификатора с предупреждением в случае, когда количество символов в нем больше шести; процедуру анализа целой константы без знака с преобразованием символьного представления в число и предупреждением о переполнении (максимальное значение - 65535). Используя эти процедуры, напишите по А-грамматике программу анализа индексов ФОРТРАНа из упражнения 1.7.

1.9. Постройте КС - грамматики для цепочек ( n ( 0, m ( 0 )
(а) x n y n z m,
(б) x m y n z n,
(в) x n y m z n.

1.10. Постройте КС - грамматики для следующих цепочек в бинарном алфавите ((({0,1}, n, m ( 0 ):
(a) 0 n 1 m 0 m 1 n;
(б) (a(R, где ( - любая цепочка из нулей и единиц, а (R - обращение (симметричный поворот) цепочки (;
(в) 0 n 1 2n+3;
(г) всех цепочек, содержащих равное количество нулей и единиц;
(д) всех цепочек, содержащих равное количество нулей и единиц и такие, у которых количество нулей в каждой левой подцепочке не меньше чем единиц;
(е) 1n0m1p, где n+p>m>0.

1.11. Опишите языки, порождаемые следующими грамматиками с начальным нетерминалом S:
(a) S ( 10S0 S ( aA
A ( bA A ( a
(б) S ( SS S ( 1A0
A ( 1A0 A ( (
(в) S ( 1A S ( B0
A ( 1A A ( C
B ( B0 B ( C
C ( 1C0 C ( (
(г) S ( aSS S ( a
(д) S ( bADc D ( Gl
A ( aGs G ( (

1.12. Какие из приведенных ниже цепочек можно вывести в данной грамматике? В каждом случае постройте левый вывод, правый вывод и дерево вывода.
S ( aAcB S ( BdS
B ( aScA B ( cAB
A ( BaB A ( aBc
A ( a B ( b
(a) aacb
(б) aaacbdaacb
(в) aabcbd
(г) acabaaaacbcacb
(д) aaaaacbcacccab

1.13. (а) Найдите КС-грамматику для логических выражений, составленных из логических переменных, констант, скобок и знаков операций отрицания ((), дизъюнкции (() и конъюнкции ((). Приоритеты обычные: ( выполняется перед (, а ( - перед (.
(б) Добавьте к указанному языку первичные логические выражения, каждое из которых представляет собой арифметическое выражение, за которым следует знак отношения ( (( (( (( (( (( () и еще одно арифметическое выражение, и постройте соответствующую грамматику.

1.14. Постройте КС-грамматику оператора FORMAT языка ФОРТРАН, ограничиваясь форматами A, X, I, F. Примеры правильных цепочек:
10 FORMAT(I5)
100 FORMAT (X10,A5,3A4,I6,4(I3,X2,5(F8.3,X4,3A2,I6),X2,2(3A3,I4)),I7)

2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ

Второй распространенный метод, обеспечивающий задание языка конечными средствами состоит в использовании распознавателей (автоматов). В сущности, распознаватель - это схематизированный алгоритм, определяющий некоторое множество. Он состоит из четырех частей: входной ленты, головки чтения (/записи), управляющего устройства с конечной памятью и внешней (вспомогательной, рабочей) памяти (рис. 2.1).
13 EMBED Word.Picture.6 1415
Входную ленту можно рассматривать как линейную последовательность клеток (ячеек). Причем, в каждой ячейке может содержаться только один входной символ из некоторого конечного алфавита (. Самую левую и самую правую ячейки могут занимать особые символы - концевые маркеры; маркер может стоять только на правом конце ленты; его может не быть совсем.
Входная головка в каждый данный момент читает (обозревает) одну входную ячейку. За один шаг работы распознавателя входная головка может сдвинуться на ячейку вправо R, остаться неподвижной N или сдвинуться влево L. Распознаватель, который никогда не передвигает свою входную головку влево, называется односторонним. Обычно предполагается, что входная головка только читает, т.е. в ходе работы распознавателя символы на входной ленте не меняются. Но можно рассматривать и такие распознаватели - преобразователи, входная головка которых не только читает, но и пишет, например, машина Тьюринга общего вида.
Внешняя память распознавателя - это хранилище информации (данных) некоторого типа. Алфавит памяти(( конечен и информация в памяти образована только из символов этого алфавита. Предполагается, что в любой момент времени можно конечными средствами описать содержимое и структуру памяти, хотя с течением времени и работы распознавателя, объем памяти может становиться сколь угодно большим.
Поведение вспомогательной памяти для заданного класса распознавателей можно охарактеризовать с помощью двух функций: функции доступа к памяти (ФДП) и функции преобразования памяти (ФПП).
ФДП - это отображение множества состояний (конфигураций) памяти в конечное множество информационных символов, которое может совпадать с алфавитом памяти. Например, единственная информация доступная в каждый данный момент в магазине (стеке) - верхний символ магазина. Таким образом функция доступа к магазинной памяти f - это такое отображение ( ( в (, где ( - алфавит памяти, что
f(z1z2...zn) = z1,
где z i ( ( для всех 13 EMBED Equation.2 141513 EMBED Equation.2 1415
ФПП - это отображение, описывающее изменение памяти. Она отображает состояние памяти и управляющую цепочку в состояние памяти. Если предполагается, что операция над магазинной памятью заменяет верхний символ конечной цепочкой символов памяти, то соответствующую ФПП можно определить как такое отображение g: ( + ( ( ( ( ( (, что
g(z1z2...zn,x1x2...xm) = x1x2...xmz2...zn ,

где z i , x j ( ( для всех 13 EMBED Equation.2 1415 и 13 EMBED Equation.2 1415. Если верхний символ магазина z1 заменяется пустой цепочкой, то z2 станет верхним символом магазина.
Вообще именно тип внешней памяти определяет название распознавателя. Например, распознаватель, память которого организована как магазин, называется распознавателем с магазинной памятью. (Обычно его называют автоматом с магазинной памятью или МП-автоматом.)
Ядром же распознавателя является управляющее устройство с конечной памятью, под которым можно понимать программу, управляющую поведением распознавателя. Управляющее устройство представляет собой множество состояний Q вместе с отображением (, которое описывает как меняются состояния в соответствии с текущим входным символом (т.е. находящимся под входной головкой) и текущей информацией, извлеченной из внешней памяти. Управляющее устройство определяет также в каком направлении сдвинуть входную головку и какую информацию поместить в память.
Распознаватель работает, проделывая некоторую последовательность шагов или тактов. В начале такта читается текущий входной символ и с помощью функции доступа исследуется память. Входной символ и информация из памяти вместе с текущим состоянием управляющего устройства определяют каким должен быть следующий такт. Собственно такт состоит из следующих моментов:
(1) входная головка сдвигается на одну ячейку вправо, влево или сохраняет исходное положение;
(2) в память помещается некоторая информация;
(3) изменяется состояние управляющего устройства.
Поведение распознавателя удобно описывать в терминах конфигурации - мгновенного снимка распознавателя, на котором изображены:
(1) состояние устройства;
(2) содержимое входной ленты вместе с положением входной головки;
(3) содержимое памяти.
Управляющее устройство распознавателя может быть недетерминированным, т.е. для каждой конфигурации существует конечное множество всевозможных следующих шагов, любой из которых распознаватель может сделать, исходя из этой конфигурации. Устройство может быть детерминированным, если для каждой конфигурации существует не более одного следующего шага. Недетерминированный распознаватель - удобная математическая абстракция, но ее трудно моделировать на практике.
Конфигурация называется начальной, если управляющее устройство находится в заданном начальном состоянии q0, входная головка обозревает самый левый входной символ на ленте, а память имеет заранее установленное начальное содержимое.
Конфигурация называется заключительной, если управляющее устройство находится в одном из состояний заранее выделенного множества заключительных состояний F ( Q, а головка обозревает правый концевой маркер, или, если маркер отсутствует, сошла с правого конца ленты. Часто требуют, чтобы память в заключительной конфигурации тоже удовлетворяла некоторым условиям.
Говорят, что распознаватель допускает входную цепочку (, если начиная с начальной конфигурации, в которой ( записана на входной ленте, распознаватель может проделать последовательность шагов, завершающуюся заключительной конфигурацией. Недетерминированный распознаватель может при этом проделать много последовательностей шагов и если хотя бы одна из них заканчивается заключительной конфигурацией, то исходная входная цепочка будет допущена.
Язык, определяемый распознавателем - это множество входных цепочек, которые он допускает.
Для каждого класса грамматик в иерархии Хомского существует естественный класс распознавателей, определяющий тот же класс языков. Справедливы следующие утверждения:

Язык L автоматный тогда и только тогда, когда он определяется односторонним детерминированным конечным автоматом.

Язык L контекстно свободный тогда и только тогда, когда он определяется односторонним недетерминированным МП - автоматом.

Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно-ограниченным (ЛО-) автоматом.

Язык L рекурсивно перечислимый (без ограничений) тогда и только тогда, когда он определяется машиной Тьюринга общего вида.

Заметим, что все интересующие нас распознаватели называются автоматами и неслучайно термин автомат вынесен в название данного раздела и всего пособия.

3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ

Автоматную грамматику можно представить в виде таблицы, где строки соответствуют терминалам, а столбцы нетерминалам. На пересечении строки a и столбца A записываются нетерминалы B, которые входят в правила A ( aB. На рис. 3.1 представлена таблица переходов, построенная для А-грамматики из примера 1.9. Приведенная таблица представляет собой ничто иное, как функциональную таблицу или таблицу переходов конечного автомата.
Конечный автомат - это частный случай одностороннего распознавателя, где головка движется всегда вправо на каждом такте работы и отсутствует внешняя память.

Конечный автомат M можно определить пятеркой множеств
M = {Q, (, (,q0, F},
где
Q - конечное множество состояний автомата (при построении автоматов оно обычно совпадает с множеством нетерминалов грамматики);
( - конечное множество символов внешнего алфавита (конечное множество допустимых входных символов, совпадающих с множеством терминалов);
( - функция переходов, отображающая множество состояний и входных символов в множество состояний
Q(((Q
и представляемая, обычно, в виде таблицы переходов (например, из таблицы с рис. 3.1 следует, что ( (чис, +) = чбз, а ( (дчп, Е) = пор );
q0 - начальное состояние (на рис. 3.1 - чис);
F - множество заключительных состояний (в теории конечных автоматов заключительные состояния называются также допускающими, так как они допускают обрыв (завершение) цепочки или, иными словами, допускают пустую цепочку. На рис. 3.1 допускающие состояния дчп и пбз отмечены единицами в строке под таблицей, остальные состояния там отвергающие, обрыв цепочки в них недопустим и они отмечены нулем в нижней строке таблицы.
13 EMBED Word.Picture.6 1415
Таким образом, конечный автомат является эквивалентом автоматной грамматики. Собственно термин автоматная грамматика и связан с этой эквивалентностью. Здесь мы рассматриваем обе эти модели описания А-языков, так как одни утверждения и теоремы проще подтвердить и доказать, используя конечные автоматы, другие - автоматные грамматики.

3.1. Эквивалентность недетерминированных и
детерминированных конечных автоматов и А-грамматик

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

Недетерминированный автомат (НДА) - это автомат, где значение функции переходов ( - не отдельное состояние, как в детерминированном автомате (ДА), а множество состояний. В общем случае у НДА может быть также не одно, а множество начальных состояний (если начальное состояние не единственно, то эти состояния при изображении таблицы переходов будут помечаться стрелкой).

НДА изучается, так как для заданного множества иногда легче найти недетерминированное описание.

Говорят, что НДА допускает входную цепочку, если он позволяет связать одно из его начальных состояний с одним из допускающих.

Так автомат, представленный на рис. 3.2, допускает цепочку 11, так как
13 EMBED Equation.2 1415,
причем В - начальное, а С - допускающее состояния. Существование одной этой последовательности достаточно, чтобы показать допустимость входной цепочки 11, и существование другой последовательности
13 EMBED Equation.2 1415,
где A - отвергающее, на это не влияет.

13 EMBED Word.Picture.6 1415
На рис. 3.3 представлен еще один НДА с входным алфавитом {а, л, н, о, с, ь}, который допускает только две цепочки лассо и лань.
13 EMBED Word.Picture.6 1415
Понятие НДА приобретает практическое значение, так как для каждого НДА существует эквивалентный ему ДА, то есть ДА, допускающий в точности те же цепочки, что и НДА.
Основная идея построения ДА по НДА заключается в том, что после обработки отдельной входной цепочки состояние ДА будет представлять собой множество всех состояний НДА, которые он может достичь из начальных состояний после применения данной цепочки. Переходы ДА можно получить из НДА, вычисляя множества состояний, которые могут следовать после данного множества при различных входных символах. Допустимость цепочки определяется исходя из того, является ли последнее детерминированное состояние, которого достиг ДА, множеством недетерминированных состояний, включающим хотя бы одно допускающее состояние. Результирующий ДА будет иметь конечное множество состояний, так как число подмножеств состояний НДА конечно. В общем случае, если НДА содержит n состояний, то ДА будет содержать 2 n состояний. На практике многие из этих подмножеств представляют собой недостижимые состояния.
13 EMBED Word.Picture.6 1415
13 EMBED Word.Picture.6 1415
В приведенной ниже процедуре перехода от НДА к ДА переходы строятся только для тех подмножеств, которые действительно необходимы.
Пусть Мн - НДА, а Мд - эквивалентный ему ДА. Процедура перехода от НДА к ДА задается пятью шагами.
1. Пометить первый столбец функциональной таблицы для Мд множеством начальных состояний автомата Мн. Применить к этому множеству шаг 2.
2. По данному множеству состояний X, помечающему столбец таблицы переходов Мд, для которого переходы еще не вычислены, определить те состояния Мн, которые могут быть достигнуты из X с помощью каждого входного символа a, и поместить множества последующих состояний Ya в соответствующие ячейки таблицы Мд. Символически это выражается так: если ( функция НДА, то функция ДА ( | задается формулой
( | (X,a) = {y | y( ( (x,a), для некоторого x из X}
3. Для каждого множества Y, порожденного переходами на шаге 2, определить, имеется ли уже в Мд столбец, помеченный этим множеством. Если нет, то создать новый столбец и пометить его этим множеством Y. Если множество Y уже использовалось как метка, то никаких действий не требуется.
4. Если в таблице Мд есть столбец, для которого переходы еще не вычислены, вернуться назад и применить к этому столбцу шаг 2. Если все переходы вычислены, перейти к шагу 5.
5. Пометить столбец как допускающее состояние Мд, когда он содержит допускающее состояние Мн. В противном случае пометить как отвергающее.

На рисунках 3.4 (а) и 3.5 представлены функциональные таблицы ДА, полученные по предложенному алгоритму из НДА с рисунков 3.2 и 3.3 соответственно. На рисунке 3.4 (б) та же таблица, что и на 3.4 (а), но с новыми именами состояний. Во всех этих таблицах пустая ячейка - ни что иное, как ошибочное состояние.
Приведенный алгоритм можно использовать и для перехода от недетерминированной А-грамматики к детерминированной.

Пример 3.1. Пусть задана недетерминированная А-грамматика вида
S ( aB(aC(bB(bS(c
B ( cC(c
C ( a(aS(c
Эта грамматика не имеет естественного символа, ограничивающего цепочку, поэтому во всех правилах вида
A ( a
добавим предзаключительное состояние F( и получим правила
A ( a F(
Добавим также символ ограничения цепочки, например, ( и правило
F( ( (F,
где F - заключительное состояние. В результате получим модифицированную грамматику
S ( aB(aC(bB(bS(cF(
B ( cC(cF(
C ( aF( (aS(cF(
F| ( (F
Рассматриваем для недетерминированных правил неупорядоченные безповторные достижимые подмножества множества нетерминалов и в результате получим детерминированную грамматику
S ( a(b(cF(
( a(c
( a(b(c
( a(b(cF(((F
( a(cF(((F
F( ( (F
Полученная грамматика порождает те же цепочки, что и исходная. Отметим, что дерево вывода в автоматной грамматике вырождено, и его вполне можно представлять, в виде строки. Так дерево вывода цепочки acac( в исходной грамматике имеет вид
S a B c C a S c F( ( F ,
а в полученной детерминированной
S a c a c F( ( F.
Отличие состоит в том что каждый шаг порождения в детерминированной грамматике однозначен, что и определяет преимущество таких грамматик с точки зрения практического построения программ анализа по грамматике.
Можно переименовать нетерминалы сформированной детерминированной грамматики и получить грамматику в традиционной форме:
S ( aA(bB(cF(
A ( aC(cD
B ( aA(bB(cD
C ( aA(bB(cF(((F
D ( aC(cF(((F
F| ( (F (

3.2. Минимизация конечных автоматов

Для любого конечного автомата (КА) существует бесконечное число других КА, которые распознают тоже самое множество цепочек. При конструировании распознавателей для данной проблемы естественно учитывать возможность существования какого-либо другого автомата, который определяется проще и при реализации в качестве программы будет занимать меньше памяти.
В этом разделе мы установим, что для каждого конечного распознавателя существует единственный КА, распознающий то же самое множество цепочек, при этом число его состояний не больше числа состояний любого другого КА для этого множества. То есть существует единственный конечный автомат M(, имеющий наименьшее число состояний среди всех КА, допускающих язык L(M). Такой автомат будем называть минимальным.
Когда мы говорим единственный, то имеется в виду, что с точностью до имен состояний. Для любого автомата можно построить новый с тем же числом состояний, но другими именами. Однако, имена состояний на практике не играют никакой роли для распознания цепочек. Поэтому автоматы, различающиеся только именами состояний, можно считать одинаковыми.
Первый шаг в изложении теории минимизации - понятие эквивалентности состояний. Неформально - два состояния эквивалентны, если они одинаково реагируют на все возможные продолжения входной цепочки. Это понятие применимо и к состояниям одного и того же автомата и различных автоматов.

Состояние s конечного распознавателя M эквивалентно состоянию t конечного распознавателя N тогда и только тогда, когда автомат M, начав работу в состоянии s будет допускать в точности те же цепочки, что и автомат N, начавший работу в состоянии t.

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

Пример 3.2. На рис. 3.6 (а) представлен автомат, у которого состояния q4 и q5 явно
13 EMBED Word.Picture.6 1415
эквивалентны, так как оба они допускающие, при чтении символа a переходят в q2, а при чтении b переходят в q3. Объединяя q4 и q5 в одно состояние x, получим автомат, представленный на рис. 3.6 (б). Обычно, эквивалентность состояний менее очевидна, чем в этом примере, и необходим специальный тест на эквивалентность. (

Вторая цель проверки состояний на эквивалентность состоит в выяснении того, делают ли два автомата одно и тоже, то есть совпадают ли множества допустимых ими цепочек. Это достигается просто проверкой эквивалентности начальных состояний автоматов. Если они эквивалентны, то по определению эквивалентности состояний оба автомата допускают и отвергают одни и те же цепочки.

Таким образом автоматы M и N эквивалентны тогда и только тогда, когда эквивалентны их начальные состояния.

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

Пример 3.3. На рис. 3.7 представлены два автомата, у которых состояния X и A неэквивалентны, так как различающая их цепочка - 101:
13 EMBED Equation.2 1415
13 EMBED Equation.2 1415,
причем C - допускающее состояние, а Z - нет.
13 EMBED Word.Picture.6 1415
Поскольку A и X начальные состояния двух автоматов, то они неэквивалентны. (

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

Эквивалентность состояний является отношением эквивалентности в математическом смысле: оно рефлексивно (каждое состояние эквивалентно самому себе), симметрично (из s ( t следует, что t ( s) и транзитивно (если s ( t и t ( u, то s ( u).

3.2.1. Проверка эквивалентности двух состояний.

Состояния s и t эквивалентны тогда и только тогда, когда выполняются следующие два условия:
(1) условие подобия, - состояния s и t, должны быть оба допускающими, либо оба отвергающими;
(2) условие преемственности, - для всех входных символов состояния s и t должны переходить в эквивалентные состояния, то есть их преемники должны быть эквивалентны.

Нетрудно убедиться в том, что эти два условия выполняются, когда s и t не имеют различающей цепочки.
Условия (1) и (2) можно использовать в общем методе проверки на эквивалентность двух состояний. (Изложенный ниже метод надо понимать как проверку на неэквивалентность и рассматривать как метод поиска различающей цепочки).
На рис. 3.8 (а) представлена таблица переходов конечного автомата. Проверим у него состояния 0 и 7 на эквивалентность. Оба эти состояния отвергающие, следовательно, условие подобия для них выполняется. По входному символу z состояния 0 и 7 переходят в состояние 3, эквивалентное самому себе, а по входному символу y в состояния 0 и 6 соответственно. Для состояний 0, 6 условие подобия не выполняются. Эти состояния неэквивалентны, следовательно по условию преемственности неэквивалентны и состояния 0, 7 и y - различающая их цепочка.
13 EMBED Word.Picture.6 1415
Общая процедура теста на эквивалентность основывается на построении таблицы эквивалентности и определяется следующими шагами:
1. Начать построение таблицы эквивалентности состояний с отведения столбца для каждого входного символа. Пометить первую строку парой состояний, подвергаемых проверке.
2. Выбрать в таблице эквивалентности состояний строку, ячейки которой еще не заполнены и проверить подобны ли состояния, которыми она помечена. Если они неподобны, то два исходных состояния неэквивалентны и процедура окончена. Если они подобны, вычислить результат применения каждого входного символа к этой паре состояний и записать полученные пары состояний в соответствующие ячейки рассматриваемой строки.
3. Для каждого элемента таблицы, полученного на шаге 2, существует три возможных варианта. Если элемент - пара одинаковых состояний, то для этой пары не требуется никаких действий. Если элемент - пара состояний, которые уже использовались как метка строки таблицы, то для нее также никаких действий не требуется. Наконец, если элемент - это пара разных состояний, которые еще не использовались как метка, то для нее нужно добавить строку и пометить ее этой парой. В данном случае порядок состояний s, t или t, s неважен (эквивалентность симметрична). После того, как проделаны необходимые действия с каждой парой строки, перейти к пункту 4.
4. Если все строки таблицы эквивалентности заполнены, исходная пара состояний и все пары состояний, порожденные в ходе проверки эквивалентны и проверка закончена. Если таблица не заполнена, нужно обработать по крайней мере одну строку и для нее применяется шаг 2.

На рис. 3.8 (б) приведена таблица, построенная по предложенному алгоритму и проверяющая эквивалентность состояний 0,1 автомата с рис. 3.8 (а). Таблица полностью заполнена, следовательно 0(1. Но предложенный алгоритм дает значительно больше результатов. Кроме (0,1) эквивалентны (0,2), (3,5), (3,7) и (5,7). Из 0(1 и 0(2 следует 1(2, то есть состояния 0,1,2 эквивалентны. Аналогично эквивалентны и состояния 3,5,7. Используя полученные результаты и сократив эквивалентные столбцы, получим новую таблицу (рис. 3.8 (в)).

3.2.2. Недостижимые состояния.

Среди состояний автомата могут быть такие, которые недостижимы из начального состояния ни для какой входной цепочки. На рис 3.8 (а) и 3.8 (в) таким является состояние 4. Такие состояния называются недостижимыми и столбцы, соответствующие этим состояниям, можно удалить, получив автомат с меньшим числом состояний.
Для любого конечного автомата довольно просто составляется список достижимых состояний:
1. Начать список начальным состоянием.
2. Для каждого состояния, уже включенного в список, добавить все еще не занесенные в него состояния, которые могут быть достигнуты из этого нового состояния под действием каждого входного символа.
Если эта процедура перестает давать новые состояния, то все достижимые состояния уже получены, а все остальные можно удалить как недостижимые. Число шагов процедуры ограничено числом состояний.

Пример 3.4. На рис. 3.9 (а) приведена таблица переходов автомата с начальным состоянием s0. Сформируем для него список достижимых состояний, по предложенному алгоритму. Вначале занесем в список s0. Затем добавим к нему s1 и s5. Из s1 имеется переход в s2 и s7, а из s5 - в s3 и s1, причем новым является только состояние s3. Из s2, s7 и s3 нет переходов в новые состояния, следовательно, окончательный список достижимых состояний
s0 s1 s5 s2 s7 s3.
Оставшиеся состояния s4, s6 и s8 - недостижимы. Удалив соответствующие им столбцы, получим таблицу, представленную на рис. 3.9 (б).
13 EMBED Word.Picture.6 1415(

Будем говорить, что автомат приведенный (минимальный), если он не содержит недостижимых состояний и никакие два его состояния неэквивалентны друг другу.

Если автомат не приведенный, то можно получить эквивалентный ему автомат, с меньшим числом состояний, либо исключая недостижимые состояния, либо объединяя эквивалентные в одно состояние. Приведенный автомат, полученный таким способом, имеет число состояний меньшее, чем исходный (если он уже не был приведенным), и может быть компактно реализован на вычислительной машине.
Метод нахождения недостижимых состояний, приведенный выше, достаточно эффективен. Однако, использовать тест эквивалентности для минимизации автоматов нецелесообразно, так как он позволяет обработать одновременно только два состояния. Далее предлагается более эффективный способ поиска и объединения эквивалентных состояний.

3.2.3. Метод разбиения

Этот метод состоит в разбиении множества состояний автомата на непересекающиеся подмножества или блоки, такие, что неэквивалентные состояния попадают в разные блоки. Рассмотрим этот метод на примере автомата, таблица которого представлена на рис. 3.10 (а).
13 EMBED Word.Picture.6 1415
Сначала разбиваем множество его состояний на два блока, один из которых содержит отвергающие, а другой - допускающие состояния:
P0=({1,2,3,4},{5,6,7})
Ни одно из состояний первого блока неэквивалентно состояниям из второго блока, так как нарушается условие подобия. Посмотрим, что происходит с состояниями блока {1,2,3,4} под воздействием символа a. Состояния 3,4 переходят в состояния 1,4 из блока 1, а состояния 1,2 переходят в 6,7 из второго блока. Это означает, что для любого состояния из множества {1,2} и любого состояния из {3,4} соответствующие состояния - приемники неэквивалентны по входу a. Это нарушает условие преемственности и поэтому мы можем заключить, что ни одно из состояний {1,2} не эквивалентно ни одному из состояний {3,4}. Это позволяет провести новое разбиение:
P1=({1,2},{3,4},{5,6,7})
причем состояния из разных блоков всегда неэквивалентны.
Теперь попробуем найти такой входной символ и блок в P1, чтобы его можно было разбить на новые блоки, относительно этого входного символа. Так повторяем до тех пор, пока ни одно разбиение невозможно. Например, {3,4} из P1 разбивается относительно a и получается
P2=({1,2},{3},{4},{5,6,7})
Блок {5,6,7} из P2 разбивается относительно a или b и получается
P3=({1,2},{3},{4},{5},{6,7})
Полученное P3, не допускает дальнейшего разбиения. Действительно, блок {1,2} по a переходит в блок {6,7}, а по b - в {3}; блок {6,7} по a переходит в {4}, а по b - в {1,2}; остальные блоки имеют по одному состоянию.
Когда процедура разбиения закончена, состояния внутри каждого блока эквивалентны, то есть их можно объединить и получить минимальный автомат (см. рис. 3.10 (б)), так как недостижимых состояний в рассматриваемом примере не было. В общем случае процедура разбиения должна сопровождаться удалением недостижимых состояний в целях получения минимального автомата.
Попрактиковавшись, можно научиться опознавать эквивалентные состояния (нетерминалы), которые приводят к одной и той же ситуации, но каким бы ни было число ненужных состояний в автомате (нетерминалов в грамматике), с помощью предложенных алгоритмов всегда можно получить минимальное описание.

3.3. Линейное сжатие и ускорение автоматов

Автомат называется линейно-огранниченным по памяти, если для обработки цепочки длины n он использует не более p(n ячеек памяти.

Автомат называется линейно-ограниченным по времени, если для обработки цепочки длины n он требует не более c(n шагов по времени.
Здесь p,c ( 1 - некоторые малые константы.

Справедлива следующая теорема о линейном сжатии.
Теорема 3.1. Если язык распознается (обрабатывается) автоматом с оценкой p(n по памяти, то можно построить автомат, распознающий тот же язык с оценкой p(n/k, где k - целое число (n ( k ( 1).

Доказательство. (Проведем его конструктивно, построением “сжатого” автомата для общего случая, когда автомат является преобразователем, то есть не только читает, но и пишет символы на ленту).
Пусть 13 EMBED Equation.2 1415 - внешний алфавит, 13 EMBED Equation.2 1415 - внутренний алфавит (множество состояний) исходного автомата, а k - заданная константа.
Построим новый внешний алфавит
13 EMBED Equation.2 1415,
состоящий из упорядоченных последовательностей по k символов старого алфавита и новое множество состояний 13 EMBED Equation.2 1415, где 13 EMBED Equation.2 1415
Смысл здесь состоит в том, что k старых символов из A предполагается записывать в одну клетку входной ленты.
Построим правила переходов. Пусть эти правила в исходном автомате имели вид:
13 EMBED Equation.2 1415 ,
что означает: “читая с ленты символ 13 EMBED Equation.2 1415и находясь в состоянии 13 EMBED Equation.2 1415, автомат записывает на ленту символ 13 EMBED Equation.2 1415, осуществляет сдвиг головки 13 EMBED Equation.2 1415, где 13 EMBED Equation.2 1415 может принимать значения 13 EMBED Equation.2 1415 (влево), 13 EMBED Equation.2 1415 (вправо) и 13 EMBED Equation.2 1415 (остаться на месте), и переходит в состояние 13 EMBED Equation.2 1415“. При построении правил для нового автомата надо учитывать тот факт, что новый автомат обозревает сразу k букв старого алфавита, но на самом деле исходный автомат смотрел на 13 EMBED Equation.2 1415-тую букву из этих k.
Правила перехода нового автомата будут иметь вид:
(а) если 13 EMBED Equation.2 1415 то
13 EMBED Equation.2 1415
где
13 EMBED Equation.2 1415 если в исходном автомате был сдвиг 13 EMBED Equation.2 1415 входной головки;
13 EMBED Equation.2 1415 если в исходном автомате был сдвиг 13 EMBED Equation.2 1415;
13 EMBED Equation.2 1415 если в исходном автомате был сдвиг 13 EMBED Equation.2 1415;
(б) если 13 EMBED Equation.2 1415 и в исходном автомате был сдвиг 13 EMBED Equation.2 1415, то
13 EMBED Equation.2 1415
(в) если 13 EMBED Equation.2 1415 и в исходном автомате был сдвиг 13 EMBED Equation.2 1415, то
13 EMBED Equation.2 141513 EMBED Equation.2 1415 (

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

Теорема 3.2. Для любого конечного автомата можно построить эквивалентный ему автомат, распознающий цепочки длины n за n/k шагов, где k - целое число (n ( k ( 1).

Доказательство. Сожмем исходный автомат в k раз и заменим каждые k шагов исходного автомата одним шагом в новом ускоренном автомате. Для этого, группы правил перехода исходного автомата, имеющие вид
13 EMBED Equation.2 1415
заменим на правила
13 EMBED Equation.2 1415. (

Пример 3.5. Пусть автомат распознает цепочки вида dobyto, doto, doby и никаких других. Каждая правильная цепочка завершается символом #. Таким образом внешний алфавит предложенного автомата A = {d,o,b,t,#}. и его можно определить, используя восемь состояний с таблицей переходов, представленной на рис 3.11 (а).

13 EMBED Word.Picture.6 1415
Ускорим этот автомат в два раза, а для этого сначала сожмем его вдвое и получим новый входной алфавит, содержащий пары символов
13 EMBED Equation.2 1415 = {, , , <# >, , , ...}.
Хотя таких пар будет всего 25, перечислять их все не имеет смысла. Правильные сочетания - это четыре первых пары приведенного множества. Встреча со всеми остальными всегда приводит к ошибке.
Новый автомат строим, заменяя пары правил перехода исходного автомата на одно правило результирующего. Например, правила
dq0 ( q1
oq1 ( q2
заменяем на
Q0 ( Q2 ,
а правила
bq2 ( q3
yq3 ( q4
на
Q2 ( Q4 .
В результате получим функциональную таблицу, приведенную на рис. 3.11 (б). Полученный автомат, обрабатывает входные цепочки за n/2 шагов. (

Выводы для практики. Реально в одну позицию - байт невозможно записать несколько символов, но используя команды ЭВМ для работы со строками или процедуры, подменяющие их, можно за одно обращение к ним пересылать или сравнивать группы символов. Если в языке требуется определенная последовательность терминальных символов в какой-то части цепочки, то соответствующую часть программы можно линейно сократить и ускорить. Так вместо группы правил
S ( wA
A ( hB
B ( iC
C ( lD
D ( eE
при обработке ключевого слова while вполне можно записать
S ( while A.
Аналогичными могут быть правила
N1 ( if N2
M0 ( integer M1
и т.п.

Упражнения.

3.1. Постройте детерминированные А-грамматики для следующих цепочек, завершающихся символом “;”:
(a) целых чисел без знака и беззначащих нулей;
(б) четных целых чисел без знака;
(в) идентификаторов, содержащих четное количество символов;
(г) для цепочек из упражнения 1.5.

3.2. Постройте конечный автомат, который будет распознавать слова go to , причем между ними может быть произвольное число пробелов, включая нулевое.

3.3. Постройте конечные распознаватели для описанных ниже множеств цепочек из нулей и единиц:
(а) число единиц четное, а нулей - нечетное;
(б) между вхождениями единиц четное число нулей;
(в) за каждым вхождением пары 11 следует 0;
(г) каждый третий символ - единица;
(д) имеется по крайней мере одна единица.

3.4. Постройте конечный автомат с входным алфавитом {0,1}, который допускает в точности такое множество цепочек:
(а) все входные цепочки;
(б) все входные цепочки, кроме пустой;
(в) ни одной входной цепочки;
(г) входную цепочку 101;
(д) две входные цепочки: 01 и 0100;
(е) все входные цепочки, начинающиеся с 0 и заканчивающиеся на 1;
(ж) все цепочки, не содержащие ни одной единицы;
(з) все цепочки, содержащие в точности три единицы;
(и) все цепочки, в которых перед и после каждой единицы стоит 0;

3.5. Опишите словами множества цепочек, распознаваемых каждым из следующих автоматов:
13 EMBED Word.Picture.6 1415

3.6. Постройте детерминированную А-грамматику по следующей недетерминированной:
S ( aA(aB(bB(bD
A ( aB(aS(bD
B ( cS(cB(bD(b
D ( dD(dB(bB(bA(a(c

3.7. Опишите словами множества цепочек, распознаваемых каждым из недетерминированных автоматов, изображенных на рисунке.
13 EMBED Word.Picture.6 1415

3.8. Найдите детерминированный автомат, эквивалентный следующему недетерминированному:
13 EMBED Word.Picture.6 1415
3.9. Найдите различающую цепочку (если она существует) для такой пары автоматов:
13 EMBED Word.Picture.6 1415

3.10. Для каждого из автоматов, приведенных ниже, найдите входную цепочку или цепочки с минимальной суммарной длиной, такие, что под их действием
(а) каждое состояние имеет место хотя бы раз;
(б) каждый переход происходит хотя бы раз.

13 EMBED Word.Picture.6 1415
3.11. Постройте конечный автомат, который будет допускать только те цепочки, которые можно построить из подцепочек go, goto, too, on. Возможны повторения, но не пересечения. Так, одна из допустимых цепочек goongotoongotooon. Можно сначала построить недетерминированный автомат, а затем преобразовать его в детерминированный.

3.12. Найдите недостижимые состояния автомата

13 EMBED Word.Picture.6 1415

3.13. Найдите минимальные эквивалентные таблицы переходов для следующих автоматов:
13 EMBED Word.Picture.6 1415


13PAGE 15


13PAGE 144315





Приложенные файлы

  • doc 7731125
    Размер файла: 681 kB Загрузок: 0

Добавить комментарий