Контекстно-свободная грамматика называется q-грамматикой тогда и только тогда, когда выполняются два условия:
1. Правая часть каждого правила либо представляет собой пустую цепочку e, либо начинается с терминального символа.
2. Множество выбора правил с одной и той же левой частью не пересекаются.
Второе условие следует рассмотреть подробнее, так как необходимо ввести ряд определений. Одно из них – множество выбора. Для демонстрации определений будем использовать пример q-грамматики G9.4(S):
1. S → aAS
2. S → b
3. A → cAS
4. A → e
О том, что это не S-грамматика говорит правая часть правила 4, которая не начинается с терминального символа. Однако, метод построения НАМП, изложенный для S-грамматики почти подходит и здесь.
Множество терминалов, следующих за данным нетерминалом X (Обозначим через СЛЕД(X)) – множество терминальных символов, которые могут следовать непосредственно за Х в какой-либо промежуточной цепочке, выводимой из S┤, включая и ┤.
Это множество символов называется также множеством следуемых за Х терминалов. Для приведенной грамматики можно определить следующие множества:
СЛЕД (А) = { a, b }
СЛЕД (S) = { a, b }
Терминалы, следующие за A, определяются исходя из того, что за A следует всегда нетерминал S, правая часть правила для которого начинается либо с a, либо с b. Терминалы, следующие за S, выводятся путем подстановки в правило 1 правила 3, которая показывает, что за S всегда следует S, начинающаяся либо с a, либо с b:
S Þ aAS Þ acASS.
Данное понятие используется для того, чтобы показать, когда следует применять правило с пустой правой частью A → e. Если входной символ Ti Ï { a, b }, то есть, является символом c или ┤, a на вершине магазина А, то бесполезно применять A → e. Если это правило будет применено, то А удаляется из стека, а так как за А символы c или ┤ следовать не могут, то в результате процесс останавливается. Представим, что у нас уже есть автомат, соответствующий грамматике G9.4, и очень похожий на АМП, распознающий S-грамматику. Тогда, применительно к цепочке аасbb, можно получить несколько решений. В начале рассмотрим стратегию, при которой в первую очередь применяется всегда пустое правило.
| Номер шага | Содержимое стека | Остаток входной цепочки | Номер применяемого правила | Комментарий |
| Ñ S | aacbb┤ | |||
| Ñ SA | acbb┤ | Иначе, процесс разбора дальше не пойдет | ||
| Ñ S | acbb┤ | |||
| Ñ SA | cbb┤ | А здесь данный шаг ведет к отказу по отношению к правильной цепочке | ||
| Ñ S | cbb┤ | Отвергнуть | Придется осуществлять возврат |
Правильным было бы применение на шаге 4 правила 3, в соответствии с ранее рассмотренными рекомендациями о месте и времени применения пустого правила.
| Номер шага | Содержимое стека | Остаток входной цепочки | Номер применяемого правила | Комментарий |
| Ñ S | aacbb┤ | |||
| Ñ SA | acbb┤ | Иначе, процесс разбора дальше не пойдет | ||
| Ñ S | acbb┤ | |||
| Ñ SA | cbb┤ | Пойдем в соответствии с предложенными рекомендациями | ||
| Ñ SSA | bb┤ | Иначе, процесс разбора дальше не пойдет | ||
| Ñ SS | bb┤ | |||
| Ñ S | b┤ | |||
| Ñ | ┤ | Допустить |
Таким способом решается одна из задач детерминированного разбора, связанная с особенностями применения пустого правила. Однако, при разборе, построенном на основе q-грамматики возможна и такая ситуация, когда:
A → bα, A → e и b Î СЛЕД (A).
В этом случае стоит проблема выбора одного из правил с одинаковыми левыми частями. Для ее решения введем понятие множества выбора для данного правила.
Если правило грамматики имеет вид: A → bα, где b – терминал, а α – цепочка терминалов и нетерминалов, то определим множество выбора для правила A → bα равным b. Обозначим данную запись следующим образом:
ВЫБОР (A → bα) = b.
Если правило имеет вид: A → e, то определим:
ВЫБОР (A → e) = СЛЕД (A).
Если p – номер правила, то будем также писать «ВЫБОР (p)» вместо «ВЫБОР (правило)»
ВЫБОР (p) – множество выбора правила p.
Проиллюстрируем построение множества выбора на примере грамматики G9.4.
ВЫБОР (1) = ВЫБОР (S → aAS) = { a }
ВЫБОР (2) = ВЫБОР (S → b) = { b }
ВЫБОР (3) = ВЫБОР (A → cAS) = { c }
ВЫБОР (4) = ВЫБОР (A → e) = СЛЕД (A) = { a, b }
В соответствии с определением, рассмотренным в начале, имеем q-грамматику, так как:
ВЫБОР (1) È ВЫБОР (2) = Æ,
ВЫБОР (3) È ВЫБОР (4) = Æ.
