Детерминированный восходящий синтаксический анализ

1. Детерминированный восходящий синтаксический анализ

Вопросы:
1.Общие принципы
2. Грамматики предшествования
3. Технология построения анализатора предшествования в
системе «Каштан»

2. Общие принципы синтаксического анализа снизу-вверх

Для заданной входной цепочки восходящий МП-автомат моделирует ее правый вывод в
обратном порядке и манипулирует своими магазинными и текущими входными символами с
помощью операций переноса и свертки.
Операция переноса – это операция, которая вталкивает в магазин некоторый символ,
соответствующий текущему входному символу и сдвигает вход.
Операция свертки, для некоторого правила p с r символами в правой части – это операция,
которая выбирается только тогда, когда с верхних символов магазина представляют правую часть
правила р. Операция свертки выталкивает из магазина верхние r символов и вталкивает туда символ,
соответствующий левой части правила р.
Пример Пусть задана грамматика G = <N, T, P, S> у которой
N = <S, L, I>, Т = {i, , , real}, S = {S} и
Р={
1. S real L
2. L L , I
3. L I
4. I i }
и входная цепочка real i , i.
Правый вывод этой цепочки в грамматике G имеет вид:
S real L real L, I real L, i real I, i real i, i

3.

Обращение правого вывода имеет вид:
real i , i ├
real I , i ├ real L, i ├ real L , I ├ real L ├ S ├
4
3
4
2
1
Команды МП-автомата:
Содержимое
магазина
Применяемая
команда
Содержимое
входной ленты
real i , i├
ПЕРЕНОС
# real
i , i├
ПЕРЕНОС
# real i
, i├
СВЕРТКА (4)
Комбинация
входного
символа на ленте и символа
на вершине магазина должны
в каждом такте работы МПавтомата,
однозначно
инициировать
выполнение
одной из его команд:
# real I
, i├
СВЕРТКА (3)
ПЕРЕНОС
# real L
, i├
ПЕРЕНОС
ОТВЕРГНУТЬ
# real L
i├
ПЕРЕНОС
ДОПУСТИТЬ
# real L , i
├
СВЕРТКА (4)
СВЕРТКА (k)
# real L , I
├
СВЕРТКА (2)
# real L
├
СВЕРТКА (1)
где k - номер основывающей
подстановки
#S
├
ДОПУСТИТЬ
#

4. Грамматики предшествования

Метод предшествования.
Пусть G = <N, T, P, S> – КС-грамматика и i, j V = {N Т} и пусть в ходе порождения
предложений языка L(G) на некотором шаге вывода получена сентенциальная форма вида:
*r i j *p
Символы i и j стоят рядом в сентенциальной форме. При этом их соседство можно
охарактеризовать с помощью отношений специального вида, которые называют отношениями
предшествования.
Определение
1. Между символами i и j существует отношение i j , если в грамматике G есть правило вида
А i j , где , {N Т}*.
2. Между символами i и j существует отношение i <o j , если в грамматике G есть правила вида
А iB и вывод B=> i , где A, B N; , , {N
Т}*.
3. Между символами i и j существует отношение i >o j , если в грамматике G есть правила вида
А BC и выводы B=> 1 i, C j 2 , где A, B, C N; 1, 2 {N Т}*
или правило вида
А B j 1 и вывод B=> 2 i.

5.

Иначе:
i j , то символы i и j принадлежат одной основе;
i <o j , то символ j - самый левый символ некоторой основы;
i >o j , то символ i - самый правый символ некоторой основы.
Пример
промежуточные цепочки обращенного правого вывода:
# < real < i > , < i > ├
основа
# < real < I > , < i > ├
основа
# < real < L , < i > ├
основа
# < real < L , I > ├
основа
# < real L > ├
основа
# < S > ├
основа

6. Правила нахождения отношений предшествования.

1. Для вычисления отношения одинакового предшествования просмотреть все правые
части правил грамматики pi P и выписать все пары соседствующих символов ( i , j). Объединить
их в множество PVV ( ) = {( i , j) | i j}.
2. Для вычисления отношения < и построения множества PVV (< ) = {( i , j) | i< j}
определим:
2.1. Множество PVN ( ) = {( i , nj) | i nj {P ( ) {VxN}}}.
2.2. ( i , j) PVN включить в множество P( >) пары вида { i} x F+(nj), где F+(nj) множество всех символов, которые могут быть начальными в предложениях за один и более шагов
выводимых из нетерминала nj по правилам из Р.
3. Для вычисления отношения > и построения множества
P( >) = {( i , tj) | i > tj, tj T}
определим:
3.1. Множество PNT ( ) = {(ni , tj) | ni tj {PVV ( ) {NxT}}}.
3.2. ni включить в множество P( >) пары вида (R+ (ni) x {tj}), где R+ (ni) - множество
символов, которые могут быть самыми правыми в предложениях, нетривиально (т.е. за один или
более шагов) выводимых из ni.
3.3. Построить множество
PNN ( ) = {(ni , nj) | ni nj {PVV ( ) {NxV}}}.
3.4. ni и nj PNN () включить в множество P( >) пары вида: R+ (ni) x {F+ (nj) Т}.

7.

Определение
Грамматика G называется грамматикой простого предшествования, если она
приведенная, не содержит -правил и для любой пары ее символов выполняется не более одного
отношения предшествования.
Пример
Для КС-грамматики G=<N, T, P, S> N={S, L, I}, T={real, ... , i}, S={S},
P = {S real L
L L,I
L I
I i }
Построим множества отношений предшествования:
1. PVV ( ) = {(real, L), (L, ,), (, , I)}
2. Найдем элементы множества P (< ):
2.1. PVN ( ) = {(real, L), (, , I)}
2.2. F+(L) = {L, I, i}
F+(I) = {i}
F+(L) = {L, I, i}
P (< ) = {(real, L), (real, I), (real, i), (, , i)}
3. Найдем элементы множества P ( >):
3.1. PNT ( ) = {(L, ,)}
3.2. R+(L) = {I, i}
P ( >) = {(I, ,), (i, ,)}
3.3. PNN ( ) = .
данная грамматика не является грамматикой простого предшествования: между символами real и L
выполняются одновременно отношения и < .

8.

Преобразуем в грамматику простого предшествования. Для этого достаточно ввести новый
нетерминал и новое правило, получим:
G' = <N', T, P', S>, N' = {S, L, L', I}, T = {real, i, ,}, S = {S},
P' = { S real L'
L' L
L L,I
L I
I i }.
Построенные множества отношений предшествования для преобразованной грамматики
имеют вид:
P ( ) = {(real, L'), (L, ,), (, , I)}
P (< ) = {(real, L), (real, I), (real, i), (, , i)}
P ( >)= {(I, ,), (i, ,)}.
грамматика G' является грамматикой простого предшествования.

9. Такт работы МП - анализатора

варианты:
1) Ни одно из отношений не определено, т.е. символы не могут стоять рядом в цепочке.
Тогда входная цепочка отвергается.
2) Для пары определено отношение или <о. Тогда СДВИГ: анализатор записывает в магазин
символ <о, если это отношение выполняется для данной пары, переносит после этого в магазин левый
символ входной цепочки и сдвигает входную цепочку на одну ячейку влево.
3) Для пары определено отношение о>. Тогда СВЕРТКА:
Шаг 1. Просматривает справа налево символы в магазине, пока не будет обнаружен символ
<о и выделяет подцепочку, состоящую из просмотренных символов (без символа <о). Переходит к
шагу 2.
Шаг 2. Ищет правило вывода грамматики, правая часть которого совпадает с выделенной на
первом шаге подцепочкой. Если такое правило найдено, то переходит к шагу 3, в противном случае - к
шагу 5.
Шаг 3. Исключает из магазина найденные на первом шаге подцепочку и символ <о.
Образует пару, состоящую из символа, оказавшегося в магазине правым, и символа из левой части
найденного на втором шаге правила грамматики. Переходит к шагу 4.
Шаг 4. Ищет отношение предшествования для образованной на третьем шаге пары. Если
ни одно из отношений не выполняется, то входная цепочка отвергается. В противном случае в магазин
записывается символ <° и нетерминальный символ из левой части правила. После этого свертка
заканчивается.
Шаг 5. Анализирует содержимое магазина и входной ленты. Если в магазине находится
цепочка # <о S, где S - аксиома грамматики, а на входной ленте остался один лишь маркер конца
цепочки ├, то входная цепочка допускается. В противном случае она отвергается.

10.

Технология разработки восходящего анализатора в системе
«Каштан»
Назначение системы:
Система «Каштан» предназначена для автоматизации:
•Конструирования корректного описания языка, заданного в БНФ
•Автоматического синтеза и исследования моделей лексического и
синтаксического анализа
Состав системы:
•Управляющая подсистема
•Процессор синтаксического анализа
•Процессор лексического анализа
•Подсистема отображения