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

Запись правил грамматик с использованием метасимволов предполагает, что в строке правила грамматики могут встречаться специальные символы — мета­символы, — которые имеют особый смысл и трактуются специальным образом. В качестве таких метасимволов чаще всего используются следующие символы: () (круглые скобки), [ ] (квадратные скобки), { } (фигурные скобки)," " (кавыч­ки) и, (запятая).

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

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

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

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

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

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

Вот как должны выглядеть правила рассмотренной выше грамматики G, если их записать с использованием метасимволов:

<число> ® [(+,-)]<цифра>{<цифра>}

<цифра> ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Вторая строка правил не нуждается в комментариях, а первое правило читается так: "число есть цепочка символов, которая может начинаться с символов + или -, должна содержать далее одну цифру, за которой может следовать любое количество цифр". В отличие от формы Бэкуса-Наура, в форме записи с помощью метасимволов, как видно, во-первых, убран из грамматики малопонятный нетерминальный символ <чс>, а во-вторых — удалось полностью исключить ре­курсию. Грамматика в итоге стала более понятной.

Форма записи правил с использованием метасимволов — это удобный и понятный способ представления правил грамматик. Она во многих случаях позволяет полностью избавиться от рекурсии, заменив ее символом итерации { } (фигурные скобки). Как будет понятно из дальнейшего материала, эта форма наиболее употребительна для одного из типов грамматик — регулярных грамматик.

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

Для рассмотренной выше грамматики G таким способом можно, например, запи­сать правила, если предположить, что она должна порождать целые десятичные числа, содержащие не более 15 цифр:

<<число> ® [(+,-)]<цифра>{<цифра>}14

<цифра> ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Для записи того же самого ограничения в форме Бэкуса-Наура или в форме с метасимволами потребовалось бы 15 правил.