Элементы компиляции программ
Таким образом, для формального описания языка необходимы по крайней мере два элемента – алфавит и набор правил (синтаксис) – для построения предложений языка. Существует еще несколько элементов формального описания, которые также важны для процесса однозначного построения и распознавания предложений языка. Знакомство с ними целесообразно вести в рамках такого понятия, как грамматика языка.
Грамматика языка представляет собой механизм порождения предложений языка и определяет форму (синтаксис) допустимых предложений языка. Это важное положение, запомните его. В своем изложении мы постараемся по возможности избежать "формализмов", которыми изобилует теория компиляции, хотя полностью сделать это нам не удастся. В частности, без этого трудно ввести понятие грамматики. Формально грамматику языка G можно определить как совокупность четырех объектов: G-{Vt. Vn. P. Z}.
Эти объекты можно описать следующим образом.
- Vt – множество терминальных символов грамматики. Кстати, в этом контексте слово "символ" не означает отдельную литеру. В контексте терминальных и нетерминальных символов символы – это ключевые слова, допустимые имена идентификаторов, знаки операций, разделительные знаки, то есть все отдельные объекты исходного текста программы, имеющие смысл для компилятора. По сути, множество терминальных символов представляет собой набор лексем, которые являются допустимыми словами языка, составляющими его лексику. Таким образом, важно понимать, что исходный текст программы состоит только из терминальных символов.
- Vn – множество нетерминальных символов. Эти символы являются вспомогательными конструкциями, определенными внутри грамматики. К пояснению того, что представляют собой нетерминальные символы, мы вернемся чуть позже. Важно отметить, что множества Vt и Vn не пересекаются. Объединение множеств Vt и Vn составляет алфавит языка. Отметим, что введенное здесь понятие алфавита грамматики (а значит, и языка) отличается от того, что есть в букваре. Не забывайте об этом важном моменте при проведении дальнейших аналогий.
- P – набор правил грамматики, определяющих синтаксис языка. Эти правила называются правилами вывода. Эти правила определяют возможность получения любого предложения языка.
- Z – начальный символ языка. Он входит в множество Vn. Одна из его особенностей состоит в том, что он должен встретиться по крайней мере в левой части одного из синтаксических правил, входящих в множество Р. И именно это правило является первым в процессе вывода любого допустимого предложения языка.
Далее, если не оговорено особо, прописными буквами будем обозначать терминальные символы, а строчными – нетерминальные.
Поясним, как с помощью грамматики задается язык. Начнем с простого примера. Опишем грамматику Gint языка целых чисел:
Gint = {Vt=(0.1.2.3.4.5.6.7.8.9). VrH число, цифра). Р .r=(число)}.
Множество правил Р грамматики Gint выглядит так:
число:: = цифра число:: = цифра число цифра:: = 0 цифра:: = 1 цифра:: = 2 цифра:: = 3 цифра:: = 4 цифра:: = 5 цифра:: = 6 цифра:: = 7 цифра:: = 8 цифра:: = 9
Обычно подобные правила записывают короче:
число:: = цифра | цифра число цифра:: = 0|1|2|3|4|5|6|7|8|9
Здесь символ | означает альтернативу выбора, при этом все элементы, которые он разделяет, равноправны по отношению к нетерминальному символу левой части. Покажем, что эта простая грамматика действительно однозначно определяет язык, с помощью которого можно получить любое целое число. Процесс получения предложения языка, задаваемого грамматикой, называется выводом и определяется правилами вывода, входящими во множество Р. Причем начинать вывод предложения можно не с любого правила, а только с одного из тех, в левой части которых стоит начальный символ языка Z. В нашем случае таким символом является нетерминальный символ число. Видно, что он стоит в левой части двух правил:
число:: = цифра (2.9) число:: = цифра число (2.10)
Сам процесс вывода предложения языка итеративный и состоит из одного или нескольких шагов. Например, рассмотрим процесс получения предложения 8745. Согласно сказанному выше, на первом шаге вывода можно использовать правило (2.9) или (2.10). Если использовать правило (2.9), то это означает, что предложение будет состоять из одной цифры. В нашем случае на первом шаге необходимо применить правило (2.10). Производя дальнейшие подстановки, можно получить предложение, состоящее из любого количества цифр. Заметьте, что на последнем шаге вместо правила (2.10) применяется правило (2.9), что в конечном итоге приводит к желаемому результату.