Конечные автоматы и регулярные языки. Синтаксический анализ регулярных языков

Задачей синтаксического анализа считается проверка, принадлежит ли произвольная заданная цепочка a О T ^* языку L (G) для заданной грамматики G. На основе методов синтаксического анализа решаются задачи синтаксически управляемой обработки данных (например, текстов). Такой задачей является и задача трансляции. Регулярные языки и порождающие их А-грамматики используются, в основном, для лексического анализа - распознавания в тексте его лексических единиц, лексем, т.е. слов, из которых по более сложным правилам строится текст.

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

Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

Существуют различные способы задания конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки: , где

· — входной алфавит (конечное множество входных символов), из которого формируются входные цепочки, допускаемые конечным автоматом;

· — множество состояний;

· — начальное состояние ;

· — множество заключительных состояний ;

· — функция переходов, определенная как отображение , такое, что , т.е. значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).

Конечный автомат начинает работу в состоянии q₀, считывая по одному символу входной цепочки. Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Читая входную цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил цепочку x.

Конечные автоматы широко используются на практике, например, в синтаксических и лексических анализаторах, тестировании программного обеспечения на основе моделей.

Установим теперь соответствие между А-грамматиками и конечными автоматами. Грамматика G = (N, T, P, S) и автомат A = (Q, T, t, q ₀, F) называются соответствующими друг другу, если N = Q, S = q ₀, X ® aY О P Ы (X, a) ® Y О t, X ® e О P Ы X О F.

Для того, чтобы доказать, что в этом случае L (G) = L (A), введем понятие диаграммы А-грамматики. Это помеченный ориентированный граф, вершинами которого являются символы из N, помеченная дуга X - a ® Y соответствует правилу X ® aY. Если X ® e О P, то вершину X будем изображать двойным кружком.

Построенная А-грамматика для чисел представляется диаграммой

Очевидны также следующие леммы.

Л е м м а. X ® _G ^* aY Û в диаграмме грамматики есть путь из X в Y, метки дуг которого образуют цепочку a.

Л е м м а. Графы соответствующих друг другу грамматики и автомата совпадают.
Из лемм следует теорема

Т е о р е м а. L (G) = L (A) для соответствующих друг другу грамматики G и автомата A.

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

С л е д с т в и е 1. Класс регулярных языков совпадает с классом языков, допускаемых конечными автоматами.

В настоящее время широко стоит проблема синтаксического анализа текстов. В данное время существует много методов синтаксического анализа. Одним из таких методов является проверка по регулярным выражениям.

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

Синтаксический анализ программ на различных языках программирования имеет очень большое значение. Он позволяет избежать множества ошибок в программах. Синтаксический анализ на базе регулярных выражений является наиболее простым на начальных стадиях проверки программы, когда не требуется глубокий разбор всех лексематических и синтаксических средства выбранного языка

Разработка технологии обработки информации.

Ввод информации осуществляется из файла, имя файла будет являться одним из аргументов запуска программы. Предварительной подготовкой является:

- создание файла;

- заполнение его данными;

- размещение на носителе;

- доступном для программы;

- разрешение доступа для чтения.

Программа должна работать в пакетном режиме. Выходные данные будут записываться в стандартный поток вывода.

Структура технологического процесса обработки информации должна быть следующая:

- считать файл;

- удалить из файла все комментарии (сначала много строчные, затем одно строчные);

- построчно разделить оставшийся текст в массив строк;

- произвести синтаксический анализ каждой строки на различные операторы;

- для каждой части строки произвести дополнительный синтаксический анализ на математические и логические операции