如何在yacc中识别皮卡丘语言？

Question

我正在尝试做一个简单的lex＆yacc程序，它可以识别皮卡丘的三种声音：pi，pika和pikachu。我唯一的规则是，一个令牌不能连续出现3次。我已经试过了：

%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
    ;
%%

但是这不适用于所有组合，例如Pika Pikachu pikachu。我该如何重写？还尝试了限制lex中的令牌，例如{0,2}，但是当我编写pi pi pi时，即使它不起作用，它仍然可以工作。更新。根据下面的想法，我确实做到了这一点。我离我很近，我所需要的只是保持追踪，是否还有2次重复。我做了这样的事：

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
    ;

Answer 1

您的语法在正确的轨道上，但是需要一些调整。

直觉上，每个非终结符都会跟踪您看到的最后一个终结符，因此您不允许同一字符串连续出现两次。您可以通过使非终端机跟踪以下信息来扩展此思想：我看到的最后一个终端机是什么，我看到了多少个副本？因此，例如，当最后一个终端为PI时，您将有两个非终端；当PI读取为第一个PI时，您将有两个非终端。考虑到到目前为止所读到的内容，思考一下作品如何在这些不同的非终端之间转换。