Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 16 стр.

                                                                      16

     Идея заключается в том, что любое предложение можно получить из
начального символа <предложение> последовательным применением правил
подстановки.
     Формализм, или нотация, использованный при написании этих правил,
называется     Бэкуса–Наура   формой   (БНФ).   синтаксические   единицы
<предложение>,       <подлежащее>      и     <сказуемое>      называются
нетерминальными символами, слова "кошки", "собаки", "спят", "едят" –
терминальными символами, а правила – порождающими правилами.
Символы “::=”, “|”, а также скобки нетерминальных символов “<>” – это
метасимволы языка БНФ (метасимволы не принадлежат описываемому
языку, а относятся к языку описания. Семантика задает значение всем
предложениям языка. Изменим пример про животных:
     <предложение>::=<подлежащее><сказуемое>
     <подлежащее> ::= люди | собаки
     <сказуемое> ::= говорят | спят
     Методы формального описания семантики разработаны недостаточно
хорошо и в этих целях часто используется естественный язык.
     Для рассмотрения задачи спецификации синтаксиса дадим несколько
определений.
     Алфавит – множество символов. Например: Русские буквы, Латинские
буквы, цифры.
     Если A – алфавит, A* (замыкание A) обозначает множество всех строк
(включая пустую строку), составленных из символов, входящих в A. A+
обозначает множество всех строк (исключая пустую строку), состоящих из
символов, входящих в A. Пустая строка обычно обозначается с помощью ε
(эпсилон).
     Синтаксис языка можно определить, пользуясь системой изображения
множеств, например L = { 0n1n | n ≥ 0}. Данный язык включает строки,
состоящие из одного или более нулей и того же числа последующих единиц,
а также пустую строку.