Способы описания формальных языков

1.3 Формы Бэкуса - Наура

Цепочки языка могут содержать метасимволы, имеющие особое назначение. Метаязык, предложенный Бэкусом и Науром (БНФ) использует следующие обозначения:

  1. символ «::=» отделяет левую часть правила от правой (читается: «определяется как»);
  2. нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки «<» и «>»;
  3. терминалы - это символы, используемые в описываемом языке;
  4. правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или»).

Для повышения удобства и компактности описаний, в расширенных БНФ вводятся следующие дополнительные конструкции (метасимволы):

  1. квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;
  2. фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз;
  3. сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;
  4. круглые скобки «(» и «)» используются для ограничения альтернативных конструкций;
  5. кавычки используются в тех случаях, когда один из метасимволов нужно включить в цепочку обычным образом.

Пример 1.10. Правила, определяющие понятие «идентификатор» языка программирования, могут выглядеть следующим образом:
<буква> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w |
                     x | y | z
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<идентификатор> ::= <буква> {<буква> | <цифра>}

1.4 Диаграммы Вирта

В метаязыке диаграмм Вирта используются графические примитивы, представленные на рисунке 1.2.
При построении диаграмм учитывают следующие правила:

  1. каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно изображаются на противоположных сторонах;
  2. каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;
  3. альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием;
  4. должна быть одна входная дуга (располагается обычно слева или сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа или снизу);
  5. стрелки на дугах диаграмм обычно не ставятся, а направления связей отслеживаются движением от начальной дуги в соответствии с плавными изгибами промежуточных дуг и ветвлений.

 

Рисунок 1.2 – Графические примитивы диаграмм Вирта

1) – терминальный символ, принадлежащий алфавиту языка;
2) – постоянная группа терминальных символов, определяющая название лексемы;
3) – нетерминальный символ, определяющий название правила;
4) – входная дуга с именем правила, определяющая его название;
5) – соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах.

 

Пример 1.11. Возможные правила, определяющие понятие «идентификатор» языка программирования, показаны на рисунке 1.3.

 

fig02-02

Рисунок 1.3 – Диаграмма Вирта понятия «идентификатор»

Яндекс.Метрика