How could I recognise the Pikachu language in yacc?

Admin 1
Viewed 48

I am trying to do a simple lex&yacc program that can recognise the three sound of pikachu: pi, pika and pikachu. My only rule is that one token can not appear 3 times in a row in line. I have tried this:

%token PI PIKA PIKACHU

%%
program : program line '\n'
    |
    ;
line: PI piWords
    | PIKA pikaWords
    | PIKACHU pikachuWords
    ;
piWords: PI 
    | PI pikaWords
    | PI pikachuWords
    ;
pikaWords: PIKA 
    | PIKA piWords
    | PIKA pikachuWords
    ;
pikachuWords: PIKACHU
    | PIKACHU piWords
    | PIKACHU pikaWords
    ;
%%

but this doesn't work on all combinations, for example Pika Pikachu pikachu. How could I rewrite this? Also tried limiting the tokens in lex like {0,2} but when I write pi pi pi for example it still works even if it shouldn't.
UPDATE.
Based on ideas below, I did managed to finish this. I was pretty close, all I needed was to keep track is there was 2 repetitions also. I did smth like this:

program : program line '\n'
    |
    ;
line: piWords
    | pikaWords
    | pikachuWords
    ;
piWords: PI  
    | PI pikaWords
    | PI PI pikaWords
    | PI pikachuWords
    | PI PI pikachuWords
    ;
pikaWords: PIKA 
    | PIKA piWords
    | PIKA PIKA piWords
    | PIKA pikachuWords
    | PIKA PIKA pikachuWords
    ;
pikachuWords: PIKACHU
    | PIKACHU piWords
    | PIKACHU PIKACHU piWords
    | PIKACHU pikaWords
    | PIKACHU PIKACHU pikaWords
    ;
yacc parsing
1 Answers

Your grammar here is on the right track, but needs a little tuning.

Intuitively, each of your nonterminals keeps track of the last terminal you’ve seen so that you don’t allow for the same string to appear twice in a row. You can expand on this idea by having nonterminals keep track of the following information: what was the last terminal I saw, and how many copies of it did I see? So, for example, you’d have two nonterminals for when the last terminal was PI, one for when the PI read was the first PI and one for when the PI read was the second PI. Think about how the productions would transition between these different nonterminals based on what’s been read so far.

user_5015570
Related