Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

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

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 → EE | 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 → EE | E=E | E<>E | (B)

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

Для организации таблицы идентификаторов выберем комбинированный способ, поскольку в нем отсутствуют ограничения на количество входных идентификаторов и он не требует разработки сложной и эффективной хэш-функции (разработка комбинированной таблицы в данном случае проще, чем выбор хорошей хэш-функции).

В качестве такого способа возьмем комбинацию хэш-адресации и бинарного дерева, которая была использована при выполнении лабораторной работы № 1.

Программный код, реализующий такую таблицу идентификаторов, приведен в листингах П3.1 и П3.2 в приложении 3. Для того чтобы в таблице идентификаторов в именах переменных не различались строчные и прописные буквы, этот код должен быть откомпилирован с указанием соответствующих условий.

Для построения лексического анализатора воспользуемся подходом, использованном в лабораторной работе № 2.

Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются:

• двенадцать ключевых слов языка (prog, end., if, else, begin, end, while, end, not, or, xor и and);

• разделители: открывающая и закрывающая круглые скобки, точка с запятой;

• знаки операций: присваивание, сравнение (четыре знака), сложение, вычитание и унарный минус;

• идентификаторы;

• целые десятичные константы без знака.

Можно заметить, что end и end. – это разные лексемы.

Кроме перечисленных лексем распознаватель должен уметь определять и исключать из входного текста комментарии, принцип построения которых описан выше. Для выделения комментариев ключевыми символами должны быть открывающая и закрывающая фигурные скобки.

Отдельного внимания заслуживает знак «унарный минус», который не случайно был взят в качестве иллюстрации для этого примера.

Если не делать различий между унарным минусом и бинарным, то правила грамматики G для символов E, T и F имели бы следующий вид:

E → E—T | E+T | T

T → —T | F

F → (E) | a | c

Однако такая грамматика будет очень сложна для синтаксического анализа, поскольку в ней возникает проблема выбора правила между E—T и – T при выполнении свертки (можно проверить и прийти к выводу, что она, например, не является грамматикой операторного предшествования). Преобразования для этой грамматики неочевидны.