Запись правил грамматик с использованием метасимволов
Запись правил грамматик с использованием метасимволов предполагает, что в строке правила грамматики могут встречаться специальные символы — метасимволы, — которые имеют особый смысл и трактуются специальным образом. В качестве таких метасимволов чаще всего используются следующие символы: ( ) (круглые скобки), [ ] (квадратные скобки), { } (фигурные скобки)," " (кавычки) и , (запятая).
Эти метасимволы имеют следующий смысл:
Ø круглые скобки означают, что из всех перечисленных внутри них цепочек символов в данном месте правила грамматики может стоять только одна цепочка;
Ø квадратные скобки означают, что указанная в них цепочка может встречаться, а может и не встречаться в данном месте правила грамматики (то есть может быть в нем один раз или ни одного раза);
Ø фигурные скобки означают, что указанная внутри них цепочка может не встречаться в данном месте правила грамматики ни одного раза, встречаться
один раз или сколь угодно много раз;
Ø запятая служит для того, чтобы разделять цепочки символов внутри круглых скобок;
Ø кавычки используются в тех случаях, когда один из метасимволов нужно включить в цепочку обычным образом — то есть когда одна из скобок или запятая должны присутствовать в цепочке символов языка (если саму кавычку нужно включить в цепочку символов, то ее надо повторить дважды — этот принцип знаком разработчикам программ).
Вот как должны выглядеть правила рассмотренной выше грамматики 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 правил.
Дата добавления: 2016-02-02; просмотров: 1108;