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)). Покажите, каким образом для данной цепочки определяются операнды в каждой операции.