Книга: Системное программное обеспечение. Лабораторный практикум

Грамматика входного языка

Грамматика входного языка

Грамматику входного языка построим на основе фрагментов грамматик, рассмотренных в заданиях по лабораторной работе № 3. Там имеются правила для линейных операций (арифметические и логические операции) и для условного оператора. По аналогии с условным оператором построим оператор цикла. Для составного оператора и всей программы в целом останется определить еще одно понятие – последовательность операторов. Будем рассматривать последовательность операторов как цепочку операторов, разделенных знаком «точка с запятой».

В результате получим КС-грамматику в форме Бэкуса—Наура:

G({prog,end.,if,else, begin, end,while, do, or,xor,and,not,<,>,=, <>, (,), – ,+,um,a,c,=},

{S,L, 0,B,C,D,E, T,F},P,S)

с правилами P:

S ? prog L end.

L ? О | L;0 | L;

О ? if(B) О else О | if(B) О | begin L end | while(B)do О | a:=E

В ? В or С | В xor С | С

С ? С and D | D

D ? E<E | E>E | E=E | E<>E | (В) | not(B)

E ? E-T | E+T | T

T ? um T | F

F ? (E) | a | с

Жирным шрифтом выделены терминальные символы.

Всего в построенной грамматике G 28 правил. Нетерминальные символы грамматики имеют следующий смысл:

• S вся программа;

• L последовательность операторов (может состоять и из одного оператора);

• О – оператор (пять видов: полный условный оператор, неполный условный оператор, составной оператор, оператор цикла, оператор присваивания);

• В, С – логическое выражение и его элементы;

• D операция сравнения или логическое выражение в скобках;

• Е,Т, F – арифметическое выражение и его элементы.

Можно обратить внимание на следующие моменты в грамматике:

• операция um («унарный минус») обозначена отдельным терминальным символом, не совпадающим со знаком арифметической операции вычитания («-»), хотя в тексте исходной программы эти два символа идентичны;

• константы и переменные обозначены двумя различными терминальными символами – а и с соответственно – это говорит о том, что они должны различаться на этапе синтаксического анализа;

• операция отрицания not обязательно требует после себя выражения в скобках, что не совсем соответствует традиционной записи логических операций (но не противоречит заданию!), традиционная запись могла бы быть записана в виде правил:

D ? not D | G

G ? E<E | E>E | E=E | E<>E | (B)

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

Оглавление книги