Анализ основ грамматики по регулярным выражениям. Сущность способов, с помощью которых можно задавать формальные языки. Построение конечного автомата на основе леволинейной грамматической концепции. Стройная система для распознавания идентификаторов.
Аннотация к работе
По сути это строка-образец (англ. pattern, по-русски ее часто называют «шаблоном», «маской»), состоящая из символов и метасимволов и задающая правило поиска. Регулярные грамматики произвели прорыв в электронной обработке текстов в конце XX века. Многие современные языки программирования имеют встроенную поддержку регулярных выражений. Регулярные грамматики используются некоторыми текстовыми редакторами и утилитами для поиска и подстановки текста. Например, при помощи регулярных выражений можно задать шаблоны, позволяющие:-найти все последовательности символов «кот» в любом контексте, как то: «кот», «котлета», «терракотовый»;Множество языков, получаемое из элементарных языков в результате применения конечного числа регулярных операций, - регулярные множества. Способ их описания - регулярные выражения и недетерминированные конечные автоматы, допускающие цепочки из этих множеств. Тогда для алфавита V регулярные множества определяются рекурсивно: 1. Фактически регулярные множества - это множества цепочек символов над заданным алфавитом, построенные определенным образом (с использованием операций объединения, конкатенации и итерации). Три основных способа, с помощью которых можно задавать регулярные языки - это:-регулярные (праволинейные и леволинейные) грамматики,-конечные автоматы (КА) и-регулярные множества (равно как и обозначающие их регулярные выражения).Множество называется замкнутым относительно некоторой операции, если в результате выполнения этой операции над любыми элементами, принадлежащими данному множеству, получается новый элемент, принадлежащий тому же множеству. Например, множество целых чисел замкнуто относительно операций сложения, умножения и вычитания, но оно не замкнуто относительно операции деления - при делении двух целых чисел не всегда получается целое число. Регулярные множества (и однозначно связанные с ними регулярные языки) замкнуты относительно многих операций, которые применимы к цепочкам символов. Например, регулярные языки замкнуты относительно следующих операций:-пересечения; Лемма о разрастании для регулярных языков формулируется следующим образом: если дан регулярный язык и достаточно длинная цепочка символов, принадлежащая этому языку, то в этой цепочке можно найти непустую подцепочку, которую можно повторить сколь угодно много раз, и все полученные таким способом новые цепочки будут принадлежать тому же регулярному языку.Регулярные выражения и регулярные грамматики связаны между собой следующим образом:-для любого регулярного языка, заданного регулярным выражением, можно построить регулярную грамматику, определяющую тот же язык; Регулярные выражения и недетерминированные конечные автоматы связаны между собой следующим образом:-для любого регулярного языка, заданного регулярным выражением, можно построить конечный автомат, определяющий тот же язык; -для любого регулярного языка, заданного конечным автоматом, можно получить регулярное выражение, определяющее тот же язык. Алгоритм построения регулярного выражения по конечному автомату здесь не представляет интереса, поскольку проще построить грамматику, эквивалентную заданному конечному автомату, а потом уже найти регулярное выражение для заданного грамматикой языка. Строим множество состояний автомата Q, Состояния автомата строятся таким образом, чтобы каждому нетерминальному символу из множества VN грамматики G соответствовало одно состояние из множества Q автомата М.Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. (пустая строка) ? обозначает строку, не содержащую ни одного символа. (символьный литерал) «a», где a - символ алфавита ?. и следующие операции: (сцепление, конкатенация) RS обозначает множество {?? | ? ? R & ? ? S}. * () {}, которые могут быть предварены символом \ (обратная косая черта) («экранированы», «защищены») для представления их самих в качестве символов текста. Если требуется указать символы, которые не входят в указанный набор, то используют символ ^ внутри квадратных скобок, например [^0-9] означает любой символ, кроме цифр.Рассмотрим грамматику G({"a", "(", "*", ")", "{", "}"}, {S.C.K}, Р, S) (символы а, (, *, ), {, } из множества терминальных символов грамматики взяты в кавычки, чтобы выделить их среди фигурных скобок, обозначающих само множество): Р:S ® С) | К} После преобразования получим леволинейную автоматную грамматику следующего вида: G"({"a", "(", "*",.")", "{", "}"}, {S, D, C, E, K}, P", S): Р":S ® E) | К} Построим множество состояний автомата: Q = VNE{H}= {S, E, C, D, K, H}. В качестве алфавита входных символов автомата берем множество терминальных символов грамматики. Это недетерминированный конечный автомат, поскольку существует состояние, в котором множество, получаемое с помощью функции переходов по одному и тому же символу, имеет более одного следующего состояния.
План
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ГРАММАТИКИ ПО РЕГУЛЯРНЫМ ВЫРАЖЕНИЯМ
1.1 Сущность регулярных операций и выражений
1.2 Свойства регулярных языков
1.3 Взаимосвязь регулярных множеств, регулярных грамматик и конечных автоматов
ГЛАВА 2. ПРАКТИКА СОЗДАНИЯ ГРАММАТИКИ ПО РЕГУЛЯРНЫМ ВЫРАЖЕНИЯМ И ПОСТРОЕНИЕ ДЕРЕВА ВЫВОДА
2.1 Состав и синтаксис регулярных выражений
2.2 Пример построения конечного автомата на основе заданной грамматики
2.3 Разработка программы грамматики по регулярным выражениям и построение дерева вывода