ほんまにコメントほしい

機械学習やめました。

言語自作への道、ただしyaccとlexに触れただけ

この記事は 自作OS Advent Calendar 2019 - Adventar の 3 日目の記事です。

前書き 

自作OSを一旦中断し(難しすぎてわからない)、 自作コンパイラからやってやろうと思いました。

ちなみに、ひと昔話題になったbrawnのような自作言語においてyaccとlexというものが関係しているらしいです。

今回はとりあえずそれらを動かしてみます。

字句解析と構文解析

いきなりですが疑問としてコンピュータがどうやって我々の入力を理解しているか?がありますよね。

例えば僕たちは日本語でも英語でもなんでもいいんですけど会話するときに主語は、、動詞は、、みたいに考え無いですよね。

けどコンピュータくんはそうはいかないですよね。

そこでコンピュータに文法を教えよう、的なイメージがこの記事の格です。

字句解析とは

字句解析を行なうプログラムのことをレキシカルアナライザ(lexical analyzer)と呼びますが、 これを自動生成してくれるのがlexです。

構文解析とは

  • トークンの並びから、解析木を構築する処理

構文解析を行なうプログラムのことを パーサ(parser)と呼びます。yaccはこれを自動生成してくれるプログラムです。

下の図がそれぞれの具体的な流れです

f:id:kiwamizamurai:20191203223636p:plain
lex and yacc

Lexの例

とりあえず見てください。

%{
    #include <stdio.h>
%}

%%
[0-9]+          printf("Thats Number\n");
[a-zA-Z]+       printf("Thats Character\n");
[a-zA-Z0-9]+    printf("Thats Word\n");
[ \t\n]         ;
"HelloWorld"    printf("hello matched\n");
.               printf("unexpected character\n");
%%

左に正規表現、右にその対応を書きます。

では実行してみると

$ lex test.l
$ cc -o test lex.yy.c -ll
$ echo hell000 | ./test
Thats Word

のようになります。

Lexについて

これだけでわわからないので一歩づつまとめます。

Lexのファイルは.lの拡張子で次のようなルールがあります。

... definitions ...
%%
... rules ...
%%
... subroutines ...

まあルールのところに色々書くと思うんですけど、わからなければはじめはルールの部分だけとりあえず気にかけておけばいいと思います。

pattern     action

という形で書きます。この際にパターンには正規表現を使います。

f:id:kiwamizamurai:20191204081310p:plain
RE sample 1

f:id:kiwamizamurai:20191204081305p:plain
RE smaple 2

ちなみにですが環境によってはコンパイルに次が必要になるときがあるそうです。

int yywrap(void)
{
    return 1;
}

この関数は、ファイル終わり (または入力終わり) が検出されるときに呼び出されます。この関数が 1 を戻す場合、解析は停止します

もちろんこの他にもlexには予約語があります。

f:id:kiwamizamurai:20191204082030p:plain
Predefined Variables

まあlexだけでは全然イメージわかないと思います。なのであまり気にせずとりあえず読み進めてください。

Yaccの例

%{
 #include <stdio.h>
 int yylex(void);
 void yyerror(char *);
%}
%token INTEGER
%%
program:
 program expr '\n' { printf("%d\n", $2); }
 |
 ;
expr:
 INTEGER { $$ = $1; }
 | expr '+' expr { $$ = $1 + $3; }
 | expr '-' expr { $$ = $1 - $3; }
 ;
%%
void yyerror(char *s) {
 fprintf(stderr, "%s\n", s);
}
int main(void) {
 yyparse();
 return 0;
} 

なんか一気に難しいですよね、、、いやぁ難しい、泣ける

Yaccについて

前述通りlexによってできたトークンを用いて構文解析を行うのがyaccです。

Backus Naur Form (BNF)というグラマーらしいです。

なのでyaccファイルである.yの定義部ではトークンを定義することが可能です。

%token NUMBER 621 

トークンを定義すると自動的にナンバーが割り振られるようですが上のように明示的に与えることも可能です。

またyaccにはシンボルというものがあります。

expression : expression1 '+' expression2
{  $$      =    $1       +      $3   }

$$は構文規則の左辺、$nは右辺の各トークンをあらわしています。

この場合だとexpression1が$1でexpression1が$3です。

ちなみに右辺はcもかけます。

具体例

ここまででくそわからないと思うのは僕だけですか?まじでわからない。

では最近寒くなってきたのでyacclexを使ってエアコン用のコンパイラでも作りましょう。

yacc

%{
        #include <stdio.h>
        #include <string.h>

        void yyerror(const char *str)
        {
                fprintf(stderr, "error: %s\n", str);
        }

        int yywrap()
        {
                return 1;
        }

        main()
        {
                yyparse();
        }
%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

%%

commands:
        | commands command
        ;

command:
        heat_switch
        |
        target_set
        ;

heat_switch:
        TOKHEAT STATE
        {
                if($2)
                        printf("\t Heat turned on \n");
                else
                        printf("\t Heat turned off \n");
        }
        ;

target_set:
        TOKTARGET TOKTEMPERATURE NUMBER
        {
                printf("\t Temperature set to %d\n", $3);
        }
        ;
  • includeのところ

とりあえずincludeしてください。c言語知らないのでなんのためにあるのかよくわからないです。

  • yyerrorのところ

エラー処理的なやつです。これから定義する文法以外の入力に対するエラー処理です。

  • yywrapのところ

前述通りあった方がいいやつです。コンパイルの関係でいるらしいです。

  • mainのところ

yyparse()で構文解析しよう!的なやつです。エラーだと1を返すようです。

  • %tokenのところ

トークンの定義です。これはあとで書くlex用だと思ってください。ようはプログラムを書くときの変数的なやつです。

  • NUMBER: エアコンの温度用の変数的なイメージ
  • TOKHEAT: エアコンのオンオフ用の合図的なイメージ
  • STATE: エアコンのon|offという状態用の変数的なイメージ
  • TOKTARGET: エアコンの温度をセットするコマンド的なイメージ
  • TOKTEMPERATURE: TOKTARGETコマンドの引数の一つ的なイメージ

これだけだとわからないので下で書くlexと照らし合わせてみてください。

  • commandsのところ

ここが根幹と言っても過言では無いです。

使いたいcommandを定義します。ここではheat_switchとtarget_setの二つの自作関数(的なイメージ)を作りました。

  • heat_switchのところ

ここで自作関数heat_switchの詳細を定義します。TOKHEATが実際のコマンドでSTATEはその引数的なイメージです。$2はSTATEをさします。

  • target_setのところ

自作関数target_setの詳細を定義します。$3はNUMBERをさします。

lex

こっちは簡単です。

%{
    #include <stdio.h>
    #include "y.tab.h"
%}

%%

[0-9]+      yylval = atoi(yytext); return NUMBER;
heat        return TOKHEAT;
on|off      yylval = !strcmp(yytext, "on"); return STATE;
target      return TOKTARGET;
temperature return TOKTEMPERATURE;
\n          ;
[ \t]+      ;

%%
  • includeのところ

とりあえずincludeしてください。y.tab.hyaccの出力ファイルです。これが必要になるのでまずyaccから説明しました。

  • [0-9]+のところ

yylval = atoi(yytext); return NUMBER;

前述の温度に当たるとこです。atoiで入力値をyylvalに格納してます。

  • heatのところ

return TOKHEAT;

前述のheat_switchのコマンド名にあたります。

  • on|offのところ

yylval = !strcmp(yytext, "on"); return STATE;

heat_switchのコマンドの引数にあたります。strcmpはc言語の関数でcompareしてます。

  • targetのところ

return TOKTARGET;

前述のtarget_setのコマンド名にあたります。

  • temperatureのところ

return TOKTEMPERATURE;

target_setのコマンドの引数にあたります。

実行

これでもわからないかもしれません。なので動かしましょう。

実行準備

$ lex test.l
$ yacc -d test.y
$ cc lex.yy.c y.tab.c -o test
test.y:15:9: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
        main()
        ^
test.y:17:17: warning: implicit declaration of function 'yyparse' is invalid in C99 [-Wimplicit-function-declaration]
                yyparse();
                ^
y.tab.c:1242:16: warning: implicit declaration of function 'yylex' is invalid in C99 [-Wimplicit-function-declaration]
      yychar = YYLEX;

僕の環境では上のようになりましたが気にせず。

では実行。

$ ./test         
heat on         
         Heat turned on 
heat off
         Heat turned off 
target temperature 32
         Temperature set to 32
heat on
         Heat turned on 
target timer 5
error: syntax error
timer%      

おーー、なるほど。

感想

まあ基礎の基礎の基礎くらいしか触って無いのでなんともいえないです。

ちなみに今回が自作OS Advent Calendar 2019 - Adventar初参加でした。楽しかったです。

一方で皆さんの為になる記事が書けなくてすいません。

電卓作れそうです。ふふ

参考文献

funningboy.blogspot.com

www.ibm.com

https://cse.iitkgp.ac.in/~bivasm/notes/LexAndYaccTutorial.pdf

ja.tech.jar.jp

berthub.eu