Parsim Python code with Flex and Bison

Introduction

For about two years now I have been participating in the OpenSource project SourceAnalyzer , and now there is a need to write a parser for the Python language, which should be able to build a call graph (Call Graph) and a class dependency graph (Class Graph Dependency). More precisely, the graph is constructed using other tools, and the parser should only prepare data for these tools.

The process of working on the parser was quite entertaining and I would like to share my experience with you, as well as tell you about some of the pitfalls that we met at the development stage.

Terminology

If you have already worked with grammars and know how the compiler works, feel free to step into the next paragraph, the rest of Welcome.

The parser development process has been divided into two main components:

• Analysis of the input stream and its splitting into tokens (Lexical analysis)
• Parsing tokens with a set of syntax rules (Parsing)

Let's look at a little example. Let there be an expression (or input data stream):

3 + 4 * 15

Build the rules for converting the input stream:

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

Thus, after lexical analysis we get:

NUMBER(3) PLUS(+) NUMBER(4) MULT(*) NUMBER(15) EQUAL(=)

The following is an example of a grammar, with which later, applying the rules, you can parse the expression:

exp: NUMBER
   | exp sign exp
sign: PLUS | MULT
       *
     /  \
   +     15
  / \
3    4

In this example NUMBER, MULT, PLUS, by definition, the terminals, or tokens, defined at the stage of lexical analysis. expr, sign- not terminals, as they are composite units.

This introduction is not exhaustive, therefore, for the theory should refer to the book Flex & Bison O'Relly.

Grammar

The full grammar for Python (version 2.5.2) can be found here:
http://docs.python.org/release/2.5.2/ref/grammar.txt

My task was only to identify the definition of classes, functions and function calls.

To begin with, we will describe the necessary part of the grammar using the extended Backus-Naur form (RBNF) ( 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}

Here [X]- 0 or 1 occurrence X, {Y}- 0 or more occurrences Y.

To determine the class name and its dependencies is enough. Now for the features.

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

By the way, it is assumed that the user code will be correct (from the point of view of the interpreter), otherwise grammar rules must be defined more strictly.

Well, for now, let's finish with the grammar and move on to the lexer (lexical analyzer), since before analyzing the grammar, the original python code should be broken into tokens.

Lexical analyzer

The lexer is generated by Flex. The simplest example:

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

How to compile this example:

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

Learn to describe the grammar for the lexer:
http://rus-linux.net/lib.php?name=/MyLDP/algol/lex-yacc-howto.html

OK, now let's decide on the tokens. In grammar, we have already used the following:
CLASS, COLON, COMMA, DEF, DOT, ID, LBRACE, MESSAGE, RBRACE, OTHER, STAR
We also need DEFINED- reserved Python words.

We make a lexer.
Code: https://gist.github.com/2158334

Brief analysis: comments, empty lines and spaces are ignored. Everything else (the so-called token stream) is given to Bison input.

A character set that finds a pattern (for example, by pattern [ \t]+) is placed in yytext. By default it yytextis a char pointer, but if you add the key -lat compilation, thenyytextwill be perceived as a char array. Before returning the token to the bison, we write the value defined by the template into a variable yylval(for more details, see below).

It's time to move on to the grammar description for Bison.

Bison

Learn to describe the grammar for the bison: http://rus-linux.net/lib.php?name=/MyLDP/algol/lex-yacc-howto.html

I am referring you to this article again, because those who cannot compose Grammar for a bison, easily learn using the material at this link. Well, who knows how - great, let's move on.

So, looking at the paragraph of the Grammar article, we will try to compile a grammar for the bison:

Code: https://gist.github.com/2158315

In the Bison rule, each token has a meaning. The value of the group collected by the current rule is stored in $, the values ​​of the remaining tokens are stored in$1, $2, …

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

The value stored in $nis nothing more than the value of the variable yylvalat the moment the lexer returns the token.

Running Bison with the parameter -d, the file is generated имя.tab.h, it contains macro definitions of the types of tokens that are used in the lexer. Each token corresponds to a number > 257. This file should be included in the lexer, which we did: #include "pyparser.tab.h".

How does the analyzer work? A function is called yyparsefrom main, which starts the analysis - reads tokens, performs some actions, and exits if it encounters the end of the input text ( return 0) or a syntax error ( return 1).

More information about the work of Bison: http://www.linux.org.ru/books/GNU/bison/bison_7.html

We are trying to compile and test what we have:

% 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

Test example:

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

Result:

 >> CLASS: Foo()
 >> CLASS: Test(Foo)
 >> CLASS: Test2()
 >> FUNC:  __init__(self)
 >> FUNC:  foo()

In principle, it is true, although not quite. I would like to see the “full name” in the definition of the function, that is:

>> CLASS: Foo()
>> CLASS: Test(Foo)
>> CLASS: Test2()
>> FUNC:  Test.Test2.__init__(self)
>> FUNC:  Test.Test2.foo()

To do this, proceed as follows: we will create a stack in which we will add the name of the current class. As soon as a function definition is found, we gradually get the class names from the stack, concatenating with the function name. If a new class occurs deeper in level, we add it to the stack, otherwise we delete elements from the stack until we reach the current level of nesting (and one less less), and add a new class to the stack.

The idea and implementation is further.

Python Features

The obvious problem is to find out the level of nesting. As you know, in Python tabs (or spaces) are used for this. Therefore, it is necessary to store the current indentation in some kind of global variable, accessible both to the analyzer and to the lexer. The Bison manual says that the yyparse function expects the position of the just parsed token in the text to be in a global variable yylloc.

yylloc- is a structure of chetryeh elements: first_line, first_column, last_line и last_column. We first_linewill store the current line number (useful for debugging, and it is part of my task), last_columnwe will keep the indent.

We make changes to the code. In the lexer, define the type of the yylloc variable and the default value for the line number:

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

When we meet a new line:

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

If the line starts with spaces:

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

yyleng- the length of the token found by the template. SPACES_PER_INDENTset to 4 by default (by standard).

If the line begins with a tab character:

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

Now we will correct the line count. There are triple quotes in python, usually used for long documentation comments. For ignore, we write a function:

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++;
    }
}

Here, in fact, it was possible to do with a regular expression, but then it will not be possible to correctly determine the line number - we will not be able to find out the number of lines eaten by the regexp (or can we? If so, write a way).

Also do not forget to ignore the comment line:

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

We pass to the stack algorithm.

We determine the nesting function

We act according to the algorithm described by me above.

For convenience, we define the types:

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

We put a couple on the stack <имя_нового_класса, отступ>

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 );
    }
;

Function to clear the stack before the current indent:

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

Well, we determine the full name of the function:

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();
      }
  }

Conclusion

I did not describe the definition of a function call in the article, since it is actually similar to finding a function declaration, although it has its own difficulties. If there is interest, here is my repository on github: https://github.com/sagod/pyparser . Comments, comments and pool requests are welcome.

Literature

• Flex & Bison by John Levine: shop.oreilly.com/product/9780596155988.do
• Bison: www.linux.org.ru/books/GNU/bison/bison_7.html
• Flex: www.delorie.com/gnu/docs/flex/flex_1.html
• Good article on rus-linux: rus-linux.net/lib.php?name=/MyLDP/algol/lex-yacc-howto.html