Extended Backus Naur 문법을 어떻게 변형 할 수 있습니까?

Question

나는 그 표현식을 0 번 이상 나타내는 대괄호 '{}'사이의 표현식을 포함하는 문법을 가지고 있으며, 대괄호 '[]'사이의 표현식은 그 표현식을 1 번 또는 전혀 나타내지 않으며, 이런 종류의 문법은 Extended Backus-Naur Form Grammars 라 불리는 것입니다. 문법을 일반 형식 (대괄호 나 대괄호가없는 곳)으로 변환하고 싶습니다.

기존 알고리즘이 있습니까?

나는 A -> B [CD] E를 A -> BE, A -> BCDE로 대체 할 수 있다는 것을 알고 있지만, 순서대로 구현할 수있는 기존 알고리즘이 있는지 알고 싶습니다. 그 표현을 변형시키는 것.

Answer 1

가장 쉬운 방법은 모든 EBNF 구문을 새로운 규칙으로 대체하는 것입니다. 여기 동등성은 사용할 수 있습니다 :

옵션 ɛ는 빈 문자열을 나타냅니다

A ::= B [C D] E ; 

A ::= B X E ; 
X ::= C D | ɛ ; 

.

반복

A ::= B {C D} E ; 

0 번 이상 :

그룹화

A ::= B X E ; 
X ::= C D | C D X ; 

:

A ::= B X E ; 
X ::= C D X | ɛ ; 

한 번 이상

A ::= B (C D) E ; 

A ::= B X E ; 
X ::= C D ; 

반복적으로 이러한 변환을 적용하고 당신은 바닐라 BNF하게 될 겁니다.