字句解析を自作する

### 概要
コンパイラを作るため，まずは字句解析を自作する．構文解析でyacc(bison)を利用するつもりなので，その流儀に従って(要するにlexの役割を真似て)実装していく．なお，この実装にはgperfを使っているので．gperfに関しては[こちら](https://qiita.com/hiro4669/items/e49829c20bbf73ddb15c)を参照してください．


### トークンの定義
トークンとは，プログラム言語で用いる演算子，予約語，リテラルなどである．字句解析は，記述されたプログラム(文字列)をトークンに区切り，その種類を返す役割を担う．そのため，言語で使用するトークンの種類を定義する．

```c:scantest.h
#ifndef _SCANTEST_H_
#define _SCANTEST_H_

#define INT_LITERAL    100 // 10のような整数の数字
#define DOUBLE_LITERAL 101 // 10.0のような実数の数字
#define LP             102 // "("の記号
#define RP             103 // ")"の記号
(省略)
// reserved keyword
#define IF             200 // if
#define ELSE           201 // else
(省略)
```

```c:dlex.h
typedef union {
    int iv;
    double dv;
    char *name;
} YYSTYPE;

YYSTYPE yylval; // 値を格納する変数

#endif
```
scantest.hでトークンの種類と値を格納する変数を定義する．この変数は，トークンの種類によってはその種類だけでなく，値を必要とすることがある．例えば，"1000"などは，数字なので種類としては`INT_LITERAL`を返せばよいが，それだけでなく値1000も保持したい(そうじゃないと記述したプログラムで使えない)．そのため，それを格納するための変数として`yylval`を定義する．
なお，この変数名や方が`union`なのは，yaccの流儀に従っている．
想定する言語では，とりあえず値は`int`と`double`しか対応しないので，その値を格納する場所として`iv`,`dv`を利用し，関数名などを格納するために`name`を利用する．

### 字句解析の実装
lexの流儀に従って(yaccがそれを期待するので)，解析してトークンの種類を返す関数を`int yylex()`とする．以下，字句解析の主要な部分だけ載せる．

```c:scanner.c
(略)
#include "keyword.h"
#include "scantest.h"
(略)
extern struct OPE *in_word_set(char*, unsigned int);

FILE *yyin = NULL;
char *yytext;
static void addText(char c) {
    if (ytp == (yt_max - 1)) {
        yt_max += BUFSIZE;
        yytext = (char*)realloc(yytext, yt_max);
    }
    yytext[ytp++] = c;
    yytext[ytp] = 0;
}

int yylex() {
    char c;
    ytp = 0;    

retry:
    switch(c = read()) {
        case '#': { // (1) skip comment
            while ((c = read()) != '\n');
            goto retry;
        }
        case ' ':
        case '\t': { // (2)skip space and tab
            goto retry;
        }
        case '\n': { // (3)ignore return and count the number
            goto retry;
        }
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':            
        case '5':
        case '6':            
        case '7':
        case '8':                        
        case '9': {
            addText(c);
            while(isdigit(c = read())) {  // (4)数字である限り読み込む
                addText(c);
            }
            if (c == '.') {               // (5) double value
                addText(c);
                uint8_t dbl_flg = 0;
                while(isdigit(c = read())) {　//(6) 少数点以下を読み込む
                    dbl_flg = 1;
                    addText(c);
                }
                if (dbl_flg) {           // (7)xx.yyのような正しい形
                    pushback();                    
                    double d_value;
                    sscanf(yytext, "%lf", &d_value);
                    yylval.dv = d_value;
                    return DOUBLE_LITERAL;                    
                } else {                // xx.で終わるようなエラー
                    fprintf(stderr, "double error\n");
                    exit(1);
                }                
            } else {  // int value
                pushback();
                int i_value;
                sscanf(yytext, "%d", &i_value);
                yylval.iv = i_value;
                return INT_LITERAL;
            }            
            break;
        }
        case ';': {
            return SEMICOLON;
        }
        case '(': {
            return LP;
        }
        case ')': {
            return RP;

        (略)
        case EOF: {
            return EOF;
        }
        default: {
            break;
        }
    }
    
    while (is_identchar(c)) {  (8)数字でも文法記号でもない文字列(関数や変数名など)
        addText(c);
        c = read();
    }
    pushback();    
    struct OPE *op = in_word_set(yytext, strlen(yytext));  // (9)予約語か否かの判定
    if (op != NULL) {
        return op->type;
    } 
    
    yylval.name = yytext;　  // (10)予約語ではない場合，文字列をyylval.nameにセット
    return IDENTIFIER;
}
```
`yylex`では，1文字ずつ文字列を読み込み，文法記号，数字，識別子などの種類を判定してその結果を返す．そして，読み込んだ文字列を保存しておく必要がある場合，`addText`を使って保存する．`addText`では，`yytext`という変数を使っているが，これはyaccがこの変数名を前提にするためである．


(1)
この言語では，`#`から始まって改行までをコメントとして扱う．そのため，#から改行までを読み飛ばす．

(2)(3)
タブや改行，スペースは無視する．

(4)
読み込んだ一文字が数字である場合，数値の可能性があるので数字が続く限り読み込む．そして，数字以外の文字を読み込んだら，区切りだと考える．

(5)
数字の後，ドット(.)が続く場合，整数ではなく実数の可能性があるので，(6)更に読み込む.

(7)
`12.1`でのような，実数表現かどうかを確認する．`dbg_flg`が1ならば，少なくとも1文字は数字が続いているので正しい表現となる．

(8)
数字でも文法記号でもない文字が続く限り読み取り，文字列を生成する．

(9)
[gperf](https://qiita.com/hiro4669/items/e49829c20bbf73ddb15c)を使って，予約語かどうかを判定する

(10)
予約語でない場合には，識別子として認識し，`yylval.name`に値を格納する．


### テスト
実装した字句解析が正しく機能するかテストする．

```c:scannertest.c
#include <stdio.h>
#include <stdlib.h>

#include "scantest.h"

int main(void) {
    
    extern FILE *yyin;   // 
    extern int yylex();
    yyin = fopen("tests/test.cs", "r"); 
    if (yyin == NULL) {
        fprintf(stderr, "cannot open file\n");
        exit(1);
    }
    
    int t_type;
        
    while(1) {
        t_type = yylex();
        switch(t_type) {
            case INT_LITERAL: {
                printf("INT_LITERAL: %d\n", yylval.iv);
                break;
            }
            case DOUBLE_LITERAL: {
                printf("DOUBLE_LITERAL: %lf\n", yylval.dv);
                break;
            }
          (略)
            case EOF: {
                printf("END OF FILE\n");
                exit(1);
                break;
            }
```

このように，トークンを読み込んで種類を出力してみる．`EOF`が返されたら終了する．以下のようなファイルを用意する

```test/test.cs
123456710;
1+2;
if;
else;
elsif;
while;
```

実行してみる．

```
>./scant
INT_LITERAL: 123456710
SEMICOLON:
INT_LITERAL: 1
ADD
INT_LITERAL: 2
SEMICOLON:
....
```
ここまでの実装は[git](https://github.com/hiro4669/csua)から取得可能
以下のコマンドソースを取得して実行できる

```
>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch org_scanner origin/org_scanner
>git checkout org_scanner
>make
>cd comp
>./scant
```
[目次](https://qiita.com/hiro4669/items/563466ccce42eb8342b9)に戻る