Файл: Методические указания по выполнению лабораторных работ по дисциплине (модулю) Лингвистическое и программное обеспечение автоматизированных систем.doc

, мы просто дописываем цифру справа (поскольку привыкли писать слева направо) к уже написанному ряду цифр. А этот ряд цифр, начиная от одной цифры, тоже в свою очередь является числом. Тогда определение для понятия "число" можно построить таким образом: "число — это любая цифра либо другое число, к которому справа дописана любая цифра". Именно это и составляет основу правил грамматик G и G' и отражено в правилах <чс>  <цифра> | <чс><цифра> и Т  Р | ТF (вторая строка правил). Другие правила в этих грамматиках позволяют добавить к числу знак (первая строка правил) и дают определение понятию "цифра" (третья строка правил). Они элементарны и не требуют пояснений.

Принцип рекурсии (иногда его называют "принцип итерации") — важное понятие в представлении о формальных грамматиках. Так или иначе, явно или неявно рекурсия всегда присутствует в грамматиках любых реальных языков программирования. Именно она позволяет строить бесконечное множество цепочек языка, и говорить об их порождении невозможно без понимания принципа рекурсии. Как правило, в грамматике реального языка программирования содержится не одно, а целое множество правил, построенных с помощью рекурсии.

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

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

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

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

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

---

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

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

Вот как должны выглядеть правила рассмотренной выше грамматики 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 правил.

---

2.3. Запись правил грамматик в графическом виде

При записи правил в графическом виде вся грамматика представляется в форме, набора специальным образом построенных диаграмм. Эта форма была предложена при описании грамматики языка Pascal, а затем она получила широкое рас­пространение в литературе. Она доступна не для всех типов грамматик, а только для тех типов, где в левой части правил присутствует не более одного символа, но этого достаточно, чтобы ее можно было использовать для описания грамма­тик известных языков программирования.

В такой форме записи каждому нетерминальному символу грамматики соответствует диаграмма, построенная в виде направленного графа. Граф имеет следую­щие типы вершин (Рис. 2.1):

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

Рис. 2.1 – Условные обозначения на синтаксических диаграммах
Каждая диаграмма имеет только одну точку входа и одну точку выхода, но сколько угодно вершин других трех типов. Вершины соединяются между собой направленными дугами графа (линиями со стрелками). Из входной точки дуги могут только выходить, а во входную точку — только входить. В остальные вер­шины дуги могут как входить, так и выходить (в правильно построенной грамматике каждая вершина должна иметь как минимум один вход и как минимум один выход).

Чтобы построить цепочку символов, соответствующую какому-либо нетерми­нальному символу грамматики, надо рассмотреть диаграмму для этого символа. Тогда, начав движение от точки входа, надо двигаться по дугам графа диаграммы через любые вершины вплоть до точки выхода. При этом, проходя через вершину, обозначенную нетерминальным символом, этот символ следует поместить в ре­зультирующую цепочку. При прохождении через вершину, обозначенную цепочкой терминальных символов, эти символы также следует поместить в результирую­щую цепочку. При прохождении через узловые точки диаграммы над результи­рующей цепочкой никаких действии выполнять не надо.

---

Через любую вершину графа диаграммы, в зависимости от возможного пути движения, можно пройти один раз, ни разу или сколь угодно много раз. Как только мы попадем в точку выхода диаграммы, построение результирующей цепочки будет закончено.

Результирующая цепочка, в свою очередь, может содержать нетерминальные символы. Чтобы заменить их на цепочки терминальных символов, нужно, опять же, рассматривать соответствующие им диаграммы. И так до тех пор, пока в цепоч­ке не останутся только терминальные символы. Очевидно, что для того, чтобы построить цепочку символов заданного языка, надо начать рассмотрение с диаграммы целевого символа грамматики.

Это удобный способ описания правил грамматик, оперирующий образами, а потому ориентированный исключительно на людей. Даже простое изложение его основных принципов здесь оказалось довольно громоздким, в то время как суть способа довольно проста. Это можно легко заметить, если посмотреть на описание понятия "число" из грамматики G с помощью диаграмм на Рис. 2..

Как уже было сказано выше, данный способ в основном применяется в литературе при изложении грамматик языков программирования. Для пользователей — разработчиков программ — он удобен, но практического применения в компиляторах пока не имеет.

Структура синтаксических диаграмм идентична структурам языков программирования, что позволило широко использовать диаграммы для написания трансляторов различных языков. Первым языком, описанным с помощью синтаксических диаграмм, был язык Pascal.

Чтение диаграммы производится в направлении стрелок; в точке ветвления может выбираться любой маршрут. В качестве метаязыка может использоваться естественный русский язык; языки программирования строятся на англоязычной основе. Терминальные символы переписываются в конструкции формального языка дословно. Нетерминальные символы могут выражаться через терминальные или другие нетерминальные – в этом случае для них строятся уточняющие диаграммы; в конечном счете, все нетерминальные символы должны быть выражены через терминальные. При использовании синтаксических диаграмм принимается условие, что среди терминальных символов языка-объекта не должно быть одинаковых, а также ни один из терминальных символов не может служить началом другого. При нарушении данного условия возможно неоднозначное чтение диаграммы и, как следствие, построение или распознавание неверной конструкции языка.

---