Алгоритм Эрли – это классический нисходящий алгоритм синтаксического анализа, применимый ко всем КС-грамматикам. Это один из самых эффективных общих алгоритмов. Этот алгоритм пытается построить все возможные нетерминалы из подстрок входной строки. Читая входную строку символ за символом, алгоритм для каждой позиции входной строки формирует список всех тех частично завершённых правил грамматики, из которых прочтённый префикс входной строки и его части могут быть выведены и после чтения очередного символа этот список модифицируется.
Входная строка a1 a2 a3 … an читается слева направо. Для каждого символа ai строится множество ситуаций Mi, определяющее состояние распознавателя после анализа этого символа. Ситуации это:
1. Помеченное правило грамматики Pr Î R, согласно которому в данный момент считывается сегмент входной цепочки, выводящийся в соответствии с правилом Pr.
2. Место в правиле Pr, показывающее, какая доля правой части этого правила уже распознана (отмечается мета-символом ·).
3. Указатель позиции во входной цепочке, после которого начался поиск возможности применения этого правила.
Для удобства дополним грамматику правилом S¢®#S#, где S¢ - новый нетерминал, а # - дополнительные терминальные ¢скобки¢, в которые будет помещаться каждая терминальная строка, порождаемая исходной грамматикой. Тогда начальное множество ситуаций M0 = {<S¢®·#S#; 0>}.
Множество ситуаций изменяется операторами:
¨ Предсказатель. Если во множестве ситуаций Mi есть ситуация <A®a·Bb; q>, то предсказатель добавляет в Mi ситуации <B®·g; i> для всех правил грамматики вида B®g. Назовём ситуацию <A®a·Bb; q> родительской, ситуацию <B®·g; i> - порождённой.
¨ Считыватель. Если в Mi есть ситуация <A®a·bb; q> и если b – очередной символ ai+1, то в Mi+1 добавляет ситуацию <A®ab·b; q>
¨ Завершитель. Применяется к любой ситуации вида <A®a·; q> в Mi. В Mq завершитель ищет ситуацию <A®·a; q>, и для каждой ситуации <B®g·Am; s>, которая является родительской для <A®·a; q>, в Mi он добавляет новую ситуацию <B®gA·m; s>
Эти три оператора применяются до тех пор, пока Mi и Mi+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®a·b; i> находится во множестве Mi тогда и только тогда, когда существует вывод SÞ*gAd такой, что gÞ*a1a2…ai и aÞ*ai+1ai+2… aj
Алгоритм Эрли имеет временную сложность O(n3) и пространственную сложность O(n2). Для недвусмысленной грамматики временная сложность составляет O(n2).
LR(k) – грамматики
Это наиболее широкий класс КС-грамматик, допускающих эффективный восходящий грамматический разбор. ‘L’ – означает, что анализируемая цепочка просматривается слева-направо, ‘R’ – означает, что восстанавливается правый вывод цепочки, k – указывает количество символов, которые алгоритм просматривает вперёд для принятия однозначного решения.
LR(k) алгоритм считывая цепочку посимвольно определяет самую левую сворачиваемую подстроку, а также тот нетерминал левой части, которым следует заменить эту подстроку. LR(k) учитывает при этом информацию о всей просмотренной части цепочки.
LR(k) алгоритм читает цепочки и выдаёт ответ: какое правило определяет очередную подцепочку после просмотра ровно k символов после этой подцепочки. Другой взгляд: LR(k) алгоритм – это конечный автомат, состояния которого – множества ситуаций.
Опр. Ситуация это помеченное правило, метка указывает, в каком месте продукции находится алгоритм на данном шаге. Формально ситуация – это
<A®a·b; g>,
что соответствует правилу A®ab, а знак · - метка, g - правый контекст длиной k.
Так как правил конечное количество, их помеченных наборов тоже конечное количество, контекстов длины g тоже конечное количество, то множеств ситуаций тоже конечное количество.