Языки программированияКонтекстносвободные грамматики М. Л. ЦымблерЯзыки программирования

• Название: Языки программированияКонтекстносвободные грамматики М. Л. ЦымблерЯзыки программирования
• Дата: 02.12.2021
• Размер: 1.07 Mb.
• Имя файла: 6.pdf
• Тип: Документы; #289427

Языки программирования
Контекстно-свободные
грамматики

© М.Л. Цымблер
Языки программирования
2
Содержание

Понятие контекстно-свободной грамматики

КС-грамматики и конечные распознаватели

Синтаксически управляемые процессы обработки языков

Атрибутные транслирующие грамматики

© М.Л. Цымблер
Языки программирования
3
Формальные грамматики

Формальный язык
– множество символьных цепочек.

Формальная грамматика
– набор правил, с помощью которых порождаются цепочки формального языка.

Формальные грамматики можно преобразовать в конечные распознаватели и обрабатывающие автоматы, которые распознают/транслируют соответствующие множества цепочек.

© М.Л. Цымблер
Языки программирования
4
Пример формальной грамматики
1.
<предложение>
<подлежащее><сказуемое>
<дополнение>
2.
<подлежащее>
<прилагательное><существит ельное>
3.
<дополнение>
<прилагательное><существите льное>
4.
<сказуемое>
сдает
5.
<прилагательное>
каждый
6.
<существительное>
экзамен
7.
<существительное>
студент

© М.Л. Цымблер
Языки программирования
5
Пример формальной грамматики
<предложение>
<подлежащее> <сказуемое> <дополнение>
<прилагательное> <существительное>
<прилагательное> <существительное>
каждый студент каждый экзамен сдает

© М.Л. Цымблер
Языки программирования
6
Контекстно-свободная грамматика

Для задания
КС-грамматики
необходимо:
•
конечное множество
терминалов
– символов, не требующих дополнительных определений
•
конечное множество
нетерминалов
– символов, которые определяются через терминалы и другие нетерминалы
•
конечное множество
правил (продукций)
–
определений вида <А>
, где
левая часть <А> – нетерминал
правая часть
– конечная, возможно пустая, цепочка терминалов и нетерминалов
•
начальный нетерминал

© М.Л. Цымблер
Языки программирования
7
Подстановки и выводы

Подстановка
– замена нетерминала правой частью определяющей его продукции.

Вывод
– последовательность подстановок.

КС-язык
– множество терминальных цепочек, которые можно вывести из начального нетерминала КС-грамматики.

© М.Л. Цымблер
Языки программирования
8
Пример вывода
1.

ac
2.

3.

c
4.

b
5.

b
6.

a


1
ac

a
4
c abc

a
3
bc acbc

ac
6
bc acabc

ac
2
abc acabc

acab
6
c acabac, то есть
*
acabac

© М.Л. Цымблер
Языки программирования
9
Пример вывода


1
ac

a
c

© М.Л. Цымблер
Языки программирования
10
Пример вывода


1
ac

a
4
c abc

a
c


b

© М.Л. Цымблер
Языки программирования
11
Пример вывода


1
ac

a
4
c abc

a
3
bc acbc

a
c


b c

© М.Л. Цымблер
Языки программирования
12
Пример вывода


1
ac

a
4
c abc

a
3
bc acbc

ac
6
bc acabc

a
c


b c


a

© М.Л. Цымблер
Языки программирования
13
Пример вывода


1
ac

a
4
c abc

a
3
bc acbc

ac
6
bc acabc

ac
2
abc acabc

a
c


b c


a

© М.Л. Цымблер
Языки программирования
14
Пример вывода


1
ac

a
4
c abc

a
3
bc acbc

ac
6
bc acabc

ac
2
abc acabc

acab
6
c acabac

a

c


b c


a a

© М.Л. Цымблер
Языки программирования
15
Неоднозначность вывода

Цепочке языка может соответствовать более чем один вывод.
1.

ac
2.

3.

c
4.

b
5.

b
6.

a


1
ac

a
4
c
abc

a
3
bc acbc

ac
6
bc acabc

ac
2
abc acabc

acab
6
c
acabac


1
ac

a
5
c
abc

a
3
bc acbc

ac
6
bc acabc

ac
2
abc acabc

acab
6
c
acabac

© М.Л. Цымблер
Языки программирования
16
Неоднозначность КС-грамматики

Если вывод каждой цепочки КС-языка единственный, то соответствующая КС- грамматика называется
однозначной
, иначе –
неоднозначной

© М.Л. Цымблер
Языки программирования
17
Лево- и правосторонние выводы

Лево-/правосторонний вывод
–
последовательность подстановок, в которой на каждом шаге заменяется самый левый/правый нетерминал.

Каждому дереву вывода соответствует единственный левосторонний и единственный правосторонний выводы.

© М.Л. Цымблер
Языки программирования
18
Пример левостороннего вывода
1.

ac
2.

3.

c
4.

b
5.

b
6.

a


1
L
ac

a
4
c
L
abc

a
3
bc
L
acbc

ac
2
bc
L
acbc

ac
6
bc
L
acabc

acab
6
c
L
acabac, то есть
L
*
acabac

© М.Л. Цымблер
Языки программирования
19
Пример правостороннего вывода
1.

ac
2.

3.

c
4.

b
5.

b
6.

a


1
R
ac

a
6
c
R
aac

a
4
ac
R
abac

a
3
bac
R
acbac

ac
6
bac
R
acabac

ac
2
abac
R
acabac, то есть
R
*
acabac

© М.Л. Цымблер
Языки программирования
20
Упражнение

Построить КС-грамматику констант языка
Pascal.
<константа>
?

Вывести константы ’ABRACADABRA’, 123,
$123, 1E23
с помощью лево/правостороннего вывода.

© М.Л. Цымблер
Языки программирования
21
КС-грамматики и конечные распознаватели

Утверждение 1.
Регулярные множества являются КС-языками.

Доказательство
Построение КС-грамматики регулярного множества конечного распознавателя:
1.
Терминалы: символы алфавита распознавателя
2.
Нетерминалы: множество состояний
3.
Правила:
для перехода A
x
B продукция
x для допускающего состояния A правило
4.
Начальный нетерминал: начальное состояние.

© М.Л. Цымблер
Языки программирования
22
Пример построения КС-грамматики для конечного распознавателя

«Контролер нечетности единиц» с регулярным множеством всех цепочек, состоящих из 0 и 1 и имеющих нечетное число единиц.
0
1
ЧЕТ
ЧЕТ
НЕЧЕТ
0
НЕЧЕТ
НЕЧЕТ ЧЕТ
1
1.
<ЧЕТ>
1<НЕЧЕТ>
2.
<ЧЕТ>
0<ЧЕТ>
3.
<НЕЧЕТ>
0<НЕЧЕТ>
4.
<НЕЧЕТ>
1<ЧЕТ>
5.
<НЕЧЕТ>

© М.Л. Цымблер
Языки программирования
23
КС-грамматики и конечные распознаватели

Утверждение 2.
Если КС-грамматика содержит только продукции вида x и
, то существует конечный распознаватель для соответствующего КС-языка.

Доказательство
Построение конечного распознавателя:
1.
Алфавит: множество терминалов
2.
Состояния: множество нетерминалов
3.
Переходы: для правила x переход
A
x
B
4.
Допускающие состояния: A в переходе
5.
Начальное состояние: начальный нетерминал.

© М.Л. Цымблер
Языки программирования
24
Пример построения конечного распознавателя для КС-грамматики

КС-грамматика идентификатора Pascal
1.
<идентификатор>
L<цепочка букв и цифр>
2.
<цепочка букв и цифр>
L<цепочка букв и цифр>
3.
<цепочка букв и цифр>
D<цепочка букв и цифр>
4.
<цепочка букв и цифр>

Конечный распознаватель идентификатора
Pascal (недетерминированный!):
L
D
идентификатор
цепочка букв и цифр
0
цепочка букв и цифр
цепочка букв и цифр цепочка букв и цифр
1

© М.Л. Цымблер
Языки программирования
25
Праволинейные КС-грамматики

КС-грамматика называется
праволинейной
, если ее продукции имеют вид

w или
w, где и – нетерминалы, w – цепочка терминалов (возможно пустая).

Пример праволинейной грамматики:
<описание>
<тип><идентификатор><список переменных>;
<список переменных>
,<идентификатор><список переменных>
<список переменных>
int a, b, c, i, j, k;

Праволинейные грамматики можно преобразовать в грамматики специального вида (из Утверждения 2).

© М.Л. Цымблер
Языки программирования
26
Пример преобразования праволинейной
КС-грамматики
1.

a
2.

bc
3.


4.

abb
5.

c
6.

1.

a
2.

bEpsilon>
3.
Epsilon>
c<Epsilon>
4.
<Epsilon>
5.

a
6.

c
7.

8.

a
9.

b
10.

b
11.

c
12.

© М.Л. Цымблер
Языки программирования
27
Пример преобразования праволинейной
КС-грамматики
a
b
c
S
A, bbS cEpsilon
A
1
cEpsilon
Epsilon
0
Epsilon
1
A
bbS
A
1
bbS
bS
0
bS
S
0
1.

a
2.

bEpsilon>
3.
Epsilon>
c<Epsilon>
4.
<Epsilon>
5.

a
6.

c
7.

8.

a
9.

b
10.

b
11.

c
12.

© М.Л. Цымблер
Языки программирования
28
Упражнения
1.
Написать алгоритм преобразования произвольной праволинейной грамматики в грамматику специального вида.
2.
КС-грамматика порождает дерево вывода:
a)
построить левосторонний вывод b)
найти общее число выводов c)
найти дерево вывода для цепочки ab






b b
a a

© М.Л. Цымблер
Языки программирования
29
Синтаксически управляемые процессы обработки языков

Синтаксически управляемая
обработка КС- языка основана на обработке каждого отдельного правила соответствующей КС- грамматики.

Синтаксически управляемые процессы используются в решении задачи распознавания
КС-языков.

© М.Л. Цымблер
Языки программирования
30
Транслирующие грамматики

Транслирующая грамматика (грамматика перевода)
– КС-грамматика, терминалы которой разбиты на два подмножества:
•
входные символы грамматики;
•
символы действия – подпрограммы обработки
(преобразования, печати и др.) входных символов.

Цепочка языка, определяемого транслирующей грамматикой, называется
последовательностью
актов

Рассмотрим задачу построения грамматики перевода арифметических выражений в польскую запись.

© М.Л. Цымблер
Языки программирования
31
Польская запись

Обычная форма записи арифметических выражений –
инфиксная.
a+b*c
a*b+c

В
постфиксной (польской)
записи
знак операции помещается после операндов.
abc*+
ab*c+
Ян Лукашевич
1878 – 1956 гг.

© М.Л. Цымблер
Языки программирования
32
Польская запись

Польская запись никогда не содержит скобок:
(a+b)*c
ab+c*
a+b*(c+d)*(e+f)
abcd+*ef+*+

Выражения в польской записи легко вычислять.

В структуру синтаксического блока некоторых компиляторов включается специальный блок
перевода арифметических выражений в
постфиксную форму.

© М.Л. Цымблер
Языки программирования
33
Вычисление значения выражения в польской записи
STACK.INIT;
while not (
конец_цепочки) do case
тип_текущего_символа of операнд
:
STACK.PUSH(
значение_операнда);
знак_операции
:
begin арг1 := STACK.POP;
a рг2 := STACK.POP;
STACK.PUSH(
арг1 знак_операции арг2);
end;
end;
Результат := STACK.TOP;

© М.Л. Цымблер
Языки программирования
34
КС-грамматика польской записи
1.
<операнд>
<операнд><операнд><знак>
2.
<операнд>
I
3.
<знак>
+
4.
<знак>
*
5.
<знак>
/
6.
<знак>
… где
I – идентификатор

© М.Л. Цымблер
Языки программирования
35
Перевод в польскую запись

a+b*c
abc*+

Шаги перевода:
•
read(a); write(a);
•
read(+); read(b);
•
write(b); read(*);
•
read(c); write(c);
•
write(*); write(+);

Последовательность актов:
a{a}+b{b}*c{c}{*}{+}

© М.Л. Цымблер
Языки программирования
36
Грамматика перевода инфиксных выражений
1.

+
2.


3.

*
4.

5.
()
6.
a
7.
b
8.
c
1.

+
{+}
2.


3.

*
{*}
4.

5.
()
6.
a
{a}
7.
b
{b}
8.
c
{c}

© М.Л. Цымблер
Языки программирования
37
Перевод инфиксных выражений


L
(a+b)*c

2

3

4
*
{*}
5
*
{*}
(
1
)*
{*}
(+{+})*
{*}
*
(a{a}+b{b}{+})*c{c}{*}
{a}{b}{+}{c}{*}
ab+c*
1.

+{+}
2.


3.

*
{*}
4.

5.
()
6.
a{a}
7.
b{b}
8.
c{c}

© М.Л. Цымблер
Языки программирования
38
Синтаксически управляемый перевод

Входная грамматика
– транслирующая грамматика с вычеркнутыми символами действия.
Входной язык
– язык входной грамматики.

Выходная грамматика
– транслирующая грамматика с вычеркнутыми входными символами.
Выходной язык
– язык выходной грамматики.

Транслирующая грамматика
– грамматика перевода цепочек входного языка в цепочки выходного языка.

Перевод, определяемый транслирующей грамматикой
, –
множество пар
(подпоследовательность входных символов,
подпоследовательность действий)

Замечание.
Перевод можно определить более чем одной транслирующей грамматикой.

© М.Л. Цымблер
Языки программирования
39
Упражнения
1.
Вычислить постфиксные выражения:

3 7 8 + * 4 –

6 9 5 2 * + *

1 2 3 – 4 5 * 6 7 + * + -
2.
Перевести в постфиксную форму:

a+b*c*(a+b)*(a+c)

a+(b+c)*((a+b)*c+a)
3.
Построить грамматику перевода инфиксных выражений в функциональные. Например:
a+b
PLUS(a,b)
a*b
MUL(a,b)
a+b*c
PLUS(a,MUL(b,c))

© М.Л. Цымблер
Языки программирования
40
Содержание

Понятие контекстно-свободной грамматики

КС-грамматики и конечные распознаватели

Синтаксически управляемые процессы обработки языков

Атрибутные транслирующие грамматики

© М.Л. Цымблер
Языки программирования
41
Атрибутные транслирующие грамматики

Атрибутные транслирующие грамматики
позволяют не только переводить цепочки, но и вычислять их значение в некотором смысле.

Входные символы, символы действия и нетерминалы атрибутной транслирующей грамматики обладают конечным множеством
атрибутов
– свойств, которые используются для вычисления значения цепочки.

Атрибуты делятся на
синтезируемые
и
наследуемые

© М.Л. Цымблер
Языки программирования
42
Пример синтезируемых атрибутов

Как построить синтаксический блок, вычисляющий арифметические выражения, состоящие из символов
( ) + * C ?
•
Данные символы являются лексемами, полученными от лексического блока;
•
C
– константа с некоторым значением.

Используем следующую грамматику перевода:
1.


{ОТВЕТ}
2.

+
3.


4.

*
5.

6.
()
7.
C

© М.Л. Цымблер
Языки программирования
43
Пример синтезируемых атрибутов
1.

{ОТВЕТ}
2.

+
3.


4.

*
5.

6.
()
7.
C

Рассмотрим цепочку S=(С
3
+С
8
)*(С
1
+С
9
), где индексы – атрибуты, обозначающие значение константы.

Как осуществить перевод S ОТВЕТ
110
?

Очевидное решение – сопоставить каждому нетерминалу значение атрибута в порождаемом им выражении.

© М.Л. Цымблер
Языки программирования
44
Пример синтезируемых атрибутов
1.

{ОТВЕТ}
2.

+
3.


4.

*
5.

6.
()
7.
C
1.


q
{ОТВЕТ
r
}
r q
2.

p

q
+
r p
q+r
3.

p

q p
q
4.

p

q
*
r p
q*r
5.

p q p
q
6.
p
()
q p
q
7.
p
C
q p
q

© М.Л. Цымблер
Языки программирования
45
Пример синтезируемых атрибутов

Дерево вывода цепочки
(С
3
+С
8
)*(С
1
+С
9
)


110
{
ОТВЕТ}
110

110

11

10
*


11
(
)

11

3

8
+

3


3
C
3


8
C
8


10
(
)

10

1

9
+

1


1
C
1


9
C
9

© М.Л. Цымблер
Языки программирования
46
Пример наследуемых атрибутов

Как построить синтаксический блок, который по описанию переменных устанавливает соответствие между переменной и ее типом?

Грамматика описания переменных:
1.
<описание>
V<список переменных> : ТИП
2.
<список переменных>
,V<список переменных>
3.
<список переменных>
ТИП
– Integer | Real | Boolean | …
V
– указатель на элемент таблицы имен

Используем процедуру
УСТ_ТИП(указатель, тип)

© М.Л. Цымблер
Языки программирования
47
Пример наследуемых атрибутов

Грамматика описания переменных:
1.
<описание>
V<список> : ТИП
2.
<список>
,V<список>
3.
<список>

Грамматика перевода описания переменных:
1.
<описание>
V
{УСТ_ТИП}
<список> : ТИП
2.
<список>
,V
{УСТ_ТИП}
<список>
3.
<список>

© М.Л. Цымблер
Языки программирования
48
Пример наследуемых атрибутов

Грамматика перевода описания переменных:
1.
<описание>
V{УСТ_ТИП}<список> : ТИП
2.
<список>
,V{УСТ_ТИП}<список>
3.
<список>

Введем атрибуты p
(указатель) и t
(тип) для символа действия {УСТ_ТИП}. Атрибутная грамматика описания переменных:
1.
<описание>
V
p
{УСТ_ТИП}
p1,t1
<список>
t2
: ТИП
t t1
t, t2
t, p1
p
2.
<список>
t
,V
p
{УСТ_ТИП}
p1,t1
<список>
t2
t1
t, t2
t, p1
p
3.
<список>
t

© М.Л. Цымблер
Языки программирования
49
Пример наследуемых атрибутов

Дерево вывода для описания переменных v1, v2, v3 : Real;
<
описание>
v1
<
список>
Real
:
{
УСТ_ТИП}
1,Real
ТИП
Real v2
<
список>
Real
{
УСТ_ТИП}
2,Real
,
v3
<
список>
Real
{
УСТ_ТИП}
3,Real
,
;

© М.Л. Цымблер
Языки программирования
50
Перевод арифметических выражений

Задача: построить атрибутную транслирующую грамматику, которая описывает обработку арифметических выражений синтаксическим блоком компилятора.

Пример использования искомой грамматики:
•
Выражение: (a+b)*(a+c)
•
Входная цепочка лексем: (I
A
+I
B
)*(I
A
+I
C
)
•
Выходная цепочка атомов:
СЛОЖ(A,B,R1) СЛОЖ(A,C,R2) УМНОЖ(R1,R2,R3)
•
Таблица имен:
A
– индекс идентификатора a, B – индекс идентификатора b,
C
– индекс идентификатора c, R1, R2, R3 – индексы промежуточных результатов

© М.Л. Цымблер
Языки программирования
51
Перевод арифметических выражений

Введем символы действия
{СЛОЖ}
и
{УМНОЖ}
, которые соответствуют атомам
СЛОЖ
и
УМНОЖ
, и построим грамматику перевода
(аналогично грамматике постфиксной записи):
1.

+
{СЛОЖ}
2.


3.

*
{УМНОЖ}
4.

5.
()
6.
I

© М.Л. Цымблер
Языки программирования
52
Перевод арифметических выражений

Введем атрибуты и правила их вычисления, чтобы полученная грамматика стала грамматикой перевода и позволяла вычислять значения выходных символов:
•
синтезируемые – один для каждого нетерминала, обозначает индекс элемента таблицы имен, который указывает на выражение, порождаемое данным нетерминалом
•
наследуемые – три для каждого символа действия, обозначают левый операнд, правый операнд и результат операции

Введем системную подпрограмму НОВТ, которая выдает индекс некоторого неиспользованного элемента таблицы имен.

© М.Л. Цымблер
Языки программирования
53
Перевод арифметических выражений
1.

+{СЛОЖ}
2.


3.

*
{УМНОЖ}
4.

5.
()
6.
I
1.

x

q
+
r
{СЛОЖ
y,z,p
}
(x,p)
НОВТ
y
q z
r
2.

x

p
x
p
3.

x

q
*
r
{УМНОЖ
y,z,p
}
(x,p)
НОВТ
y
q z
r
4.

x
p
x
p
5.
x
(
p
)
x
p
6.
x
I
p
x
p

© М.Л. Цымблер
Языки программирования
54
Перевод оператора

Для перевода оператора присваивания вида
идентификатор := арифметическое выражение
нужно дополнить грамматику перевода арифметических выражений правилом
<оператор>
I
var1
:=
expr1
{ПРИСВОИТЬ
var2,expr2
}
var2
var1
expr2
expr1

© М.Л. Цымблер
Языки программирования
55
Заключение

Для задания
КС-грамматики
нужно определить конечное множество
терминалов
, конечное множество
нетерминалов
, конечное множество
правил (продукций)
и начальный нетерминал

КС-язык
состоит из цепочек, которые можно получить из начального нетерминала КС-грамматики.
Класс КС-языков мощнее, чем класс регулярных
множеств
: любое регулярное множество можно описать с помощью КС-грамматики; конечный распознаватель КС-языка можно построить только в том случае, если правила КС-грамматики имеют специальный вид.

© М.Л. Цымблер
Языки программирования
56
Заключение

Синтаксически управляемая обработка
КС- языка означает обработку каждого отдельного правила соответствующей КС-грамматики.

Транслирующая грамматика (грамматика
перевода)
– КС-грамматика, терминалы которой разбиты на два подмножества:
входные символы
и
символы действия

Рассмотрена задача построения грамматики перевода арифметических выражений в
польскую запись
, в которой знак операции помещается после операндов.

© М.Л. Цымблер
Языки программирования
57
Заключение

Атрибутные транслирующие грамматики
позволяют, помимо перевода цепочек, вычислять их значение в некотором смысле.

Входные символы, символы действия и нетерминалы атрибутной транслирующей грамматики обладают конечным множеством
атрибутов
– свойств, которые используются для вычисления значения цепочки.

Атрибуты делятся на
синтезируемые
и
наследуемые