recursion - 语言的递归定义

Question

假设我有一种只由平衡括号组成的语言，即 {ε, ( ), ( ( ) ), ( ) ( ), ( ( ( ) ) ), ( ( ) ( ) ), ... } 和 I' m 要求为它写一个递归定义。有人可以给我一个例子，看看它可能是什么样子吗？- 我对这种类型的计算机科学理论有点陌生。

Answer 1

一种递归定义是语法。生成平衡括号的语言：

S --> (S) | SS | ^

这是递归的，因为S出现在RHS生产规则中。

制作规则： LHS --> RHS

编辑

为什么(s)不S呢？

因为要()递归地添加对并且不止一次。

S --> (S) --->  ((S))   

在第二步中，内部S被替换为(S).

Answer 2

TEXT ::= BRACES | BRACKETS | LIST;
BRACES ::= "{" ( TEXT | /* nothing */ ) "}";
BRACKETS ::= "(" ( TEXT | /* nothing */ ) ")";
LIST ::= ( BRACES | BRACKETS ) | ( BRACES | BRACKETS ) "," LIST;