注釈付きでマークされた文字列の解析 #10

書いたBNFを元に構文解析器と字句解析器のソースを書いてみる。
まず、構文解析器。

parser.y

%{
#define YYSTYPE char*

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

static char *estrdupcat(const char *s1, const char *s2);
%}

%token STRING_EXCEPT_SPECIAL

%%

text :
      string_headed
    | marked_string_headed
    ;

string_headed :
      string_except_parenthesis { printf("string [%s]\n", $1); free($1); }
    | string_except_parenthesis { printf("string [%s]\n", $1); free($1); } marked_string_headed
    ;

marked_string_headed :
      marked_string
    | marked_string marked_string_headed
    | marked_string string_headed
    ;

marked_string :
      '(' marked_string_body_with_annotation ')'
    ;

marked_string_body_with_annotation :
      STRING_EXCEPT_SPECIAL
        {
            printf("marked-string [%s]\n", $1); free($1);
        }
    | STRING_EXCEPT_SPECIAL ':' string_except_parenthesis
        {
            printf("marked-string [%s]: annotation[%s]\n", $1, $3);
            free($1); free($3);
        }
    ;

string_except_parenthesis :
      STRING_EXCEPT_SPECIAL
        {
            $$ = estrdupcat(NULL, $1);
            free($1);
        }
    | ':'
        {
            $$ = estrdupcat(NULL, ":");
        }
    | string_except_parenthesis STRING_EXCEPT_SPECIAL
        {
            $$ = estrdupcat($1, $2);
            free($1); free($2);
        }
    | string_except_parenthesis ':'
        {
            $$ = estrdupcat($1, ":");
            free($1);
        }
    ;

%%

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

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

static char *estrdupcat(const char *s1, const char *s2)
{
    size_t len = (s1 == NULL ? 0 : strlen(s1)) + strlen(s2) + 1;
    char *p = malloc(len);
    if (p == NULL) {
        fputs("error: estrdupcat cannot allocate any memories.\n", stderr);
        exit(1);
    }
    return s1 == NULL ? strcpy(p, s2) : strcat(strcpy(p, s1), s2);
}

colon_forbidden関係は必要なくしたので、
規則中のアクションのようにソースを見づらくするものが最小限に戻った。
STRING_EXCEPT_PARENTHESISは終端記号として字句解析器から供給されないので、
%tokenでの宣言を無くし、非終端記号string_except_parenthesisとして規則部で定義している。
定義した関数estrdupcatはこの括弧無し文字列を生成していくための補助関数である。
この関数は、新たに割り当てた領域に、引数で与えられた二つの文字列を連接してコピーする。
第一引数がNULLの場合は第二引数の文字列を割り当てた領域にコピーするだけである。
標準関数のstrcatやstrcpyと違い、引数とは別に領域を割り当てるので引数の文字列はどちらもconst修飾している。

lexer.l

...snip

static char *estrdup(const char *s);
%}

...snip
%%

[^():]+ { yylval = estrdup(yytext); return STRING_EXCEPT_SPECIAL; }
[():]   { return yytext[0]; }

%%
...snip

字句解析器については、colon_forbiddenのextern宣言と、
括弧を含まない文字列に対応するパターン[^()]+の行を削除しただけである。
関数yylexは単純に括弧やコロンを含まない文字列を返すか、括弧やコロンを一文字ずつ返すかだけを行う。
非常にシンプルになったし、#8で使ったREJECTは高コストなので使わないならそれに越したことはない。

構文解析系と字句解析系の分担としては、このくらいのバランスが妥協点なのかもしれない。