БНФ-нотация и КС-грамматики.

Нотация Бэкуса-Наура Для формального задания различных грамматик формальных языков также необходим язык. Такой язык называется метаязыком. Исторически первым метаязыком является нотация Бэкуса-Наура, или БНФнотация, которая названа так в честь Дж.Бэкуса (который был главным разработчиком первого компилятора для языка Фортран) и Питера Наура (который играл основную роль в разработке одного из первых алгоритмических языков – Алгола-60). Эта нотация, использованная впервые для строгого определения Алгола-60, была предшественницей правил порождающей КС-грамматики Хомского. Нетерминалы здесь помещаются в угловые скобки, символ '::=' используется вместо стрелки "→". Именно здесь было использовано упрощение, при котором альтернативы одного и того же нетерминала записываются в правой части одного правила через знак '|', имеющий смысл "либо". Расширенная БНФ-нотация включает две конструкции, полезные при спецификации практических языков программирования. Первая с помощью фигурных скобок позволяет легко описать повторение 0 или произвольное число раз некоторой цепочки. Например, синтаксис Турбо-Паскаля (1985 г.) описывает структуру описаний переменных так: <variable-declaration-part>::=var <variable-declaration> {; <variable-declaration>} При замене нетерминала левой части продукции содержимое фигурных скобок может повторяться произвольное число раз, в том числе и ни разу. Это, очевидно, похоже на операцию итерации Клини для регулярных множеств, что можно, конечно, представить так: {β} в БНФ эквивалентно (β)* в регулярных выражениях. В общем, продукция БНФ А::=α{β}γ эквивалентна трем продукциям: А→αВγ, В→Вβ и В→ε в стандартной записи грамматик Хомского. Вторая конструкция с помощью квадратных скобок определяет опцию – необязательный элемент. Например, целая константа может быть описана как: <integer-constant>::= [ + | - ] <digit> {<digit>} Эта спецификация задает возможность отсутствия знака перед целой константой, представляющей собой цепочку из одной или более цифр. В общем, продукция БНФ А::=α[β]γ эквивалентна двум продукциям: грамматики Хомского А→αβγ и А→αγ. г.

Часто нетерминалы в БНФ не выделяются никак, в то время как терминалы явно выделяются парой апострофов, а вместо символа '::=' используется просто '=': ident = letter { letter | digit } integer-constant =[ '+' | '-' ] digit { digit } Итак, БНФ-нотация – это просто удобная форма записи правил КС-грамматик Хомского как регулярных выражений (а не цепочек символов). Очевидно, что такое обобщение не выводит грамматику из класса КС-грамматик. Язык, который может быть специфицирован одним регулярным выражением, может быть представлен одним выражением в БНФ-нотации или же грамматикой типа 3 (автоматной грамматикой).

Грамматики типа 3 (регулярные) удобны для генерирования символов, которые создаются во время лексического анализа, но они не очень подходят для описания способов объединения этих символов в предложения типичных языков высокого уровня. Например, как уже отмечалось выше, согласование скобок нельзя специфицировать с помощью грамматики типа 3. КСграмматики (типа 2), хотя и не могут специфицировать все свойства типичных языков программирования, являются более универсальными и поэтому более пригодными в качестве основы для фазы синтаксического анализа (разбора) компиляции. КС-грамматики традиционно служат основой для фазы синтаксического анализа компиляции. Если какой-либо язык программирования нельзя генерировать с помощью КС-грамматики, всегда можно найти такую КС-грамматику, которая генерирует надмножество языка, т.е. язык, включающий в себя заданный язык программирования. Применение такой грамматики для синтаксического анализа означает, что ряд ограничений в реальном языке (например, обязательное объявление всех идентификаторов в программе) не будет проверяться анализатором. Однако в компиляторе нетрудно предусмотреть другие действия по выполнению необходимых проверок в исходной программе (например, за счет применения таблицы символов). Из определения КС-грамматики ясно, что класс КС-грамматик более мощный (т.е. может генерировать больше языков), чем класс регулярных грамматик, но менее мощный, чем класс контекстно-зависимых (КЗграмматик). Язык { an bn | n ≥ 0 } является контекстно-свободным, но не регулярным. Он генерируется грамматикой с порождающими правилами S → aSb | ε С другой стороны, язык { an bn cn | n ≥ 0 } является контекстно-зависимым, а не контекстно-свободным. Контекстно-свободные грамматики имеют ряд характеристик, для которых справедливы следующие положения.

1) Каноническая форма а) Каждая КС-грамматика эквивалентна (т.е. генерирует тот же язык) грамматике в нормальной форме Хомского, т.е. со всеми порождающими правилами вида A → BC | a при обычных условиях, касающихся терминалов и нетерминалов. б) Каждая КС-грамматика эквивалентна грамматике в нормальной форме Грейбаха, т.е. со всеми порождающими правилами вида A → bα где α – строка нетерминалов (возможно, пустая). 2) Самовложение Если в грамматике G есть нетерминал A, для которого A ⇒ α1 A α2 (здесь α1 и α2 являются непустыми строками терминалов и/или нетерминалов), то о такой грамматике говорят, что она содержит самовложение. Например, две приведенные ниже грамматики содержат самовложение: 1) G1 = ({S}, {a, b}, P, S), где элементы P: S → aSb S → ε 2) G2 = ({S, A}, {begin, end,[,]}, P, S), где элементы P: S → begin A end S → ε A → [S] В последнем случае об A и S говорят, что они проявляют свойство самовложения. Теоретически любая КС-грамматика, не содержащая самовложения, эквивалентна регулярной грамматике и генерирует регулярный язык. С другой стороны, регулярная грамматика не может содержать самовложения. Именно самовложение позволяет эффективно различать КС (нерегулярные) и регулярные языки. Как видно из второго примера, согласование скобок и т.п. требует самовложения, поэтому его нельзя специфицировать посредством регулярной грамматики. С точки зрения разбора важно, что КС язык в состоянии распознавать автомат магазинного типа, эквивалентный конечному автомату, к которому добавлена память магазинного типа (стек). В функции автомата магазинного типа входит: а) чтение входного символа, замещение верхнего символа стека строкой символов (возможно, пустой) и изменение состояния или б) все то же самое, но без чтения входного символа. Автомат магазинного типа можно представить кратным (K, S, Г, δ, S0, Z0), где K – конечное множество состояний, S – входной алфавит, Г – алфавит магазинный, δ – множество переходов, S0 – начальное состояние, Z0 – символ магазина, который первоначально находится в стеке. Рассмотрим, например, автомат магазинного типа М, определенный следующим образом: K = {A}, S = { '(', ')'}, Г = {O, I}, S0 ={A}, Z0 = I. δ задается как δ (A, I, '(') = (A, IO) (что означает: в состоянии A с I в вершине стека при чтении '(' перейти к состоянию A и заменить I на IO). δ (A, O, '(') = (A, OO), δ (A, O, ')') = (A, ε), δ (A, I, ε) = (A, ε). Автомат М распознает согласуемые пары скобок. Открывающие скобки (представляемые как O) помещаются в стек и удаляются оттуда, когда встречается соответствующая закрывающая скобка. Строка скобок принимается, если после считывания всей строки стек остается пустым. Это – обычный способ принятия строк автоматами магазинного типа, хотя можно также определить автоматы магазинного типа, которые принимают строки по конечному состоянию. Эти два типа эквивалентны. Описанный выше автомат магазинного типа является детерминированным, т.е. для каждого допустимого входного символа имеется однозначный переход. Что же касается конечных автоматов, то мы можем также определять недетерминированные автоматы магазинного типа, содержащие множество переходов для заданного входа, состояния и содержания стека. При разборе происходит эффективное моделирование соответствующего автомата магазинного типа. Некоторые КС языки не могут анализироваться детерминированным образом (т.е. без возврата). Язык, допускающий детерминированный анализ, называется детерминированным; большинство языков программирования являются детерминированными или, по крайней мере, почти таковыми. Между КС-грамматиками и автоматами магазинного типа существует полное соответствие, и детерминированность автомата может зависеть от того, какая грамматика используется для генерирования языка. Метод разбора является детерминированным (для конкретной грамматики), если при разборе данной грамматики не требуется делать возврат. Некоторые языки можно разбирать детерминировано с помощью только одного из методов грамматического разбора. В частности, ряд языков можно разбирать детерминировано снизу вверх, но не сверху вниз. Далее мы будем рассматривать исключительно детерминированные методы разбора. Недетерминированные методы могут применяться к таким строчно-ориентированным языкам, как Фортран. Для языков же сильно рекурсивных (С++, Паскаль), где компилятор может быть вынужден возвращаться назад не только в текущей строке, но и в большой части программы, издержки, возникающие в случае возврата, просто неприемлемы. Другой недостаток возврата заключается в том, что он может вызвать отмену действий компилятора, которые осуществляются параллельно с синтаксическим анализом.

Лексический анализ

В информатике лексический анализ — процесс аналитического разбора входной последовательности символов (например, такой как исходный код на одном из языков программирования) с целью получения на выходе последовательности символов, называемых «токенами» (подобно группировке букв в словах). Группа символов входной последовательности, идентифицируемая на выходе процесса как токен, называется лексемой. В процессе лексического анализа производится распознавание и выделение лексем из входной последовательности символов.

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

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

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

Каждый токен можно представить в виде структуры, содержащей идентификатор токена (или идентификатор класса токена) и, если нужно, последовательность символов лексемы, выделенной из входного потока (строку, число и т. д.).

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