Перейдем теперь к другому частному случаю. Пусть в КС-грамматике есть правила

K -> L

K -> M

K -> №

И других правил с левой частью K нет.

Считая, что ReadL, ReadM и ReadN корректны (для L, M и N) и что множества Нач(L), Нач(M) и Нач(N) не пересекаются, написать процедуру, корректную для K.

Решение. Схема процедуры такова:

Procedure ReadK;

Begin

| if (Next принадлежит Нач(L)) then begin

| | ReadL;

| end else if (Next принадлежит Нач(M)) then begin

| | ReadM;

| end else if (Next принадлежит Нач(N)) then begin

| | ReadN;

| end else begin

| | b := true или false в зависимости от того,

| | выводимо ли пустое слово из K или нет

| end;

End;

Докажем, что ReadK корректно реализует K. Если Next не принадлежит ни одному из множеств Нач(L), Нач(M), Нач(N),то пустое слово является наибольшим началом входа, являющимся K‑началом. Если Next принадлежит одному (и, следовательно, только одному) из этих множеств, то максимальное начало входа, являющееся K‑началом, непусто и читается соответствующей процедурой.

5.4.5. Используя сказанное, составьте процедуру распознавания выражений для грамматики (уже рассматривавшейся в примере 3):

<выр> ‑> <слаг> <оствыр> <оствыр> ‑> + <выр> <оствыр> ‑> <слаг> ‑> <множ> <остслаг> <остслаг> -> * <слаг> <остслаг> -> <множ> ‑> x <множ> ‑> ( <выр> )

Решение. Эта грамматика не полностью подпадает под рассмотренные частные случаи: в правых частях есть комбинации терминалов и нетерминалов

+ <выр>