markdown記法に対する構文解析周りを触る必要が生じたので、構文解析周りの復習をかねて簡易なパーサを作ってみたのでメモ。

目標

画像リンクを実現させてみる. つまり、

#input.md
[![AltTitle](http://example.com/example.jpg)](http://example.com)

を読み込んで、

# output.html
<a href="http://example.com" > 
    <img src="http://example.com/example.jpg" alt="AltTitle"></img> 
</a>

みたいなHTMLコードを出力させられればO.K.

サポートすべきマークダウン記法のサブセットは2種類。

# 画像埋め込み
![代替テキスト](http://img.example.com/100)

# リンク(タイトルなし).
[リンクテキスト](http://example.com)

この程度なら正規表現でできるのだが、この後いろいろと機能追加する、という想定でちゃんと構文解析して出力を生成する。

BNF表現

バッカス・ナウア記法を用いて、まずは導出則を記述する。


<Line>    ::= <Blocks> <CR> 
<Blocks>  ::= <Block>   | <Block> <Blocks>
<Block>   ::= <Element> | <Video> | <Link>
<Link>    ::= "[" <Element> "]" "(" <url> ")"
<Element> ::= <Image>     | <literal> 
<Image>   ::= "![" <literal>  "]" "(" <url> ")"

ここで、

<Line>, <Blocks>, <Block>, <Link>, <Element>, <Image>

の７個がいわゆる非終端記号で、

"[", "]", "![", "(", ")",  <literal>, <url>, <CR>

の7個がいわゆる終端記号(token)となっている。

yacc, lex での実装

ここまでできればあとは上記のBNF表記を、yacc、lexのお作法に従ってコーディングして行けば良い。

my_markdown_parser

Token定義

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

int
yywrap(void)
{
    return 1;
}
%}
%%
"["      return LINK_OPEN;
"!["     return IMAGE_OPEN;
"]"      return CLOSE;
"("      return LEFT_PAR;
")"      return RIGHT_PAR;
"\n"     return CR;
[0-9A-Za-z_,\-\.:/]+ {
    char* temp;
    int len = strlen(yytext);
    temp = calloc(sizeof(char), len + 1);
    sscanf(yytext, "%s", temp);
    yylval.literal_value = temp;
    return LITERAL;
}
%%

文法とアクションの定義

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define YYDEBUG 1
%}
%union {
char*        literal_value;
char*        string_value;
}
%token <literal_value>  LITERAL
%token LINK_OPEN IMAGE_OPEN CLOSE LEFT_PAR RIGHT_PAR CR
%type <string_value> blocks block link element image
%%
line_list
    : line
    | line_list line
    ;
line
    : blocks CR
    {
        printf("%s\n", $1);
        free($1);
    }
blocks
    : block
    | block blocks
    {
        char* buf;
        int lengths[2];
        lengths[0] = strlen($1);
        lengths[1] = strlen($2);
        int len = 0;
        for (int i=0; i < 2; i++) {
            len += lengths[i];
        }
        buf = calloc(sizeof(char), len + 2);
        sprintf(buf, "%s %s", $1, $2);
        free($1);
        free($2);
        $$ = buf;
    }
    ;
block
    : element
    | link 
    ;
link 
    : LINK_OPEN element CLOSE LEFT_PAR LITERAL RIGHT_PAR
    {
        char* buf;
        int lengths[2];
        lengths[0] = strlen($2);
        lengths[1] = strlen($5);
        int len = 0;
        for (int i=0; i < 2; i++) {
            len += lengths[i];
        }
        buf = calloc(len + 19, sizeof(char));
        sprintf(buf, "<a href=\"%s\" > %s </a>", $5, $2);
        free($2);
        free($5);
        $$ = buf;
    }
    ;
element 
    : image
    | LITERAL
    ;
image
    : IMAGE_OPEN LITERAL CLOSE LEFT_PAR LITERAL RIGHT_PAR
    {
        char* buf;
        int lengths[2];
        lengths[0] = strlen($2);
        lengths[1] = strlen($5);

        int len = 0;
        for (int i = 0; i < 2; i++) {
            len += lengths[i];
        }
        buf = calloc(len + 38, sizeof(char));
        sprintf(buf, "<img src=\"%s\" alt=\"%s\" width=\"320\" ></img>", $5, $2);
        free($2);
        free($5);
        $$ = buf;
    }
    ;
%%
int
yyerror(char const *str)
{
    extern char *yytext;
    fprintf(stderr, "parser error near %s\n", yytext);
    return 0;
}

int main(void)
{
    extern int yyparse(void);
    extern FILE *yyin;

    //yydebug = 1;
    yyin = stdin;
    if (yyparse()) {
        fprintf(stderr, "Error ! Error ! Error !\n");
        exit(1);
    }
}

実行結果

OSX Marverics で動作確認。

コンパイル

yacc -dv my_markdown.y 
lex token.l
clang -o my_markdown_parser y.tab.c lex.yy.c
# or 
# gcc -o my_markdown_parser y.tab.c lex.yy.c

実行結果

# input.md 
# [![DragonBook](http://upload.wikimedia.org/wikipedia/en/a/a3/Purple_dragon_book_b.jpg)](http://www.amazon.com/Compilers-Principles-Techniques-Tools-Edition/dp/0321486811)

cat input.md | ./my_markdown_parser

で、以下のような画像リンクが生成される。(以下は生成したHTMLをinlineで表示.)

<a href="http://www.amazon.com/Compilers-Principles-Techniques-Tools-Edition/dp/0321486811" > 
    <img src="http://upload.wikimedia.org/wikipedia/en/a/a3/Purple_dragon_book_b.jpg" alt="DragonBook" width="320" ></img> 
</a>

参考資料

Makrdown記法チートシート

テーブル表記や空行の取り扱いが必要になる記法を実現させようとすると、もうちょっと複雑になりそうだが、テキストの修飾、水平線、引用などは画像やリンクと同様の実装で実現できそう。

yaccとlex

大学の講義ページだと思う。古い記事だがとても分かりやすい。yaccの動作は、テトリスだと思えば良い、という説明が自分的にはすごくしっくり来た。

Markdown記法の一部を理解してHTMLに変換する処理をyacc,lexで実装してみる

目標

BNF表現

yacc, lex での実装

実行結果

参考資料