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

Другие способы задания грамматик

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

При создании языка программирования важно, чтобы его грамматику понимали не только те, кому предстоит создавать компиляторы для этого языка, но и пользователи языка – будущие разработчики программ.

Достаточно распространенные способы записи правил грамматики: с использованием метасимволов и запись правил грамматик в графическом виде.

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-12-27