単純なマーク付けがなされた文字列の解析 #2

既にBNFで書けているわけなので、構文解析器生成系があれば簡単に解析器を自動生成できる。

parser.y

%{
#include <stdio.h>

int yylex(void);
void yyerror(char const *);
%}

%token CHAR_EXCEPT_PARENTHESIS

%%

text : string_headed
     | marked_string_headed
     ;

string_headed : string                                            { puts("]"); }
              | string { puts("]"); } marked_string_headed
              ;

marked_string_headed : marked_string
                     | marked_string marked_string_headed
                     | marked_string string_headed
                     ;

marked_string : '(' marked_string_body ')'                        { puts("]"); }
              ;

string : CHAR_EXCEPT_PARENTHESIS                                  { printf("string [%c", $1); }
       | string CHAR_EXCEPT_PARENTHESIS                           { putchar($2); }
       ;

marked_string_body : CHAR_EXCEPT_PARENTHESIS                      { printf("marked-string [%c", $1); }
                   | marked_string_body CHAR_EXCEPT_PARENTHESIS   { putchar($2); }
                   ;

%%

int main(void)
{
    return yyparse();
}

int yylex(void)
{
    int c = getchar();
    if (c == '(' || c == ')') return c;
    if (c == EOF) return 0;
    yylval = c;
    return CHAR_EXCEPT_PARENTHESIS;
}

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

BNFで書かれた構文規則をそのまま何の工夫もなくyacc/bisonの書法で書き直しただけである。
アクションは構文規則の左辺の非終端記号へ還元される時に実行するように書いているが、
string_headedの二つ目の生成規則だけはアクションを規則の途中に入れてある。
アクションを規則の途中に入れられるのはこういうとき便利だ。
main関数や字句解析用のyylex関数も手書きで与えてあるので、このソースから生成されるCソースのみで閉じている。
このプログラムは標準入力から読み込んだ文字列を解析して標準出力にその結果を書き出す。

$ echo -n "The quick brown (fox) jumps over the lazy (dog)." | ./parser
string [The quick brown ]
marked-string [fox]
string [ jumps over the lazy ]
marked-string [dog]
string [.]

$ echo -n "(Ab)ra(cad)(a)br(a)" | ./parser
marked-string [Ab]
string [ra]
marked-string [cad]
marked-string [a]
string [br]
marked-string [a]