Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 6 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

8
ческого представления схем грамматик обычно используют форму Бэкуса-
Наура, или синтаксические диаграммы.
Форма Бэкуса -Наура
При описании синтаксиса конкретных языков программирования прихо-
дится вводить большое число нетерминальных символов, и символическая
форма записи теряет свою наглядность. В этом случае применяют форму Бэку-
са-Наура (БНФ), которая предполагает использование в качестве нетерми-
нальных символов комбинаций слов естественного языка, заключенных в угло-
вые скобки, а в качестве разделителя – специального знака, состоящего из двух
двоеточий и равенства. Например, если правила
L → EL
и
L → E
записаны в
символической форме, и символ L соответствует синтаксическому понятию
«список», а символ E – «элемент списка», то их можно представить в форме
Бэкуса-Наура так:
<список> ::= <элемент списка><список>,
<список> ::= <элемент списка>.
Чтобы сократить описание схемы грамматики, в БНФ разрешается объеди-
нять правила c одинаковой левой частью в одно правило, правая часть которого
должна включать правые части объединяемых правил, разделенные вертикаль-
ной чертой. Используя объединение правил, для рассматриваемого примера по-
лучаем:
<список>::=<элемент списка><список>|<элемент списка>.
Итерационная форма
Для получения более компактных описаний синтаксиса применяют итера-
ционную форму описания. Она предполагает введение специальной операции,
которая называется итерацией и обозначается парой фигурных скобок со звез-
дочкой. Итерация вида {a}
*
определяется как множество, включающее цепочки
всевозможной длины, построенные с использованием символа a, и пустую це-
почку. {a}
*
= {λ, a, aa, aaa, aaaa,...}.
Используя итерацию для описания множества цепочек, задаваемых симво-
лическими правилами, для списка получаем:
L → E { E }*.
Например, описание множества цепочек, каждая из которых должна начи-
наться знаком # и может состоять из произвольного числа букв x и y, может
быть представлено в итерационной форме так:
I → #{ x | y }*.
В итерационных формах описания наряду с итерационными скобками часто
применяют квадратные скобки для указания того, что цепочка, заключенная в
них, может быть опущена. С помощью таких скобок правила:
A → xAyBz и A → xBz
могут быть записаны так:
A→ x[ Ay ]Bz.

Страницы