Описание формальных грамматик

Итак, мы подошли к главному моменту изложения материала данного курса - описанию так называемых формальных грамматик. Важность формальных грамматик в обработке символьных данных, вообще в информатике сравнимо с важностью арифметики в математике, логики в философии и т.п. На принципах формальной грамматики проектируются и создаются новые языки программирования, пишутся программы для проверки орфографии и стиля, программируются "речевые" интерфейсы, создаются программы для коррекции ошибок и "оптимизации" выполнения программ. На основе формальной грамматики удалось "расшифровать" гармонию в шедеврах великих архитекторов, художников, композиторов. (Кстати говоря, большинство фуг И.С. Баха написаны так, что их порождает одна из грамматик)!

Формальная грамматика является частью алгебры и тесно связана с теорией групп и теорией автоматов. Но выводы формальной грамматики просты и понятны. Может быть, именно из-за этой "простоты" она "не в почете" ни у математиков, ни у гуманитариев. По крайней мере, по мнению автора, серьезных теоретических прорывов, начиная с середины 80-х годов прошлого века, в ней не наблюдается. Тем не менее, ее выводы в практике программирования применяются широко.

Выводы теории формальных грамматик используются в языках логического программирования (например, ПРОЛОГ) для построения деревьев вывода.

При чтении этого раздела Вам может быть потребуется обращаться как к предыдущим, так и последующим разделам. Более подробно материал из этого раздела представлен в [41].

10.1. Алфавит

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

О п р е д е л е н и е. Алфавит - это непустое конечное множество элементов.

В "классическом" языке алфавит - это набор литер. В фонетике - набор издаваемых человеком звуков речи. В музыке - это набор нот, и т.д.

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

Всякая конечная последовательность символов алфавита называется словом, или, более профессионально, цепочкой. Цепочками, состоящими из символов {a, b, c}, будут следующие последовательности: a, b, c, aa, ab, bc, ac, bb, abba и другие. Также допускается существование пустой цепочки Л - полное отсутствие символов. Важен также порядок следования символов в цепочке. Так, цепочки ab и ba - разные цепочки. Далее заглавные латинские буквы будут использованы как переменные и символы, а строчные латинские буквы будут обозначать цепочки. Например:

x = SVT

цепочка, состоящая из символов S, V и T, и именно в этом порядке.

О п р е д е л е н и е. Длиной цепочки называется число символов в этой цепочке. Она обозначается как |x|. Например: |Л| = 0, |A| = 1, |BA| = 2, |ABBA| = 4.

Если x и y являются цепочками, то их конкатенацией будет цепочка xy. От перестановки цепочек при конкатенации результат меняется (как и в теории групп). Если z = xy - цепочка, то x - голова, а y - хвост цепочки. Если нам безразлична голова цепочки, мы будем обозначать:

z = … x

а если нам безразличен хвост, мы будем писать:

z = x …

О п р е де л е н и е. Произведение двух множеств цепочек определяется как конкатенация всех цепочек, входящих в эти множества. Например, если множество A = {a, b}, а B = {c,d}, то:

AB = {ac, ad, bc, bd}

В произведении множеств, как и при конкатенации, порядок множителей существенен.

И при конкатенации цепочек, и при перемножении множеств цепочек истинным остается ассоциативный закон, записывающийся как:

z = (ab)c = a(bc) = abc

D = (AB)C = A(BC) = ABC

И, наконец, определим степень цепочки. Если x - непустая цепочка, то x0 = {Л}, x1 = x, x2 = xx, xn = x(x)(n-1). То же самое обстоит и со степенью множеств.

10.2. Терминальные и нетерминальные символы

Понятие терминальных и нетерминальных символов тесно связано с понятием правила подстановки (или продукции). Дадим его определение.

О п р е д е л е н и е. Продукцией, или правилом подстановки, называется упорядоченная пара ( U, x ), записываемая как:

U ::= x

где U - символ, а x - непустая конечная цепочка символов.

Символы, встречающиеся только в правой части, называются терминальными символами. Символы, встречающиеся и в левой, и в правой части правил, называются нетерминальными символами, или синтаксическими единицами языка. Множество нетерминальных символов обозначается как VN, а терминальных символов - VT.

О п р е д е л е н и е. Грамматикой G[Z] называют конечное, непустое множество правил, содержащее нетерминальный символ Z хотя бы один раз на множестве правил. Символ Z называют начальным символом. Далее мы все нетерминальные символы будем обозначать как <символ>.

[Пример 01]

Грамматика: "число"

<число> ::= <чс>
<чс> ::= <цифра>
<чс> ::= <чс><цифра>
<цифра> ::= 0
<цифра> ::= 1
<цифра> ::= 2
<цифра> ::= 3
<цифра> ::= 4
<цифра> ::= 5
<цифра> ::= 6
<цифра> ::= 7
<цифра> ::= 8
<цифра> ::= 9

Дадим еще определение:

О п р е д е л е н и е. Цепочка v непосредственно порождает цепочку w, если:

v = x<U>y, а w = xuy

где <U> ::= u - правило грамматики. Это обозначается как v => w. Мы также говорим, что цепочка w непосредственно выводима из v. При этом цепочки x и y могут быть пустыми.

О п р е д е л е н и е. Говорят, что v порождает w, или w приводится к v, если существует конечная цепочка выводов u0, u1, …, u[n] (n > 0), такая, что

v = u0 => u1 => u2 => … => u[n] = w

Эта последовательность называется выводом длиной n, и обозначается v =>+ w. И, наконец, пишут:

v =>* w, если v => w или v =>+ w

10.3. Фразы

О п р е д е л е н и е. Пусть G[Z] - грамматика, x - цепочка. Тогда x называют сентенциальной формой, если <Z> =>* x. Предложение - это сентенциальная форма, состоящая только из терминальных символов. Язык - это подмножество множеств всех терминальных цепочек.

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

О п р е д е л е н и е. Пусть G[Z] - грамматика. И пусть w = xuy - сентенциальная форма. Тогда u называется фразой сентенциальной формы w для нетерминального символа <U>, если:

Z =>* x<U>y и <U> =>+ u

Если же

Z =>* x<U>y и <U> => u

то цепочка u называется простой фразой.

Следует быть осторожным с термином "фраза". Тот факт, что <U> =>+ u (цепочка u выводима из <U> ) вовсе не означает, что u является фразой сентенциальной формы x<U>y; необходима также выводимость цепочки x<U>y из начального символа грамматики Z.

В качестве иллюстрации фразы рассмотрим [Пример 01] сентенциальную форму <чс>1. Значит ли это, что символ <чс> является фразой, если существует правило: <число> ::= <чс>? Конечно же, нет, поскольку невозможен вывод цепочки: <число><1> - из начального символа: <число>. Какие же фразы сентенциальной формы <чс>1? Рассмотрим вывод:

<число> => <чс> => <чс><цифра> => <чс><1>

Таким образом,

<число> =>* <чс> и <чс> =>+ <чс>1

<число>  => <чс><цифра> и <цифра> => 1

Следовательно, <чс>1 и 1 - фразы. Простой же фразой будет только 1.

О п р е д е л е н и е. Основой всякой сентенциальной формы является ее самая левая простая фраза.

Грамматика из [примера 01] описывает бесконечный язык, то есть содержащий в себе бесконечное число предложений. Это объясняется тем, что грамматика содержит правило: <чс> ::= <чс><цифра>, то есть в некотором смысле символ <чс> сам себя определяет.

В общем случае, если:

<U> =>+ … <U> …

мы говорим, что грамматика рекурсивна относительно символа <U>. Если же:

<U> =>+ <U> …

то имеет место левая рекурсия, а если

<U> =>+ … <U>

то имеет место правая рекурсия.

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

Отступление. Вообще, чем больше в грамматике рекурсивных правил, тем сложней и богаче язык и тем более сложные конструкции можно на нем описать. Это относится не только к языкам программирования, но и к "человеческим" языкам. Так, в одном из номеров журнала "Компьютерра" за 2007 год приводилась статья о языке одного бразильского индейского племени. В его языке почти отсутствовала рекурсия, характерная для большинства языков Европы и Азии. Это мешало индейцам из этого племени, например, воспринять Библию. Это позволило автору статьи сделать вывод, что чем более в языке народа рекурсии, тем более "прогрессивнее" и "цивилизованнее" народ. Автор статьи утверждает, что это пока лишь гипотеза, еще требующая подтверждения. Но эти выводы все равно подтверждают важность рекурсии при выборе грамматики.

10.4. Основные понятия и теоремы

В этом разделе обобщаются сведения, полученные на данной лекции в разделах 10.01 - 10.03, и в лекции 9. Прочтите этот раздел внимательно.

10.4.1. Синтаксические деревья и деревья вывода

Синтаксические деревья помогают понять синтаксис предложений. В качестве иллюстрации построим дерево для вывода предложения 22 из грамматики в [примере 01].

<число> => <чс> => <чс><цифра> => <цифра><цифра> => 2<цифра> => 22

Отправившись от символа <число>, нарисуем его куст, чтобы указать его непосредственный вывод (см. рисунок 10.1 a))

Куст узла - это множество подчиненных ему узлов. Чтобы показать второй вывод, из узла, представляющего заменяемый символ, рисуется куст, узлы которого образуют цепочку, заменяющую этот символ ([[#g04fb] рисунок G.04 b)]. Концевые (висящие) узлы синтаксического дерева - это узлы, не имеющие подчиненных узлов. При чтении слева направо концевые узлы образуют цепочку, вывод которой представлен деревом. Концевой куст - это куст, все узлы которого концевые.

Существует и другая терминология. В ней концевые узлы называются "листьями", не концевые узлы - "ветвями". Начальный символ вывода везде называется "корнем".

Пусть N - ветвь (узел) дерева. Сыновьями N называются узлы куста, подчиненного N. N - их отец. Сыновья называются братьями. Самым младшим братом является самый левый из них. На рисунке 10.1, b) ветвь <чс> имеет двух сыновей, <чс> и <цифра>, младшим из них является <чс>.

О п р е д е л е н и е. Пусть N - ветвь синтаксического дерева. Тогда потомками ветви (узла) N будут все выводимые из него узлы, то есть все ветви и листья, лежащие выше нее. Предками узла N будут все ветви (нетерминальные символы, включая корень), приводимые к узлу N (лежащие выше нее в дереве вывода).

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

Т е о р е м а. Концевые узлы образуют фразу для корня данного поддерева.

Д о к а з а т е л ь с т в о.

Пусть <U> - корень поддерева, а u - цепочка из концевых узлов поддерева. Тогда <U> =>+ u.

Пусть x - цепочка концевых узлов, расположенная слева от концевых узлов поддерева u, а y - цепочка концевых узлов справа от u. Тогда xuy - сентенциальная форма, то есть Z =>* xuy. Эти условия соответствуют определению фразы (10.11).

Подводя итог, сформируем следующее положения о синтаксических деревьях:

10.4.2. Однозначность грамматик

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

О п р е д е л е н и е. Грамматика неоднозначна, если она допускает неоднозначные предложения, в противном случае она однозначна.

Пример неоднозначной грамматики смотри ниже.

[Пример 02]

Неоднозначная грамматика.

Рассмотрим следующую грамматику арифметических выражений:

<врж> ::= <врж>+<врж>
<врж> ::= <врж>*<врж>
<врж> ::= (<врж>)
<врж> ::= i

Теперь рассмотрим ее сентенциальную форму:

i + i * i

Для нее возможны следующие деревья вывода (см. рисунок 10.2, {a), (b)):

Дерево, определенное на рисунке 10.2, (a) указывает на приоритет умножения, а на рисунке 10.2, (b) - приоритет сложения. Поэтому оба результата являются с точки зрения этой грамматики правильными, хотя вычисления приводят к разным результатам.

Грамматика, приведенная в примере 03 ниже, является однозначной.

[Пример 03].

Однозначная грамматика разбора арифметических выражений.

<врж> ::= <терм>
<врж> ::= <врж>+<терм>
<терм> ::= <множ>
<терм> ::= <терм>*<множ>
<множ> ::= (<врж>)
<множ> ::= i

Теперь синтаксическое дерево для сентенциальной формы (10.20) будет единственным и выглядит следующим образом:

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

Следует отметить, что большинство используемых человеческих языков построено на "неоднозначных" грамматиках (в лексическом понимании). Примеры: "Петя взял лук" (какой лук, который едят или которым стреляют?), "Казнить нельзя помиловать" (без запятой непонятно, убить ли надо человека или отпустить на волю?) и т.д. Даже такой популярный язык программирования, как C++, часто реализуется неоднозначной грамматикой. Как правило, с неоднозначностью грамматик борются введением в программу разбора контекста и правил по-умолчанию.

10.4.3. Классификация грамматик по Хомскому

Американский ученый Хомский в [11, 19] определил четыре основных классов языков в терминах грамматик, являющихся упорядоченной четверкой [V, T, P, Z], где:

Тогда грамматика с фразовой структурой (по-другому, грамматика типа 0) имеет вид:

u ::= v, где u входит в V+, а v входит в V*

то есть левая часть u также может быть последовательностью символов, а правая часть может быть пустой.

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

xUy ::= xuy, где U входит в V-T, u входит в V+, а x,y входят в V*

Термин "контекстно-чувствительный" отражает тот факт, что можно заменить U на u только в контексте x … y.

Дальнейшее ограничение дает класс грамматик типа 2, или контекстно-свободной, бесконтекстной или КС-грамматикой. Ее вид следующий:

U ::= u, где U входит в V-T, и u входит в V*

Этот класс грамматик называется контекстно-свободной потому, что U можно изменять, не обращая внимание на контекст, в котором он встретился (то есть символы меняются на цепочки независимо). Однако в КС-грамматике может встретиться правило:

U ::= <пусто>

где <пусто> - пустая цепочка. Поэтому КС-грамматика G, не имеющая правила [G.25], называется неукорачивающейся.

И, наконец, введя ограничения:

U ::= N, или U ::= NW, где N входит в T, а U и W входят в V-T

то получим грамматику типа 3, или регулярную, автоматную грамматику, или А-грамматику. Практически это праворекурсивная грамматика. Регулярные грамматики играют основную роль в теории языков и теории автоматов. Только множество цепочек регулярной грамматики может генерировать автомат с конечным числом состояний (иначе - детерминированная машина Тьюринга или ЭВМ со структурой фон Неймана, т.е. почти все современные компьютеры). Регулярные языки (то есть порожденные А-грамматиками) называются регулярными множествами. Именно их желательно использовать при программировании символьных вычислений на компьютере.

10.4.4. Практические ограничения, налагаемые на грамматику

Чтобы появиться в выводе какого-нибудь предложения, нетерминал <U> должен удовлетворять двум условиям:

Z =>* x<U>y для некоторых (в том числе пустых) цепочек x и y

<U> =>+ t для некоторой t входящей в VT+

О п р е д е л е н и е. Грамматика G[Z] называется приведенной, если каждый нетерминал <U> удовлетворяет условиям: (10.26) и (10.27).

Также грамматика не должна содержать правила:

<U> ::= <U>

10.5. Примеры грамматик

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

10.5.1. Грамматика для построения идентификаторов

В практике программирования часто используется понятие идентификатора. Дадим ему определение.

О п р е д е л е н и е. Идентификатор - это цепочка алфавитно-цифровых знаков, начинающихся с латинской буквы.

Например, следующие цепочки - идентификаторы:

A, a, i, izh003, ai, b12;

а следующие - не идентификаторы:

1, 1a, .htaccess, b[1,2], a_and_i, ai.

Грамматика, порождающая любые идентификаторы, представлена ниже (Пример 04).

[Пример 04]

<идентификатор> ::= <alphabet>{<alphanum>}
<alphanum> ::= <num>|<alphabet>
<alphabet> ::= [A-Za-z]
<num> ::= [0-9]

В принципе, для реализации грамматики из [примера 04] достаточно использовать сканер лексем (см. раздел 4 лекции 9).

10.5.2. Построение чисел

При разборе текстов часто бывает необходимо отделить числа от других слов. Сложность выделения заключается в том, что числа бывают не только натуральными, но могут быть представлены в научном формате с плавающей точкой (см. раздел 4 лекции 5). Программа-сканер, реализующая такое выделение, приведена в приложении II к лекции 9. Ниже представлена грамматика, используемая им при программировании сканера:

[Пример 05]

<число> := <научный формат> | <фиксированная точка> | <целое число>
<научный формат> ::= <фиксированная точка><порядок>
<фиксированная точка> ::= <целое число>.<целое без знака>
<целое число> ::= [(+|-)]<целое без знака>
<порядок> ::= (e|E)<целое число>
<целое без знака> ::= {(0|1|2|3|4|5|6|7|8|9)}+

10.5.3. Разбор арифметических выражений

Запишем грамматику, похожую на приведенную в примере 03, но оперирующую с большим числом выражений:

[Пример 06]

<врж> ::= <терм>|<врж>+<терм>|<врж>-<терм>
<терм> ::= <множ>|<терм>*<множ>|<терм>/<множ>
<множ> ::= <степ>|<множ>^<степ>
<степ> ::= \(<врж>\)|<идентификатор>|<число>

Грамматика из примера 06, однако, допускает выражения A+-5, или 2*+10, B++2, что не допускается в арифметике. Чтобы избежать этих коллизий, надо либо усложнить грамматику, либо ввести дополнительные проверки.

10.6. Резюме

В данной лекции Вы познакомились с основными терминами и положениями важной дисциплины "искусственного интеллекта" - формальной грамматики. Вы разобрались с понятиями "алфавит", "язык", "грамматика", выяснили, что такое сентенциальная форма, фраза грамматики и чем они отличаются. Также Вы ознакомились с представлением грамматики с помощью "деревьев вывода", а также классификацией грамматик по Хомскому.

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

10.7. Глоссарий