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

コンパイラを作るための技術の基礎を学んでもらうために、 簡単な関数電卓プログラム作成を課題とする。 基本は、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)などで表現されることが多い。 また、簡単な構文解析であれば、

  • 再帰下降パーサ
  • LR構文解析法

などが用いられる。

再帰下降パーサ

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

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

練習として、上に示す再帰下降パーサに、 (1) "(",")" を含めた場合の、BNF 記法を考え、 (2) 式を読みやすくする空白を処理できるように してみよう。

 

2016年11月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30      

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2016年11月 8日 12:40に書いたブログ記事です。

ひとつ前のブログ記事は「1年電気回路演習でアクティブラーニングを試す」です。

次のブログ記事は「コンパイラの技術と関数電卓プログラム(2)」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。