Практические ограничения, налагаемые на грамматики.

 

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

Алгоритмы, осуществляющие контроль выполнения этих условий для грамматик, описаны в общих чертах.

Правило, подобное U::=U, очевидно, не является необходимым для грамматики; более того, оно приводит к неоднозначности грамматики. Поэтому далее мы полагаем, что

(1.8) грамматика не содержит правил вида U::=U.

Грамматики могут также содержать лишние правила, которые невозможно использовать в выводе хотя бы одного предложения. Например, в следующей ниже грамматике G4[Z] нетерминал <d> не может быть использован в выводе какого-либо предложения, так как он не встречается ни в одной из правых частей правил:

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

Чтобы появиться в выводе какого-либо предложения, нетерминал U должен удовлетворять двум условиям. Во-первых, символ U должен встречаться в некоторой сентенциальной форме:

(1.9) Z=>*хUу для некоторых цепочек х и у, где Z - начальный символ грамматики.

Во-вторых, из U должна выводиться цепочка t, состоящая из терминальных символов:

(1.10) U=>+t для некоторой tÎVT⁺.

Совершенно ясно, что если нетерминальный символ U не удовлетворяет обоим этим условиям, то правила, содержащие U в левой части, не могут быть использованы ни в каком выводе. С другой стороны, если все нетерминалы удовлетворяют этим условиям, то грамматика не содержит лишних правил. Так, если U::=u - правило, то, во-первых, Z=>*хUу=>х u у. Во-вторых, так как мы можем вывести цепочку терминальных символов для каждого нетерминала, содержащегося в цепочке х u у, то

х u у=>*t для некоторой tÎVT⁺.

В конечном итоге получаем Z=>+t, т.е. вывод, в котором было использовано правило U::=u.

В описанной выше грамматике G4 нетерминальный символ <c> не удовлетворяет условию 1.10, так как при непосредственном выводе он должен быть заменен на <c>f. Очевидно, что такая замена не может привести к цепочке из терминальных символов. Если отбросить все правила, которые нельзя использовать при порождении хотя бы одного предложения, то останутся правила

Z::=<b>e,<a>::=<a>e,<a>::=e и <b>::=<a>f.

 

О п р е д е л е н и е 1.12. Грамматика G называется приведенной, если каждый нетерминал U удовлетворяет условиям 1.9 и 1.10.

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

Теперь обратим внимание на то, что нетерминал U удовлетворяет условию 1.9 тогда и только тогда, когда Z WITHIN⁺ U, где WITHIN - отношение, определенное выше. Таким образом, результаты можно использовать результаты предыдущего раздела, чтобы проверить грамматику на выполнение условия 1.9.

Рис.1.11. Алгоритм проверки условия 1.10.

 

На рис.1.11. приведена схема алгоритма, который проверяет нетерминалы, встречающиеся в наборе правил, на выполнение условия 1.10. Работа алгоритма начинается с того, что некоторым образом отмечаются те нетерминалы, для которых существует пра-вило U::=t, где tVT⁺ (первое выполнение Р1). Такие нетерминалы, очевидно, удовлетворяют условию 1.10. Далее в алгоритме проверяются все неотмеченные нетерминалы U и для каждого из них делается попытка найти правило U::=х, где х состоит только из терминальных символов или ранее отмеченных нетерминалов (повторное выполнение блока Р1). Символы, для которых такое правило существует, также, очевидно, удовлетворяют условию 1.10. Этот процесс продолжается до тех пор, пока либо все нетерминалы не будут отмечены, либо пока при выполнении блока Р1 не будет отмечено ни одного символа. Работа алгоритма завершена. Неотмеченные нетерминалы не удовлетворяют условию 1.10.

 

1.8. ДРУГИЕ СПОСОБЫ ПРЕДСТАВЛЕНИЯ СИНТАКСИСА.

 

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

 

Фигурные скобки.

 

В НБФ только с помощью рекурсии можно задать список произвольного числа элементов. Таким образом, мы пишем

 

(1.11) <спис ид>::=<ид>|<спис ид>,<ид> и

(1.12) <целое>::=<цифра>|<целое><цифра>

 

Предположим, что фигурные скобки { и } являются метасимволами и используются там, где необходимо указать, что, цепочка, заключенная в фигурные скобки, может либо отсутствовать, либо повторяться любое число раз. Можно теперь переписать 1.11 и 1.12 как

 

(1.13) <спис ид>::=<ид>{,<ид>}

<целое>::=<цифра>{<цифра>}

 

Оба способа записи считаются эквивалентными. Для того чтобы задать минимальное или максимальное число возможных повторений цепочки, после фигурных скобок используются надстрочные и/или подстрочные индексы. Например, в языке ПАСКАЛЬ идентификаторы состоят не более чем из 6 буквенно-цифровых литер. Они могут быть описаны следующим образом:

 

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

 

<ид ПАСКАЛЯ>::=<буква>{<бц>}5

 

Заметим, что эта запись отличается от

 

<ид ПАСКАЛЯ>::=<буква>{<бц>} 5

 

поскольку во втором случае есть пробел между фигурной скобкой и 5.

Фигурные скобки позволяют нам использовать метасимвол | внутри них для указания на возможный выбор: так, {х|у|z} означает, что каждая из цепочек х, у или z может входить в последовательность нуль или более раз. Воспользуемся этой возможностью и перепишем синтаксис идентификаторов ПАСКАЛЯ таким образом:

 

<ид ПАСКАЛЯ>::=<буква>{<буква>|<цифра>}5

 

Квадратные скобки.

 

Квадратные скобки [ ] часто используются для того, чтобы указать факультативную цепочку. Следовательно, квадратные скобки эквивалентны фигурным скобкам, за которыми непосредственно следует 1. Предположим, что требуется описать простую инструкцию цикла в языке, подобном FOXPRO, в которой либо экстренный выход, либо величина шага могут быть опущены. Это можно сделать так:

 

 

Круглые скобки как метасимволы.

 

В правых частях правил оператор конкатенации предшествует оператору выбора. Поэтому АВ|С означает либо АВ, либо С. Когда необходимо отказаться от нормального предшествования, круглые скобки используются почти так же, как это делается в арифметических выражениях. Таким образом, А(В|С) означает либо АВ, либо АС. Круглые скобки как метасимволы будут полезны, как мы сейчас увидим, при факторизации в правых частях. Однако возникает проблема, когда круглые скобки используются как терминальные символы языка. В дальнейшем мы будем использовать круглые скобки как обычные терминальные символы, если не будет оговорено противное.

 

Факторизация.

 

Если круглые скобки используются в качестве метасимволов, мы можем записать правила

 

U::=xy|xw|...|xz

как

U::=х(у|w|...|z),

 

где общая для всех альтернатив голова х вынесена за скобки. Скобки могут быть вложенными на любую глубину, точно так же как в арифметических выражениях. Например, пусть у=у₁у₂ и w=у₁у₃. Тогда приведенное выше правило можно переписать как

 

U::=х(у₁(у₂|у₃)|...|z)

 

Позднее мы увидим, что в некоторых случаях благодаря факторизации облегчается разбор.

Правила Е::=Т|Е+Т, обозначающие, по крайней мере, одно вхождение Т, за которым следует сколько угодно (в том числе нуль) вхождений +Т, можно переписать как

Е::=Т{+Т}

Более того, Е::=Т|Е+Т|Е-Т можно записать как

Е::=Т{(+|-)Т}

Такое преобразование, которое позволяет избавиться от левой рекурсии в правиле, будет удобным при нисходящем разборе.

 

Метасимволы как терминальные элементы.

 

Иногда нам придется описывать язык, содержащий терминалы, такие, как::=, | или {, которые одновременно являются метасимволами. В этом случае терминал заключается в кавычки, чтобы отличить его от метасимвола. Например, правила НФБ могут быть частично описаны так:

<правило>::=<лев.часть>'::='<прав.часть>

Ясно, что это условие ставит кавычки в положение метасимвола. Кавычку, если она используется как терминальный символ, следует представлять двумя кавычками, заключая их в кавычки. Следовательно, соотношение <кавычка>::='''' описывает нетерминальный символ <кавычка>; единственная цепочка, выводимая из него, состоит из одной кавычки.