Рассмотрим предложение (со следующим символом begin d semi d comma s semi s end 1 Ниже приводится разбор этого предложения.

Заметим, что некоторые терминалы проверяются несколько раз. Такой неоднократной проверки, очевидно, можно избежать, если разработчики согласны отложить обнаружение некотортх синтаксических ошибок на более поздний этап («поздний» в смысле тагов разбора, но не считанного текста). Можно также сократить число элементов в таблице разбора.

Желательно, чтобы элементы в таблице разбора были небольшими. Тогда, ограничив число терминалов в грамматике и диапазон переходов в пределах таблицы разбора, можно будет, вероятно, упаковать каждый элемент таблицы в машинное слово (24 бита в машинах серии ICL 1900). Это, очевидно, замедлит работу синтаксического анализатора во время компиляции из-за распаковки, которую придется выполнять, но зато позволит получить небольшую таблицу разбора (на несколько тысяч слов) даже для таких объемных языков, как Алгол 68. Как мы увидим позднее, при обсуждении методов разбора снизу вверх размер таблицы разбора часто представляет большую проблему для разработчика компиляторов, чем скорость анализатора.

При наличии Ы(1)-грамматикн можно написать программу для получения соответствующей таблицы разбора. Используемый при этом алгоритм имеет много общего с проверкой наличия признака LL(l), и их часто объединяют, как, например, в пакете SID/SAG, разработанном в RSRE в Малверне. Драйвер можно, конечно, применять многократно для различных компиляторов, так что при наличии соответствующих средстр программного обеспечения возможно получение Ы(1)-анализатора из грамматики с наименьшей затратой усилий.

i Действие

begin считывает и проверяется; перейти к pt [2]

2 begin считывает и принимается; перейти к pt [3]

3 d считывает и проверяется; 4 помещается в стек; перейти к pt [7]

7 d проверяется; перейти к pt [8]

d проверяется и принимается; перейти к pt [9]

semi считывает и проверяется; перейти к pt [10]

semi проверяется; перейти к pt [12]

semi проверяется и принимается; перейти к pt

d считывает и проверяется; перейти к pt [7]

d проверяется; перейти к pt [8]

d проверяется и принимается; перейти к pt [9]

разбора 0

[13]

4 0 4 0 4 0 4 0 4 0 4 0 4 0 4

0 4 0

0 1 4

5 6 7 8 0 1 5 6 7 8 9 2

9 comma считывает и проверяется; перейти к pt

[10]

comma не совпадает с semi ; ошибка ложь -перейти к pt [11]

comma проверяется; перейти к pt [14]

comma проверяется; возврат истина - pop 4; перейти к pt [4]

4 comma проверяется и принимается; перейти к pt

5 s считывает и проверяется; 6 помещается в стек; перейти к pt [15]

s проверяется; перейти к pt [16]

s проверяется и принимается; перейти к pt [17]

semi считывает и проверяется; перейти к pt [18]

semi проверяется; перейти к pt [20]

semi проверяется и принимается; перейти к pt

s считывает и проверяется; перейти к pt [15]

s проверяется; перейти к pt [16]

s проверяется и принимается; перейти к pt [17]

end считывает и проверяется; перейти к pt [18]

[21]

end не совпадает с semi; ошибка ложь - перейти

к pt [19]

end проверяется; перейти к pt [22] 2 end проверяется; возврат истина - pop 6; перейти

к pt [6]

6 end проверяется и принимается; возврат истина -pop 0; i:=0

0 Разбор заканчивается

4 0 4 0 4 0 0

6 0 6 0 6 0 6 0 6 0 6 0 6 0 6

0 6 0 6 0 6 0 6 0 0

LL(1)-метод разбора имгп ряд преимуществ:

1. Никогда не требуется возврат, поскольку этот метод -детерминированный.

2. Время разбора, (приблизительно) пропорционально длине про граммы. Как будет показано ниже, для процесса компиляции в целом это может оказаться не так, поскольку некоторые действия, выполняемые во время компиляции, например поиск в таблице, могут потребовать различное время в зависимости от размера таблиц, что в свою очередь связано с размером программы.

3. Имеются хорошие диагностические характеристики и существует возможность исправления ошибок, так как синтаксические ошибки рас познаются по первому неприемлемому символу, а в таблице разбора есть список возможных символов продолжения. Методы исправления ошибок обсуждаются в гл. 12.

4. Таблицы разбора меньше, чем соответствующие таблицы в других методах разбора.

5. LL(l)-paзбop применим к широкому классу языков - всех языков, имеющих LL( 1)-грамматики. Нужно, однако, добавить, что в большинстве случаев «очевидной» грамматикой для языка программирования оказывается не LL(1), и ее придется преобразовать в LL(l)-rpaмматику до того, как будет применен этот метод. LR(1)-разбор, как мы видим в следующей главе, можно применять к еще более широкому классу языков, а преобразования грамматик требуются редко. В той же главе мы рассмотрим и относительные достоинства этих двух методов.

Мы можем расширить принцип LL(1) -грамматик до LL(k)-rpамматик и, чтобы различать альтернативные порождающие правила для нетерминалов, использовать k(k>1) предварительно просматриваемых символов. Тогда анализатору придется рассматривать строки Длиной k, так как это весьма вероятно, задача станет намного сложнее. На практике для разбора даже LL(2) -грамматики используются редко, хотя грамматика, частично являющаяся LL (2) -грамматикой, могла бы применяться на основе LL(1) -анализатора, которому разрешается при необходимости исследовать дополнительный символ.

Примером LL(2) -грамматики может служить грамматика, приведенная в начале разд. 4.2, а примером Ы(3)-грамматики - представленная ниже:

PROGRAM->begin DECLIST semi STATELIST end

DECLIST->d semi DECLIST

STATELIST->s semi STATELIST s

Эквивалентная И(1)-грамматика:

PROGRAM->begin d semi X end X->d semi X X->s Y Y->e

Y->semi s Y

Упражнения

4.1 Определите аргументированно, какие из следующих языков являются детерминированными:

a){ucala в {0,1} * };

б) {cuara в {a,b}" }

(ar означает обратную а);

в) {0n1nn>0}; .

г) {0n12nn>0};

д) {0nlnn>0}U{0nl2nn>0}

4.2 Покажите, что следующие языки не являются контекстно-свободными:

а) {anbncnn>0};

б) (аii есть простое число).