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

4.6.1. Грамматика для констант языка ВАSIC.

Часто бывает необходимо найти КС-грамматику для какого-нибудь языка, который задан неформально. Рассмотрим грамматику для констант подмножества языка BASIC. Присвоим нетерминалам имена, соответствующие цепочкам, которые могут быть из них выведены. Начальный нетерминал-<константа>.

Рассмотрим два вида констант: с символом Е, для представления степени числа 10, и без этого символа.

Константы без Е выводятся с помощью правила:

1. <константа>®<десятичное число>

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

Константы без Е выводятся с помощью правила:

2. <константа>®<десятичное число>Е<целое>

Чтобы завершить построение грамматики, добавим правила для определения целого числа:

3. <целое>®+<целое без знака>

4. <целое>®-<целое без знака>

5. <целое>®<целое без знака>

6. <целое без знака>®d<целое без знака>

7. <целое без знака>®d

где d- представляет собой цифру. Правила 6-7 порождают последовательность цифр.

Правила для десятичного числа:

8. <десятичное число>®<целое без знака>

9. <десятичное число>®<целое без знака>.

10. <десятичное число>®.<целое без знака>

11. <десятичное число>®<целое без знака>.<целое без знака>

Таким образом, все нетерминалы описаны, и грамматика построена.

Например, константу 3.1 Е -21 можно вывести с помощью следующего левого вывода:

<константа>®<десятичное число>Е<целое>®<целое без знака>.<целое без знака>Е<целое>®3. <целое без знака>Е<целое> ® 3.1Е<целое> ®3.1Е-<целое без знака>®3.1Е-2<целое без знака>®3.1Е-21

<константа>

Соответствующее дерево вывода:

Вопросы и упражнения

Построить вывод в данной грамматике следующих констант: 0.253, 0.5E35, 2E-3

4.6.2. Грамматика для S-выражений Лиспа.

Построим грамматику для S-выражений языка Лисп. В руководстве по Лиспу S-выражения определяются рекурсивно в терминах других S-выражений и атомов, которые являются аналогами идентификаторов: «S-выражение - это либо атом, либо левая скобка, за которой следует S-выражение, точка, S-выражение и правая скобка». Если АТОМ считать терминальным символом, то грамматика выглядет так:

<S>®АТОМ

<S>®(<S>.<S>)

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

Пример вывода:

<S>®(<S>.<S>)®((<S>.<S>).<S>)®((АТОМ.<S>).<S>)®((АТОМ.(<S>.<S>)).<S>)® ((АТОМ.(АТОМ.<S>)).<S>)® ((АТОМ.(АТОМ.АТОМ)).<S>)® ((АТОМ.(АТОМ.ÀÒÎÌ)).ÀÒÎÌ)

Дерево вывода:

Вопросы и упражнения

Постройте вывод в данной грамматики следующей конструкции: ((АТОМ.(АТОМ.АТОМ))(АТОМ.АТОМ)

4.6.3.Грамматика для арифметических выражений.

Иногда грамматика не только определяет, какие цепочки принадлежат языку, но и отражает некоторую структуру языка. Рассмотрим, например, такую грамматику:

<Е>®<Е>+<T>

<Е>®<Т>

<Т>®<Т>*<F>

<T>®<F>

<F>®<F>­<P>

<F>®<P>

<P>®(<E>)

<P>®I

где <E> - начальный символ грамматики, I - произвольное целое число. Эта грамматика, в основе которой лежит грамматика для арифметических выражений, приведенная в официальном сообщении об Алголе 60, порождает все арифметические выражения Алгола 60, в которых используются целые числа и операции +,* и ­.

Дерево вывода для цепочки 1+2*3+(5+6)*7,где целые числа рассматриваются как вхождения терминального символа I:

В описании языка программирования должно быть указано не только то, какие цепочки принадлежат языку, но и то, как они должны выполняться. Поэтому описание арифметических выражений включает правила для определения операндов каждой операции в выражении. Например, операндами первой операции + в приведенном примере являются целое число 1 и результат вычисления подвыражения 2*3. Подвыражение 1+2*3 выводится из одной вершины, помеченной символом <E>, эта вершина имеет три потомка: <E>, порождающий операнд 1, + и <T>, порождающий подвыражение 2*3. Аналогично, каждая из трех остальных операций является потомком вершины, два других потомка которой порождают операнды этой операции. Таким образом, в дереве отражено, какие части входной цепочки образуют подвыражения, которые нужно вычислять, и каковы операнды каждой операции. В этом смысле дерево представляет собой «структуру» выражения.

Вопросы и упражнения

Постойте в данной грамматике вывод цепочки (2+7)*(5-(3+1)). Покажите, каким образом для данной цепочки определяются операнды в каждой операции.