Правила вычисления функции first(α). Правило Если α начинается с терминала a, то Правило Если, то

Аргументом FIRST является строка символов α (из терминалов и нетерминалов).

• Аргументом FIRST является строка символов α (из терминалов и нетерминалов).

• Определение. Функция FIRST(α) определяет множество терминальных символов, с которых могут начинаться строки, выводимые из α. Если , то

• Формально

• Правила вычисления функции FIRST(α).

• Правило 1. Если α начинается с терминала a, то

• Правило 2. Если , то .

• Правило 3. Если α начинается с нетерминала A, то включает в себя .

Определение. Функция FOLLOW (A) для нететрминала A определяется как множество терминальных символов, которые могут следовать за A в какой-нибудь промежуточной цепочке вывода. Формально

• Определение. Функция FOLLOW (A) для нететрминала A определяется как множество терминальных символов, которые могут следовать за A в какой-нибудь промежуточной цепочке вывода. Формально

• Обычно исходная грамматика преобразуется так, что вводится новый начальный символ S' с правилом .

• Это гарантирует, что ни один нетерминал не окажется крайним справа ни в одной цепочке вывода в этой грамматике.

• Рекурсивный алгоритм для нахождения FOLLOW(A). Просматриваются последовательно все правила грамматики, в правой части которых встречается A, и для каждого такого правила вида помещаем в FOLLOW(A) все элементы

• , кроме . Если в этой продукции , то помещаем в FOLLOW(A) все элементы FOLLOW(B).