형식 문법은 어떤 언어가 가지는 문법을 형식적으로, 엄밀히 정의하는 방법이다.
개요[편집 | 원본 편집]
사람이 일반적으로 사용하는 언어, 즉 자연어는 설계되어 만들어진 것이 아니라 사용하면서 서서히 만들어진 것이기 때문에 엄밀한 규칙보다는 외워야 할 예외가 많은 것이 일반적이다. 그러나 프로그래밍 언어의 경우에는 사람과의 대화가 아니라 컴퓨터에게 정보를 전달하기 위해 만들어진 언어이기 때문에, 규칙을 정확히 서술해야 하는 문법이 필요하다. 형식 문법은 이런 경우에 주로 사용된다.
노엄 촘스키가 제정한 촘스키 계층에서는 형식 문법을 4단계로 나눈다: 무제약 문법, 문맥 의존 문법, 문맥 자유 문법, 정규 문법. 오른쪽으로 갈 수록 제약이 강해지기 때문에 표현력은 적어지는 대신 처리에 있어서는 더 빠른 속도를 낼 수 있다. 정규 문법의 경우에는 정규표현식과 대응한다. 일반적으로 프로그래밍 언어에서는 문맥에 따라 형식이 바뀌지 않는 문맥 자유 문법을 사용하며, 간혹 언어가 발전하며 문법이 계속 추가되거나 처음부터 설계가 잘못된 경우, 아니면 아예 처음부터 그렇게 설계된 경우에는 문맥 의존 문법, 심지어는 무제약 문법을 사용하는 경우도 있다.