Как построить LEX для этого?

Question

Я хочу заставить автоматы принимать следующие регулярные выражения, используя lex и yacc. Регулярное выражение: R = (ab + a) *.

Может кто-нибудь помочь мне сконструировать этот автомат, используя lex и yacc.

Спасибо.

Answer 1

Первое, что приходит на ум, это что-то вроде этого. Не завершенные программы, но кое-что, с чего можно начать:

Сканер (лекс):

%%
a           return TOKENA; /* for an a in the input */
b           return TOKENB; /* for a b in the input */
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

Парсер (yacc):

commands: /* empty */
        | commands command
        { printf("found a (ab + a)* pattern"); }

command:
        ab
        |
        a
        ;

ab: TOKENA TOKENB
    ;
a: TOKENA
    ;

Я не совсем уверен, работает ли грамматика или есть конфликты редукции.