Лекция 01. Тема Общая характеристика языков программирования высокого уровня

Лекция 15 
Тема 6. Основы синтаксиса языка программирования. 
В середине 1950-х г в лингвистике произошла революция: ученому-
лингвисту Ноаму Хомски удалось сформулировать понятие метаязыка как 
способа формализованного описания языка. Такой метаязык называется 
грамматика. Грамматики могут быть контекстно-свободными (КС), 
регулярными, контекстно-зависимыми и т.д.
Наиболее универсальна и проста контекстно-свободная грамматика, 
именно она была использована в 1960 г. разработчиками АЛГОЛА-60 
Джоном Бэкусом и Питером Науром для описания синтаксиса языка 
программирования. С тех пор этот способ используется всегда и носит 
название формы Бэкуса- Наура (БНФ). Начнем рассмотрение синтаксиса 
ЯПВУ с понятия контекстно-свободной грамматики (КС-грамматики).
6.1. Основные понятия КС-грамматики. 
Определение. КС-грамматика G представляет собой кортеж четырех 
объектов:
G = {T, V, S, P}, 
где
1. Множество T – это конечное множество символов, из которых 
состоят цепочки языка. Множество Т называется множеством терминалов и 
представляет собой алфавит языка.
2. Множество V – множество переменных грамматики, при этом 
любая переменная представляет собой класс цепочек языка, обладающих 
единым метасмыслом. Множество V называется еще множеством 
нетерминальных символов.
3. S 

V – это стартовый (начальный) символ, т.е. переменная, которая 
представляет определяемый язык. Другие переменные позволяют 
доопределить описываемый язык, задаваемый стартовым символом.

---

4. Множество P – это множество продукций или правил вывода, 
которые представляют собой правила образования цепочек языка. Таким 
образом, предложения языка создаются с помощью последовательности 
продукций, начиная со стартового символа – этот процесс называется 
порождением или выводом и обозначается символами 

или 

.
Определение. Если кортеж G есть КС-грамматика, то язык L(G), 
описываемый 
этой 
грамматикой, 
представляет 
собой 
множество 
терминальных цепочек w, порожденных из стартового символа S
 
L(G )= { w

 T : S 

w }. 
G 
 
 
 
 
Рассмотрим введенные понятия на примере языка палиндромов. 
Палиндром pal  – это цепочка w, читаемая как слева направо, так и справа 
налево: 
pal  

w : w = w
R
 ,
где w
R
– обращение цепочки, т.е. цепочка, прочитанная справа налево.
Пусть T={0,1}, тогда язык палиндромов над алфавитом Т 
представляется множеством Lpal={0,1,101,1001,…}. Определим грамматику, 
т.е. множества V, S, P для языка палиндромов Lpal следующим образом:
V={A}, S=A,
Р : А 

0
А 

1
А 

е
А 

0А0
А 

1А1
Продукционные правила Р обозначают: если цепочка w равна или 
принадлежит переменной А, то цепочки 0, 1, е, 0А0 или 1А1, тоже 
принадлежат А: 

---

A
е
A
A
A













1
0
1
1
0
0

.
Пусть требуется вывести цепочки 101, 1001. В грамматике языка 
палиндромов Lpal порождение требуемых цепочек выглядит следующим 
образом:
A

1A1

101;
A

1A1

10A01

10

01

1001.
Теперь опишем грамматику арифметических выражений.
Пусть 
T = { +, *, (, ), a, b, 0, 1}; 
V = { E, I }, где E – множество выражений;
I – идентификатор, начинающийся с буквы a или b;
S = E; 
P : I

a | b | aI | bI | I0 | I1
E

I | E+E | E*E | (E)
В описанной грамматике требуется получить порождение следующих 
арифметических выражений a*(a+b00), (b0101)*(a101).
1. Порождение цепочки a*(a+b00):
E

E*E

E*(E)

I*(E)

I*(E+E)

a*(E+E)

a*(I+E)

a*(I+I)

a*(a+I)
