ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ
50. Формальные языки и грамматики. Классификация грамматик по Хомскому. Контекстно-свободные грамматики и их свойства. Распознаватели. Конечные автоматы.
Понятия грамматика, словарь, цепочка, язык.
Мы неформально определяем язык как подмножество множеств всех предложений из "слов" или символов некоторого основного словаря. Нас не интересует смысл этих предложений. Например, русский язык состоит из предложений, которые являются последовательностями, составленными из слов (Пусть, всегда, будет, солнце и т.д) и знаков пунктуации (например, запятые, точки, скобки). Язык программирования Паскаль состоит из программ, которые являются последовательностями, составленными из таких символов, как begin, end, знаков пунктуации, букв и цифр. Язык четных чисел состоит из последовательностей, составленных из цифр 1, ..., 9, в которых последней цифрой должны быть О, 2, 4, 6 или 8.
Алфавит - это непустое конечное множество элементов. Назовём элементы алфавита символами. Всякая конечная последовательность символов алфавита А называется цепочкой. Вот несколько цепочек "в алфавите" А={ а, b, c}: а, b, с, ab и ааса. Мы также допускаем существование пустой цепочки , т. е. цепочки, не содержащей ни одного символа. Важен порядок символов в цепочке; так цепочка ab не то же самое, что ba, и abca отличается от aabc. Длина цепочки х (записывается как |х|) равна числу символов в цепочке. Таким образом, | |=0, |a|=1, |abb|=3.
Заглавные буквы М, N, S, Т, U, используются как переменные или имена символов алфавита, в то время как строчные буквы u, v, w используются для обозначения цепочек символов. Таким образом, можно написать x=STV, и это означает, что х является цепочкой, состоящей из символов S, Т и V именно в таком порядке.
( Вместо термина цепочка (в английском языке - string) некоторые авторы используют термины строка или строчка. )
Если x и y - цепочки, то их катенацией xy является цепочка , полученная путем дописывания символов цепочки y вслед за символами цепочки x. Например, если x = XY, y = YZ, то xy = XYYZ и yx = YZXY. Поскольку Λ, не содержащая символов, то в соответствии с правилом катенации для любой цепочки x мы можем записать:
Λx = xΛ = x.
Если z = xy - цепочка, то x - голова, а y - хвост цепочки z. x - правильная голова, если y - не пустая цепочка, z - правильный хвост, если x - не пустая цепочка. Множества цепочек в алфавите обычно обозначаются заглавными буквами A, B . . . Произведение AB двух множеств цепочек A и B определяется как
AB = {xy | x  A, y  B}
и читается как "множество цепочек xy такое, что x из A, а y из B". Например, если A = {a, b}, B ={c, d} , то множество AB={ac, ad, bc, bd}. Поскольку Λx = xΛ =x справедливо для любой цепочки x, мы имеем
{Λ} A = A {Λ } =A.
Заметьте, что здесь символ Λ заключен в фигурные скобки. Произведение определено для множеств, тогда как Λ символом. {Λ } - это множество, состоящее из пустого символа Λ.
Мы можем определить степени цепочек. Если x - цепочка, то x0 - пустая цепочка , x1 = x, x2 = xx, и в общем случае
xn = x....x (n раз).
Для n>0 имеем xn = xxn-1 = ( xn-1 )x.
Так же можно определить степени алфавита A:
для n > 0:
A0 = { Λ }; A1 = A; An = AAn-1.
Используя это, определим две последние операции в этом разделе - итерацию A* множества A и усеченную итерацию A+ множества A:
A+ = A1  A2  ...  An  ...,
A* = A0  A+ .
Таким образом, если А={а, b}, то А* включает цепочки Λ, а, b, аа, аb, bа, bb, ааа, ааb...
Заметим, что А+=АА*=(А*)А.
Иногда удобнее и, как правило, нагляднее писать х... вместо ху, если нас не интересует у - остальная часть цепочки. Таким образом, три точки "..." обозначают любую возможную цепочку, включая и пустую. Наиболее часто встречаются следующие обозначения:
Обозначение Смысл
z = х ...    x - голова цепочки z, нам безразличен хвост.
z = ...х    x - хвост цепочки z. нам безразлична голова.
z = ...x...     х встречается где-то в цепочке z.
z = S...    Символ S-первый символ цепочки z.
z = ...S    Символ S - последний символ цепочки z.
z = ...S...    Символ S встречается где-то в цепочке z.
Грамматики.
Определение. Грамматикой G[Z] называется конечное, непустое множество правил; Z - это символ, который должен встретиться в левой части по крайней мере одного правила. Он называется начальным символом . Все символы, которые встречаются в левых и правых частях правил, образуют словарь V.
Если из контекста ясно, какой символ является начальным символом Z, мы будем писать G вместо G[Z].
0пpeдeлeние. В заданной грамматике G символы, которые встречаются в левой части правил, называются нетерминалами или синтаксическими единицами, языка. Они образуют множество нетерминальных символов VN.
Символы, которые не входят в множество VN, называются терминальными символами (или терминалами). Они образуют множество VT.
Таким образом, V=VN  VT. Как правило, нетерминалы мы будем заключать в угловые скобки <и>, чтобы отличить их от терминалов. В грамматике G1 символы 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 - терминальные, а <число>, <чс> и <цифра> - нетерминальные. Мы будем пользоваться надстрочными литерами в том случае, когда нам надо отличить различные вхождения одного и того же нетерминала. Так, можно написать <чс1 >: := <чс2 > <цифра> вместо <чс>::=<чс><цифра>.
Множество правил U::=х, U::=у,..., U::=z с одинаковыми левыми частями будем записывать сокращенно как U : :=х|у|...|z.
Определение языка, соответствующего грамматике.
Что является предложением этого языка? Для того чтобы ответить на эти вопросы, нам надо определить символы "=>" и "=>+", которыми мы интуитивно пользовались при выводе предложений. Неформально мы пишем v=>w, если можно вывести w из v, заменив нетерминальный символ в v на соответствующую правую часть некоторого правила.
0пределение. Пусть G - грамматика. Мы говорим, что цепочка v непосредственно порождает цепочку w, и обозначаем это как
v=>w,
если для некоторых цепочек х и у можно написать
v=xUy, w=xuy,
где U ::= u - правило грамматики G. Мы также говорим, что w непосредственно выводима из v или что w непосредственно приводится (редуцируется) к v. Цепочки x и у могут, конечно, быть пустыми. Следовательно, для любого правила U ::= u грамматики G имеет место U=>u. Чтобы задать грамматику G=(E,Sym,P), требуется указать:
 множество символов алфавита (или терминальных символов) E. Будем обозначать их строчными символами алфавита и цифрами;
 множество нетерминальных символов Sym (или метасимволов), не пересекающееся с E со специально выделенным начальным символом S. Будем обозначать их прописными буквами;
 множество правил вывода P определяющих правила подстановки для цепочек. Каждое правило состоит из двух цепочек (например, x и y), причем x должна содержать по крайней мере один нетерминал; и означает, что цепочку x в процессе вывода можно заменить на y. Вывод цепочек языка начинается с нетерминала S. Правило грамматики будем записывать в виде x : y. (Также употребляется запись x ::= y или x -> y)
Более строго, определим понятие выводимой цепочки:
 S - выводимая цепочка;
 если xyz - выводимая цепочка и в грамматике имеется правило y:t, то xtz - выводимая цепочка;
 определяемый грамматикой язык состоит из выводимых цепочек, содержащих только терминальные символы.
Для сокращения записи принято использовать символ "или" - "|".
Классификация языков по Хомскому
Хомский определил четыре основных класса языков в терминах грамматик, являющихся упорядоченной четверкой (V, Т, Р, Z), где
1. V - алфавит;
2. Т  V - алфавит терминальных символов;
3. Р - конечный набор правил подстановки;
4. Z - начальный символ, принадлежащий множеству V - Т.
Язык, порождаемый грамматикой, - это множество терминальных цепочек, которые можно вывести из Z. Различие четырех типов грамматик заключается в форме правил подстановки, допустимых в Р. Говорят, что G - это (по Хомскому) грамматика типа 0 или грамматика с фразовой структурой, если правила имеют вид
u:: = v, где u V и v V*. (5.1)
То есть левая часть u может быть тоже последовательностью символов, а правая часть может быть пустой. Грамматикам с фразовой структурой посвящено сравнительно немного работ. Если ввести ограничение на правила подстановки, то получится более интересный класс языков типа 1, называемых также контекстно-чувствительными или контекстно-зависимыми языками. В этом случае правила подстановки имеют следующий вид:
xUy::= хuу, где U  V - Т, u V+ и x,у V*. (5.2)
Термин "контекстно-чувствительная" отражает тот факт, что можно заменить U на u лишь в контексте х...у. Дальнейшее ограничение дает класс грамматик, полностью подобный классу, который мы используем; грамматика называется контекстно-свободной, если все ее правила, имеют вид
U::=u, где U  V-T и u V*. (5.3)
Этот класс назван контекстно-свободным потому, что символ U можно заменить цепочкой u, не обращая внимания на контекст, в котором он встретился. В КС-грамматике может появиться правило вида U := Λ, где Λ - пустая цепочка. Однако, чтобы не усложнять терминологию и доказательства, мы не допускаем таких правил в наших грамматиках. По заданной КС-грамматике G можно сконструировать Λ-свободную (или неукорачивающую) грамматику G1 (наш тип), такую, что L(G1) = L(G) - {Λ }. Более того, если G однозначна, то G1 также однозначна, поэтому фактически мы не вносим ограничений.
Если мы ограничим правила еще раз, приведя их к виду
U ::= N или U ::= WN, где N Т, а U и W  V - T, (5.4)
то получим грамматику типа 3, или регулярную грамматику. Регулярные грамматики играют основную роль как в теории языков, так и в теории автоматов. Множество цепочек, порождаемых регулярной грамматикой, "допускается" машиной, называемой автоматом с конечным числом состояний (которую мы определим в следующей главе), и наоборот. Таким образом, мы имеем характеристику этого класса грамматик в терминах автомата. Регулярные языки (те, что порождаются регулярными грамматиками), кроме того, называются регулярными множествами. Известно, что если L1 и L2 - регулярные множества, то таковыми же являются L1  L2, L1 ∩ L2, L1 - L2, L1•L2 = {xy | x  L1 и у L2} и L1* ={Λ}  L1  L12  L13  ... .
Вводя все большие ограничения, мы определили четыре класса грамматик. Таким образом, есть языки с фразовой структурой, которые не являются контекстно-чувствительными, контекстно-чувствительные языки, которые не являются контекстно-свободными, и контекстно-свободные, которые не являются регулярными.
В большинстве работ по теории формальных языков изучаются контекстно-свободные или регулярные языки, или их подмножества. Поэтому мы также ограничимся этими классами.
Один из основных вопросов, который возникает при рассмотрении грамматики, - это вопрос ее однозначности. К сожалению (или к счастью, в зависимости от того, как вы на это смотрите), было доказано, что эта проблема алгоритмически неразрешима для класса КС-грамматик. Это означает, что нельзя построить эффективный алгоритм (написать программу), который для любой заданной грамматики за конечное число шагов мог бы решить, является она однозначной или нет. Оказываются алгоритмически неразрешимыми и многие другие интересные вопросы, касающиеся контекстно-свободных языков (например, совпадают ли два языка, пересекаются ли два языка). В этом случае ищут интересные подклассы языков, для которых этот вопрос алгоритмически разрешим. Большинство доказательств теорем алгоритмической неразрешимости в теории формальных языков прямо или косвенно зависит от результатов теоремы Поста.
Доказано, что проблема однозначности для произвольной КС- грамматики алгоритмически неразрешима. Следующий вопрос, который может возникнуть: всегда ли существует однозначная грамматика для произвольного контекстно-свободного языка? Ответ отрицательный. Есть языки, для которых не существуют однозначные грамматики; первым это показал Парик. Такие языки называются существенно-неоднозначными. Пример такого языка: {ai bi cj | i, j ≥ 1} u {ai bj cj | i, j ≥ 1}.
Распознаватели.
Сканер представляет собой ту часть компилятора, которая читает литеры первоначальной исходной программы и строит слова, или иначе символы, исходной программы (идентификаторы, служебные слова, целые числа, одно- или двулитерные разделители, такие, как *, +, **, /*). Иногда символы называют атомами, или лексемами. В чистом виде сканер выполняет простой лексический анализ исходной программы в отличие от синтаксического анализа, и поэтому сканер называют также лексическим анализатором.
Сразу же возникает вопрос, почему лексический анализ нельзя объединить с синтаксическим анализом. В конце концов для описания синтаксиса символов можно воспользоваться БНФ. Например, в ФОРТРАНе идентификатор можно описать следующим образом:
<идентификатор> : : = буква {буква | цифра}
Однако есть несколько серьезных доводов в пользу отделения лексического анализа от синтаксического.
1. Значительная часть времени компиляции тратится на сканирование литер. Выделение же позволяет нам сконцентрировать внимание на сокращении этого времени. Одним из способов сокращения времени является программирование части или всего сканера на автокоде, а это сделать легче, если сканер выделен. Конечно же, мы не рекомендуем пользоваться автокодом, если не предполагается широкое и массовое применение компилятора.
2. Синтаксис символов можно описать в рамках очень простых грамматик. Если отделить сканирование от синтаксического распознавания, то можно разработать эффективную технику разбора, которая наилучшим образом учитывает особенности этих грамматик. Более того, тогда для конструирования сканеров можно разработать автоматические методы, в которых используется эта эффективная техника.
3. Так как сканер выдает символы вместо литер, синтаксический анализ на каждом шаге получает больше информации о том, что надо делать. Более того, некоторые специфические проверки контекста, необходимые при разборе символов, проще и уместнее выполнить в сканере, чем в формальном синтаксическом анализаторе. Например, легко выяснить, что означает в ФОРТРАНе инструкция D010I = ... , установив, какой из символов "," или "(" встречается раньше после знака равенства.
4. Развитие языков высокого уровня требует внимательного отношения как к лексическим, так и к синтаксическим свойствам языка. Разделение этих двух свойств позволит нам исследовать их независимо друг от друга.
5. Часто для одного и того же языка существует несколько различных внешних представлений. Например, в некоторых реализациях АЛГОЛа служебные слова заключены в кавычки и пробелы не играют никакой роли - они попросту игнорируются. В других же компиляторах служебные слова не могут использоваться как идентификаторы и смежные служебные слова и идентификаторы должны отделяться друг от друга по крайней мере одним пробелом. Внешние представления на перфоленте, картах и на телетайпе могут быть совершенно различными.
Выделение сканера позволит написать один синтаксический анализатор и несколько сканеров (которые написать проще и легче) по одному на каждое представление исходной программы и/или устройство ввода. При этом каждый сканер переводит символы в одинаковую внутреннюю форму, используемую синтаксическим анализатором.
Сканер можно запрограммировать как отдельный проход, на котором выполняется полный лексический анализ исходной программы и который выдает синтаксическому анализатору таблицу, содержащую исходную программу в форме внутренних символов. В другом варианте это может быть подпрограмма SCAN, к которой обращается синтаксический анализатор всякий раз, когда ему необходим новый символ. В ответ на каждый вызов SCAN распознает следующий символ исходной программы и отсылает его синтаксическому анализатору. Последний вариант, вообще говоря, лучше, поскольку нет необходимости конструировать целиком всю внутреннюю исходную программу и хранить ее в таком виде в памяти. Далее мы будем предполагать, что сканер должен быть реализован именно таким способом.
Будем считать, что исходная программа пишется в формате, в котором границы полей не фиксируются, т. е. в виде непрерывной последовательности литер.
Иногда остается неясным различие между символами и конструкциями более высокого уровня. Например, можно рассматривать в качестве символов как целое, так и вещественное число вида <целое> . <целое> или же можно рассматривать целое число как символ, а вещественное - как конструкцию более высокого уровня. В таких случаях мы будем делать произвольный выбор главным образом в интересах простоты изложения.
Конечный автомат – система объектов  , в которой  ,  ,  , Q, T, V – конечные множества (алфавиты), Q - алфавит состояний, Т - входной алфавит, V - выходной алфавит,   - функция переходов (определяется как отображение множества   в множество  , т.е.  ),   - функция выходов  , т.е. отображается на множестве V.
Упрощенная схема конечного автомата.
Состояние автомата отождествляется с состоянием внутренней памяти. Внутреннее состояние зависит от состояния входа в данный момент и от внутреннего состояния в предыдущий момент времени. Состояние автомата задается совокупностью внутреннего состояния и состояния входа.
Функция перехода   описывает смену внутреннего состояния автомата, т.е. изменение содержимого внутренней памяти в зависимости от того, что в ней хранилось до изменения входного символа и от того, как изменилось состояние входа. Т.е. это функция двух аргументов:  .
Значение   зависит от   - это состояние, в котором окажется автомат после замены входного сигнала ai на aj, если он начинает работу, находясь в состоянии qi.
Если функция   по данному текущему состоянию к текущему входному символу указывает множество возможных следующих состояний, то автомат называется недетерминированным, т.е.

Если множество   содержит не более одного состояния для абсолютно любого q и a, то автомат называется недетерминированным.
Функция выходов   описывает изменение выходных символов автомата под действием входных символов и в зависимости от состояния внутренней памяти автомата  .
Значение   - тот символ, который установится на выходе автомата после замены входного символа ai на aj и перехода автомата из состояния qi к qk.

Если для некоторого состояния   значения   и   (или одного из них) не определены, то автомат V частичным (не полностью определенным).
Если множества   и   содержат точно по одному элементу для любых q, a, V, то автомат называется полным.
Способы задания конечных автоматов.
Q T
a1 a2 a3
q1 q3, V1 q3, V2 q2, V1
q2 q4, V1 q1, V1 q1, V1
q3 q2, V1 q3, V1 q3, V2
q4 q4, V1 q2, V1 q1, V2
I. Конечный способ.

Столбцы таблицы соответствуют различным входам автомата. Строки соответствуют состояниям автомата. В любой клетке таблицы записываются значения следующего состояния автомата и значение выходного сигнала, соответствующего следующему состоянию qk и Ve.
II. Граф перехода.
Вершины помечаются номерами состояний автомата. Дуги, соединяющие вершины, помечаются входным символом, который вызвал переход автомата из I-го состояния в j-тое, а также выходным символом, который устанавливается на выходе автомата в результате этого перехода.
Пусть автомат находится в состоянии q3, a1 – это устойчивое состояние. При замене а1 на а2 автомат перейдет в состояние q2, не задержится и перейдет в q1, затем в q3.
Детерминированным называется автомат, граф перехода которого не содержит вершин, имеющих одинаково помеченные дуги.
III. Матрица переходов.
Это точная копия графа перехода. Строки и столбцы матрицы переходов соответствуют записям над дугами соответствующих вершин.