Жанр: Учеба
Программирование в теоремах и задачах
...ь в грамматике имеются два правила с нетермииналом
K в левой части, имеющих вид
K -" LK
K -"
по которым K-слово представляет собой конечную последовательность
L-слов, причем множества Посл(L) и Нач(K) (в данном
случае равное Нач(L)) не пересекаются. Используя корректную для
L процедуру ReadL, написать корректную для K процедуру ReadK, не
используя рекурсии. Предполагается, что пустое слово не выводимо
из L.
Решение. По нашим правилам следовало бы написать
procedure ReadK;
begin
| if (Next принадлежит Нач (L)) then begin
| | ReadL;
| | if b then begin ReadK; end;
| end else begin
| | b := true;
| end;
end;
завершение работы гарантируется тем, что пустое слово не выводимо
из L (и, следовательно, перед рекурсивным вызовом длина непрочитанной
части уменьшается).
Эта рекурсивная процедура эквивалентна нерекурсивной:
procedure ReadK;
begin
| b := true;
| while b and (Next принадлежит Нач (L)) do begin
| | ReadL;
| end;
end;
Формально можно проверить эту эквивалентность так. Завершаемость
в обоих случаях ясна. Достаточно проверить поэтому, что тело рекурсивной
процедуры эквивалентно нерекурсивной в предположении,
что ее рекурсивный вызов эквивалентен вызову нерекурсивной процедуры.
Подставим:
if (Next принадлежит Нач (K)) then begin
| ReadL;
| if b then begin
| | b := true;
| | while b and (Next принадлежит Нач (L)) do begin
| | | ReadL;
| | end;
| end;
end else begin
| b := true;
end;
Первую команду b := true можно выкинуть (в этом месте и так b
истинно). Вторую команду можно перенести в начало:
b := true;
if (Next принадлежит Нач (K)) then begin
| ReadL;
| if b then begin
| | while b and (Next принадлежит Нач (L)) do begin
| | | ReadL;
| | end;
| end;
end;
Теперь внутренний if можно выкинуть (если b ложно, цикл while
все равно не выполняется) и добавить в условие внешнего if условие
b (которое все равно истинно).
b := true;
if b and (Next принадлежит Нач (L)) then begin
| ReadL;
| while b and (Next принадлежит Нач (A)) do begin
| | ReadL;
| end;
end;
что эквивалентно приведенной выше нерекурсивной процедуре (из
которой вынесена первая итерация цикла).
13.2.7. Доказать корректность приведенной выше нерекурсивной
программы непосредственно, без ссылок на рекурсивную.
Решение. Рассмотрим наибольшее начало входа, являющееся
K-началом. Оно представляется в виде конкатенации (последовательного
приписывания) нескольких непустых L-слов и, возможно,
одного непустого L-начала, не являющегося L-словом. Инвариант
цикла: прочитано несколько из них; b "=" (последнее прочитанное
является L-словом).
Сохранение инварианта: если осталось последнее слово, это
очевидно; если осталось несколько, то за первым B-словом (из
числа оставшихся) идет символ из Нач(B), и потому это слово -
максимальным началом входа, являющееся B-началом.
На практике при записи грамматики используют сокращения.
Если правила для какого-то нетерминала K имеют вид
K -" L K
K -"
(т.е. K-слова - это последовательности L-слов), то этих правил
не пишут, а вместо K пишут L в фигурных скобках. Несколько правил
с одной левой частью и разными правыми записывают как одно
правило, разделяя альтернативные правые части вертикальной чертой.
Например, рассмотренная выше грамматика для "выр" может
быть записана так:
"выр" -" "слаг" { + "слаг" }
"слаг" -" "множ" { * "множ" }
"множ" -" x | ( "выр" )
13.2.8. Написать процедуру, корректно для "выр", следуя
этой грамматике и используя цикл вместо рекурсии, где можно.
Решение.
procedure ReadSymb (c: Symbol);
| b := (Next = c);
| if b then begin Move; end;
end;
procedure ReadExpr;
begin
| ReadAdd;
| while b and (Next = '+') do begin
| | Move;
| | ReadAdd;
| end;
end;
procedure ReadAdd;
begin
| ReadMult;
| while b and (Next = '*') do begin
| | Move;
| | ReadMult;
| end;
end;
procedure ReadMult;
begin
| if Next = 'x' do begin
| | Move;
| end else if Next = '(' then begin
| | Move;
| | ReadExpr;
| | if b then begin ReadSymb (')'); end;
| end else begin
| | b := false;
| end;
end;
13.3. Алгоритм разбора для LL(1)-грамматик.
В этом разделе мы рассморим еще один метод проверки выводимости
в КС-грамматике, называемый по традиции LL(1)-разбором.
Вот его идея в одной фразе: можно считать, что в процессе вывода
мы всегда заменяем самый левый нетерминал и нужно лишь выбрать
одно из правил; если нам повезет с грамматикой, то выбрать правило
можно, глядя на первый символ выводимого из этого нетерминала
слова. Говоря более формально, дадим такое
Определение. Левым выводом (слова в грамматике) называется
вывод, в котором на каждом шаге замене подвергается самый левый
из нетерминалов.
13.3.1. Для каждого выводимого слова (из терминалов) существует
его левый вывод.
Решение. Различные нетерминалы заменяются независимо; если
в процессе вывода появилось слово ..K..L.., где K, L - нетерминалы,
то замены K и L можно производить в любом порядке. Поэтому
можно перестроить вывод так, чтобы стоящий левее нетерминал заменялся
раньше. (Формально говоря, надо доказывать индукцией по
длине вывода такой факт: если из некоторого нетерминала K выводится
некоторое
слово A, то существует левый вывод A из K.)
13.3.2. В грамматике с 4 правилами
(1) E -"
(2) E -" T E
(3) T -" ( E )
(4) T -" [ E ]
найти левый вывод слова A = [()([])] и доказать, что он
единствен.
Решение. На первом шаге можно применить только правило (2):
E -" TE
Что будет дальше с T? Так как слово A начинается на "[", то может
примениться только правило (4):
E -" TE -" [E]E
Первое E должно замениться на TE (иначе вторым символом была бы
скобка "]"):
E -" TE -" [E]E -" [TE]E
и T должно заменяться по (3):
E -" TE -" [E]E -" [TE]E -" [(E)E]E
Далее первое E должно замениться на пустое слово (иначе третьей
буквой слова будет "(" или "[" - только на эти символы может начинаться
слово, выводимое из T):
E -" TE -" [E]E -" [TE]E -" [(E)E]E -" [()E]E
и далее
... -" [()TE]E -" [()(E)E]E -" [()(TE)E]E -" [()([E]E)E]E -"
-" [()([]E)E]E -" [()([])E]E -" [()([])]E -" [()([])].
Что требуется от грамматики, чтобы такой метод поиска левого
вывода был применим? Пусть, например, на очередном шаге самым
левым нетерминалом оказался нетерминал K, т.е. мы имеем слово
вида AKU, где A - слово из терминалов, а U - слово из терминалов
и нетерминалов. Пусть в грамматике есть правила
K -" L M N
K -" P Q
K -" R
Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор,
глядя на первый символ той части входного слова, которая
выводится из KU.
Рассмотрим множество Нач(LMN) тех терминалов, с которых начинаются
непустые слова, выводимые из LMN. (Это множество равно
Нач(L), объединенному с Нач(M), если из L выводится пустое слово,
а также с Нач(N), если из L и из M выводится пустое слово.)
Чтобы описанный метод был применим, надо, чтобы Нач(LMN),
Нач(PQ) и Нач(R) не пересекались. Но этого мало. Ведь может быть
так, например, что из LMN будет выведено пустое слово, а из слова
U будет выведено слово, начинающееся на букву из Нач(PQ).
Следующие определения учитывают эту проблему.
Напомним, что определение выводимости в КС-грамматике было
дано только для слова из терминалов. Оно очевидным образом обобщается
на случай слов из терминалов и нетерминалов. Можно также
говорить о выводимости одного слова (содержащего терминалы и нетерминалы)
из другого. (Если говорится о выводимости слова без
указания того, откуда оно выводится, то всегда подразумевается
выводимость в грамматике, т.е. выводимость из начального нетерминала.)
Для каждого слова X из терминалов и нетерминалов через
Нач(X) обозначаем множество всех терминалов, с которых начинаются
непустые слова из терминалов, выводимые из X. (В случае, если
из любого нетерминала выводится хоть одно слово из терминалов,
не играет роли, рассматриваем ли мы при определении Нач(X) слова
только из терминалов или любые слова. Мы будем предполагать далее,
что это условие выполнено.)
Для каждого нетерминала K через Послед(K) обозначим множество
терминалов, которые встречаются в выводимых словах сразу
же за K. Кроме того, в Послед(K) включается символ EOI, если существует
выводимое слово, оканчивающееся на K.
Для каждого правила
K -" V
(где K - нетерминал, V - слово, содержащее терминалы и нетерминалы)
определим множество "направляющих терминалов", обозначаемое
Напр(K-"V). По определению оно равно Нач(V), к которому добавлено
Послед(K), если из V выводится пустое слово.
Определение. Грамматика называется LL(1)-грамматикой, если
для любых правил K-"V и K-"W с одинаковыми левыми частями множества
Напр(K-"V) и Напр(K-"W) не пересекаются.
13.3.3. Является ли грамматика
K -" K #
K -"
(выводимыми словами являются последовательности диезов)
LL(1)-грамматикой?
Решение. Нет: символ # принадлежит множествам направляющих
символов для обоих правил (для второго - поскольку # принадлежит
Послед(K)).
13.3.4. Написать LL(1)-грамматику для того же языка.
Решение.
K -" # K
K -"
Как говорят, "леворекурсивное правило" заменено на "праворекурсивное".
Следующая задача показывает, что для LL(1)-грамматики существует
не более одного возможного продолжения левого вывода.
13.3.5. Пусть дано выводимое в LL(1)-грамматике слово X, в
котором выделен самый левый нетерминал К: X=AKS, где A - слово
из терминалов, S - слово из терминалов и нетерминалов. Пусть существуют
два различных правила грамматики с нетерминалом K в левой
части, и мы применили их к выделенному в X нетерминалу K,
затем продолжили вывод и в конце концов получили два слова из
терминалов, начинающихся на A. Доказать, что в этих словах за
началом A идут разные буквы.
Решение. Эти буквы принадлежат направляющим множествам различных
правил.
13.3.6. Доказать, что если слово выводимо в LL(1)-грамматике,
то его левый вывод единствен.
Решение. Предыдущая задача показывает, что на каждом шаге
левый вывод продолжается однозначно.
13.3.7. Грамматика называется леворекурсивной, если из некоторого
нетерминала K выводится слово, начинающееся с K, но не
совпадающее с ним. Доказать, что леворекурсивная грамматика, в
которой из каждого нетерминала выводится хотя бы одно непустое
слово из терминалов и для каждого нетерминала существует вывод
(начинающийся с начального нетерминала), в котором он встречается,
не является LL(1)-грамматикой.
Решение. Пусть из K выводится KU, где K - нетерминал, а U -
непустое слово. Можно считать, что это левый вывод (другие нетерминалы
можно не заменять). Рассмотрим вывод K --" KU --" KUU
-"... (знак --" обозначает несколько шагов вывода) и левый вывод
K -" A, где A - непустое слово из терминалов. На каком-то шаге
второй вывод отклоняется от первого, а между тем по обоим путям
может быть получено слово, начинающееся на A (в первом случае
это возможно, так как сохраняется нетерминал K, который может
впоследствии быть заменен на A). Это противоречит возможности
однозначного определения правила, применяемого на очередном шаге
поиска левого вывода. (Oднозначность выполняется для выводов из
начального нетерманала, и надо воспользоваться тем, что K по
предположению встречается в таком выводе.)
Таким образом, к леворекурсивным грамматикам (кроме тривиальных
случаев) LL(1)-наука неприменима. Их приходится преобразовывать
к эквивалентным LL(1)-грамматикам - или пользоваться
другими методами распознавания.
13.3.8. Используя сказанное, построить алгоритм проверки
выводимости слова из терминалов в LL(1)-грамматике, не являющейся
леворекурсивной.
Решение. Мы следуем описанному выше методу поиска левого
вывода, храня лишь часть слова, находящуюся правее уже прочитанной
части входного слова. Другими словами, мы храним слово S из
терминалов и нетерминалов, обладающее таким свойством (прочитанную
часть входа обозначаем через A):
| (1) слово AS выводимо в грамматике;
(И) | (2) любой левый вывод входного слова проходит через стадию
| AS
Вначале A пусто, а S состоит из единственного символа - начального
нетерминала.
Если в некоторый момент S начинается на терминал t и t =
Next, то можно выполнить команду Move и удалить символ t, являющийся
начальным в S, поскольку при этом AS не меняется.
Если S начинается на терминал t и t не равно Next, то входное
слово невыводимо - ибо по условию любой его вывод должен
проходить через AS. (Это же справедливо и в случае Next = EOI.)
Если S пусто, то из условия (И) следует, что входное слово
выводимо тогда и только тогда, когда Next = EOI.
Остается случай, когда S начинается с некоторого нетерминала
K. По доказанному выше все левые выводы из S слов, начинающихся
на символ Next, начинаются с применения к T одного и того
же правила - того, для которого Next принадлежит направляющему
множеству. Если таких правил нет, то входное слово невыводимо.
Если такое правило есть, то нужно применить его к первому символу
слова S - при этом свойство (И) не нарушится. Приходим к такому
алгоритму:
S := пустое слово;
error := false;
{error =" входное слово невыводимо;}
{not error =" (И)}
while (not error) and not ((Next=EOI) and (S пусто)) do begin
| if (S начинается на терминал, равный Next) then begin
| | Move; удалить из S первый символ;
| end else if (S начинается на терминал, не равный Next)
| | then begin
| | error := true;
| end else if (S пусто) and (Next "" EOI) then begin
| | error := true;
| end else if (S начинается на нетерминал и Next входит в
| | направляющее множество одного из правил для этого
| | нетерминала) then begin
| | применить это правило
| end else if (S начинается на нетерминал и Next не входит в
| | направляющее множество ни одного из правил для этого
| | нетерминала) then begin
| | error := true;
| end;
end;
{входное слово выводимо "=" not error}
Алгоритм заканчивает работу, поскольку при появлении нетерминала
в начале слова S происходит чтение со входа или остановка, а
бесконечный цикл сменяющих друг друга терминалов в начале S означал
бы, что грамматика леворекурсивна.
Замечания. 1. Приведенный алгоритм использует S как стек
(все действия производятся с левого конца).
2. Действия двух последних вариантов внутри цикла не приводят
к чтению очередного символа со входа, поэтому их можно заранее
предвычислить для каждого нетерминала и каждого символа
Next. После этого на каждом шаге цикла будет читаться очередной
символ входа.
3. При практической реализации удобно составить таблицу, в
которой записаны варианты действий в зависимости от входного
символа и первого символа S, и небольшую программу, выполняющую
действия в соответствии с этой таблицей.
Глава 14. Синтаксический разбор слева направо (LR)
Сейчас мы рассмотрим еще один метод синтаксического разбора,
называемый LR(1)-разбором, а также некоторые упрощенные его
варианты.
14.1. LR-процессы
Два отличия LR(1)-разбора от LL(1)-разбора: во-первых,
строится не левый вывод, а правый, во-вторых, он строится не с
начала, а с конца. (Вывод в КС-грамматике называется правым, если
на каждом шаге замене подвергается самый правый нетерминал.
14.1.1. Доказать, что если слово, состоящее из терминалов,
выводимо, то оно имеет правый вывод.
Нам будет удобно смотреть на правый вывод "задом наперед".
Определим понятие LR-процесса над словом A. В этом процессе, помимо
A, будет участвовать и другое слово S, которое может содержать
как терминалы, так и нетерминалы. Вначале слово S пусто. В
ходе LR-процесса разрешены два вида действий:
(1) можно перенести первый символ слова А (его называют
очередным символом и обозначают Next) в конец слова S, удалив
его из A (это действие называют сдвигом);
(2) если правая часть одного из правил грамматики оказалась
концом слова S, то разрешается заменить ее на нетерминал, стоящий
в левой части этого правила; при этом слово A не меняется.
(Это действие называют сверткой, или приведением.)
Отметим, что LR-процесс не является детерминированным: в
одной и той же ситуации могут быть разрешены разные действия.
Говорят, что LR-процесс на слове A успешно завершается, если
слово A становится пустым, а в слове S остается единственный
нетерминал - начальный нетерминал грамматики.
14.1.2. Доказать, что для любого слова A (из терминалов)
успешно завершающийся LR-процесс существует тогда и только тогда,
когда слово A выводимо в грамматике. В ходе доказательства
установить взаимно однозначное соответствие между правыми выводами
и успешно завершающимися LR-процессами.
Решение. При сдвиге слово SA не меняется, при свертке слово
SA подвергается преобразованию, обратному шагу вывода. Этот вывод
будет правым, так как сворачивается конец S, а в A все символы
- терминальные. Таким образом, каждому LR-процессу соответствует
правый вывод. Обратное соответствие: пусть дан правый
вывод. Представим себе, что за последним нетерминалом в слове
стоит перегородка. Применяя к этому нетерминалу правило грамматики,
мы должны сдвинуть перегородку влево (если правая часть
правила кончается на терминал). Разбивая этот сдвиг на отдельные
шаги, получим процесс, в точности обратный LR-процессу.
Поскольку в ходе LR-процесса все изменения в слове S происходят
с правого конца, слово S называют стеком LR-процесса.
Задача построения правого вывода для данного слова сводится,
таким образом, к правильному выбору очередного шага LR-процесса.
Нам нужно решить, будем ли мы делать сдвиг или свертку, и
если свертку, то по какому правилу - ведь подходящих правил может
быть несколько. В LR(1)-алгоритме это решение принимается на
основе S и первого символа слова A; если используется только S,
то говорят о LR(0)-алгоритме. (Точные определения смотри ниже.)
Пусть K -" U - одно из правил грамматики (K - нетерминал, U
- слово из терминалов и нетерминалов). Определим множество слов
(из терминалов и нетерминалов), называемое левым контекстом правила
K -" U. (Обозначение: ЛевКонт(K-"U).) По определению в него
входят все слова, которые являются содержимым стека непосредственно
перед сверткой U в K в ходе некоторого успешно завершающегося
LR-процесса.
14.1.3. Переформулировать это определение на языке правых
выводов.
Решение. Рассмотрим все правые выводы вида
"начальный нетерминал" --" XKA -" XUA,
где A - слово из терминалов, X - слово из терминалов и нетерминалов.
Все возникающие при этом слова XU и образуют левый контекст
правила K-"U. Чтобы убедиться в этом, следует вспомнить,
что мы предполагаем, что из любого нетерминала можно вывести какое-то
слово из терминалов (другие грамматики мы не рассматриваем),
так что правый вывод слова XUA может быть продолжен до правого
вывода какого-то слова из терминалов.
14.1.4. Все слова из ЛевКонт(K-"U) кончаются, очевидно, на
U. Доказать, что если у всех них этот конец U отбросить, то полученное
множество слов не зависит от того, какое из правил для
нетерминала K выбрано. (Это множество обозначается Лев(K).)
Решение. Из предыдущей задачи ясно, что Лев(K) - это все,
что может появиться в правых выводах левее самого правого нетерминала
K.
14.1.5. Доказать, что в предыдущей фразе можно отбросить
слова "самого правого": Лев(K) - это все то, что может появляться
в правых выводах левее любого вхождения нетерминала K.
Решение. Продолжив построение правого вывода, все нетерминалы
справа от K можно заменить на терминалы (а слева от K при
этом ничего не изменится).
14.1.6. Построить грамматику, содержащую для каждого нетерминала
K исходной грамматики нетерминал "ЛевК", причем следующее
свойство должно выполняться для любого нетерминала K исходной
грамматики: в новой грамматике из "ЛевК" выводимы все элементы
Лев(K) и только они.
Решение. Пусть P - начальный нетерминал грамматики. Тогда в
новой грамматике будет правило
"ЛевP" -" (пустое слово)
Для каждого правила исходной грамматики, например, правила
K -" L t M N (L, M, N - нетерминалы, t - терминал),
в новую грамматику мы добавим правила
"ЛевL" -" "ЛевК"
"ЛевМ" -" "ЛевК" L t
"ЛевN" -" "ЛевК" L t M
и аналогично поступим с другими правилами. Смысл новых правил
таков: пустое слово может появиться слева от P; если слово X может
появиться слева от K, то X может появиться слева от L, XLt
может появиться слева от M, XLtM - слева от N. Индукцией по длине
правого вывода легко проверить, что все, что может появиться
слева от какого-то нетерминала, появляется в соответствии с этими
правилами.
14.1.7. Почему в предыдущей задаче важно, что мы рассматриваем
только правые выводы?
Ответ. В противном случае следовало бы учитывать преобразования,
происходящие внутри слова, стоящего слева от K.
14.1.8. Для данной грамматики построить алгоритм, который
по любому слову выясняет, каким из множеств Лев(K) оно принадлежит.
(Замечание для знатоков. Существование такого алгоритма - и
даже конечного автомата, т.е. индуктивного расширения с конечным
числом значений, - вытекает из предыдущей задачи, т.к. построенная
в ней грамматика имеет специальный вид: в правых частях ее
всего один нетерминал, причем он стоит у левого края. Тем не менее
мы приведем явное построение.)
Решение. Будем называть ситуацией данной грамматики одно из
ее правил, в правой части которого отмечена одна из позиций (до
первой буквы, между первой и второй буквой,..., после последней
буквы). Например, правило
K -" L t M N (K, L, M, N - нетерминалы, t - терминал)
порождает пять ситуаций
К -" _LtMN, K-" L_tMN, K-" Lt_MN, K-" LtM_N, K -" LtMN_.
(позиция указывается знаком подчеркивания).
Будем говорить, что слово S согласовано с ситуацией K-"U_V,
если S кончается на U, то есть S=TU при некотором T, и, кроме
того, T принадлежит Лев(K). (Смысл этого определения примерно
таков: в стеке S подготовлена часть U для будущей свертки UV в
K.) В этих терминах ЛевКонт(K-"X) - это множество всех слов,
согласованных с ситуацией K-"X_, а Лев(К) - это множество всех
слов, согласованных с ситуацией K-"_X (где K-"_X - любое правило
для нетерминала K).
Эквивалентное определение в терминах LR-процесса: S согласовано
с ситуацией K-"U_V, если существует успешный LR-процесс,
в котором события развиваются так:
- в ходе процесса в стеке появляется слово S, и оно оканчичивается
на U;
- некоторое время S не затрагивается, а справа от него появляется
V;
- UV сворачивается в K;
- процесс продолжается и успешно завершается.
14.1.9. Доказать эквивалентность этих определений.
Указание. Если S=TU и T принадлежит Лев(K), то можно получить
в стеке сначала T, потом U, потом V, потом свернем UV в K и
затем успешно завершим процесс. (Мы используем несколько раз тот
факт, что из любого нетерминала что-то да выводится: благодаря
этому мы можем добавить в стек любое слово.)
Наша цель - построение алгоритма, распознающего принадлежность
произвольного слова к Лев(K). Рассмотрим функцию, сопоставляющую
с каждым словом S (из терминалов и нетерминалов) множество
всех согласованных с ним ситуаций. Это множество называют
состоянием, соответствующим слову S. Будем обозначать его
Сост(S). Достаточно показать, что функция Сост(S) индуктивна,
т.е. что значение Сост(SJ), где J - терминал или нетерминал, может
быть вычислено, если известно Сост(S) и символ J. (Мы видели
ранее, как принадлежность к Лев(К) выражается в терминах этой
функции.) Значение Сост(SJ) вычисляется по таким правилам:
(1) Если слово S было согласовано с ситуацией K-"U_V, причем
слово V начиналось на букву J, то есть V=JW, то теперь слово
SJ будет согласовано с ситуацией K-"UJ_W.
Это правило полностью определяет все ситуации с непустой
левой половиной (то есть не начинающиеся с подчеркивания), согласованные
с SJ. Осталось определить, для каких нетерминалов K
слово SJ принадлежит Лев(K). Это делается по двум правилам:
(2) Если уже выяснено, что ситуация L-"U_V согласована с SJ
(по правилу (1)), а V начинается на нетерминал К, то SJ принадлежит
Лев(K).
(3) Если уже выяснено, что SJ входит в Лев(L) для некоторого
L, L-"V - правило грамматики и V начинается на нетерминал K,
то SJ принадлежит Лев(K).
Заметим, что правило (3) можно рассматривать как аналог
правила (2): в указанных в (3) предположениях ситуация L-"_V
согласована с SJ, а V начинается на нетерминал K.
Корректность этих правил в общем-то очевидна, если хорошенько
подумать. Единственное, что требует некоторых пояснений -
это то, почему с помощью правил (2) и (3) обнаружатся ВСЕ терминалы
K, для которых SJ принадлежит Лев(K). Попытаемся это объяснить.
Рассмотрим правый вывод, в котором SJ стоит слева от K.
Откуда мог взяться в нем нетерминал K? Если правило, которое его
породило, породило также и конец слова SJ, то принадлежность SJ
к Лев(K) будет обнаружена по правилу (2). Если же K было первой
буквой слова, порожденного каким-то другим нетерминалом L, то -
благодаря правилу (3) - достаточно установить принадлежность SJ
к Лев(L). Осталось применить те же рассуждения к L и т.д.
В терминах LR-процесса то же самое можно сказать так. Сначала
нетерминал K может участвовать в нескольких свертках, не
затрагивающих SJ (они соответствуют применению правила (3)), но
затем он обязан подвергнуться свертке, затрагивающей SJ (что соответствует
применению правила (2)).
Осталось выяснить, какие ситуации согласованы с пустым словом,
то есть для каких нетерминалов K пустое слово принадлежит
Лев(K). Это определяется по следующим правилам: (1) начальный
нетерминал таков; (2) если K таков и K -" V - правило грамматики,
причем слово V начинается с нетерминала L, то и L таков.
14.1.1
...Закладка в соц.сетях
