Введение

План на семестр, Литература

• Flex (http://www.gnu.org/software/flex/)
• Bison (http://www.gnu.org/software/bison/)
• LLVM (http://llvm.org/)

Требования

• В конце каждого занятия формулируется домашнее задание.
• Сдавшие задание к следующему занятию получают 5 баллов, через одно - 4 балла,
• через 2 - 3 и так далее.
• Получившие 80% - 100% от максимального возможного балла получают отлично, 60% - 79% - хорошо, 40% - 59% - удовлетворительно или зачтено.

Этапы работы компилятора

• Flex : Лексический анализ -> поток токенов
• Bison : Синтаксический анализ -> дерево разбора (parse tree)
• C++ : Семантический анализ -> построение AST, различные проверки
• llvm : Генерация кода -> ассемблерный код -> исполняемый модуль

Flex

Установка

$ sudo apt-get install flex     # debian, ubuntu

Пример 1

%{
#include <iostream>
%}
%option noyywrap

PI      "PI"
E       "E"
INT     [0-9]+
PLUS    "+"
MINUS   "-"
MULT    "*"
DIV     "/"
NL      "\r"|"\n"
%%
{PI}  { std::cout << "PI detected" << std::endl; }
{INT} { std::cout << "INT: " << yytext << std::endl; }
{DIV} { std::cout << "DIV detected" << std::endl; }
%%
int main()
{
    yylex();
}

Сборка и запуск:

$ flex calc.l
$ g++ lex.yy.c
$ ./a.out

Пример 2

Взят с http://flex.sourceforge.net/manual/Simple-Examples.html#Simple-Examples:

/* scanner for a toy Pascal-like language */

%option noyywrap

%{
#include <math.h>
%}

DIGIT    [0-9]
ID       [a-z][a-z0-9]*

%%

{DIGIT}+ {
    printf("An integer: %s (%d)\n", yytext, atoi(yytext));
}

{DIGIT}+"."{DIGIT}* {
    printf("A float: %s (%g)\n", yytext, atof(yytext));
}

if|then|begin|end|procedure|function {
    printf("A keyword: %s\n", yytext);
}

{ID}    printf("An identifier: %s\n", yytext);

"+"|"-"|"*"|"/"     printf("An operator: %s\n", yytext);

"{"[\^{}}\n]*"}"    /* eat up one-line comments */

[ \t\n]+    /* eat up whitespace */

.   printf( "Unrecognized character: %s\n", yytext );

%%

int main(int argc, char **argv)
{
    ++argv, --argc;  /* skip over program name */
    if ( argc > 0 )
        yyin = fopen( argv[0], "r" );
    else
        yyin = stdin;

    yylex();
}

Bison

Установка

$ sudo apt-get install bison     # debian, ubuntu

Пример 1

/*
%{
Prologue
%}

Bison declarations

%%
Grammar rules
%%
Epilogue
*/

%{
    #include <stdio.h>
    #include <ctype.h>
    #define YYSTYPE double

    int yylex(void);
    void yyerror(char const *);
%}

%token NUM

%%

input   : /* empty */
        | input line
        ;

line    : '\n'
        | exp '\n' { printf("%g\n", $1); }
        ;

exp     : NUM
        | exp exp '+' { $$ = $1 + $2; }
        | exp exp '-' { $$ = $1 - $2; }
        | exp exp '*' { $$ = $1 * $2; }
        | exp exp '/' { $$ = $1 / $2; }
        ;

%%

int yylex(void)
{
    int c;
    while ((c = getchar()) == ' ' || c == '\t');
    if (c == '.' || isdigit(c)) {
        ungetc(c, stdin);
        scanf("%lf", &yylval);
        return NUM;
    }
    if (c == EOF)
        return 0;
    return c;
}

void yyerror(char const *s)
{
    fprintf(stderr, "%s\n", s);
}

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

Сборка и запуск:

$ bison calc.y
$ g++ calc.tab.c
$ ./a.out

Домашнее задание

Изменить пример с bison так, чтобы была инфиксная запись, реализовать лексер при помощи flex.