Сборник по задачам и примерам Assembler


Формальное описание языка программирования - часть 3


  • Vn — множество нетерминальных символов. Эти символы являются вспомогательными конструкциями, определенными внутри грамматики. К пояснению того, что представляют собой нетерминальные символы, мы вернемся чуть позже. Важно отметить, что множества Vt и Vn не пересекаются. Объединение множеств Vt и Vn составляет алфавит языка. Отметим, что введенное здесь понятие алфавита грамматики (а значит, и языка) отличается от того, что есть в букваре. Не забывайте об этом важном моменте при проведении дальнейших аналогий.
  • P- набор правил грамматики, определяющих синтаксис языка. Эти правила называются правилами вывода. Эти правила определяют возможность получения любого предложения языка.
  • Z- начальный символ языка. Он входит в множество Vn. Одна из его особенностей состоит в том, что он должен встретиться по крайней мере в левой части одного из синтаксических правил, входящих в множество Р. И именно это правило является первым в процессе вывода любого допустимого предложения языка.
  • Далее, если не оговорено особо, прописными буквами будем обозначать терминальные символы, а строчными — нетерминальные.

    Поясним, как с помощью грамматики задается язык. Начнем с простого примера. Опишем грамматику G1nt языка целых чисел:

    Glnt = {Vt=(0.1.2,3.4.5.6.7.8.9). VrH число, цифра). Р. г=(число)}.

    Множество правил Р грамматики Gint выглядит так:

    число::=цифра

    число::=цифра число

    цифра::=0

    цифра::=1

    цифра::=2

    цифра::-3

    цифра::=4

    цифра::=5

    цифра::=6

    цифра::-7

    цифра::-8

    цифра::=9

    Обычно подобные правила записывают короче:

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

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




    - Начало -  - Назад -  - Вперед -