촘스키의 4가지문법, BNF와 EBNF차이, 의미론

소개글

학자 촘스키의 4가지 문법과 프로그래밍언어의 BNF와 EBNF

그리고 3가지 의미론에 대한 내용입니다.

목차

Chomsky`s 4 classes of grammars
BNF
EBNF
정적의미론
공적의미론
표기의미론
출처

본문내용

촘스키의 0문법과 1문법

Type-0 문법 (unrestricted grammars) 은 모든 형식문법을 포함한다. 튜링기계 (Turing Machine) 로 인식가능한 모든 언어를 정확히 생성한다. 그 인식가능한 언어란 튜링기계가 멈추는 모든 string 들을 의미한다. 이 언어들은 또한 회귀열거가능 언어로 알려져있다. 이것은 튜링기계를 항상 정지시켜서 결정가능한 recursive language 와는 다르다는 것을 주목해야 한다.

Type-1 문법 (context-sensitive grammars) 은 context-sensitive languages 를 생성한다. 이 문법은 αAβ → αγβ 형태의 규칙을 가진다. strings α 와 β 는 empty 일 수 있지만 γ 는 nonempty 이어야 한다. 만일 S 가 어떤 규칙의 우측에 나타나지 않으면 규칙 S → ε 가 허용된다. 모든 생성 규칙은 α->β 에서 β의 길이가 α의 길이보다 길다. 이는 |α|≦|β|를 의미하는 것이다

참고 자료

촘스키와 세계화 ㈜시공사 - 존 라이언스
2001. 06. 26
촘스키 (시공사) – 존 라이언스
프로그래밍 언어론 (21세기사) – 김일민 외 지음
1999. 02. 10