Все существующие программы. Часть 3

 

Предположим, мы хотим написать грамматику для упрощенного объявления классов языка C#. Давайте предположим, что наш идентификатор состоит из одного символа, класс может быть открытым (public) или внутренним (internal) и что не существует вложенных или обобщенных типов, и также не существует членов. Как насчет такого?

DECL:     MODIFIER class ID : ID { }
MODIFIER: public | internal
ID:       a | b | c | d

Итак, строка public class d : b {} является корректной. Но мы забыли, что модификатор доступа должен быть необязательным:

DECL:           WITHMODIFIER | WITHOUTMODIFIER
WITHMODIFIER:   MODIFIER WITHOUTMODIFIER
WITHOUTMODIFER: class ID : ID { }
MODIFIER:       public | internal
ID:             a | b | c | d

И мы забыли, что базовый класс также является необязательным…

DECL:            WITHMODIFIER | WITHOUTMODIFIER
WITHMODIFIER:    MODIFIER WITHOUTMODIFIER
WITHOUTMODIFIER: MAYBEBASE { }
MAYBEBASE :      WITHOUTBASE : ID | WITHOUTBASE
WITHOUTBASE:     class ID
MODIFIER:        public | internal
ID:              a | b | c | d

Все это выполнимо, но, как вы видите, становится несколько запутанным. Гораздо легче, если бы мы могли сказать «вообще ничего» является корректной заменой. Поскольку эта запись становится весьма сложной, я собираюсь создать новое правило, по которому NIL будет являться специальным терминальным символом, что является отличным способом записи пустой строки. В этом случае нашу грамматику читать станет значительно проще:

DECL: MODIFIER class ID BASE { }
MODIFIER: NIL | public | internal
BASE: NIL | : ID
ID: a | b | c | d

Это добавление влечет очень интересные последствия. До этого любое применение правила делало «текущую строку» не короче в терминах количества терминальных плюс нетерминальных символов. Теперь после замены мы можем получить результирующую строку с меньшим количеством нетерминальных символов без добавления каких-либо терминальных символов. Но я забегаю немного вперед.

Здесь я описал “NIL”, как терминальный символ, который является особым случаем записи пустой строки. Также символ “NIL” можно описать, как нетерминальный символ; NIL – это особый нетерминальный символ, который может быть заменен только на пустую строку. В оставшихся статьях этой серии я буду рассматривать этот символ, как удобный способ записи пустой терминальной строки.

В следующий раз: рассмотрим механизмы генерации всех членов языка программирования

Оригинал статьи