이론적으로 BNF는 모든 파일 형식을 설명하기에 충분합니까?

Question

BNF에서 설명 할 수없는 파일 형식이 있습니까?

Answer 1

아니요, BNF가 충분하지 않습니다. BNF는 context-free grammars을 설명합니다. 모든 상상할 수있는 문법에 근접하지는 않습니다. 거의 모든 프로그래밍 언어, 대부분의 경우 제정신이 아닌 데이터 직렬화 형식 등이 있습니다. 은 문맥에 관계없이이지만 이론에 대해 물어 본 결과 대답은 아니오입니다. 처음에는 context-sensitive grammars이 있습니다. 이름이 알려지지 않은 경우 문맥이없는 문법으로 표현할 수 없습니다. 간단한 예가 n 번 a이고 그 다음에 n 번 b이 이어지고 n 번 c (각각에 대해 n과 같음)이 될 것입니다.

또한 문법은 문법이나 구문만을 설명합니다. 파일 형식에 따라 유효 형식 (유효 형식)의 데이터가 필요합니다. 예를 들어 프로그래밍 언어의 형식 검사를 생각하십시오. 문맥 - 자유 문법이나 그 문법에 대한 대부분의 문법으로는 그러한 의미 제약을 기술 할 수 없다. 이론적으로 복잡한 작업이있을 수 있습니다. 물론 이에 상응하는 것은 비실용적입니다.

Answer 2

예. BNF는 문맥 자유 문법만을 기술한다. 파일에 고유 한 구.에 대한 설명이 들어 있으면 해당 파일을 읽는 규칙을 BNF에서 표 현할 수 없습니다. 이를 위해 튜링 기계가 필요합니다. 마찬가지로, 파일을 수락하거나 거부하는 결정이 푸시 다운 오토 마 타로 표현 될 수 없다면 bnf는 작동하지 않을 것입니다.

BNF는 예를 들어 영어 구문을 완벽하게 설명 할 수 없습니다.