1.2 Грамматики

1.2.1 Общие сведения

В расширенном представлении под термином "язык" понимают всякое средство общения, состоящее из:

- знаковой системы, т.е. множества допустимых последовательностей знаков;

- множества смыслов этой системы;

- соответствия между последовательностями знаков и смыслами, делающими осмысленными допустимые последовательности знаков.

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

Семантика языка существенно зависит от назначения языка, в то время, как для синтаксиса можно сформулировать понятия и методы, не зависящие от назначения и целей языка. Для исследования синтаксиса сложился специальный математический аппарат - теория формальных грамматик, в котором язык понимается уже не как средство общения, а как множество формальных объектов - последовательностей символов алфавита. Эти последовательности называют цепочками и язык понимают как множество цепочек.

Пусть задан алфавит V, в котором можно построить множество V*(читается - итерация алфавита V) цепочек. Формальный язык L в алфавите V - это подмножество цепочек из V* (L V*). Описание формальных языков осуществляется с помощью формальных порождающих грамматик (формальных грамматик).

Формальная порождающая грамматика G (в дальнейшем - грамматика G) - это формальная система, определяемая четверкой объектов:

G[Z] = (VN, VT, Z, P),

где VN - алфавит нетерминалов (вспомогательных символов);

VT - алфавит терминалов (основных символов);

Z - начальный символ (аксиома) грамматики;

P - конечное множество правил.

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

Каждое правило из множества P имеет вид x y, - где x, y цепочки, состоящие из терминальных и нетерминальных символов. В дальнейшем будем рассматривать грамматики, содержащие только правила, левые части которых состоят из одного нетерминального символа (контекстно-свободные грамматики). При этом должно быть хотя бы одно правило, левая часть которого - начальный символ грамматики.

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

Сентенциальная форма - любая цепочка терминальных и нетерминальных символов, которая получается на любом шаге процесса вывода. Множество сентенциальных форм можно получить из дерева вывода, обходя его по узлам и соблюдая следующие правила:

- начинать обход с самого левого узла;

- обход надо совершать так, чтобы при переходе к следующему узлу образованное поддерево не включало, как элемент, предыдущее поддерево.

Фраза - часть сентенциальной формы, выводимая из одного нетерминала за несколько шагов. Для простой фразы шаг вывода равен 1.

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

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

- Каждой цепочке выводимой в заданной грамматике соответствует одно или несколько деревьев вывода.

- Каждому дереву соответствует один или больше выводов.

- Каждому дереву соответствует единственный правый и единственный левый выводы.

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

Языком L(G), порождаемым грамматикой G, называется множество всех цепочек в алфавите терминальных символов VT, выводимых из начального символа грамматики.

1.2.2 Классификация грамматик

Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик (рисунок 1):

Рисунок 1 - Классификация грамматик

Каждый тип грамматик включает грамматики более высоких типов, как частные случаи.

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

1.2.3 Эквивалентные преобразования грамматик

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

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

1.2.5 Построение грамматик для заданного КА

Любое регулярное множество, которое распознается КА, можно описать с помощью автоматной грамматики. Алгоритм построения грамматики следующий:

- Начальное состояние КА - начальный символ грамматики.

- Алфавит КА (без символа конец цепочки-"+") - терминальные символы грамматики.

- Множество состояний КА - нетерминальные символы грамматики.

- Если в таблице переходов КА есть переход из состояния А в состояние В при воздействии входного символа х - ввести правило следующего вида: А xB.

- Если D- допускающее состояние КА, то ввести правило следующего вида: D*,где *- пустая цепочка(для отвергающих состояний правил нет).

- Закончить составление правил, когда будут обработаны все непустые клетки управляющей таблицы ("0" - пустая клетка).

Delphi - это комбинация нескольких важнейших технологий:

-Высокопроизводительный компилятор в машинный код

- Объектно-ориентированная модель компонент

- Визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов

- Масштабируемые средства для построения баз данных

Компилятор в машинный код. Компилятор, встроенный в Delphi, обеспечивает высокую производительность, необходимую для построения приложений в архитектуре “клиент-сервер”. Этот компилятор в настоящее время является самым быстрым в мире, его скорость компиляции составляет свыше 120 тысяч строк в минуту на компьютере 486DX33. Он предлагает легкость разработки и быстрое время проверки готового программного блока, характерного для языков четвертого поколения (4GL) и в то же время обеспечивает качество кода, характерного для компилятора 3GL. Кроме того, Delphi обеспечивает быструю разработку без необходимости писать вставки на Си или ручного написания кода (хотя это возможно).

В процессе построения приложения разработчик выбирает из палитры компонент готовые компоненты как художник, делающий крупные мазки кистью. Еще до компиляции он видит результаты своей работы - после подключения к источнику данных их можно видеть отображенными на форме, можно перемещаться по данным, представлять их в том или ином виде. В этом смысле проектирование в Delphi мало чем отличается от проектирования в интерпретирующей среде, однако после выполнения компиляции мы получаем код, который исполняется в 10-20 раз быстрее, чем то же самое, сделанное при помощи интерпретатора. Кроме того, компилятор компилятору рознь, в Delphi компиляция производится непосредственно в родной машинный код, в то время как существуют компиляторы, превращающие программу в так называемый p-код, который затем интерпретируется виртуальной p-машиной. Это не может не сказаться на фактическом быстродействии готового приложения.

Объектно-ориентированная модель программных компонент. Основной упор этой модели в Delphi делается на максимальном реиспользовании кода. Это позволяет разработчикам строить приложения весьма быстро из заранее подготовленных объектов, а также дает им возможность создавать свои собственные объекты для среды Delphi. Никаких ограничений по типам объектов, которые могут создавать разработчики, не существует. Действительно, все в Delphi написано на нем же, поэтому разработчики имеют доступ к тем же объектам и инструментам, которые использовались для создания среды разработки. В результате нет никакой разницы между объектами, поставляемыми Borland или третьими фирмами, и объектами, которые вы можете создать. В стандартную поставку Delphi входят основные объекты, которые образуют удачно подобранную иерархию из 270 базовых классов.

Страницы: 1, 2, 3