жения:
<выражение>::= <терм>│
<выражение>+<терм>│
<выражение>-<терм>
<терм> ::= <множество>│
<терм>*<множество>│
<терм>/<множество>
<множество> ::= (<выражение>)│ i
i - идентификатор
Алфавит языка - это некоторое непустое конечное множество
элементов, называемых символами.
Всякая конечная последовательность символов языка называет-
ся цепочкой.
Пустая цепочка - цепочка, не содержащая ни одного символа.
Ее длина равна 0.
Множества цепочек в алфавите обычно обозначаются заглавными
буквами.
Х = mABCn
│ │
голова хвост
xy - конкатенация цепочек x, y. х - голова, у - хвост цепоч-
ки z=xy.
Произведение АВ двух множеств цепочек А и В:
AB = { xy │ x C A, y C B }
Степень цепочки: x^0 - "", x^N = x^(N-1)*x
V* - рефлексивно-транзитивное замыкание (итерация).
V+ - транзитивное замыкание (усеченная итерация).
Бесконечные множества:
V* = V^0 U V^1 U ... U V^N U ...
Формальное описание строки:
V*={z │ z = "",z = xU}, z,x C V*, U C V - любой символ из V.
Строка x непосредственно порождает y относительно P (x->y),
когда существуют строки u, w, (возможно пустые) такие, что x=uVw,
y=uzw, V ::= z C P.
Строка x порождает y относительно P (x=>y), когда сущес-
твует последовательность строк x0, x1, x2, ... xN, такая, что
x=x0, y=xN, xI-1 -> xI (I=1,2,...,N).
Язык - некоторое множество предложений:
Lg = { x │ x C Vt*, S => x }.
Порождение (либо свертывание) строк Lg можно представить в
виде дерева. Терминальные символы не порождают новых символов,
нетерминальные - порождают. Иначе терминальные символы - это те,
на которых образуются конструкции Lg.
Cентенциальная форма: S => x, х C V+.
Предложение - цепочка терминальных символов, выведенных из
аксиомы: { x │ S => x, x C Vt* }
Пусть w=xuy - сентенциальная форма. Тогда u - фраза для U C
Vn, если S => xUy и U => u. Простая фраза - если U -> u.
Основа - самая левая простая фраза. Существуют леворекурсив-
ные и праворекурсивные грамматики. Различные грамматики могут по-
рождать один и тот же L. Мы можем генерировать синтаксически пра-
вильные сообщения.
<предложение>::=<определение><подлежащее><сказуемое><дополнение>
<определение>::=<голодный>│<большой>
<подлежащее>::=<верблюд>│<слон>│ ...
<сказуемое>::=<съел>│<взял>│ ...
<дополнение>::=<колючку>│<ветку>│ ...
Используя функции порождения строк относительно синтаксиса
этого языка, можно генерировать строки, формально принадлежащие
этому языку, правильные синтаксически, но неверные семантически (
Пример - Глоклая куздра бодланула куздренка).
G1 и G2 эквивалентны, если порождаемые ими языки Lg1 и Lg2
равны. Эквивалентные преобразования грамматик могут быть ис-
пользованы для удобства выбора семантических программ.
Однозначная грамматика - если существует только одно дерево
вывода для каждого предложения Lg.
Разбор или синтаксический анализ сентенциальной формы - это
построение вывода и, возможно, синтаксического дерева для нее.
Существуют методы как нисходящего, так и восходящего разбо-
ра (относительно движения по синтаксическому дереву).
Непосредственный вывод xUy -> xuy называют каноническим, ес-
ли u C Vt*. Вывод w=>v канонический, если все непосредственные
выводы в нем канонические.
Сентенциальная форма, имеющая канонический вывод - канони-
ческая сентенциальная форма.
Свертывание будем называть проходом или анализом. В дальней-
шем будем считать, что в процессе анализа считывание входного
текста происходит слева направо, а свертывание начинается с той
самой левой части строки, которая может быть свернута без допол-
нительного анализа последующего текста. Такое свертывание будем
называть каноническим.
Отношения
->, => - символы отношений между цепочками.
Пара цепочек (c,d) принадлежит отношению R, если выполняет-
ся cRd.
Отношение P включает R, если из (c,d) C R следует (c,d) C Р.
Отношение, обратное R - R^(-1).
Рефлексивное отношение - при справедливости сRc.
Например: i <= i - рефлексивное, а i < i - не рефлексивное
отношение.
Транзитивное отношение R - если выполняется aRb, bRc => aRc.
Произведение R,P: cRPd - если существует е, такое что cRe и ePd.
Итерация R - (обозначается R*): aR*b - когда a=b или aR+b.
Ограничения, накладываемые на грамматику G:
- нет правил вида U ::= U;
- S=>xUy, U=>t, t C Vt* - приведенная грамматика;
Пример. G - язык арифметических выражений.
S ::= E
E ::= T
E ::= E+T
T ::= P
T ::= T*P
P ::= (E)
P ::= I
ЛЕКЦИЯ 3
АНАЛИЗ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ
С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ
Будем рассматривать каноническое свертывание контекстно-сво-
бодных (КС) языков. Нахождение эффективных методов свертывания -
одна из важнейших задач в теории построения трансляторов. В рас-
сматриваемых алгоритмах анализа входного текста, написанного на
КС-языке, используются отношения предшествования между каждой па-
рой соседних символов строки.
Рассмотрим подробнее отношения предшествования: пусть Si и
Sj - символы языка L (Si,Sj С V). Если в некоторой строке языка
они могут быть записаны рядом (...SiSj...), то между ними могут
существовать только три отношения.
1. В строке ...SiSj... свертываемая часть строки начинается
└──┘
с символа Sj, то есть Sj - самый левый символ свертываемой под-
строки. Если при этом Si не является последним символом другой
строки свертываемой подстроки, то будем говорить, что Si предшес-
твует Sj. Запишем это условие в виде Si < Sj.
2. В строке ...SiSj... символы Si и Sj входят в одну и ту
└────┘
же свертываемую часть строки.Этот факт запишем в виде Si = Sj и
будем говорить, что Si и Sj входят в одно и то же свертывание.
3. В строке ...SiSj... свертываемая часть строки кончается
└──┘
символом Si, то есть Si - самый правый символ свертываемой части
строки. Это условие запишем в виде Si > Sj и будем говорить, что
Sj следует за Si.
Отношения <, =, > назовем отношениями предшествования. Отно-
шения предшествования обычно записываются в виде матрицы, стол-
бцы и строки которой соответствуют символам словаря V. На пересе-
чении i-ой строки и j-го столбца записывается отношение предшес-
твования между символами Si и Sj. Элементами матрицы являются
знаки <, =, > или пусто. Последний случай означает, что символы
Si и Sj ни в одной строке языка не могут стоять рядом.
В дальнейшем будет введено формальное определение отношений
предшествования и дан алгоритм их определения.
Сейчас же мы рассмотрим алгоритм анализа программы, разрабо-
танный Виртом и Вебером.
Достоинство этого алгоритма заключается в том, что он сни-
мает дополнительное ограничение на грамматику языка, и допускает,
чтобы в правилах грамматики два нетерминальных символа стояли ря-
дом. Но и в этом алгоритме требуется, чтобы между каждой парой
символов языка существовало не более одного отношения предшество-
вания и в множестве синтаксических правил не было двух одинако-
вых правых частей, т.е. правил, у которых правые части одинаковы,
а левые - разные.
Алгоритм основан на каноническом свертывании, т.е. на выде-
лении самой левой свертываемой части строки. Блок-схема алгорит-
ма показана на рис. 1 (@ - символ начального (конечного) ограни-
чителя входного анализируемого текста; не входит в алфавит языка).
┌────────────────────────────────┐
│ ^
┌─────┴───┬─┐ │
┌───────┬─┐ │ i:=i+1 │2│ │
│ i:=1 │1│ │ └─┤ │
│ └─┤ │ j:=i │ │
│ k:=2 │ │ │ │
│ │ │ R :=L │ │
│ R :=@ │ │ i k │ │
│ i │ │ │ │
└────┬────┘ │ k:=k+1 │ │
│ └────┬──────┘ │
│ │ │
│ ___│___ │
│ / │3\ ┌─────────┬──┐ │
│ / └──\ Да │ Конец │10│ │
│ / R равно @ \─────>┤ работы └──┤ │
│ \ i / │ алгорита │ │
│ \ / └────────────┘ │
│ \_______/ │
│ │ │
│ │ │
└───────────────────>─┤ │
┌───────────────────>─┤ Нет │
│ ___│____ │
│ / │4\ │
│ / └──\ Нет │
│ / R > L \__________________________│
│ \ i k /
│ \ ? /
│ \________/
│ Да│
│ ├<────────────────────┐
│ ____│______ │
│ / │5\ │
│ / └──\ ┌─────┴───┬─┐
│ / R = R \______│ │6│
│ \ j-1 j / Да │ j:=j-1 └─┤
│ \ / │ │
│ \___________/ └───────────┘
│ │Нет
│ ┌────────┴─────┬─┐
│ │ │7│
│ │ U < R ... R└─┤
│ │ j i │
│ └────────┬───────┘
│ │
│ │
│ ┌───────┴─────┬─┐
│ │ │8│
│ │ Переход на └─┤
│ │ семантические │
│ │ подпрограммы │
│ │ │
│ └───────┬───────┘
│ │
│ ┌───────┴────┬─┐