parsing - 我怎么能在yacc中识别皮卡丘语言？

Question

我正在尝试做一个简单的 lex&yacc 程序，它可以识别皮卡丘的三种声音:pi、pika 和 pikachu。我唯一的规则是一个 token 不能在一行中连续出现 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
    ;
%%

但这并不适用于所有组合，例如皮卡皮卡丘皮卡丘。我怎么能重写这个？
还尝试限制像 {0,2} 这样的 lex 中的标记，但是当我编写 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 时的非终结符，一个用于读取 PI 是第二个 PI 时的非终结符。根据目前所读到的内容，考虑产生式如何在这些不同的非终结符之间转换。