Урок 4: Синтаксический анализатор, часть 2

Вступление

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

Выполнение

Вызовы функций

У нас уже есть возможность объявлять функции, но пока что нет возможности их вызывать. Вызовом функции является идентификатор, после которого в круглых скобках идёт список аргументов, разделённых запятой. Примеры вызовов функций:


f1();

f2(2);

f3(a, b, c);

f4(a + b, c || true, f1());

Теперь запишем правила для распознавания таких примеров:


call_expr:

  ident_token '(' arg_cons ')'  { printNonTerminal("ident_token '(' arg_cons ')'"); }

;

Аргументом функции может быть любое выражение:


arg_cons:

  expr                      { printNonTerminal("expr"); }

| expr ',' arg_cons         { printNonTerminal("expr ',' arg_cons"); }

| %empty                    { /* Ничего не пишем */ }

;

Функцию можно вызывать в рамках выражения, поэтому не забудем добавить её как ещё одну возможную продукцию правила expr. Кроме того, функцию можно вызывать как отдельное выражение. Следовательно, его также надо добавить как возможную продукцию правила single_statement. Теперь мы можем принимать программы следующего вида:


int main(int argc)

{

    f1();

    f2(f1() + 10, f3(argc) / 20);

}

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

Объявление переменных

Пора бы уже научиться объявлять переменные. Ранее мы делали подобную вещь в предыдущем уроке, когда прописывали сигнатуры функций. Сейчас правила будут сложнее, т.к. объявления подразумевают последовательность идентификаторов после объявления типа, а также возможность присваивания во время объявления. Примеры возможных присваиваний будут выглядеть так:


int a, d = 10, c ;

bool b = true;

Начнём распознавание объявлений с простого случая без присваиваний:


decl_statement:

  type_token ident_token decl_list                          {

      printNonTerminal("type_token ident_token decl_list");

  }

;



decl_list:

  ',' ident_token decl_list { printNonTerminal("',' ident_token decl_list");}

| %empty

;

Тут следует обратить внимание на построение списка объявляемых переменных. Ранее мы принимали списки из нуля и более элементов. Так, например правило decl_list может принимать на вход как пустую последовательность, так и содержащую один и более элементов. Но в нашем случае после объявления типа обязан идти хотя бы один идентификатор, что и отражено в правиле decl_statement.

Кстати, сам decl_statement следует добавить как возможную продукцию в правило single_statement. Теперь надо добавить возможность делать присваивания во время объявления. В обычном случае я бы не стал включать такую возможность в учебный язык, но ближе к концу урока станет понятно зачем пришлось её добавить.


decl_list:

  ',' ident_token decl_list { printNonTerminal("',' ident_token decl_list");}

| ',' ident_token '=' expr decl_list { printNonTerminal("',' ident_token '=' expr decl_list"); }

| %empty

;

У нас добавилась всего одна строчка, которая отличается наличием возможности писать знак = и выражение после идентификатора. Надо не забыть добавить эту же возможность для первого идентификатора в объявлении:


decl_statement:

  type_token ident_token decl_list                          {

      printNonTerminal("type_token ident_token decl_list");

  }

| type_token ident_token '=' expr decl_list                 {

      printNonTerminal("type_token ident_token '=' expr decl_list");

  }

;

Мы добавили возможность объявления переменных, хотя позже нам ещё придётся ещё доработать это правило для возможности работы с массивами.

Условные конструкции

Перейдём к условным конструкциям. В нашем языке мы определили их как последовательность if-elif-else. Более того, для того чтобы избежать проблемы «висячего else», мы требуем чтобы тело условия всегда обрамлялось фигурными скобками. Такие правила сложнее с точки зрения грамматики, однако удобнее для пользователя. Рассмотрим примеры условий:


if( a ) { /* ... */ }



if( b == 1 ) { /* ... */ }

elif( b == 2 ) { /* ... */ }

else { /* ... */ }



if( c == false ) { /* ... */ }

else { /* ... */ }



if( d == 5 ) { /* ... */ }

elif ( f1() ) { /* ... */ }

Грамматика такой конструкции будет состоять из трёх правил. Начнём с наиболее простого:


elif_statement:

  TOK_ELIF '(' expr ')' '{' func_body '}' elif_statement    { printNonTerminal("TOK_ELIF '(' expr ')' '{' func_body '}' elif_statement"); }

| %empty                                                    { /* Ничего не пишем */ }

;

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

Правило для повторяющихся конструкций elif мы составили, теперь необходимо составить правило для двух неповторяющихся конструкций: if и else. Начнём мы с головы условной конструкции:

if_statement_head: TOK_IF '(' expr ')' '{' func_body '}' elif_statement { printNonTerminal("TOK_IF '(' expr ')' '{' func_body '}' elif_statement"); } ;

Принцип правила остался прежним. Теперь мы умеем допускать конструкции, начинающиеся с if и завершающиеся произвольным количеством конструкций elif. Осталось только добавить необязательную конструкцию else:

if_statement: if_statement_head { printNonTerminal("if_statement_head"); } | if_statement_head TOK_ELSE '{' func_body '}' { printNonTerminal("if_statement_head TOK_ELSE '{' func_body '}'"); } ;

Эти три простых правила обеспечивают нам распознавание синтаксической конструкции if-elif-else. Теперь добавим её в качестве возможного выражения:

statement: single_statement ';' { printNonTerminal("single_statement ';'"); } | if_statement { printNonTerminal("if_statement"); } ;

И не забудем объявить токены:

%token TOK_IF TOK_ELIF TOK_ELSE

Если сравнивать с языком Си, то прелесть данной грамматики заключается в нескольких вещах. Во-первых наша грамматика не допускает выражений присваивания в условии перехода (например такого if( a = foo() )), что приводит к ошибкам из-за путаницы = и ==. Во-вторых мы запретили использовать тело сравнения без обрамления фигурными скобками, что в языке Си тоже приводит к неочевидным ошибкам. Т.к. из-за такого запрета мы не можем использовать классическую конструкцию else if, мы ввели ключевое слово elif, которое несёт тоже семантическое значение, но делает код несколько понятнее.

Циклы

В языке Си существует три вида циклов: for, do-while, while-do. Проще всего было бы сделать два последних варианта, но мы пойдём по сложному пути и будем делать цикл for, причём с его возможностями из стандарта 1999 года, но с некоторыми ограничениями.

Циклы такого вида подразумевают три необязательных секции:

Инициализация - здесь мы можем сделать объявление одной переменной с присваиванием, или просто выражение присваивания.
Условие выхода - здесь мы можем писать выражения, которые при истинном результате обязывают не начинать следующую итерацию.
Эффект итерации - выражение присваивания, которое выполняется при переходе на каждую следующую итерацию. Подразумевается что здесь должна быть работа с индуктивной переменной.

Рассмотрим примеры циклов (не все комбинации, но общий смысл понятен):

for(;;) { /* ... */ } for(a = 0; a < N; a = a + 1) { /* ... */ } for(int b; ; ) { /* ... */ } for(; b < N ; ) { /* ... */ } for(;; b = b + 1) { /* ... */ }

Соответственно, цикл можно задать следующим правилом:

for_statement: TOK_FOR '(' loop_expr_1 ';' loop_expr_2 ';' loop_expr_3 ')' '{' func_body '}' { printNonTerminal("TOK_FOR '(' loop_expr_1 ';' loop_expr_2 ';' loop_expr_3 ')' '{' func_body '}'"); } ;

Как мы видим, ничего сложного здесь нет, а секции цикла задаются также легко:

/* Опционально заводим переменную в первой секции цикла */ loop_expr_1: assign_expr { printNonTerminal("assign_expr"); } | type_token assign_expr { printNonTerminal("type_token assign_expr"); } | %empty { /* Ничего не пишем */ } ; /* Опциональное выражение во второй секции цикла (подразумевает проверку) */ loop_expr_2: expr { printNonTerminal("expr"); } | %empty { /* Ничего не пишем */ } ; /* Опциональное выражение в третьей секции цикла (работа с индукцией) */ loop_expr_3: assign_expr { printNonTerminal("type_token assign_expr"); } | %empty { /* Ничего не пишем */ } ;

В принципе, данный код не должен вызывать вопросов, все правила нам давно известны. Теперь необходимо добавить возможность перейти на правило распознавания цикла:

statement: single_statement ';' { printNonTerminal("single_statement ';'"); } | if_statement { printNonTerminal("if_statement"); } | for_statement { printNonTerminal("for_statement"); } ;

Для полноты работы с циклами не хватает ещё двух элементов: возможности завершить работу цикла и возможности немедленно перейти на следующую итерацию. Сделать их не представляет никаких проблем:

single_statement: decl_statement { printNonTerminal("decl_statement"); } | call_expr { printNonTerminal("call_expr"); } | assign_expr { printNonTerminal("assign_expr"); } | TOK_BREAK { printTerminal("TOK_BREAK"); } | TOK_CONTINUE { printTerminal("TOK_CONTINUE"); } ;

При этом не забываем объявлять токены в соответствующей секции, а также дорабатывать лексический анализатор для возврата сооветствующих классов токенов.

Итог

Мы выполнили вторую часть урока по созданию синтаксического анализатора. В язык добавлены вызовы, услвия и циклы, что в целом уже позволяет решать некоторое множество задач, однако это пока что не все возможности которые мы хотим добавить. Примеры исходного кода можно скачать здесь.

2020-12