FreeStyleWiki

Bison/Flex

このエントリーをはてなブックマークに追加

[Linux]

Bison/Flex

以前、Go言語でつくるインタプリタをやったが、あれはパーサジェネレータを使わず自力で字句解析と構文解析を行っていた。今回はBison/Flexというパーサジェネレータを使ってそれをやっていく。

字句解析(=scanner.ll)
flexを使う。文字列をトークンに分けるので全てのキーワード(fn, let, if, else, return)などを登録しておく。
構文解析(=parser.yy)
bisonを使う。トークンを抽象構文木に落とし込む。
抽象構文木(AST)
C++のクラスをunionの中に定義しておき、型とトークンを紐づける。
ASTを作る際の学術的ポイント
終端記号と非終端記号 非終端要素ごとに抽象クラスが必要

終端記号は、生成規則の右辺のみに現れ、左辺には現れない。よって、生成規則によってそれ以上は変換されない(これが“終端”と呼ばれる理由である

  Flex

Flexの記法

Flexスキャナ定義のほとんどの要素は、 必須要素ではありません。 全体的な定義フォーマットは以下のようになります。

定義、初期Cコード
%%
ルール 
%%
他のCコード

上記の「初期Cコード」と「他のCコード」の部分に直接Cのコードを含めることができる。

記法は以下の通り:

%{ 
   C code
   ...
%}

定義

  • Flexが構文解析の際に使う識別子を定義する
// 凡例
definition_name    definition

// 実例
DIGIT     [0-9]
LETTER    [a-z]
IDENT     [a-z_][a-z0-9_]*
ALPHANUM  {LETTER}|{DIGIT}

ルール

patternが何を認識するべきかを定義し、 actionsがその何かを認識した時に何を実行するべきであるかをスキャナに知らせます。 patternの部分は空白によって区切られます。

// 凡例
pattern       actions

// 実例
hi         |
bonjour    |
hello      printf("hello!\n");
goodbye    {  printf("goodbye!\n"); }
konnichiwa {                   
               line 1      
               ...             
               line n      
           } 
sayonara   printf("lex will not "); printf("print this\n");
  • pipeの左にあるパターンを順に下まで見ていくということ
  • pattern部分は正規表現で書ける

  Bison

Bisonの記法

Bison文法ファイルは4つの主要な部分からなります。 それらを、適切な区切り文字とともに示します。

%{
C宣言部(C declarations)
%}

Bison宣言部(Bison declarations)

%%
文法規則部(Grammar rules)
%%

追加のCプログラム部(Additional C code)

`/* ... */'で囲まれたコメントは、どの部分にも書けます。

api.value.type variant

  • bisonのC++の例ではunionを使わずに構文解析するサンプルになっている
    • 以下のパラメータを設定している
// 下記2行を設定すると
%define api.token.constructor
%define api.value.type variant

// 以下は上記のアサート?
%define parse.assert

このあたりの記述は 10.1.7.2 Complete Symbols にあった。

api.token.prefix

パーサを生成した際にトークン名にprefixをつける

3.7.14 %define Summary

%define api.token.prefix {TOK_}  <-- この部分
%token
END  0  "end of file"
ASSIGN  ":="
MINUS   "-"
PLUS    "+"
STAR    "*"
SLASH   "/"
LPAREN  "("
RPAREN  ")"
;
  • ドキュメントが見つからないのだけど
    • lexerのファイルに以下のように書くと
"="        return yy::parser::make_ASSIGN(loc);
    • 生成ファイルに関数が自動的に定義される
return yy::parser::make_ASSIGN(loc);
	YY_BREAK

      static
      symbol_type
      make_ASSIGN (location_type l)
      {
        return symbol_type (token::TOK_ASSIGN, std::move (l));
      }