LL(1)-грамматики

Рассмотрим свойства грамматик, поддерживающих методы нисходящего синтаксического анализа с одним символом предпросмотра. Будем считать, что грамматики являются однозначными, так что каждому предложению языка соответствует единственное левое порождение – порождение, при котором на каждом этапе заменяется крайний левый нетерминал. Нетерминал – символ, используемый грамматикой для генерации предложений языка. В данном случае для каждого нетерминала, который находится в левой части нескольких продукций, необходимо найти такие непересекающиеся множества символов предпросмотра, чтобы каждое множество содержало символы, соответствующие точно одной возможной правой части. Выбор конкретной продукции для замены данного нетерминала будет определяться символом предпросмотра и множеством, к которому принадлежит данный символ. Объединение различных непересекающихся множеств для заданного нетерминала не обязательно должно составлять алфавит, на котором определен язык. Если символ предпросмотра не принадлежит ни одному из непересекающихся множеств, можно сделать вывод о наличии синтаксической ошибки.

Множество символов предпросмотра, соотнесенных с применением определенной продукции, называется ее множеством первых порождаемых символов (director symbol set). Перед определением данного понятия определим вначале следующие два:

1. Стартовый символ данного нетерминала определяется как любой символ (например, терминал), который может появиться в начале строки, генерируемой нетерминалом.

2. Символ-последователь данного нетерминала определяется как любой символ (терминал или нетерминал), который может следовать за нетерминалом в любой сентенциальной форме.

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

Продукция Множество стартовых символов

T–> aG {a}

T–> bG {b}

В общем случае, если продукция начинается с терминала, ее множество стартовых символов просто состоит из этого терминала. В то же время если продукция не начинается с терминала, для нее все равно нужно вычислить множество стартовых символов. Пусть в рассматриваемой грамматике имеются следующие продукции для нетерминала R

R–>BG

R–>CH

Тогда множество стартовых символов для этих продукций нельзя определить "с ходу". В то же время пусть имеются только следующие продукции для нетерминала В

B®cD

B®TV

Тогда можно заключить, что множеством стартовых символов для продукции

R®BG

будет набор

{а, b, с}

состоящий из всех стартовых символов для В.

Введение символа с в множество стартовых является очевидным (см. первую продукцию для В), а введение набора (а, b) объясняется тем, что эти символы являются стартовыми для Т. В общем случае ситуация может быть значительно сложнее.

Еще одним источником сложностей можно назвать нетерминалы, которые могут генерировать пустые строки. Допустим, имеются следующие продукции:

A®BC

B®e

В этом случае множество стартовых символов для продукции A®ВСбудет включать стартовые символы С, а также стартовые символы В (определяемые не приведенными здесь продукциями). Если оба нетерминала В и С могут генерировать пустые строки, то на использование данной продукции будут указывать символы предпросмотра, являющиеся последователями А и стартовыми символами ВС. Множество первых порождаемых символов продукции выбирается как множество всехтерминалов, которые, выступая как символы предпросмотра, указывают на использование данной продукции.

Существует алгоритм поиска множеств первых порождаемых символов для всех продукций грамматики. Сложность этого алгоритма, в основном, связана с тем, что символы могут генерировать пустые строки; в данной книге этот алгоритм приводиться не будет. После вычисления всех множеств первых порождаемых символов их можно проверить на предмет пересечения. LL(1)-грамматикуможно определить как грамматику, в которой для каждого нетерминала, появляющегося в левой части нескольких продукций, множества первых порождаемых символов всех продукций, в которых появляется этот нетерминал, являются непересекающимися. Термин LL(1) имеет следующее происхождение: первое L означает чтение слева (Left) направо, второе L означает использование левых (Leftmost) порождений, а 1 – один символ предпросмотра. Если вычислены все множества первых порождаемых символов для всех возможных правых частей продукций, то языки, которые описываются LL(1)-грамматикой, всегда анализируются детерминированно, т.е. без необходимости отменять продукцию после ее применения. Существуют более распространенные классы грамматик, которые могут использоваться для детерминированного нисходящего анализа, но обычно используются именно LL(1)-грамматики. Недетерминированный нисходящий анализ, основанный на откате (backtracking), уже не считается эффективной процедурой, хотя в начале эры компиляторов он широко использовался в языках, подобных FORTRAN. Грамматики LL(k),требующие kсимволов предпросмотра для различения альтернативных правых частей, также уже не считаются практичными с точки зрения синтаксического анализа.

LL(1) – это язык, который можно сгенерировать посредством LL(1)-грамматики. Отсюда следует, что для любого LL(1)-языка возможен нисходящий синтаксический анализ с одним символом предпросмотра. Рассмотрим некоторые "теоретические" результаты, связанные с LL(1)-грамматиками и языками, после чего перейдем к более практическим вопросам реализации.

Во-первых, как было сказано выше, существует алгоритм определения, относится ли данная грамматика к классу LL(1), поэтому грамматику можно проверить на " LL(1)-ность", прежде чем создавать на ее основе программу синтаксического анализа. В то же время что может несколько удивить на первый взгляд, не существует алгоритма определения, относится ли данный язык к классу LL(1), т.е. имеет он LL(1)-грамматику или нет. Это означает, что не-LL(1)-грамматика может иметь или не иметь эквивалентную LL(1), генерирующую тот же язык, и не существует алгоритма, который для данной произвольной грамматики определит, является ли генерируемый ею языкLL(1) или нет. Разумеется, существуют алгоритмы, которые могут использоваться для частных случаев, например, если грамматика является LL(1) – язык также является LL(1); также можно выделить определенные классы грамматик, которые никогда не будут генерировать LL(1)-языки. В то же время в общем случае задача является неразрешимой в том же смысле, как неразрешимы задача определения однозначности языка и проблема остановки для машин Тьюринга.

Имеются грамматики, не являющиеся LL(1), которые, тем не менее, генерируют LL(1)-языки, т.е. грамматики имеют эквивалентные LL(1)-грамматики. Это означает, что грамматики нужно преобразовывать, прежде чем использовать с методами нисходящего синтаксического анализа. Фактически грамматики, которые обычно используются в определениях языков или в учебниках, редко являются LL(1) и, следовательно, не могут непосредственно использоваться для эффективного нисходящего анализа. Тем больше оснований сожалеть, что не существует алгоритма определения, имеет ли грамматика эквивалентную LL(1), а это означает, что в любом случаене существует алгоритма поиска эквивалентной LL(1)-грамматики, если даже такая грамматика и существует. Впрочем, в этом несовершенном мире иногда приходится иметь дело с несовершенными алгоритмами. Так что, если нет алгоритма выполнения преобразования в общем случае (т.е. для всех случаев), имеются алгоритмы, работающие для большого числа групп частных случаев, которые никогдане дают неверного результата. В то же время эти алгоритмы иногда могут зацикливаться.

Не стоит пугаться, что существует одно свойство грамматики, которое (если оно присутствует) препятствует тому, чтобы грамматика была LL(1), и это – левая рекурсия.

Использование данной продукции никогда не даст ни одной строки терминалов, поскольку не существует способа избавиться от нетерминала D, если таковой появится в сентенциальной форме. Грамматика с продукциями, которые не могут использоваться или (по каким-то причинам) не являются необходимыми, часто называется «нечистой»(unclean); далее предполагается, что все рассматриваемые грамматики являются «чистыми».

Левая рекурсия может быть непрямой, включающей две или более продукции. Рассмотрим, например, следующий набор продукций.

Здесь имеет место непрямая левая рекурсия, в которой задействованы нетерминалы А, В, D и F. Разумеется, должны существовать нерекурсивные правила, по крайней мере, для некоторых нетерминалов, гарантирующие чистоту грамматики. Как и для прямой левой рекурсии, любая грамматика, имеющая непрямую левую рекурсию, будет характеризоваться пересекающимися множествами первых порождаемых символов для некоторых нетерминалов и, следовательно, такая грамматика не может быть LL(1). Итак, ни одна леворекурсивная грамматика не является LL(1). Это не представляет такой уж серьезной проблемы, как может показаться на первый взгляд, поскольку можно показать, что вселевые рекурсии грамматики можно заменить правыми, не затронув генерируемый язык.

Преобразования грамматик, выполняемые автоматически или вручную, являются неотъемлемой частью LL(1)-анализа и, как говорят многие, одним из его ограничений.

Будет полезно почитать по теме: