有没有比这更好的方法来编写右递归语法的生产规则？

Question

场景：为 RIGHT 递归语法提供生产规则描述由字符构成的所有非空字符串的集合R 和 N，可以包含任意多个连续的重复 R，但恰好是两个或三个连续的N的重复。

答：

A -> N B |R⁺ A

B -> N D |北 C |N ε

C -> N D |N ε

D

-> R⁺ D |R ε

Answer 1

不正确：

A -> NNB | NNNB | RA | R
B -> R | RA | ε

编辑：以上不正确，我误解了场景。

正确：

S -> RS | A
A -> NA | NB
B -> RB | RC
C -> NC | ND
D -> RD | RE | ε
E -> NE | NF
F -> RF | ε

工作原理：它以 S 开头，可以生成 0 或多个 R，或者移动到 A，生成第一组 Ns。然后它移动到 B，在 N 的第一组和第 2 组之间生成 Rs。然后它移动到 C，生成第 2 组 Ns。然后它移动到 D，它可以生成 0 个或多个 R，然后完成或移动到 E，生成第 3 组 Ns。 最后，它移动到 F，生成 0 个或更多 Rs。

Answer 2

这也同样有效，而且更简单：

S -> RS | A
A -> NA | NB
B -> RB | RC
C -> NC | ND
D -> RD | E
E -> NE | F
F -> RF | ε

直到 D 也是如此，它

不是提供ε选项，而是提供了一个选项来添加另一组 R 或转到另一组 N 的 E，但如果以前没有 R，这不会发生，因为它们会被输出为从 C 的转换， 然后是递归添加 R 或空字符串的另一个选项。

从输入 NRNR 生成的解析树示例

S
  
   A
  / 
 N   B
    / 
   R   C
      / 
     N   D
        / 
       R   D
            
             E
              
               F
                
                 ε