FlexとBisonを使用したParsim Pythonコード

エントリー

約2年間、私はOpenSourceプロジェクトSourceAnalyzerに参加しており、現在、コールグラフ（コールグラフ）とクラス依存関係グラフ（クラスグラフ依存関係）を構築できるPython言語のパーサーを作成する必要があります。 より正確には、グラフは他のツールを使用して作成され、パーサーはこれらのツールのデータのみを準備する必要があります。



パーサーで作業するプロセスは非常に面白かったので、開発段階で遭遇した落とし穴のいくつかについて説明するとともに、私の経験を共有したいと思います。

用語

すでに文法学者と仕事をしていて、コンパイラーがどのように機能するかを知っているなら、次のパラグラフであるWelcomeに進んでください。



パーサー開発プロセスは、2つの主要なコンポーネントに分割されています。

• 入力ストリームの分析とトークンへの分割（語彙分析）
• 一連の構文ルールを使用したトークンの解析（解析）

少し例を見てみましょう。 式（または入力データストリーム）があるとします。

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



私の仕事は、クラス、関数、および関数呼び出しの定義を識別することだけでした。



まず、拡張Backus-Naur形式（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}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、 [X]



は[X]



0回または1回の出現、 {Y}



は{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



OK、トークンを決めましょう。 文法では、すでに次のものを使用しています。

CLASS, COLON, COMMA, DEF, DOT, ID, LBRACE, MESSAGE, RBRACE, OTHER, STAR





DEFINED



予約済みPythonワードも必要です。



レクサーを作成します。

コード： https : //gist.github.com/2158334



簡単な解析：コメント、空白行、スペースは無視されます。 他のすべて（いわゆるトークンストリーム）は、Bisonの入力に与えられます。



パターンを検出する文字セット（たとえば、パターン[ \t]+



）はyytext



配置されyytext



。 デフォルトでは、 yytext



はcharポインターですが、コンパイル時に-l



スイッチを追加すると、 yytext



はchar配列として扱われます。 トークンをバイソンに返す前に、テンプレートで定義された値をyylval



にyylval



（詳細については、以下を参照してください）。



それでは、バイソンの文法の説明に移りましょう。

バイソン

バイソンの文法の説明を学ぶ： http : //rus-linux.net/lib.php? name=/ MyLDP / algol / lex-yacc-howto.html



バイソンの文法を構成できない人は、このリンクの資料を使用して簡単に学習できるため、この記事を再度参照します。 さて、誰がその方法を知っていますか？



したがって、文法記事の段落を見て、バイソンの文法を作成しようとします。



コード： https : //gist.github.com/2158315



Bisonルールでは、各トークンには意味があります。 現在のルールによって収集されたグループの値は$



に格納され、残りのトークンの値は$1, $2, …



格納され$1, $2, …

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

$n



格納されている値は、字句解析器がトークンを返す時点でのyylval



値に他なりません。



-d



を指定してBisonを実行すると、ファイル.tab.h



生成されます。このファイルには、レクサーで使用されるトークンのタイプのマクロ定義が含まれています。 各トークンは、 > 257



数字に対応しています。 このファイルは、レクサーに含める必要があります。これは、 #include "pyparser.tab.h"



でした。



アナライザーはどのように機能しますか？ yyparse



関数はmain



からyyparse



れ、分析を開始します-トークンを読み取り、いくつかのアクションを実行し、入力テキストの終わり（ 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()
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これを行うには、次の手順に従います。現在のクラスの名前を追加するスタックを作成します。 関数定義が見つかるとすぐに、スタックからクラス名を徐々に取得し、関数名と連結します。 新しいクラスがより深いレベルで発生する場合は、スタックに追加します。そうでない場合は、現在のネストレベル（1つ少ないレベル）に達するまでスタックから要素を削除し、新しいクラスをスタックに追加します。



アイデアと実装はさらに進んでいます。

Python機能

明らかな問題は、ネストのレベルを見つけることです。 ご存じのとおり、Pythonではタブ（またはスペース）がこれに使用されます。 したがって、アナライザーとレクサーの両方にアクセス可能な、何らかのグローバル変数に現在のインデントを保存する必要があります。 Bisonのマニュアルでは、yyparse関数は、テキスト内の解析されたばかりのトークンの位置がyylloc



グローバル変数にあるとyylloc



しているとyylloc



ます。



yylloc



は、 first_line, first_column, last_line last_column



4つの要素の構造です。 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;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、行数を修正します。 Pythonには三重引用符があり、通常はドキュメントに関する長い解説に使用されます。 無視するために、関数を書きます：

 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です。 コメント、コメント、プールのリクエストは大歓迎です。

文学

• ジョン・レヴィンによるフレックスとバイソン： shop.oreilly.com/product/9780596155988.do
• バイソン： www.linux.org.ru/books/GNU/bison/bison_7.html
• フレックス： www.delorie.com/gnu/docs/flex/flex_1.html
• rus-linuxに関する良い記事： rus-linux.net/lib.php?name =/ MyLDP / algol / lex - yacc - howto.html