ホーム » 2016 » 11月

月別アーカイブ: 11月 2016

2016年11月
 12345
6789101112
13141516171819
20212223242526
27282930  

検索・リンク

2016年11月27日(第503回)

高専ライブ500回記念月間の総仕上げ!!
教員による生放送でお送りしました。

  • ジャズバー歴史の舞台裏
  • 数学の部屋の思い出
  • 英語の囃子の思い出 徳山からの長水先生、生電話
  • 「まるトレ」からのお知らせ
    • 12月9日の高専カフェでまるトレが再現
    • 12月4日と11日の高専ライブで、まるトレ、復活!!

担当:吉田(英語科教員)、手嶋(社会科教員)、中村(国語科教員、MC)、西(電子情報工学科教員、MIX)

構造体を使ったプログラム例

今日はテスト前で、構造体の全体的な説明も終わり、演習の時間。 以下のようなオブジェクト指向の考え方を取り入れた、 構造体ポインタ渡しのスタンダードなプログラムを示す。

#include <stdio.h>
#define SIZE 10
struct Person {
   char  name[ 20 ] ;
   int   age ;
} ;
int read_Person( struct Person* p ) {
   return scanf( "%s%d" , p->name , &(p->age) ) == 2 ;
}
void print_Person( struct Person* p ) {
   printf( "%s %d\n" , p->name , p->age ) ;
}

int main() {
   int i , size ;
   struct Person table[ SIZE ] ;
   // データの入力処理
   for( i = 0 ; i < SIZE ; i++ ) {
      if ( !read_Person( &( table[i] ) ) )
         break ;
   }
   size = i ;
   // データの出力処理
   for( i = 0 ; i < size ; i++ )
      print_Person( &( table[i] ) ) ;
   return 0 ;
}

ファイル入出力にも慣れてもらおう

#include <stdio.h>
#define SIZE 10
struct Person {
   char name[ 20 ] ;
   int  age ;
} ;
int read_Person( struct Person* p , FILE* fp ) {
   return fscanf( fp , "%s%d" , p->name , &( p->age ) ) == 2 ;
}
void print_Person( struct Person* p , FILE* fp ) {
   fprintf( "%s %d\n" , p->name , p->age ) ;
}
int main() {
   int    i , size ;
   struct Person table[ SIZE ] ;
   FILE*  fp_in ;

   if ( (fp_in = fopen( "data.txt" , "rt" )) != NULL ) {
      for( i = 0 ; i < SIZE ; i++ )
         if ( ! read_Person( &( table[i] ) , fp_in ) ) {
            size = i ;
            break ;
         }
      for( i = 0 ; i < size ; i++ )
         print_Person( &( table[i] ) , stdout ) ;
   }
   return 0 ;
}

オブジェクト指向っぽく

#include <stdio.h>
#define SIZE 10
class Person {
private:
   char  name[ 20 ] ;
   int   age ;
public:
   int read() {
      return scanf( "%s%d" , name , &age ) == 2 ;
   }
   void print() {
      printf( "%s %d\n" , name , age ) ;
   }
} ;
int main() {
   int size ;
   Person table[ SIZE ] ;

   for( int i = 0 ; i < SIZE ; i++ )
      if ( !table[i].read() ) {
         size = i ;
         break ;
      }
   for( int i = 0 ; i < size ; i++ )
      table[i].print() ;
   return 0 ;
}

2016年11月20日(第502回)

学生さんがテスト期間中につき、教員による収録でお送りしました。

  • 新任教員紹介 一般科目教室物理科 挽野先生
  • ジャズバー歴史 63杯目 「古鉄」
  • 研修旅行の話

ゲスト:一般科目教室物理科 挽野先生

担当:亀山(機械工学科教員)、川上(電子情報工学科教員)、中村(国語科教員、MC)、西(電子情報工学科教員、MIX)

倍精度で精度が足りない…

他の先生の卒研の学生から、「C言語のプログラムを書いているけど、 精度が足りないのでどうしたらいいか?」 という質問をうける。

double 型で計算をしているようなので、 計算アルゴリズムの問題かもしれない。 積分計算なら、台形法じゃなく「シンプソンの公式」を使うとか、 微分方程式を解くのなら、「オイラー法」とか 「ルンゲクッタ法」を使うとか…。 でも、この辺は、私は自信がないので、 物理系のシミュレーションの卒研をしている先生の方が 詳しいので、計算方法アドバイスしてもらうべき…

もう一つの対応という点では、もっと精度の いい型を使う方法。整数型演算が絡む場合であれば、 bignum というライブラリで…という方法もあるけど、 今回は double 型の計算。

ということで、long double 型を説明する。

#include <stdio.h>
#include <math.h>
int main() {
   long double x = 3.14159265358979323846264338327950288L ;
   printf( "%Lf\n" , x ) ;
   return 0 ;
}

3.14の後ろについている"L"が重要。 "l"でもいいけど、"1"と区別ができないので、大文字で書くべき。

2016年11月13日(第501回)

  • クラシックコンサートの話
  • 越前ガニの話
  • 風邪の話
  • 七五三の話
  • ジャズバー歴史 62杯目 「史料の持つ情報」

担当:木下(3EI,MC)、西島(2EI,MIX)、上野(F1)、西村(F2)

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

前半では、1文字の数字と簡単な演算子で表現される計算式を再帰下降パーサで計算する処理で、 演習を行った。

後半は、さらに実際のコンパイラに近いものとして、 C言語で広く使われている、字句解析(lexical analyzer : lex or flex)ツール、 構文解析(parser : yacc or bison) のツールを使って、 さらに現実的な関数電卓プログラムを作ってみる。

lex or flex による字句解析

lexは、字句解析のプログラムを自動生成するツール。 “%%”行の内側に、正規表現とそのパターンの際の処理を書き並べる。 また、”%{ … %}”の内側に、その処理に必要なC言語のソースを書き、 lex で処理を行うと、lex.yy.c というC言語のソースを出力する。

# flex は、lex の改良版。

(( mycalc.l ))
%{
#include <stdio.h>
// yaccが出力するヘッダファイル
#include "y.tab.h"

int yywrap( void )
{
   // 1: スキャナ終了
   // 0: yyin を切り替えて継続
   return 1 ;
}
%}
%%
"+"  return ADD ;
"-"  return SUB ;
"*"  return MUL ;
"/"  return DIV ;
"\n" return CR  ;
[0-9][0-9]* {
   int temp ;
   sscanf( yytext , "%d" , &temp ) ;
   yylval.int_value = temp ;
   return INT_LITERAL;
}
%%

このプログラムを、lex で処理させると、+ 記号に ADD という定数記号を割り振るとか、数字列をみつけると、文字列から数値を生成(sscanf)して、その場合の記号に INT_LITERAL という定数記号を割り振る…といった処理のプログラムを生成してくれる。

yacc or bison

yacc ( Yet Another Compiler Compiler ) もしくはその改良版の bison は、構文解析の処理を行ってくれる。 構文をバッカス記法で記載すると、構文のパターンの状態遷移に応じた遷移テーブルを自動生成し、 その遷移テーブルを用いた処理のプログラムをC言語で出力してくれる。

トークンが出力するデータは、様々なデータが考えられるので、 その型を “%union” の中に記載する。 “%%”〜”%%” の間には、BNF記法と、それに対応する処理を記載する。

# bison(水牛)は、yacc(山牛)の改良版。

(( mycalc.y ))
%{
#include <stdio.h>
#include <stdlib.h>

// yacc が定義する内部関数のプロトタイプ宣言
#define YYDEBUG 1
extern  int  yyerror( char const* ) ;
extern  char *yytext ;
extern  int  yyparse( void ) ;
extern  FILE *yyin ;
extern  int  yylex( void ) ;
%}

// 字句(トークン)の定義
%union {
   int  int_value;
}
%token <int_value>  INT_LITERAL
%token ADD SUB MUL DIV CR
%type  <int_value>   expression term primary_expression

%%
// 構文の定義
line_list  : line
           | line_list line
           ;

line       : expression CR       { printf( ">>%d\n" , $1 ) ; }
           ;

expression : term
           | expression ADD term { $$ = $1 + $3 ; }
           | expression SUB term { $$ = $1 - $3 ; }
           ;

term       : primary_expression
           | term MUL primary_expression { $$ = $1 * $3 ; }
           | term DIV primary_expression { $$ = $1 / $3 ; }
           ;

primary_expression
           : INT_LITERAL
           ;
%%

// 補助関数の定義
int yyerror( char const* str )
{
   fprintf( stderr , "parser error near %s\n" , yytext ) ;
   return 0 ;
}
int main( void )
{
   yyin = stdin ;
   if ( yyparse() ) {
      fprintf( stderr , "Error ! Error ! Error !\n" ) ;
      exit( 1 ) ;
   }
}

このプログラムを、yacc で処理すると、「加算式 + 乗算式」という文になっている部分を見つけると、
「$1(加算式部分の値)と、$3(乗算式の部分)の値を加えて、$$(式の結果)を求める」といった処理を生成してくれる。yyparse() 関数を呼び出すと、構文の一番最上部の line_list に相当する処理が起動される。yyerror()は、構文解析の途中で文法エラーになった時に呼び出される関数。

生成されるパーサの内容に興味があるなら、生成される y.tab.c の内容を読むと良い。

make と Makefile

これらのプログラムでは、字句解析を行う mycalc.l , 構文解析を行う mycalc.y を 作ったが、これを組合せて1つの実行ファイルにコンパイルする。 これらの手順は煩雑なので、make ツールを使う。

make は、 Makefile に記載されている”ターゲット”と、それを作るために必要な”依存ファイル”、 “依存ファイル”から”ターゲット”を生成する処理から構成される。 make は、ターゲットと依存ファイルの更新時間を比較し、 必要最小限の処理を行う。

(( Makefile ))
# 最終ターゲット
mycalc:	y.tab.o lex.yy.o
        gcc -o mycalc y.tab.o lex.yy.o
# 構文解析処理
y.tab.o: mycalc.y
        bison -dy mycalc.y	# -dy : yacc互換モード
        gcc -c y.tab.c
# 字句解析処理
lex.yy.o: mycalc.l mycalc.y
        flex -l mycalc.l        # -l : lex互換モード
        gcc -c lex.yy.c
clean:; rm mycalc y.tab.c y.tab.h lex.yy.c *.o

((ファイルの依存関係))
mycalc.l           mycalc.y
  |     \           |
lex.yy.c  y.tab.h  y.tab.c
  |            \    |
lex.yy.o        y.tab.o
        \    /
         mycalc

この課題にあたり、後半の実験では flex, bison などの unix 系プログラミング環境を利用する。

macOS の利用者であれば MacPorts や、Windows 利用者であれば、wsl(Windows subsystem for Linux) などをインストールし実行すること。

今回の実験であれば、”apt-get install flex bison gcc make” にて、必要なパッケージをインストールして実験を行うこと。

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

コンパイラを作るための技術の基礎を学んでもらうために、 簡単な関数電卓プログラム作成を課題とする。 基本は、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) 式を読みやすくする空白を処理できるように してみよう。

2016年11月6日(第500回)

高専ライブ500回記念放送!!
500回の節目の放送を迎えることができました。お聞きいただいている皆様に厚くお礼申し上げます。
11月は「高専ライブ500回記念月間」ということで、高専ライブのこれまでを振り返りながらお伝えしてまいります。

  • 500回放送のお祝いメッセージご紹介
  • メンバーの初出演放送に関するクイズ
  • 今後の高専ライブの目標について

担当:川﨑(3EI,MC)、田中(3B,MIX)、田嶋(3C)、水島(2C)、西(教員)

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー