Формальные языки и грамматики

Лекция 1: Формальные языки и грамматики 1 Основные понятия Язык - это заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого естественного или искусственного языка является алфавит, определяющий набор допустимых символов языка. Алфавит - это счетное множество допустимых символов языка. Будем обозначать это множество символом V. Согласно формальному определению, алфавит не обязательно должен быть конечным (перечислимым) множеством, однако все существующие языки строятся на основе конечных алфавитов. Цепочкой символов (или строкой) называют произвольную последовательность символов, записанных один за другим. Понятие символа (или буквы) является базовым в теории формальных языков и не нуждается в определении. Цепочки символов обозначаются греческими буквами: α, β, γ. Для цепочки символов важен состав и количество символов в ней, а также порядок символов в цепочке. Количество символов в цепочке называют длиной цепочки. Длина цепочки символов а обозначается как |α|. Очевидно, что если α = β, то и |α| = |β|. Основной операцией над цепочками символов является операция конкатенации (объединения или сложения) цепочек. Конкатенация (сложение, объединение) двух цепочек символов - это дописывание второй цепочки в конец первой. Конкатенация цепочек а и в обозначается как αβ. Так как в цепочке важен порядок символов, то очевидно, что операция конкатенации не обладает свойством коммутативности, то есть в общем случае существуют α и β такие, что αβ≠βα. Также очевидно, что конкатенация обладает свойством ассоциативности, то есть (αβ)γ = α(βγ). Можно выделить еще две операции над цепочками: − обращение цепочки - это запись символов цепочки в обратном порядке; обозначается как αR. Если α= «абвг», то αR= «гвба». Для операции обращения справедливо следующее равенство – существуют α, β: (αβ)R = βRαR; − итерация (повторение) цепочки n раз, где n∈N, n > 0 - это конкатенация цепочки самой с n собой n раз. Итерация цепочки α n раз обозначается как α . Для операции повторения 1 2 3 справедливы следующие равенства – существует α: α = αα, α = αα, α = ααα, ... и т.д. Среди всех цепочек символов выделяется одна особенная - пустая цепочка. Пустая цепочка символов - это цепочка, не содержащая ни одного символа. Пустая цепочка обозначается греческой буквой λ (иногда обозначается также латинской буквой е или греческой ε). Цепочка символов α является цепочкой над алфавитом V: α(V), если в нее входят только символы, принадлежащие множеству символов V. Для любого алфавита V пустая цепочка λ может как являться, так и не являться цепочкой λ(V). Это условие оговаривается дополнительно. Если V - некоторый алфавит, то: − V+ - множество всех цепочек над алфавитом V без λ; 10 − V* - множество всех цепочек над алфавитом V, включая λ. + Справедливо равенство: V* = V U {λ}. Языком L над алфавитом V - L(V) - называется некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. Из этого определения следуют два вывода: во-первых, множество цепочек языка не обязано быть конечным; во-вторых, хотя каждая цепочка символов, входящая в язык, обязана иметь конечную длину, эта длина может быть сколь угодно большой и формально ничем не ограничена. Все существующие языки подпадают под это определение. Большинство реальных естественных и искусственных языков содержат бесконечное множество цепочек. Также в большинстве языков длина цепочки ничем не ограничена. Цепочку символов, принадлежащую заданному языку , часто называют предложением языка, а множество цепочек символов некоторого языка L(V) - множеством предложений этого языка. Для любого языка L(V) справедливо: L(V)⊆V*. Язык определяется тремя способами: − Перечисление всех допустимых цепочек. − Указание способов порождения цепочек. − Определение метода распознавания цепочек языка. Основные понятия любого языка: − Синтаксис – это набор правил, определяющие допустимые конструкции языка. − Семантика – это раздел языка, определяющий значения предложений языка (смысл для всех допустимых цепочек языка). − Лексика (лексемы) – словарный запас языка. Для задания языка программирования необходимо: − Определить алфавит – множество допустимых символов . − Определить множество правильных программ языка (или конструкций языка) – определить синтаксис и семантику. − Задать смысл для каждой правильной программы. 2 Определение грамматики Грамматика (G) – это математическая система, определяющая язык в виде правил, порождающих цепочки, основанных на этом языке. Для языков программирования грамматика содержит два вида правил: ƒ Определение синтаксических конструкций языка. ƒ Определение семантических ограничений. Грамматика задается четырьмя составляющими G(VT,VN,P,S): ƒ ƒ ƒ ƒ VT– алфавит терминальных символов. VN– алфавит нетерминальных символов. P– множество правил грамматики, где правила – упорядоченная цепочка символов. S– стартовый символ грамматики. Для записи грамматики и формул чаще всего используют формулу Бекуса-Наура. Пример: g({0,1,..,9,-,+},{<число>,<чс>, <цифра>},P,<число>) 11 P: <число> -><чс>|+<чс>|-<чс> <чс>-><цифра>|<цифра><чс> <цифра> ->0|1|…|9 Кроме Бекуса-Наура существуют другие методы задания грамматики: 1 С помощью метасимволов: a b – означает, что в данном месте должна стоять одна цепочка. – означает, что цепочка может встречаться, а может не встречаться в данном месте. c – означает, что цепочка может не встречаться, может встречаться один раз, или более. d – служит для разделения символа внутри круглых скобок. e « » – служит для включения метасимволов в цепочку. 2 В графическом виде – грамматика представляется в форме диаграммы, в которой используются следующие фигуры: a Точка – обозначает начало или конец дуги. b Прямоугольник – обозначает нетерминальный символ. c Овал – обозначает терминальный символ. d Дуга (вектор) – означает движение к следующему правилу. 3 Распознаватели (разборщик) Распознаватель – это специальный автомат, позволяющий определить принадлежность цепочки к некоторому языку. Распознаватель выполняет элементарные операции: 1 2 3 4 Чтение очередного символа из входной цепочки. Сдвиг входной цепочки на заданное количество символов. Доступ к памяти или записи данных. Преобразование данных в памяти устройства управления и изменение состояния устройств управления. Конфигурация распознавателя определяется параметрами: 1 2 3 4 Содержимым входной цепочки символов. Положением считывающей головки. Состоянием устройств управления. Содержимым памяти. Виды распознавателей: 1 По виду считывающих устройств: a Односторонние b Двусторонние 12 2 По виду устройств управления: a Детерминированные – для каждой текущей конфигурации существует только одна следующая конфигурация. b Недетерминированный – распознаватель может перейти в несколько разных конфигураций из текущей. 3 По виду внешней памяти: a Без внешней памяти. b С ограниченной внешней памятью. c С неограниченной внешней памятью. Распознаватель решает основную задачу разбора: проверки соответствия написанных цепочек (человеком) заданному языку программирования. Задача разбора может быть реализована не для всех языков. Доказано, что четко формализовать разбор можно только для языков программирования на этапах лексического и синтаксического анализа. На этапах семантики существует большое количество неоднозначностей, поэтому данные задачи решаются частично. 2.1.4 Цепочка вывода. Сентенциальная форма вывода Вывод – это процесс порождения предложения языка на основе правил, определяющих язык грамматики. называется непосредственно выводимой из цепочк в грамматики , где также определен алфавит , , если в грамматике существует правило по правилам заданной этой грамматикой. называется выводимой из цепочки , если выполняется одно из двух условий: 1 непосредственно выводима из 2 Существует такая , что непосредственно выводима из . непосредственно выводима из , то есть , то есть , и . Последовательность называется цепочкой вывода, а одно преобразование называется шаг вывода. При количестве шагов вывод называется тривиальным, а если , то не тривиальным (нужно совершить больше шагов). Вывод называется законченным, если на основе цепочки нельзя больше делать ни одного шага вывода. Пример: . Цепочка символов называется сентенциальной формой грамматики , , если она выводима из целевого символа грамматики . Если , то цепочка символов называется конечной сентенциальной формой. Язык с заданной грамматикой – это множество всех конечных сентенциальных форм грамматики . Вывод называется левосторонним, если на каждом шаге вывода правила грамматики применяется к крайнему левому нетерминальному символу цепочки. Вывод называется правосторонним если меняется крайний правый символ. 13 2.1.5 Дерево вывода Дерево вывода грамматики – это граф, который соответствует некоторой цепочке вывода и удовлетворяет условиям: 1 Каждая вершина дерева обозначается символом грамматики. 2 Корнем дерева является вершина с целевым символом грамматики . 3 Листьями дерева (конечными вершинами) являются вершины, обозначенные терминальными символами или пустым символом. 4 Если узел графа обозначен нетерминальным символом, а связанные с ним узлы символами , при этом , то грамматике существует правило . Дерево можно строить двумя способами: 1 Сверху вниз (левосторонний способ). 2 Снизу вверх от листьев к целевому символу (правосторонний способ). Грамматика называется однозначной, если для каждой цепочки символов языка , заданной грамматикой , можно построить единственный левосторонний и единственный правосторонний граф или вывод. Если будет более одного вывода, то грамматика называется неоднозначной. Для создания грамматики языка программирования важно, чтобы она была однозначной. Для проверки однозначности грамматики существуют некоторые правила. Если хотя бы одно правило выполняется, то грамматика является неоднозначной. Также доказано, что в большинстве случаев возможно преобразование грамматики из неоднозначной в однозначную. Литература: [1]; [6].