является 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 не входит в
| | направляющее множество ни одного из правил для этого
