Вступление


Уже около двух лет я участвую в OpenSource проекте SourceAnalyzer, и вот появилась необходимость написать парсер для языка Python, который должен уметь строить граф вызовов (Call Graph) и граф зависимостей классов (Class Graph Dependency). Если точнее, граф строится с помощью других инструментов, а парсер должен лишь подготовить для этих инструментов данные.

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

Терминология


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

Процесс разработки парсера был разделен на две основных составляющих:
  • Анализ входного потока и разбиения его на токены (Лексический анализ)
  • Разбор токенов набором синтаксических правил (Синтаксический Анализ)

Давайте рассмотрим маленький примерчик. Пусть есть выражение (или входной поток данных):

3 + 4 * 15


Построим правила преобразования входного потока:


[1-9]*  ->  NUMBER
+       ->  PLUS
*       ->  MULT


Таким образом, после лексического анализа получим: 
NUMBER(3) PLUS(+) NUMBER(4) MULT(*) NUMBER(15) EQUAL(=)


Далее следует пример грамматики, с помощью которой впоследствии, применяя правила, можно сделать разбор выражения:


exp: NUMBER
   | exp sign exp
sign: PLUS | MULT

       *
     /  \
   +     15
  / \
3    4


В данном примере NUMBER, MULT, PLUS — по определению терминалы, или токены, определенные на этапе лексического анализа. expr, sign — не терминалы, так как являются составными единицами.

Данное введение не является сколь-либо исчерпывающим, поэтому за теорией следует обратиться к книге Flex&Bison O’Relly.

Грамматика


Полную грамматику для языка Python (версии 2.5.2) можно найти здесь:
http://docs.python.org/release/2.5.2/ref/grammar.txt

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

Для начала опишем нужную часть грамматики с помощью ра��ширенной формы Бэкуса-Наура (РБНФ) (wiki).


class_def = CLASS classname [inheritance] COLON suite
classname = ID
inheritance = LBRACE class_args_list RBRACE
class_args_list = [class_arg]
class_arg = dotted_name {COMMA dotted_name}
dotted_name = ID {DOT ID}

Здесь [X] — 0 или 1 вхождение X, {Y} — 0 и более вхождений Y.

Для определения имени класса и его зависимостей вполне достаточно. Теперь для функций.


func_def = DEF funcname LBRACE [func_args_list] RBRACE COLON suite
funcname = ID
func_args_list = [func_arg]
func_arg = (dotted_name | star_arg) {OTHER | COMMA | dotted_name | star_arg | MESSAGE}
star_arg = [STAR] STAR ID

Кстати, предполагается, что код пользователя будет корректным (с точки зрения интерпретатора), иначе правила грамматики надо определять строже.

Отлично, на этом пока закончим с грамматикой и перейдем к лексеру (лексическому анализатору), так как перед разбором грамматики исходный python-код следует разбить на токены.

Лексический анализатор


Лексер генерируется программой Flex. Простейший пример:

%{
#include <stdio.h>
%}

%%
start    printf("START\n");
stop     printf("STOP\n");
.        ; /* игнорируем все остальное */
%%

Как скомпилировать данный пример:

% flex lexer.l && gcc lex.yy.c -o lexer -lfl


Научиться описывать грамматику для лексера:
http://rus-linux.net/lib.php?name=/MyLDP/algol/lex-yacc-howto.html

ОК, теперь определимся с токенами. В грамматике мы уже использовали следующие:
CLASS, COLON, COMMA, DEF, DOT, ID, LBRACE, MESSAGE, RBRACE, OTHER, STAR
Еще нам понадобится DEFINED — зарезервированные слова Python.

Составляем лексер.
Код: https://gist.github.com/2158334

Краткий разбор: комментарии, пустые строки и пробелы игнорируем. Все остальное (так называемый, поток токенов) отдаем на вход Bison.

Набор символов, который находит паттерн (например, по шаблону [ \t]+), помещается в yytext. По умолчанию yytext — это char pointer, но если добавить ключ -l при компиляции, то yytext будет восприниматься как char array. Перед тем, как вернуть бизону токен, запишем определенное по шаблону значение в переменную yylval (подробнее — далее).

Самое время перейти к описанию грамматики для Бизона.

Bison


Научиться описывать грамматику для бизона: http://rus-linux.net/lib.php?name=/MyLDP/algol/lex-yacc-howto.html

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

Итак, заглядывая в пункт статьи Грамматика, попробуем составить грамматику для бизона:

Код: https://gist.github.com/2158315

В правиле Bison каждая лексема имеет значение. Значение группы, собираемой текущим правилом, хранится в $, значения остальных лексем — в $1, $2, …

test_rule: token1, token2, token3;
    $$       $1      $2      $3

Значение, хранящееся в $n есть не что иное, как значение переменной yylval в момент, когда лексер возвращает токен.

Запуская Bison с параметром -d, генерируется файл имя.tab.h, он содержит макроопределения типов лексем, которые используются в лексере. Каждой лексеме соответствует число > 257. Данный файл следует включить в лексер, что мы и сделали: #include "pyparser.tab.h".

Как работает анализатор. Происходит вызов функции yyparse из main, которая запускает анализ — читает лексемы, производит какие-то действия и завершает работу, если встречает конец входного текста (return 0) или синтаксическую ошибку (return 1).

Подробнее про работу Bison: http://www.linux.org.ru/books/GNU/bison/bison_7.html

Пробуем скомпилировать и затестить то, что имеем: 

% bison -d pyparser.y --verbose && flex lexer.l && g++ -c lex.yy.c pyparser.tab.c && g++ -o parser lex.yy.o pyparser.tab.o -ll -ly

Пример теста:
class Foo:
    pass

class Test(Foo):
    class Test2:
        def __init__(self):
            pass
        def foo():
            pass

Результат:
 >> CLASS: Foo()
 >> CLASS: Test(Foo)
 >> CLASS: Test2()
 >> FUNC:  __init__(self)
 >> FUNC:  foo()

В принципе, верно, хотя и не совсем. Хотелось бы видеть “полное имя” в определении функции, то есть:
>> CLASS: Foo()
>> CLASS: Test(Foo)
>> CLASS: Test2()
>> FUNC:  Test.Test2.__init__(self)
>> FUNC:  Test.Test2.foo()

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

Идея и реализация далее.

Особенности Python


Очевидная проблема — узнать уровень вложенности. Как известно, в Python для этого используется табуляция (или пробелы). Поэтому надо хранить текущий отступ в какой-то глобальной переменной, доступной и анализатору, и лексеру. Руководство Bison говорит, что функция yyparse ожидает, что положение только что разобранной лексемы в тексте находится в глобальной переменной yylloc.

yylloc — это структура из четрыех элементов: first_line, first_column, last_line и last_column. В first_line будем хранить номер текущей строки (пригодится для отладки, да и входит в мою задачу), в last_column будем хранить отступ.

Вносим изменения в код. В лексере определим тип переменной yylloc и значение по умолчанию для номера строки:

extern YYLTYPE yylloc;
#define YY_USER_INIT yylloc.first_line=1; //иначе =0

Когда встречаем новую строку:

yylloc.first_line++;
yylloc.last_column = 0;
isNewLine = true;

Если строка начинается с пробелов:

if (isNewLine == true && 0 == yyleng % SPACES_PER_INDENT)
    yylloc.last_column = yyleng / SPACES_PER_INDENT;
isNewLine = false;

yyleng — длина найденной шаблоном лексемы. SPACES_PER_INDENT по умолчанию зададим равным 4 (по стандарту).

Если строка начинается с символа табуляции:

if (isNewLine == true)
    yylloc.last_column = yyleng;
isNewLine = false;

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

static string skipMessage(string _ch){
    string ch;
    string str = _ch;
    _ch = _ch[0];
    bool skip = false;
    int count = 1;
    for(;;ch = yyinput()) {
        str += ch;
        if (ch == _ch){
            if (count == 3)
                return str;
            else count++;
        } else
            count = 1;

        if ("\n" == ch || "\r" == ch)
            yylloc.first_line++;
    }
}

Тут, на самом деле, можно было обойтись регулярным выражением, но тогда не получится верно определить номер строки — мы не сможем узнать количество съеденных регэкспом строк (или сможем? если да — пишите способ).

Также не забываем игнорить строку комментариев:

static void skipComments(){
    for(char ch = yyinput();;ch = yyinput()) {
        if ('\0' == ch || '\n' == ch || '\r' == ch) {
            yylloc.first_line++;
            break;
        }
    }
}


Переходим к стековому алгоритму.

Определяем вложенность функции


Действуем по алгоритму, описанному мною выше.

Определим для удобства типы:

typedef pair <string, int> meta_data; // <имя_класса, отступ>
typedef stack <meta_data> meta_stack;

static meta_stack class_st;

Помещаем в стек пару <имя_нового_класса, отступ>

class_def: CLASS classname inheritance COLON suite
    {
        int indent = @1.last_column; // получаем текущий отступ
        meta_data new_class($2, indent);

        clean_stack( class_st, indent );
        class_st.push( new_class );
    }
;

Функция чистки стека до текущего отступа:

static void clean_stack( meta_stack& stack, int indent )
{
    while(!stack.empty())
    {
        if( indent > stack.top().second )
            break;
        stack.pop();
    }
}

Ну и определяем полное имя функции:

func_def: DEF funcname LBRACE func_args_list RBRACE COLON suite
  {
      string fnc_name = $2;
      int indent = @1.last_column;
      
      clean_stack( class_st, indent );
      meta_stack tmp_class_st(class_st);

      while (!tmp_class_st.empty())
      {
          fnc_name = tmp_class_st.top().first + "." + fnc_name;
          tmp_class_st.pop();
      }
  }


Заключение


Я не стал описывать в статье определение вызова функции, так как оно фактически аналогично нахождению объявления функции, хотя там есть свои сложности. Если есть интерес — вот мой репозиторий на github: https://github.com/sagod/pyparser. Замечания, комментарии и пул-реквесты только приветствуются.

Литература