구문구조의 단계
어휘 구문구조 : 언어를 구성하는 기본 기호를 정의.
구체 구문구조 : 계산식, 문장, 프로그램을 작성하는 규칙
추상 구문구조 : 구두점이나 괄호와 같은 구문 인식전용 구조를 제외한 핵심적인 구문정보만을 정의
메타언어 : 다른 언어를 기술하는데 사용하는 언어.
문법 : 언어의 문법구조를 정의하는데 사용하는 메타언어
- T (단말기호), N (비-단말기호), S (시작기호), P (생성규칙)
Chomsky의 4개의 언어 유형
A->B : 무제약 언어
A->B (A의 길이는 B의 길이보다 짧거나 같음) : 문맥의존 언어
-> aBc -> aAbc 라는 문법은 앞 뒤에 a,c가 있을 경우에만 B->Ab가 성립함. (문맥에 의존함)
비단말->B : 문맥자유 언어
-> B -> Ab 라는 문법은 앞 뒤에 무엇이 있는가와 상관없이 성립. (문맥에 자유로움)
A->Ab or b : 정규문법
BNF 문법 (문맥자유 언어)
"Integer -> Integer Digit"
- 반복을 재귀적으로 표현, 비-단말자로 그룹화한다.
- 문법 내용을 통해 파스트리로 표현할 수 있음. 이 때, 왼쪽으로 표현하냐 오른쪽으로 표현하냐에 따라 좌단, 우단 파스트리라고한다.
- 한 문법에서 두 개 이상의 다른 모양 파스트리가 나오면 모호한(Ambiguous) 문법이라고 한다..
-> 컴퓨터는 여러 개의 정답이 나오는 경우 사용하기 힘드므로, 모호한 문법은 사용할 수 없다.
EBNF 문법
- BNF 문법에 메타문자를 추가로 사용하는 문법
- '{ }' : 0번 이상 반복 가능, '[ ]' : 옵션 선택, '( )' : 여러 개 중 하나 선택
- BNF와 EBNF는 서로 변환할 수 있다.
1. 'A -> { o }'(EBNF) = 'A -> | oA'(BNF)
2. 'A -> [ b | c ]'(EBNF) = 'A -> | b | c'(BNF)
3. 'A -> ( a | b )'(EBNF) = 'A -> a | b'(BNF)
Clite
- EBNF문법으로 정의된 소규모 언어
- 설명할 때 메타언어는 파란색, 그냥 문자는 검은색으로 표현함.
- 연산자 우선순위 : 산술연산자 > 관계연산자 > 논리연산자 > 지정연산자
Q. A < B < C 연산은 가능할까?
- A < B 연산이 먼저 실행되고, 이 연산에 대한 해답은 0(false), 1(true)로 주어진다.
- 즉 ,다음 연산은 0 < C or 1 < C가 된다.
- 그러므로 A < B < C는 불가능하다.