백과

문법(grammar)에 맞는 스트링을 만들어내는 과정. 스트링들이 모여서 그 문법에 의한 언어(language)를 형성하며 언어는 여러 알파벳과 숫자, 그리고 특별한 문자(character)로 이루어진다. 생성 규칙(production rule)은 문법이 규정하는 유도 원칙이며 이것의 반복 적용이 곧 유도이다. 그리고 모든 심벌이 말단 문자(terminal character)로 이루어지면 유도는 끝나게 되고, 이때 형성된 스트링은 그 언어의 문(statement)이 된다. 생성 규칙은 α→β형태를 취한다. α가 나타난 곳이면 β로 대신할 수 있으므로 생성 규칙은 곧 치환을 의미한다.