1.3.2. Запись правил грамматики с использованием метасимволов

Форма Бэкуса-Наура удобна для формального описания грамматик и она, по существу, натолкнула исследователей на внедрение математических средств для системного описания и исследования языков программирования, и использование математического аппарата как основы для синтаксического анализа в трансляторах. Но БНФ не всегда доступна для понимания, особенно при использовании рекурсий различного вида. А при создании языка программирования важно, чтобы его грамматику понимали не только те, кому предстоит создавать компиляторы для этого языка, но и пользователи языка – программисты. Поэтому существуют другие способы описания формальных грамматик, ориентированные как бы на большую понятность для человека. Одним из таких способов является запись правил грамматики с использованием метасимволов.

Суть его заключается в том, что в строке правил грамматики могут встречаться специальные символы – метасимволы, которые имеют особый смысл и трактуются специальным образом. В качестве таких символов, например, могут использоваться скобки ( ), [ ], { }, « » (кавычки) и , (запятая).

Эти метасимволы имеют следующий смысл:

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

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

– фигурные скобки означают, что указанная внутри них цепочка может не встречаться в данном месте правил ни разу, может встречаться один раз или сколь угодно много раз;

– запятая служит для разделения цепочек внутри круглых скобок;

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

Тогда правила рассмотренной в Примере 1.1 грамматики G, записанные с помощью метасимволов будут выглядеть следующим образом:

P:

число  [(+, –)] цифра {цифра}

цифра  0123456789

Первая строка правил читается так: «число есть цепочка символов, которая может начинаться со знаков + или –, или без знака, должна содержать одну цифру, за которой может следовать любое количество цифр.

Вопрос слушателям. Каким образом на основе этих правил можно получить цепочку 125? Пояснить.

В отличие от БНФ в данной форме исключен искусственно введенный малопонятный нетерминал чс и полностью исключена рекурсия.

Кроме указанных метасимволов могут использоваться и другие метасимволы, смысл которых заранее разъяснен. Можно также произвести расширение смысла уже существующих метасимволов. Например, для метасимвола {} может быть введена запись{}n, где n целое число, n > 0. Такая запись означает, что цепочка символов, стоящая в фигурных скобках, может быть повторена от 0 до n раз. Это удобный способ ограничения на длину цепочки.

Если для грамматики G ввести условие, что она должна порождать целые десятичные числа, содержащие не более 15 разрядов, то получим G с правилами:

P:

число  [(+, –)] цифра {цифра}14

цифра  0123456789.

Для организации такого ограничения в БНФ или в немодифицированной метасимвольной форме понадобилось бы еще 15 правил.