Нисходящий алгоритм Эрли

Алгоритм Эрли – это классический нисходящий алгоритм синтаксического анализа, применимый ко всем КС-грамматикам. Это один из самых эффективных общих алгоритмов. Этот алгоритм пытается построить все возможные нетерминалы из подстрок входной строки. Читая входную строку символ за символом, алгоритм для каждой позиции входной строки формирует список всех тех частично завершённых правил грамматики, из которых прочтённый префикс входной строки и его части могут быть выведены и после чтения очередного символа этот список модифицируется.

Входная строка a₁ a₂ a₃ … a_n читается слева направо. Для каждого символа a_i строится множество ситуаций M_i, определяющее состояние распознавателя после анализа этого символа. Ситуации это:

1. Помеченное правило грамматики Pr  R, согласно которому в данный момент считывается сегмент входной цепочки, выводящийся в соответствии с правилом Pr.

2. Место в правиле Pr, показывающее, какая доля правой части этого правила уже распознана (отмечается мета-символом ).

3. Указатель позиции во входной цепочке, после которого начался поиск возможности применения этого правила.

Для удобства дополним грамматику правилом S#S#, где S - новый нетерминал, а # - дополнительные терминальные скобки, в которые будет помещаться каждая терминальная строка, порождаемая исходной грамматикой. Тогда начальное множество ситуаций M₀ = {<S#S#; 0>}.

Множество ситуаций изменяется операторами:

 Предсказатель. Если во множестве ситуаций M_i есть ситуация <AB; q>, то предсказатель добавляет в M_i ситуации <B; i> для всех правил грамматики вида B. Назовём ситуацию <AB; q> родительской, ситуацию <B; i> - порождённой.

 Считыватель. Если в M_i есть ситуация <Ab; q> и если b – очередной символ a_i+1, то в M_i+1 добавляет ситуацию <Ab; q>

 Завершитель. Применяется к любой ситуации вида <A; q> в M_i. В M_q завершитель ищет ситуацию <A; q>, и для каждой ситуации <BA; s>, которая является родительской для <A; q>, в M_i он добавляет новую ситуацию <BA; s>

Эти три оператора применяются до тех пор, пока M_i и M_i+1 не стабилизируются, а затем считывается новый символ и всё повторяется. Входная цепочка будет распознана, если в заключительном множестве будет содержаться ситуация вида <S#S#; 0>

Пример.

Дана грамматика S#E# EE+T | T TT*P | P Pa

Рассмотрим цепочку #a+a# и построим множество ситуаций.

	#		a		+		a		#
M0		M1		M2		M3		M4		M5
S#E# ; 0		S#E# ; 0		Pa ; 1		EE+T ; 1		Pa ; 3		S#E# ; 0
		EE+T ; 1		TP ; 1		TT*P ; 3		TP ; 3
		ET ; 1		TT*P ; 1		TP ; 3		TT*P ; 3
		TT*P ; 1		ET ; 1		Pa ; 3		EE+T ; 1
		TP ; 1		EE+T ; 1				EE+T ; 1
		Pa ; 1		S#E# ; 0				S#E# ; 0

Если из этих множеств удалить несущественные ситуации, то получим множества существенных ситуаций:

	#		a		+		A		#
M0		M1		M2		M3		M4		M5
S#E# ; 0		S#E# ; 0		Pa ; 1		EE+T ; 1		Pa ; 3		S#E# ; 0
		EE+T ; 1		TP ; 1				TP ; 3
		ET ; 1				TP ; 3
				ET ; 1		Pa ; 3		EE+T ; 1
		TP ; 1		EE+T ; 1
		Pa ; 1						S#E# ; 0

Теорема.

Ситуация <A; i> находится во множестве M_i тогда и только тогда, когда существует вывод S^A такой, что ^a₁a₂…a_i и ^a_i+1a_i+2… a_j

Алгоритм Эрли имеет временную сложность O(n³) и пространственную сложность O(n²). Для недвусмысленной грамматики временная сложность составляет O(n²).