GNUバイソン

/* 
* Expression.h 
* 構文ツリーを構築するために使用される構造体の定義。
*/ 
#ifndef __EXPRESSION_H__ 
#define __EXPRESSION_H__

/** 
* @brief 操作タイプ
*/ 
typedef enum tagEOperationType { eVALUE , eMULTIPLY , eADD } EOperationType ;  

    
    
    
 

/** 
* @brief 式の構造
*/ 
typedef struct tagSExpression { EOperationType type ; /* /< 操作の種類 */  

      

    int value ; /* /< 型が eVALUE の場合にのみ有効 */ struct tagSExpression * left ; /* /< ツリーの左側 */ struct tagSExpression * right ; /* /< ツリーの右側 */ } SExpression ;  
       
       
 

/** 
* @brief 識別子を作成します
* @param value 数値
* @return 式、またはメモリがない場合は NULL 
*/ 
SExpression * createNumber ( int value );  

/** 
* @brief 操作を作成します
* @param type 操作タイプ
* @param left 左オペランド
* @param right 右オペランド
* @return 式、またはメモリがない場合は NULL 
*/ 
SExpression * createOperation ( EOperationType type , SExpression * left , SExpression * right );      

/** 
* @brief 式を削除します
* @param b 式
*/ 
void deleteExpression ( SExpression * b );  

#endif /* __EXPRESSION_H__ */

/* 
* Expression.c 
* 構文ツリーを構築するために使用される関数の実装。
*/

#include "Expression.h" 

#include <stdlib.h> 

/** 
* @brief 式のためのスペースを割り当てます
* @return 式、またはメモリが足りない場合は NULL 
*/ 
static SExpression * allocateExpression () { SExpression * b = ( SExpression * ) malloc ( sizeof ( SExpression ));  

        

    b == NULLの場合、NULLを返します。   
         

    b ->タイプ= eVALUE ; b ->値= 0 ;  
      

    b ->左= NULL ; b ->右= NULL ;  
      

    bを返す; } 


SExpression * createNumber ( int値) { SExpression * b = allocateExpression ();  

       

    b == NULLの場合、NULLを返します。   
         

    b -> type = eVALUE ; b ->値=値;  
      

    bを返す; } 


SExpression * createOperation ( EOperationType type 、SExpression * left 、SExpression * right ) { SExpression * b = allocateExpression ();      

       

    b == NULLの場合、NULLを返します。   
         

    b -> type = type ; b -> left = left ; b -> right = right ;  
      
      

    bを返す; } 


void deleteExpression ( SExpression * b ) { b == NULLの場合、戻り値;  

       
        

    式bを左から削除します。式
b を右から削除します。    

    無料( b ); 
}

% {

/* 
* Lexer.l ファイル
* 字句解析プログラムを生成するには、次のコマンドを実行します: "flex Lexer.l" 
*/

#include "Expression.h" #include "Parser.h" 
 

#include <stdio.h> 

% }

%オプションoutfile = "Lexer.c"ヘッダー-ファイル= "Lexer.h" %オプションwarn nodefault  
  

%オプションreentrant noyywrap never - interactive nounistd %オプションbison - bridge    
 

%%

[ \ r \ n \ t ] * { continue ; /* 空白をスキップします。 */ } [ 0-9 ] + { sscanf ( yytext , "%d" , & yylval -> value ); return TOKEN_NUMBER ; }       
             

"*" { return TOKEN_STAR ; } "+" { return TOKEN_PLUS ; } "(" { return TOKEN_LPAREN ; } ")" { return TOKEN_RPAREN ; }             
             
             
             

. { continue ; /* 予期しない文字は無視します。 */ }              

%%

int yyerror ( SExpression **式、yyscan_tスキャナ、const char * msg ) { fprintf ( stderr 、"エラー: %s \n " 、msg ); 0を返す; }        
      
     

% {

/* 
* Parser.y ファイル
* パーサーを生成するには、次のコマンドを実行します: "bison Parser.y" 
*/

#include "Expression.h" #include "Parser.h" #include "Lexer.h" 
 
 

// Lexer.l で提供されている実装を参照します
int yyerror ( SExpression ** expression , yyscan_t scanner , const char * msg );       

% }

%コードには{ typedef void * yyscan_t ; }が必要です  
    


%出力"Parser.c" %定義"Parser.h"  
 

% api . pureを定義します% lex - param { yyscan_t scanner } % parse - param { SExpression **式} % parse - param { yyscan_t scanner } 
      
    
    

% union { int値; SExpression *式; } 
     
     


% token TOKEN_LPAREN "(" % token TOKEN_RPAREN ")" % token TOKEN_PLUS "+" % token TOKEN_STAR "*" % token <値> TOKEN_NUMBER "数値"    
    
      
      
   

% type <式> expr  

/* 優先順位 (増加) と結合性: 
   a+b+c は (a+b)+c です: 左結合性
   a+b*c は a+(b*c) です: "*" の優先順位は "+" よりも高くなります。 */ 
% left "+" % left "*" 
 

%%

入力
: expr { *式= $1 ; } ;          
    

expr 
: expr [ L ] "+" expr [ R ] { $$ = createOperation ( eADD , $L , $R ); } | expr [ L ] "*" expr [ R ] { $$ = createOperation ( eMULTIPLY , $L , $R ); } | "(" expr [ E ] ")" { $$ = $E ; } | "number" { $$ = createNumber ( $1 ); } ;                
                
                
                     
    

%%

/* 
* main.c ファイル
*/

#include "Expression.h" #include "Parser.h" #include "Lexer.h" 
 
 

#include <stdio.h> 

int yyparse ( SExpression **式、yyscan_tスキャナ);    

SExpression * getAST ( const char * expr ) { SExpression *式; yyscan_tスキャナ; YY_BUFFER_STATE状態;   

     
     
     

    if ( yylex_init ( & scanner )) { /* 初期化できませんでした */ return NULL ; }  
        
         
    

    状態= yy_scan_string (式、スキャナ);   

    if ( yyparse ( & expression , scanner )) { /* 解析エラー */ return NULL ; }   
        
         
    

    yy_delete_buffer (状態、スキャナ); 

    yylex_destroy (スキャナー);

    戻り式; } 


int assess ( SExpression * e ) { switch ( e -> type ) { case eVALUE : return e -> value ; case eMULTIPLY : return assess ( e -> left ) * assess ( e -> right ); case eADD : return assess ( e -> left ) + assess ( e -> right ); default : /* ここには記述しないでください */ return 0 ; } }  

      
         
             
         
               
         
               
        
            
             
    


int main ( void ) { char test [] = " 4 + 2*10 + 3*( 5 + 1 )" ; SExpression * e = getAST ( test ); int result = assess ( e ); printf ( "'%s' の結果は %d です\n " , test , result ); deleteExpression ( e ); return 0 ; }