Компиляция. 4: игрушечный ЯП

С грамматиками калькуляторов поиграли достаточно, переходим к языкам программирования. Бета-тестеры статьи подали идею писать JavaScript-подобный язык: начнём с простейшего скобчатого скелета, и будем его постепенно обращивать наворотами — синтаксическим сахаром, типами данных, поддержкой функций, и т.д.

Чтобы неполноценность нашего языка была понятна уже из названия, назовём его JSkrip.

Далее в посте

1. Синтаксис
2. Грамматика
3. Парсер
4. Синтаксическое дерево
5. Pretty-printing

Синтаксис

В начальном варианте языка будут арифметические конструкции над целыми числами, if, while, и exit; и пара «предопределённых функций»: echo() для печати, и input() для ввода.

from = 0; to = 1000;
echo("Задумай число от ",from," до ",to,", а я буду угадывать\n");
while (from <= to) {
   guess = (from+to)/2;
   echo("Это ",guess,"?  (1=меньше, 2=больше, 3=попал) ");
   i = input();
   if (i==1)
      to = guess-1;
   else if (i==2)
      from = guess+1;
   else if (i==3) {
      echo("Ура! Я молодец!\n");
      exit;
   } else
      echo("Я ничего не понял!\n");
}
echo("Врёшь, так не бывает!\n");


Грамматика

Смотрим на пример программы, и пытаемся формализовать язык:

PROGRAM: OPS ;  // последовательность операторов
OPS: OP | OPS OP ;
OP: '{' OPS '}' // блок
    | EXPR ';'  // выражение
    | 'if' '(' EXPR ')' OP
    | 'if' '(' EXPR ')' OP 'else' OP
    | 'while' '(' EXPR ')' OP
    | 'exit' ';' ;
EXPR: NUM // переменная
    | ID  // литерал
    | ID '(' ARGS ')' // вызов функции
    | EXPR '+' EXPR | EXPR '-' EXPR | EXPR '*' EXPR | EXPR '/' EXPR | '(' EXPR ')' | '-' EXPR // арифметика
    | EXPR '==' EXPR | EXPR '<=' EXPR | EXPR '>=' EXPR | EXPR '!=' EXPR | EXPR '>' EXPR | EXPR '<' EXPR
    | '!' EXPR // не будем заводить отдельные булевы операции; вместо && будет *, и вместо || будет +
    | ID '=' EXPR ;   // присваивание
ARGS: // пустой список
    | ARG // один аргумент
    | ARGS ',' ARG ;
ARG: EXPR | STRING ;  // строки возможны только в аргументах


Натыкаемся на уже знакомые неоднозначности: с else, и с группировкой операторов в выражении. Уже знаем, как починить грамматику:

PROGRAM: OPS ;
OPS: OP | OPS OP ;
// операторы, за которыми может следовать else внешнего условия
OP1: '{' OPS '}' | EXPR ';'
     | 'if' '(' EXPR ')' OP1 'else' OP1 // if с else: оператором не может быть if без else
     | 'while' '(' EXPR ')' OP1
     | 'exit' ';' ;
// операторы, заканчивающиеся на if без else
OP2: 'if' '(' EXPR ')' OP     // if без else: оператор может быть любой
     | IF '(' EXPR ')' OP1 ELSE OP2
     | WHILE '(' EXPR ')' OP2 ;
OP: OP1 | OP2 ;
EXPR: EXPR1 | ID '=' EXPR ;   // низший приоритет и правая ассоциативность
// остальные операторы левоассоциативные, по возрастанию приоритета
EXPR1: EXPR2
     | EXPR1 '==' EXPR2 | EXPR1 '<=' EXPR2 | EXPR1 '>=' EXPR2
     | EXPR1 '!=' EXPR2 | EXPR1 '>' EXPR2 | EXPR1 '<' EXPR2 ;
EXPR2: TERM | EXPR2 '+' TERM | EXPR2 '-' TERM ;
TERM: VAL | TERM '*' VAL | TERM '/' VAL ;
VAL: NUM | '-' VAL | '!' VAL | '(' EXPR ')' | ID | ID '(' ARGS ')' ;
ARGS: | ARG | ARGS ',' ARG ;
ARG: EXPR | STRING ;


Парсер

Достаточно добавить привычный бизоний заголовок, чтобы превратить грамматику в парсер-пустышку:

%{
    #include <iostream>
    extern int yylineno;
    extern int yylex();
    void yyerror(char *s) {
      std::cerr << s << ", line " << yylineno << std::endl;
      exit(1);
    }
    #define YYSTYPE std::string
%}

%token IF ELSE WHILE EXIT
%token EQ LE GE NE
%token STRING NUM ID

%%

PROGRAM: OPS
;

OPS:    OP
|       OPS OP
;

OP1:    '{' OPS '}'
|       EXPR ';'
|       IF '(' EXPR ')' OP1 ELSE OP1
|       WHILE '(' EXPR ')' OP1
|       EXIT ';'
;

OP2:    IF '(' EXPR ')' OP
|       IF '(' EXPR ')' OP1 ELSE OP2
|       WHILE '(' EXPR ')' OP2
;

OP:     OP1 | OP2 ;

EXPR:   EXPR1
|       ID '=' EXPR

EXPR1:  EXPR2
|       EXPR1 EQ EXPR2
|       EXPR1 LE EXPR2
|       EXPR1 GE EXPR2
|       EXPR1 NE EXPR2
|       EXPR1 '>' EXPR2
|       EXPR1 '<' EXPR2
;

EXPR2: TERM
|       EXPR2 '+' TERM
|       EXPR2 '-' TERM
;

TERM:   VAL
|       TERM '*' VAL
|       TERM '/' VAL
;

VAL:    NUM
|       '-' VAL
|       '!' VAL
|       '(' EXPR ')'
|       ID
|       ID '(' ARGS ')'
;

ARGS:
|       ARG
|       ARGS ',' ARG
;

ARG:    EXPR
|       STRING
;

%%
int main() { return yyparse(); }

В этот раз нам удобнее в каждом токене хранить не число, а строку (std::string). Тип для значений символов задаётся макросом YYSTYPE.

Осталось приделать к грамматике лексер; в нём будет небольшая хитрость — именованные состояния, для распознавания искейпов внутри строк.
Файлы нашего языка будем называть jsk.

%{
   #include <string>
   #define YYSTYPE std::string
   #include "jsk.tab.h"
   void yyerror(char *s);
%}

%option yylineno
%option noyywrap

%x STR

%%

[/][/].*\n      ; // comment
if              return IF;
else            return ELSE;
while           return WHILE;
exit            return EXIT;
==              return EQ;
[<]=            return LE;
>=              return GE;
!=              return NE;
[0-9]+          { yylval = yytext;
                  return NUM;
                }
[a-zA-Z_][a-zA-Z0-9_]* { yylval = yytext;
                  return ID;
                }
["]             { yylval = ""; BEGIN(STR); }
<STR>[^\\\n"]+  yylval += yytext;
<STR>\\n        yylval += '\n';
<STR>\\["]      yylval += '"';
<STR>\\         yyerror("Invalid escape sequence");
<STR>\n         yyerror("Newline in string literal");
<STR>["]        { BEGIN(INITIAL); return STRING; }
[ \t\r\n]       ; // whitespace
[-{};()=<>+*/!,] { return *yytext; }
.               yyerror("Invalid character");

%%

Объявление %x определяет именованное состояние, в которое лексер переходит не в результате чтения входных символов, а в результате явного вызова BEGIN(STR). Начальное состояние называется INITIAL; чтобы вернуться в него, вызываем BEGIN(INITIAL). В результате у нас в лексере есть два разных набора регэкспов: один для основной программы, другой для строковых литералов. На каждой кавычке переключаемся между этими двумя наборами.

Получившийся парсер-пустышка ищет в программе ошибки синтаксиса; и если не находит, то не выводит ничего:
[tyomitch@home ~]$ lex jsk.lex
[tyomitch@home ~]$ bison -d jsk.y
[tyomitch@home ~]$ c++ lex.yy.c jsk.tab.c
[tyomitch@home ~]$ ./a.out < test.jsk
[tyomitch@home ~]$ ./a.out
{ foo();
bar; }
}
syntax error, line 3


Синтаксическое дерево

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

Определим для каждого типа узла в дереве отдельный класс, и в стеке парсера будем хранить указатели на объекты-узлы. Кроме них, в стеке могут лежать пришедшие от лексера строки, а также «промежуточные результаты», для которых решим не выделять в дереве отдельного узла. В нашем примере, символу ARGS не соответствует узел дерева: ссылки на все аргументы функции будем хранить прямо в узле «вызов функции». Иными словами, синтаксическое дерево не обязано соответствовать дереву разбора в точности; имеем право перестраивать его поудобнее. Другой пример несоответствия — что в нашем синтаксическом дереве не будет узла «оператор»; только «список операторов» — возможно, из одного элемента.

%{
    #include <iostream>
    #include <list>
    extern int yylineno;
    extern int yylex();
    void yyerror(char *s) {
        std::cerr << s << ", line " << yylineno << std::endl;
        exit(1);
    }

    class oper_t { // abstract
        protected: oper_t() {}
        public: virtual ~oper_t() {}
    };

    class expr_t { // abstract
        protected: expr_t() {}
        public: virtual ~expr_t() {}
    };

    class block : public oper_t {
        std::list<oper_t*> ops;
        void append(oper_t* op) {
            block* b = dynamic_cast<block*>(op);
            if(b) {
                ops.splice(ops.end(), b->ops, b->ops.begin(), b->ops.end());
                delete b;
            }
            else ops.push_back(op);
        }
        public:
            block() {}
            block(oper_t* op) { append(op); }
            block(oper_t* op1, oper_t* op2) { append(op1); append(op2); }
    };

    class exprop : public oper_t {
        expr_t* expr;
        public: exprop(expr_t* expr) : expr(expr) {}
    };

    class ifop : public oper_t {
        expr_t* cond;
        block thenops, elseops;
        public: ifop(expr_t* cond, oper_t* thenops, oper_t* elseops) :
                cond(cond), thenops(thenops), elseops(elseops) {}
    };

    class whileop : public oper_t {
        expr_t* cond;
        block ops;
        public: whileop(expr_t* cond, oper_t* ops) : cond(cond), ops(ops) {}
    };

    class exitop : public oper_t {};

    class binary : public expr_t {
        const char* op;
        expr_t *arg1, *arg2;
        public: binary(const char* op, expr_t *arg1, expr_t *arg2) :
                op(op), arg1(arg1), arg2(arg2) {}
    };

    class assign : public expr_t {
        std::string name;
        expr_t* value;
        public: assign(const std::string& name, expr_t* value) :
                name(name), value(value) {}
    };

    class unary : public expr_t {
        const char* op;
        expr_t* arg;
        public: unary(const char* op, expr_t* arg) : op(op), arg(arg) {}
    };

    class funcall : public expr_t {
        std::string name;
        std::list<expr_t*> args;
        public: funcall(const std::string& name,
                const std::list<expr_t*>& args) :
                name(name), args(args) {}
    };

    class value : public expr_t {
        std::string text;
        public: value(const std::string& text) : text(text) {}
    };

// возможные значения символа: строка, оператор, выражение, список аргументов
    typedef struct {
        std::string str;
        oper_t* oper;
        expr_t* expr;
        std::list<expr_t*> args;
    } YYSTYPE;
    #define YYSTYPE YYSTYPE

// глобальная замена
    std::string replaceAll(const std::string& where, const std::string& what, const std::string& withWhat) {
        std::string result = where;
        while(1) {
            int pos = result.find(what);
            if (pos==-1) return result;
            result.replace(pos, what.size(), withWhat);
        }
    }
%}

%token IF ELSE WHILE EXIT
%token EQ LE GE NE
%token STRING NUM ID

%type<str> ID NUM STRING
%type<oper> OPS OP1 OP2 OP
%type<expr> EXPR EXPR1 EXPR2 TERM VAL ARG
%type<args> ARGS

%%

PROGRAM: OPS                            // обработка дерева программы
;

OPS:    OP                              // inherit
|       OPS OP                          { $$ = new block($1, $2); }
;

OP1:    '{' OPS '}'                     { $$ = $2; }
|       EXPR ';'                        { $$ = new exprop($1); }
|       IF '(' EXPR ')' OP1 ELSE OP1    { $$ = new ifop($3, $5, $7); }
|       WHILE '(' EXPR ')' OP1          { $$ = new whileop($3, $5); }
|       EXIT ';'                        { $$ = new exitop(); }
;

OP2:    IF '(' EXPR ')' OP              { $$ = new ifop($3, $5, new block()); }
|       IF '(' EXPR ')' OP1 ELSE OP2    { $$ = new ifop($3, $5, $7); }
|       WHILE '(' EXPR ')' OP2          { $$ = new whileop($3, $5); }
;

OP:     OP1 | OP2 ;                     // inherit

EXPR:   EXPR1                           // inherit
|       ID '=' EXPR                     { $$ = new assign($1, $3); }

EXPR1:  EXPR2                           // inherit
|       EXPR1 EQ EXPR2                  { $$ = new binary("==", $1, $3); }
|       EXPR1 LE EXPR2                  { $$ = new binary("<=", $1, $3); }
|       EXPR1 GE EXPR2                  { $$ = new binary(">=", $1, $3); }
|       EXPR1 NE EXPR2                  { $$ = new binary("!=", $1, $3); }
|       EXPR1 '>' EXPR2                 { $$ = new binary(">", $1, $3); }
|       EXPR1 '<' EXPR2                 { $$ = new binary("<", $1, $3); }
;

EXPR2:  TERM                            // inherit
|       EXPR2 '+' TERM                  { $$ = new binary("+", $1, $3); }
|       EXPR2 '-' TERM                  { $$ = new binary("-", $1, $3); }
;

TERM:   VAL                             // inherit
|       TERM '*' VAL                    { $$ = new binary("*", $1, $3); }
|       TERM '/' VAL                    { $$ = new binary("/", $1, $3); }
;

VAL:    NUM                             { $$ = new value($1); }
|       '-' VAL                         { $$ = new unary("-", $2); }
|       '!' VAL                         { $$ = new unary("!", $2); }
|       '(' EXPR ')'                    { $$ = $2; }
|       ID                              { $$ = new value($1); }
|       ID '(' ARGS ')'                 { $$=new funcall($1, $3); }
;

ARGS:                                   { $$.clear(); }
|       ARG                             { $$.clear(); $$.push_back($1); }
|       ARGS ',' ARG                    { $$ = $1; $$.push_back($3); }
;

ARG:    EXPR                            // inherit
|       STRING                          { $$=new value('"'+replaceAll($1, "\n", "\\n")+'"'); }
;

%%
int main() { return yyparse(); }

Объявление %type<str> задаёт для символов грамматики (терминалов и нетерминалов), каким из полей YYSTYPE следует пользоваться в качестве значения символа. Если поле задано, то бизон будет подставлять его каждый раз, когда $-тег относится к такому символу грамматики. Если поле не задано (как в предыдущих примерах), то YYSTYPE используется целиком.
В классических сишных парсерах YYSTYPE объявляли как union: каждый символ по-своему трактует одно и то же хранимое значение. Нам такое не подходит: объект с деструктором не может быть полем union; поэтому объявляем YYSTYPE как структуру, и ненужные символу поля структуры будут просто занимать зря память. Но мы не жадные.

Неприятный момент — что из-за починки конфликта с else в грамматике появилось два одинаковых правила if..else и два одинаковых правила while. На нашей совести выбрать, что неприятнее: задавать приоритет для else и ), как будто бы они операторы; или копипастить код свёртки дважды.

Итак, наш парсер строит в памяти дерево, и когда оно готово — просто выходит, даже не освобождая память. Не слишком-то впечатляюще?

Pretty-printing

Нужно совсем немного усилий, чтобы парсер делал нечто осмысленное; например, расставлял в выражениях скобки, удалял избыточные {} и, и вдобавок выравнивал операторы по BSD Kernel Normal Form.
Добавим в наши древесные классы рекурсивную распечатку.
Меняются только определения классов, и свёртка символа PROGRAM.

#define TOKENPASTE(x, y) x ## y
#define TOKENPASTE2(x, y) TOKENPASTE(x, y)
#define foreach(i, list) typedef typeof(list) TOKENPASTE2(T,__LINE__); \
                    for(TOKENPASTE2(T,__LINE__)::iterator i = list.begin(); i != list.end(); i++)

    class oper_t { // abstract
        protected: oper_t() {}
        public: virtual ~oper_t() {}
        virtual void print(int indent=0) =0;
    };

    class expr_t { // abstract
        protected: expr_t() {}
        public: virtual ~expr_t() {}
        virtual void print() =0;
    };

    class block : public oper_t {
        std::list<oper_t*> ops;
        void append(oper_t* op) {
            block* b = dynamic_cast<block*>(op);
            if(b) {
                ops.splice(ops.end(), b->ops, b->ops.begin(), b->ops.end());
                delete b;
            }
            else ops.push_back(op);
        }
        public:
            block() {}
            block(oper_t* op) { append(op); }
            block(oper_t* op1, oper_t* op2) { append(op1); append(op2); }
        int size() { return ops.size(); }
        virtual void print(int indent=0) {
            foreach(i, ops) {
                std::cout << std::string(indent, '\t');
                (*i)->print(indent);
            }
        }
        virtual ~block() { foreach(i, ops) delete *i; }
    };

    class exprop : public oper_t {
        expr_t* expr;
        public: exprop(expr_t* expr) : expr(expr) {}
        virtual void print(int indent=0) {
            expr->print();
            std::cout << ";" << std::endl;
        }
        virtual ~exprop() { delete expr; }
    };

    class ifop : public oper_t {
        expr_t* cond;
        block thenops, elseops;
        public: ifop(expr_t* cond, oper_t* thenops, oper_t* elseops) :
                cond(cond), thenops(thenops), elseops(elseops) {}
        virtual void print(int indent=0) {
            std::cout << "if "; cond->print();  std::cout << " {" << std::endl;
            thenops.print(indent+1);
            if (elseops.size()) {
                std::cout << std::string(indent, '\t') << "} else {" << std::endl;
                elseops.print(indent+1);
            }
            std::cout << std::string(indent, '\t') << "}" << std::endl;
        }
        virtual ~ifop() { delete cond; }
    };

    class whileop : public oper_t {
        expr_t* cond;
        block ops;
        public: whileop(expr_t* cond, oper_t* ops) : cond(cond), ops(ops) {}
        virtual void print(int indent=0) {
            std::cout << "while "; cond->print();  std::cout << " {" << std::endl;
            ops.print(indent+1);
            std::cout << std::string(indent, '\t') << "}" << std::endl;
        }
        virtual ~whileop() { delete cond; }
    };

    class exitop : public oper_t {
        virtual void print(int indent=0) { std::cout << "exit;" << std::endl; }
    };

    class binary : public expr_t {
        const char* op;
        expr_t *arg1, *arg2;
        public: binary(const char* op, expr_t *arg1, expr_t *arg2) :
                op(op), arg1(arg1), arg2(arg2) {}
        virtual void print() {
            std::cout<<"(";
            arg1->print();
            std::cout<<op;
            arg2->print();
            std::cout<<")";
        }
        virtual ~binary() { delete arg1; delete arg2; }
    };

    class assign : public expr_t {
        std::string name;
        expr_t* value;
        public: assign(const std::string& name, expr_t* value) :
                name(name), value(value) {}
        virtual void print() { std::cout<<name<<" = "; value->print(); }
        virtual ~assign() { delete value; }
    };

    class unary : public expr_t {
        const char* op;
        expr_t* arg;
        public: unary(const char* op, expr_t* arg) : op(op), arg(arg) {}
        virtual void print() { std::cout<<op; arg->print(); }
        virtual ~unary() { delete arg; }
    };

    class funcall : public expr_t {
        std::string name;
        std::list<expr_t*> args;
        public: funcall(const std::string& name,
                const std::list<expr_t*>& args) :
                name(name), args(args) {}
        virtual void print() {
            std::cout<<name<<"(";
            foreach(i,args) {
                if (i!=args.begin())
                    std::cout<<", ";
                (*i)->print();
            }
            std::cout<<")";
        }
        virtual ~funcall() { foreach(i,args) delete *i; }
    };

    class value : public expr_t {
        std::string text;
        public: value(const std::string& text) : text(text) {}
        virtual void print() { std::cout<<text; }
    };

PROGRAM: OPS                            { $1->print(); delete $1; }
;

Проверяем, что получилось:
[tyomitch@home ~]$ lex jsk.lex
[tyomitch@home ~]$ bison -d jsk.y
[tyomitch@home ~]$ c++ jsk.tab.c lex.yy.c
[tyomitch@home ~]$ ./a.out < test.jsk
from = 0;
to = 1000;
echo("Задумай число от ", from, " до ", to, ", а я буду угадывать\n");
while (from <= to) {
    guess = ((from + to) / 2);
    echo("Это ", guess, "? (1=меньше, 2=больше, 3=попал) ");
    i = input();
    if (i == 1) {
        to = (guess - 1);
    } else {
        if (i == 2) {
            from = (guess + 1);
        } else {
            if (i == 3) {
                echo("Ура! Я молодец!\n");
                exit;
            } else {
                echo("Я ничего не понял!\n");
            }
        }
    }
}
echo("Врёшь, так не бывает!\n");

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

Понятно, что ради одного лишь форматирования текста не было смысла заморачиваться с деревьями: достаточно было бы хранить в стеке для каждого оператора список текстовых строк, и в свёртках сливать эти строки, добавляя отступы. Да что там, ради отступов не нужно даже бизона: и flex бы справился. (Хотя расстановка скобок — это немного интереснее.)

В следующий раз отдохнём от бизона.