МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ институт радиотехники, электроники и автоматики (технический университет)Кафедра: математического обеспечения вычислительных систем (МОВС)Дисциплина: «Теория вычислительных процессов и систем»Тема доклада:«Автоматы: модель конечного автомата, распознаватели и преобразователи. Анализаторы контекстно-свободных языков»Группа: ВСМ-10-99 Студент: Рашевец С.Г.Москва, 2001 год Автоматы: модель конечного автоматаКонечным автоматом (КА) называется формальная система вида:M(Q,V,,q0,F), где - Q – конечное множество состояний автомата; V – конечное множество входных символов (алфавит); - функция переходов, отображающая декартово произведение множеств V x Q в множество подмножеств Q q0 – начальное состояние автомата Q, q0 Q; F – непустое множество конечных состояний автомата FQ.Модель КА представляет конечное управление, которое читает символы по одному с линейной входной ленты последовательно с лева на право. Множество состояний Q состоит из состояний конечного управления. 0 1 0 1 1 1 1 0 1 0 Конечное управление Первоначально конечное управление находится в состоянии q0 и сканирует крайний левый символ цепочки символов из V, которая находится на входной ленте. Работа КА представляет собой последовательность шагов (тактов)На каждом шаге работы автомат находится в одном из своих текущих состояний Q, на следующем шаге он может прейти в другое состояние или остаться в текущем. То, в какое состояние автомат перейдет на следующем шаге работы, определяет функция переходов . Эта функция зависит не только от текущего состояния, но и от символа из алфавита V, поданного на вход автомата. КА называют полностью определенным, если в каждом его состоянии существует функция перехода для всех возможных символов, т.е. aV, qQ (a,q) = R, RQ. Работа КА продолжается до тех пор, пока на его вход поступает символы их входной цепочки V+ (V+ - множество всех цепочек над алфавитом V без пустой цепочки). Конфигурацию КА на каждом шаге работы можно определить в виде (q,,n), где q – текущее состояние автомата, qQ; - цепочка входных символов, V+, n – положение указателя в цепочке символов, nN{0}, n|| (N – множество натуральных чисел). Начальная конфигурация автомата (q0,,0); заключительная конфигурация автомата (f,,n), fQ, n=||, если fF. КА M(Q,V,,q0,F) принимает цепочку символов V+, если, получив на вход эту цепочку, он из начального состояния q0 может перейти в одно из конечных состояний fF. В противном случае КА не принимает цепочку символов. Язык L(M), заданный КА M(Q,V,,q0,F), - это множество всех цепочек символов, которые принимаются этим автоматом. Два КА эквивалентны, если они задают один и тот же язык. Различаю детерминированные и недетерминированные автоматы. КА M(Q,V,,q0,F) называют детерминированным конечным автоматом (ДКА), если в каждом из его состояний для любого входного символа функция перехода содержит не более одного состояния: aV, qQ: либо (a,q)={r}, rQ, либо (a,q)=. В противном случае КА называют недетерминированным. Если функция переходов ДКА определена для каждого состояния автомата, то автомат называется полностью определенным ДКА: aV, qQ: либо (a,q)=r, rQ. Для любого КА можно построить эквивалентный ему ДКА. При построении компиляторов чаще всего используют полностью определенный ДКА, т.к. моделировать его работу существенно проще, чем произвольного КА. На основе имеющейся регулярной грамматики можно построить эквивалентный ей конечный автомат, и наоборот, для заданного конечного автомата можно построить эквивалентную ему конечную грамматику. Распознаватели – метод конечного описания бесконечных языков, простейшим примером которых являются конечные автоматы. Конечные автоматы не могут распознавать все языки, порождаемые грамматиками, языки распознаваемые ими – языки 3-го типа – регулярные языки. Регулярные языки – самый простой тип языков и самый распространенный в области вычислительных систем. Регулярные языки лежат в основе простейших конструкций языков программирования – идентификаторов, констант, строк, комментариев и т.п. На их основе строятся языки ассемблеров, командные процессоры, символьные управляющие команды.^ Распознаватели и преобразователиКомпилятор, прежде чем построить результирующую программу эквивалентную исходной программе, прежде должен исходную программу распознать. Распознаватель (разборщик) – специальный алгоритм, который позволяет определить принадлежность цепочки символов некоторому языку. Задача распознавателя заключается в том, чтобы на основании исходной цепочки дать ответ, принадлежит ли она заданному языку или нет. Распознаватели – один из способов определения языка. В общем, виде условная схема работы алгоритма распознавателя (в компьютере такой схемы нет!):Входная цепочка символов a1 a2 an Рабочая память УУ (внешняя)Распознаватель, являющийся частью компилятора, представляет собой часть ПО компьютера. Компоненты:лента, содержащая исходную цепочку символов, и считывающая головка, обозревающая очередной символ в этой цепочке;устройство управления, которое координирует работу распознавателя, имеет некоторый набор состояний и конечную память (для хранения своего состояния и некоторой промежуточной информации);внешняя (рабочая) память, которая может хранить некоторую информацию в процессе работы распознавателя и в отличие от памяти УУ может иметь неограниченный объем.Распознаватель работает с символами своего алфавита – алфавита распознавателя. Алфавит распознавателя конечен. Он включает в себя все допустимые символы входных цепочек, а также некоторый дополнительный алфавит символов, которые могут обрабатываться УУ и храниться в рабочей памяти распознавателя. В процессе своей работы распознаватель может выполнять некоторые элементарные операции, такие как чтение очередного символа их входной цепочки, сдвиг входной цепочки на заданное количество символов (вправо или влево), доступ к рабочей памяти для чтения или записи информации, преобразование информации в памяти, изменение состояния УУ. Какие операции должны выполняться в процессе работы распознавателя, определяется в УУ. В начале каждого такта, как правило, считывается очередной символ из входной цепочки, и в зависимости от этого символа УУ определяет, какие действия необходимо выполнить. Состояние распознавателя (в начале каждого такта) определяется его конфигурацией, которая в процессе работы меняется. Конфигурация распознавателя определяется параметрами:содержание входной цепочки символов и положение считывающей головки в ней;состояние УУ;содержимое внешней памяти. Всегда задается определенная конфигурация, считающаяся начальной конфигурацией. В начальной конфигурации считывающая головка обозревает первый символ входной цепочки, УУ находиться в заданном начальном состоянии, а внешняя память либо пуста, либо содержит строго определенную информацию. Также, для распознавателя задается одна или несколько конечных конфигураций. В этом случае считывающая головка, как правило, находится за концом исходной цепочки. Язык, определяемый распознавателем, - множество всех цепочек, которые допускает распознаватель. Распознаватели классифицируют в зависимости от вида составляющих их компонентов и по типам языков.По компонентам:По видам считывающего устройстваОдносторонние распознаватели Допускают перемещение считывающей головки по ленте входных символов только в одном направлении.Двусторонние распознаватели Допускают перемещение считывающей головки относительно ленты входных символов в обоих направлениях.По видам устройства управления:Детерминированные Для каждой допустимой конфигурации распознавателя, которая возникла на некотором шаге его работы, существует единственно возможная конфигурация, в которую распознаватель перейдет на следующем шаге работы.Недетерминированные Чтобы распознаватель был назван недетерминированным, достаточно иметь хотя бы одну конфигурацию, допускающую существование некоторого множества конфигураций, возможных на следующем шаге работы.По видам внешней памяти:Распознаватели без внешней памяти В процессе работы используется только конечная память устройства управления, без доступа к внешней памяти.Распознаватели с ограниченно внешней памятью Размер внешней памяти ограничен в зависимости от длины исходной цепочки символов. Эти ограничения могут налагаться зависимостью объема памяти от длины цепочки – линейной, полиномиальной, экспоненциальной и т.д. Кроме того, для таких распознавателей может быть указан способ организации внешней памяти – очередь, стек, список и т.д.Распознаватели с неограниченной внешней памятью Предполагают, что для их работы может потребоваться внешняя память неограниченного объема (вне зависимости от длины входной цепочки). У таких распознавателей предполагается память с произвольным методом доступа.Эти три составляющие позволяют организовать общую классификацию распознавателей. Например, возможен такой тип: «двусторонний недетерминированный распознаватель с линейно ограниченной внешней памятью». Чем выше в классификации стоит распознаватель, тем сложнее создавать алгоритм, обеспечивающий его работу. Сложность распознавателя также напрямую связанна с типом языка, входные цепочки которого может принимать распознаватель.По типам языков: 1. Для языков с фразовой структурой Язык с фразовой структурой – самый сложный. Все естественные языки относятся к этому типу. Структура и значение фразы естественного языка может зависеть не только от контекста данной фразы, но и от содержания того текста, где эта фраза встречается. Одно и тоже слово в естественном языке может не только иметь различный смысл в зависимости от контекста, но и играть различную роль в предложении. Компиляторы, которые бы воспринимали программы, на основе этих языков отсутствуют, т.к. необходим распознаватель, равномощный машине Тьюринга – недетерминированный двусторонний автомат, имеющий неограниченную внешнюю память. Поэтому нельзя гарантировать, что за ограниченное время на ограниченных вычислительных ресурсах распознаватель завершит работу и примет решение о принадлежности входной цепочки заданному языку. Практического применения языки с фразовой структурой не имеют. 2. Для контекстно-зависимых языков Второй по сложности язык. В общей сложности на распознавание предложений языка, экспоненциально зависит от длины исходной цепочки символов. Т.е. уже можно прогнозировать максимально возможное время за которое будет принять решение о принадлежности цепочки данному языку и какие вычислительные ресурсы для этого потребуются. В этом случае распознавателями являются двусторонние недетерминированные автоматы с линейно ограниченной внешней памятью. Как правило, такие распознаватели применяются для автоматизированного перевода и анализа текстов на естественных языках, когда временные ограничения на разбор текста несущественны. А поскольку естественные языки более сложны чем контекстно-зависимые языки, то после такой обработки текста всегда требуется вмешательство человека. В компиляторах контекстно-зависимые распознаватели не применяются. 3. Для контекстно-свободных языков КС-языки лежат в основе синтаксических конструкций большинства современных языков программирования, на их основе функционируют некоторые довольно сложные командные процессоры, допускающие управляющие команды цикла и условия. Распознавателями являются односторонние недетерминированные автоматы с магазинной (стековой) внешней памятью – МП-автоматы. При простейшей реализации алгоритма работы такого автомата он имеет экспоненциальную сложность, однако путем некоторых усовершенствований можно добиться полиномиальной (кубической) зависимости времени, необходимого на разбор входной цепочки, от длины этой цепочки. Также среди КС-языков существует много классов языка, для которых эта зависимость квадратична или линейна. Поскольку скорость работы автомата имеет существенное значение, для анализа текстов на различных яках программирования применяются контекстно-свободные преобразователи. Среди всех КС-языков можно выделить класс детерминированных КС-языков, распознавателями для которых являются детерминированные автоматы. С магазинной (стековой) внешней памятью – ДМП-автоматы. Эти языки обладают свойством однозначности – для любого детерминированного КС-языка всегда можно построить однозначную грамматику. Для таких языков существует алгоритм работы распознавателя с квадратичной сложностью. Поскольку эти языки являются однозначными, именно они представляют наибольший интерес для построения компиляторов. Среди всех детерминированных КС-языков существуют такие классы языков, для которых возможно построить линейный преобразователь. Т.е. время принятия решения о принадлежности цепочки языку имеет линейную зависимость от длины цепочки. Синтаксические конструкции практически всех языков программирования могут быть отнесены к одному из таких классов языков. Сами языки программирования не могут быть полностью отнесены к типу КС-языков, поскольку предполагают некоторую контекстную зависимость в тексте исходной программы. Поэтому комбинация из распознавателя КС-языка и дополнительного семантического анализатора является наиболее эффективной с точки зрения разбора исходной программы. 4. Для регулярных языков Регулярные языки – самый простой тип языков. Они являются самым распространенным и используемым типом языков в области вычислительных систем. Они лежат в основе простейших конструкций языков программирования (идентификаторов, констант и т.п.), на их основе строятся многие мнемокоды машинных команд (языки ассемблеров), а также командные процессоры, символьные управляющие команды и другие подобные структуры. Распознавателями являются односторонние недетерминированные автоматы без внешней памяти – конечные автоматы рассмотренные выше. Этот тип распознавателя предполагает линейную зависимость времени на разбор входной цепочки от ее длины. Любой недетерминированный автомат всегда может быть преобразован в детерминированный. В компиляторах распознаватели на основе регулярных языков используются для лексического анализа текста исходно программы – выделения в нем простейших конструкций языка. Это позволяет существенно сократить объем исходной информации и упрощает синтаксический разбор программы. Компилятор должен не просто дать ответ, принадлежит или нет входная цепочка символов заданному языку, но и определить ее смысловую нагрузку. Распознаватель служит основой для синтаксического анализатора в компиляторе. Фактически работа распознавателя в составе компилятора сводится к построению в том или ином виде дерева разбора входной цепочки. Затем уже это дерево используется для синтеза результирующего кода. Если входная цепочка не принадлежит заданному языку – программа содержит ошибку – распознаватель должен установить факт присутствия ошибки во входной программе, по возможности определить тип ошибки и место в цепочке символов, где она встречается.^ Анализаторы контекстно-свободных языковТак как любая регулярная грамматика является КС-грамматикой (но не наоборот). А синтаксические конструкции языков программирования, как правило, могут быть описаны с помощью КС-грамматик. В применении КС-грамматик действуют лексические и синтаксические анализаторы. Лексический анализатор (или сканер) – часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы входного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора. Лексема (лексическая единица языка) – структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка. Лексемы естественных языков – слова. Теоретически – лексический анализатор не является обязательной частью компилятора. Все его функции могут быть выполнены на этапе синтаксического разбора, поскольку полностью регламентированы синтаксисом входного языка. Однако существуют причины по которым в состав практически всех компиляторов включают лексический анализ:- применение лексического анализатора упрощает работу с текстом исходной программы на этапе синтаксического разбора и сокращает объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и выкидывает всю незначащую информацию;- для выделения в тексте и разбора лексем возможно применять простую, эффективную и теоретически хорошо проработанную технику анализа, в то время как на этапе синтаксического анализа конструкций исходного языка используются достаточно сложные алгоритмы;- сканер отделят сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходной программы, структура которого может варьироваться в зависимости от версии входного языка – при такой конструкции компилятора для перехода от одной версии языка к другой достаточно только перестроить относительно простой лексический анализатор. В большинстве анализаторов лексический и синтаксический анализаторы – взаимосвязанные части. Возможны два принципиально различных метода организации их взаимосвязи: последовательный и параллельный. При последовательном варианте лексический анализатор просматривает весь текст исходной программы и преобразует его в структурированный набор данных – таблицу лексем. Где ключевые слова языка, идентификаторы и константы, как правило, заменяются на специально оговоренные коды (конкретная кодировка определяется при реализации компилятора). В этом варианте таблица лексем строиться полностью вся сразу, и больше к ней компилятор не возвращается. Всю дальнейшую обработку выполняют дальнейшие фазы компиляции. При параллельном варианте лексический анализ исходного текста выполняется поэтапно так, что синтаксический анализатор, выполнив разбор очередной конструкции языка, обращается к сканеру за следующей лексемой. При этом он может сообщить какую лексему следует ожидать. В процессе разбора при возникновении ошибки может происходить «откат назад», чтобы попытаться выполнить анализ текста на другой основе. Только после того, как синтаксический анализатор успешно выполнит разбор очередной конструкции языка, лексический анализатор помещает найденные лексемы в таблицу лексем и таблицу идентификаторов и продолжает дальнейший разбор. Лексический анализатор реализуется на основе конечных автоматов. Конечный автомат для каждой входной цепочки языка отвечает на вопрос о принадлежности цепочки языку, заданному автоматом. Также, сканер должен четко определить границы лексемы, которые в исходном тексте явно не заданны. И выполнить действия для сохранения информации об обнаруженной лексеме. Наиболее известной программой решающей задачу построения лексических анализаторов является программа LEX, созданная первоначально под UNIX, а затем реализованная практически для всех ОС, программа существенно упрощает процедуру создания лексических сканеров. Фактически описав в текстовом файле нужные лексемы в терминах регулярных выражений, на выходе программист получает текст исходной программы на заданном языке программирования (обычно на C). Текст исходной программы сканера может быть дополнен вызовами любых функций из любых библиотек (естественно поддерживаемых данным языком). Синтаксический анализатор – часть компилятора, которая отвечает за выявление основных синтаксических конструкций входного языка. В задачу синтаксического анализа входит: найти и выделить синтаксические конструкции в тексте входной программы, установить тип и проверить правильность каждой синтаксической конструкции и представить их в виде, удобном для дальнейшей генерации текста результирующей программы. В основе синтаксического анализатора лежит распознаватель текста входной программы на основе грамматики входного языка. Распознаватель дает ответ на вопрос о принадлежности цепочки символов заданному языку. Но поскольку задачи синтаксического анализатора шире, он должен имеет некий выходной язык, с помощью которого он передает следующим фазам компиляции всю информацию о найденных и разработанных синтаксических структурах. Те. Синтаксический анализатор является преобразователем с магазинной памятью МП-преобразователем. Синтаксически анализ – процесс, в котором исследуется таблица лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Основу любого синтаксического анализатора всегда составляет распознаватель, построенный на основе какого-либо класса КС-грамматик. Автоматизированное построение синтаксических анализаторов может быть выполнена с помощью программы YACC (исторически корни – также UNIX). Анализируемый язык описывается в виде, близком форме Бэкуса-Наура. Результат работы YACC является исходный текст синтаксического распознавателя на языке C. Литература1. Мартыненко Б.К. Языки и трансляции – СПб.: С.-Петербургский университет, 2001. 2. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение – СПб.: Питер, 2001.