언어와 컴파일러 단상.

 해석불가 , 판단불가
            |   비결정(Undecidable) , 비형식
            |
       자연어                                              
            | 결정적 , (P , NP-Complete )
            |                             형식            춈스키 계층
언어 통사론(formal grammar)    --     context-free grammars
                                                   regular grammars
                                                           |
                                                           | 표현
                                                   CFG(Grammar of a context-free language)
                                                   context-free languages
                                                   regular languages
                                                           |
                                                           | 생성
                                   Turing Machine - 생성 Compiler (결정방법 *BNF , EBNF) - 해석 Compiler

위의 내용은 컴파일러 이론과 계산 가능성에 대한 이미지를 간략하게 표현한것이다.

춈스키는 이해 될 수 있는 언어의 형식 구조를 계층으로 분류하였는데 그것을 춈스키 계층이라 불린다.

1.context-free grammars는 결정되어지는 의미가 2개이상이 되는 문법을 이야기한다.
ex) 누구나 아는 예로서 "아버지가방에들어가신다" 는 표현이 결정할수 있는 의미는 2가지이다.

2.regular grammars은 하나의 표현은 하나의 의미를 갖는다. 수식표현이나 정형화된 언어들을 말한다.

위의 2가지 형식분류는 결정되어지기 때문에 turing machine으로 계산 가능하다.
위의 2가지를 표현한 문법이 CFG...등이고 이 문법을 이용해 생성한 문장은 인식 가능하기 때문에
이것을 이용해 간략한 표현으로 정확한 의미를 전달할수 있다.

컴파일러는 이런 결정가능한 표현법을 이용해 보다 간략한 표현으로 의미를 확장시킬수 있다.

*위 문법은 정규식(regular expression)에서도 사용되어진다.
*P(polynomial 다항식)와 NP(nondetermnistic polynomial 비결정 다항식)를 합쳐 계산 복잡성이라한다.

참고자료 : 컴파일러이론