Рекурсивное определение языка

Question

Предположим, у меня есть язык, состоящий из только сбалансированных скобок, то есть {ε, (), ( ()), () (), ( ( ())), ( () ()), ... } и I' Я попросил написать рекурсивное определение для него. Может ли кто-нибудь дать мне пример того, как это может выглядеть? - Я немного новичок в теории компьютерных наук такого типа.

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;