ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.06.2024
Просмотров: 90
Скачиваний: 0
классам языков (в зависимости от того, с какими языками работа ет машина). Поскольку все языки программирования относятся ко второму классу по классификации Хомского, то и методы в основ ном ориентированы на второй класс языков.
W |
X |
у |
j |
Рис. 21
Некоторые методы контроля вносят ограничения в грамматику языка. Обычно ограничения накладываются на правую часть пра вил: либо по числу символов, либо по их составу.
2.8.2. Метод Эйкела, Паула, Бауера, Замелзона
По сравнению с эвристическим этот метод является формали зованным, но может управлять алгоритмом грамматического раз бора, построенным только для языков определенного класса. Метод применим к языкам второго класса по классификации Хомского, т. е. к КС-языкам, правая часть которых содержит не более двух
символов: А—кг |
и |
А—>аВ. |
|
|
|
|
|
|
|
|||||
|
Ограничение длины правой части порождений, которая равна 1 |
|||||||||||||
или 2, не сужает общности метода, поскольку любое |
порождение |
|||||||||||||
вида |
А |
: : = В^2Вг... |
BhBk+l... |
BiBi+i... Вп |
возможно свести |
к |
||||||||
множеству |
порождений: |
А0: |
: = |
BiAit |
Л 4 : : = В2А2, |
А2: : = |
||||||||
= В3А3... |
|
Ап-1: |
: = Вп, |
где А\ = В2В3... |
B^Bk+i... |
Bj-Bi+i • • • В-п; |
||||||||
Л2 |
= |
В3... |
BkBk+i... |
BiBi+i... |
Вп |
и т. д. |
|
|
|
|
В2, |
|||
|
В этом |
случае |
для запоминания |
начальных |
символов |
В ь |
||||||||
В3) |
..., |
Вп |
и |
сформированных |
промежуточных |
величин Аь |
А2, |
|||||||
Аз, |
|
|
An-i используется |
специальное устройство, |
которое |
назы |
||||||||
вают либо магазином, либо стэком. Самое распространенное |
назва |
|||||||||||||
ние |
этого |
устройства — стэк. Стэк |
устроен |
так, что, |
когда |
в него |
||||||||
вводится некоторый символ, все символы, бывшие там ранее, опус каются вниз, а когда верхний символ стирается, остальные символы автоматически поднимаются на шаг вверх.
Грамматический разбор методом Бауэра-Замелзона осуществ ляется механизмом четырех таблиц: 1) стэк символов разбираемой строки; 2) синтаксическая таблица состояний п; 3) таблица дейст вий Af; 4) таблица семантических правил г.
136
Синтаксическая таблица является управляющей: состоянию п со ответствует определенное действие N — порождение или свертка. В момент определения состояния синтаксической таблицы и соот
ветствующих ей действий N подключается таблица |
семантических |
||||||
правил. При этом применение правил семантики г^Е* |
обеспечива |
||||||
ет образование кодов по входной анализируемой строке — s. |
|
||||||
Осуществление |
грамматического |
разбора |
можно |
представить |
|||
последовательностью нескольких шагов: |
|
|
|
|
|||
Шаг 1. Занесение символов входной |
строки |
в стэк. Если |
строка |
||||
имеет вид BiB2B3... |
BhBh+i ...Bi... |
Вп, |
то в стэке символы |
можно |
|||
расположить так: В^В^В^. |
..Bi. |
|
|
|
|
|
|
Шаг 2. Выявление возможного соответствия двух верхних сим волов BiBi-i стэка и текущего символа входной строки Si+i состоя нию т синтаксической таблицы. При поиске просматриваются на
соответствие только два |
верхних |
элемента стэка |
Bi |
и B j - i . |
|
|
Шаг 3. Если поиск положительный, то происходит свертка под |
||||||
строки, т. е. замена либо Si - i на |
Ai-% |
либо Bi-iBi |
на Л»_ь |
либо |
||
BiBi+i на А{, и занесение в стэк |
Bi+i. |
содержание |
стэка |
BiBi-i |
||
Шаг 3. Если поиск |
отрицателен, то |
|||||
сдвигается вниз и заносится Bi+i. |
|
|
|
|
|
|
Шаг 4. Производится |
чтение |
следующего |
символа входной |
|||
строки. |
|
|
|
|
|
|
2.8.3. Метод Флойда
Метод Флойда основан на использовании отношения «предшест- ^ вия» между двумя смежными терминальными символами, т. е. он применим также к языкам второго класса по классификации Хом-
ского, но с известным |
ограничением: порождения не должны иметь |
|||
вид с—yxWiW2y, |
где |
WiW%— смежные нетерминалы — № 4 № 2 е |
||
— Ут ), а х, у — строки |
(возможно и пустые). |
терминальных |
||
Отношения |
предшествия |
определяют состояние |
||
символов при их свертке. |
Возможные отношения |
предшествия по |
||
Вирту и Веберу записываются такими знаками: =^ F, |
-|>, |
|
Пусть при грамматическом разборе пары Т(Т^У, |
тогда: |
|
1) отношение предшествия со знаком > • будет иметь место тог |
||
да и только тогда, если Tj, |
при свертке строки s является крайне |
|
левым символом подстроки |
S ' G S , ИЛИ: |
|
....T.TJ
I>-s'
2)отношение предшествия со знаком • > имеет место тогда и только тогда, если Ti является крайне правым символом в s', или:
137
3) и, наконец, предшествие со знаком ™ имеет место тогда и только тогда, если оба символа являются частью редукцируемой подстроки s':
Если между парой символов TiTj |
нельзя |
поставить ни одного |
из отношений предшествия \Ti=Tj, |
Гг -->Г3 -, |
Ti<^-Tj\, то это гово |
рит о синтаксической ошибке. Знаки 1 / = ; 2/ • > ; 3/<^- между символами Тг и Tj можно поставить тогда и только тогда, если соот ветственно:
1)c-*xTtT}y;
|
2) c-+xTiCey и |
Ce=$*TjZ; |
|
|
||
3) |
c~>xCkTjy |
и Cfr^zTt, или |
|
|||
c^xCkCey |
и Ck=>zTlt |
Ce=>TjW, |
|
|||
где w, z, х, у — любые строки. |
|
|
|
|
||
Отношения предшествия, |
которые |
могут |
быть между |
парой |
||
символов в строке и которые |
определяются |
правилами |
вывода, |
|||
представляются в виде матрицы предшествий. Рассмотрим |
матри |
|||||
цу предшествий для одного примера. |
|
|
|
|||
Исходная матрица и правила вывода для некоторой грамматики |
||||||
заданы в следующем виде: |
|
|
|
|
|
|
Строка: 'if false |
then |
о' |
|
|
|
|
Правила вывода:
Л п/п |
Отношение предшествий символов |
Основание |
if=false 2 T h e n ~ 0
3 < state > = <[ string >
4 false • > < string >
5false • > then
6<state > < • then
7
<^state> -• if false <C string > -» then 0
< |
prog > ->- < |
state > |
<string > |
||
< |
Pr °g > |
if |
false < |
string > |
|
<C P r o S !> -* if |
false |
then 0 |
|||
< |
prog -> < |
state > |
then 0 |
||
|
|
|
ошибка |
|
|
138
Матрица предшествий будет иметь вид:
Символ |
<prog> <state> |
<string> |
l_f |
false |
then |
0 |
< prog |
> |
|
|
|
|
|
<state |
> |
|
|
|
< • |
|
< string |
> |
|
|
|
|
|
if |
|
|
|
|
|
|
false |
|
•> |
|
|
•> |
|
then |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
Число элементов такой матрицы |
очень |
велико, |
поэтому |
Вирт |
||
и Вебер обобщили метод Флойда и ввели |
новое понятие — «функ |
|||||
ция предшествия». Так как в установлении |
соотношения предшест |
|||||
вия принимают участие два символа, то требуется по крайней |
мере |
|||||
две функции — / и /, чтобы для любой |
пары символов TiTj выпол |
|||||
нялись соотношения: |
|
|
|
|
|
|
|
/(Г,.) = / ( Г ; . ) ~ 7 \ . = 7у ; |
|
|
|||
|
f(Tt) |
.>1[Т,)~ТГ>Т,; |
|
(14) |
||
/ ( 7 V ) < . / ( 7 V ) ~ 7 \ . < - 7 7
Для существования функций предшествия / и / необходимым условием является перекомпоновка матрицы предшествий таким образом, чтобы выявились три независимые области, в каждой из которых определено одно и только одно отношение из отношений предшествия:
• > e l { область }; =^=е II { область }; < • €= III { область }.
Построим матрицу предшествий для грамматики с правилами вывода:
< ехрг > -* < string > < string > ;
< ехрг > -> l i i i ;
< string > -+ < state > < ехрг > d; <^ state > -> else;
<expr > < string >_if;
<expr > if < string > .
139
