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

非終端記号の<string>と<marked-string-body>はその生成規則が全く同じである。
分けて定義しているのは構文規則のレベルで両者を区別できるようにするためだった。
しかし、この二つは字句解析段階で一種類の字句として抽出した方が構文規則がシンプルになっていいという考え方もあるだろう。
その場合、二つの区別は構文レベルでなく意味動作を与えるアクションの定義の方で行えばいい。
構文規則は以下のようになる。

<text> ::= <string-headed> | <marked-string-headed>
<string-headed> ::= <string-except-parenthesis> | <string-except-parenthesis> <marked-string-headed>
<marked-string-headed> ::= <marked-string> | <marked-string> <marked-string-headed> | <marked-string> <string-headed>
<marked-string> ::= "(" <string-except-parenthesis> ")"

件の非終端記号二つは<string-except-parenthesis>に統合されて終端記号となっている。
これを素直にyacc/bison用に書くと、

%{
#define YYSTYPE char*

#include <stdio.h>

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

%token STRING_EXCEPT_PARENTHESIS

%%

text : string_headed
     | marked_string_headed
     ;

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

marked_string_headed : marked_string
                     | marked_string marked_string_headed
                     | marked_string string_headed
                     ;

marked_string : '(' STRING_EXCEPT_PARENTHESIS ')'           { printf("marked-string [%s]\n", $2); }
              ;

%%

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

#define TEXT_BUFFER_LMAX 8192
char text_buffer[TEXT_BUFFER_LMAX];
#define END_OF_TEXT_BUFFER (text_buffer+(TEXT_BUFFER_LMAX-1))

int yylex(void)
{
    char *p = text_buffer;
    int c = getchar();
    if (c == '(' || c == ')') return c;
    if (c == EOF) return 0;
    do {
        if (p >= END_OF_TEXT_BUFFER) {
            yyerror("yylex: too long text");
            return YYERRCODE;
        }
        *p++ = (char)c;
        c = getchar();
    } while (c != '(' && c != ')' && c != EOF);
    ungetc(c, stdin);
    *p = '\0';
    yylval = text_buffer;
    return STRING_EXCEPT_PARENTHESIS;
}

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

構文解析器での処理の一端を字句解析器に担わせたため、
構文規則部がシンプルになった代わりに字句解析関数yylexが複雑になった。
変更前は構文規則に対するアクションで一文字ずつ処理していたが、
該当する部分文字列を終端記号<string-except-parenthesis>として構文解析器に渡すために、
yylexが部分文字列へのアドレスをこの記号の値としてyylvalに設定するようにしている。
この授受用の場所として固定サイズの配列text_bufferを使い、これに部分文字列をコピーしているため、
部分文字列がそのサイズTEXT_BUFFER_LMAXから1引いたものより長い時はYYERRCODEを返すようにする。
例えば、TEXT_BUFFER_LMAXを22に短くして試すと、

$ 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 [.]

のように今までどおりだが、バッファ長を21にすると、

$ echo -n "The quick brown (fox) jumps over the lazy (dog)." | ./parser
string [The quick brown ]
marked-string [fox]
yylex: too long text
syntax error

長さ21文字の部分文字列" jumps over the lazy "の抽出をyylexはエラーとして返す。