ホーム » 「BNF記法」タグがついた投稿

タグアーカイブ: BNF記法

2019年12月
« 11月    
1234567
891011121314
15161718192021
22232425262728
293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

再帰下降パーサのサンプルコード

再帰下降パーサ・サンプル

授業でもやっていない再帰下読みの説明でもあり、 簡単なサンプルコードを示したいけど、Webで探しても全体的に大きなプログラムばかりで、 再帰関数をどう記述していくか解かりにくい。 ということで、+,-,*,/と数字1桁という条件で、字句解析無しのサンプルコードを書いてみた。

// 再帰下読みの基本の一番短いサンプル
//
//   字句解析は面倒なので、
//   演算子は1文字のみ、定数は数字1桁だけとする。

#include <stdio.h>
#include <ctype.h>

// 括弧の無い +,-,*,/ だけの式の処理
//
//   今回は以下の構文だけとする。
//   以下のような文法の書き方をバッカス記法(BNF)と言う。
//
// exp_PLUS_MINUS ::= exp_MUL_DIV '+' exp_PLUS_MINUS
//                  | exp_MUL_DIV '-' exp_PLUS_MINUS
//                  | exp_MUL_DIV
//                  ;
// exp_MUL_DIV    ::= DIGIT '*' exp_MUL_DIV
//                  | DIGIT '/' exp_MUL_DIV
//                  | DIGIT
//                  ;
// DIGIT          ::= [0-9] ;

// 構文解析に使う関数のプロトタイプ宣言
int exp_PLUS_MINUS( char* , char** ) ;
int exp_MUL_DIV( char* , char** ) ;

// PLUS,MINUSだけの式
//   構文解析関数の引数
//   pc:   解析する文字列の先頭
//   endp: 解析が終わった場所
int exp_PLUS_MINUS( char* pc , char** endp ) {
   // left=乗除算式
   int left = exp_MUL_DIV( pc , endp ) ;

   if ( **endp == '+' ) {
      // right=加減算式
      int right = exp_PLUS_MINUS( *endp + 1 , endp ) ;
      return left + right ;
   } else if ( **endp == '-' ) {
      // right=加減算式
      int right = exp_PLUS_MINUS( *endp + 1 , endp ) ;
      return left - right ;
   } else {
      // 乗除算式を返す
      return left ;
   }
}

// MUL,DIVだけの式
//   DIGITに相当する構文木の処理は、組み込んでしまう。
int exp_MUL_DIV( char* pc , char** endp ) {
   if ( isdigit( *pc ) ) {
      // left=数値
      int left = *pc - '0' ;
      *endp = pc + 1 ;
      if ( **endp == '*' ) {
         // right=乗除算式
         int right = exp_MUL_DIV( *endp + 1 , endp ) ;
         return left * right ;
      } else if ( **endp == '/' ) {
         // right=乗除算式
         int right = exp_MUL_DIV( *endp + 1 , endp ) ;
         return left / right ;
      }
      // 数値を返す
      return left ;
   } else {
      printf( "Error\n" ) ;
      return 0 ;
   }
}

// 課題(1): () を含む処理にしたかったら、
//          BNF の構文木は、どう直すべきか?
// 課題(2): () を含む処理、空白を無視する処理、
//          定数式が複数桁を使える処理。

int main() {
   char* e = NULL ;
   printf( "%d\n" , exp_PLUS_MINUS( "1+2*3" , &e ) ) ;
   printf( "%d\n" , exp_PLUS_MINUS( "1*2+3" , &e ) ) ;
   return 0 ;
}

理解確認

  • このプログラムでは演算子は、右結合だろうか?、左結合だろうか?

コンパイラの技術と関数電卓プログラム(1)

コンパイラを作るための技術の基礎を学んでもらうために、 簡単な関数電卓プログラム作成を課題とする。 基本は、printf( “%d” , eval( “1+2*3”) ) みたいな計算プログラムを作成する。

計算式から、計算処理を行う場合、演算子の優先順位を正しく処理できることが求められる。
一般的には、計算の機械語を生成する場合、データを準備して計算という方法であり、 逆ポーランド記法変換が行われる。
たとえば、”1+2*3″は、”1,2,+,3,*” といった表記に改められ、変換後の式は スタックを用いて、「値はpush,演算子はpop,pop,計算して,push」という 単純なルールで処理すれば、計算を行うことができる。

字句解析と構文解析

このような、計算式の処理を実行する場合、”1“,”+“,”2“,”✳︎“,”3“という 字句に切り分ける処理を、字句解析という。 この結果から、”式✳︎式”なら掛け算、”式+式”は足し算といった、 前後の字句の組合せから、構文木を生成する処理は、構文解析という。 コンパイラであれば、この後、最適化コード生成などが行われる。

C言語であれば、コンパイル前後には以下の処理が行われる。

  • プリプロセッサ処理
    ↓(#の無いCコード)
  • コンパイル処理
    • 字句解析
    • 構文解析
    • コード生成

    ↓(中間コード)

  • リンク処理 ← ライブラリ
  • 機械語

字句解析と正規表現

字句(トークン)の切り出しでは、その文法を説明する際には、正規表現なども用いられる。

簡単な正規表現
 . 任意の文字
 * 直前の0回以上の繰り返し
 + 直前の1回以上の繰り返し
 [0-9a-z] カッコの中の文字のいずれか - は範囲を示す。
 (a|b|c) 丸カッコの|区切りのうちのどれか。
 (例) C言語の変数の正規表現 [a-zA-Z_][a-zA-Z0-9_]*

構文解析の方法

構文解析では、構文を状態遷移として考え、この式の後にくる可能性のある状態は? という考えで解析を行う。 このような構文は、一般的にバッカス・ナウア記法(BNF)などで表現されることが多い。 また、簡単な構文解析であれば、

などが用いられる。

再帰下降パーサ

簡単な再帰下降パーサの演習として、1桁の数字と+,*演算子の処理プログラムを 考える。

加減,乗除の式のバッカス記法(BNF)
exp_加減 ::= exp_乗除 '+' exp_乗除
          | exp_乗除 '-' exp_乗除
          | exp_乗除
          ;
exp_乗除 ::= DIGIT '*' exp_乗除
          | DIGIT '/' exp_乗除
          | DIGIT
          ;
DIGIT   ::= [0-9]
          ;

練習として、上に示す再帰下降パーサに、 (1) “(“,”)” を含めた場合の、BNF 記法を考え、(2) 数値として複数桁が使えるようにし、 (3) 式を読みやすくする空白を処理できるように 改造せよ。

コンパイラと関数電卓プログラム(専攻科実験2018)

専攻科1年・生産システム実験1(後期)の「コンパイラと関数電卓プログラム」の説明は、昨年度資料と共通なのでリンクを記載しておく。

意思決定木と構文解析

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

((意思決定木の例:うちの子供が発熱した時))
       38.5℃以上の発熱がある?
      no/         \yes
   元気がある?        むねがひいひい?
 yes/    \no      no/     \yes
様子をみる 氷枕で病院  解熱剤で病院  速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
                    struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ" ,
                    dtree( "速攻で病院",NULL,NULL ) ,
                    dtree( "解熱剤で病院",NULL,NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる",NULL,NULL ) ,
                    dtree( "氷枕で病院",NULL,NULL ) ) ) ;
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scant( "%d" , &ans ) ;
      if ( ans == 1 )
         d = d->yes ;
      else if ( ans == 0 )
         d = d->no ;
   }
   printf( "%s¥n" , d->qa ) ;
}

コンパイラと言語処理系

高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により

  • インタプリタ(interpreter:翻訳)
    • ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
  • コンパイラ(compiler:通訳)
    • ソースプログラムから機械語を生成し、実行する際には機械語を実行
    • トランスレーター:ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
    • バイトコードインタプリタ:ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う

に分けられる。

コンパイラが命令を処理する際には、以下の処理が行われる。

  1. 字句解析(lexical analysys)
    文字列を言語要素(token)に分解
  2. 構文解析(syntax analysys)
    tokenの並び順に意味を反映した構造を生成
  3. 意味解析(semantics analysys)
    命令に合わせた中間コードを生成
  4. 最適化(code optimization)
    中間コードを変形して効率よいプログラムに変換
  5. コード生成(code generation)
    実際の命令コードとして出力

バイトコードインタプリタとは

例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、特殊である。

(( Java の場合 ))
foo.java (ソースコード)
 ↓       Java コンパイラ
foo.class (中間コード)
 ↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上で中間コードをインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラにより、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

トークンと正規表現(字句解析)

規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言     「abd|acd」は、abd または acd にマッチする。
グループ化 「a(b|c)d」は、真ん中の c|b をグループ化
量化    パターンの後ろに、繰り返し何回を指定
      ? 直前パターンが0個か1個
       「colou?r」
      * 直前パターンが0個以上繰り返す
       「go*gle」は、ggle,gogle,google
      + 直前パターンが1個以上繰り返す
       「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
      「[0-9]+」012,31415,...数字の列
^     行頭にマッチ
$     行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

構文とバッカス記法

言語の文法を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
表現 ::= 表現1... | 表現2... | 表現3... | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
加算式 ::= 乗算式 '+' 乗算式
        | 乗算式 '-' 乗算式
        | 乗算式
        ;
乗算式 ::= 数字 '*' 乗算式
        | 数字 '/' 乗算式
        | 数字
        ;
数字   ::= [0-9]+
        ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

  +
 / \
1   *
   / \
  23   456

理解度確認

  • インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
  • 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。