문맥 자유문법(Context-free grammar)

잘 설계된 문법은 소스 프로그램을 정확한 목적 코드로 번역할 때 유용한 구조를 제공

문맥자유 문법은 프로그래밍 언어의 설계에서 뿐만 아니라 효율적인 컴파일러 작성 시에도 중요하게 사용됨

모든 생성규칙이 A->b 형태일 때, 문맥자유문법

• A가 b로 치환: A는 b로 유도(derivation)
• b가 A로 치환: b는 A로 감축(reduce)

leftmost derivation, rightmost derivation

좌단 유도는 유도 과정의 각 단계에서 가장 왼쪽에 있는 논터미널 기호를 계속해서 대체하는 경우

우단 유도는 유도 과정의 각 단계에서 가장 오른쪽에 있는 논터미널 기호를 계속해서 대체하는 경우

Example

좌파스, 우파스

좌파스 - 좌단유도에 의해서 적용된 생성규칙 순서

우파스 - 우단 유도에 의해서 적용된 생성규칙 순서의 역순

파스 트리의 정의

구문 분석 방법은 크게 두 종류가 존재

• 하향식(top-down) 구문 분석 (좌파스를 생성)
• 상향식(bottom-up) 구문 분석 (우파스를 생성)

파스트리는 올바른 문장에 대해 그 문장의 구조를 트리 형태로 나타낸 것

파스트리 만들기

좌단유도

우단유도

-> 좌단유도, 우단유도로 만든 파스트리는 같음

모호한 문법

모호한 문법이란?

하나의 문장이 서로 다른 두 개 이상의 파스 트리를 갖는다면 문법 G는 모호하다고 함

모호한 문법 파스 트리를 하나로 만든느 방법

산술식의 경우 연산자의 우선순위와 결합법칙을 이용하여 모호하지 않은 문법으로 변환

연산자의 결합법칙은 연산자의 우선순위가 같을 때, 좌측 결합(가장 왼쪽에 있는 연산자 부터 계산) -> 대부분 프로그래밍 언어에서 좌측 결합 방식을 취함

문법 변환

문법 변환 - 주어진 문법을 동등한 언어를 생성하는 문법으로 변환

어떤 문법이 구분 분석을 하는데 있어서 효율을 상당히 떨어뜨리는 경우에 효율적인 구문분석이 이루어지도록 변환

변환방법

• 불필요한 생성규칙의 제거
• ε-생성규칙의제거
• 단일생성규칙의 제거
• 좌인수분해
• 자재귀의 제거 등

불필요한 생성규칙의 제거

불필요한 생성 규칙이란 불필요한 기호를 갖고 있는 생성 규칙을말함

불필요한 기호 - 시작 기호로 부터 도달 불가능하거나 터미널 기호들을 생성하지 못하는 기호

[5-1 알고리즘] 터미널 문자열을 생성할 수 있는 논터미널 기호

-> 더 이상 새로운 논 터미널이 생성되지 않을 때까지 반복해서 구한 논터미널 기호들의 집합ㅇ르 구하면 이 논터미널 기호들은 터미널 기호들을 생성하는 기호

터미널 문자열을 생성하지 못하는 논터미널을 가진 생성 규칙 제거

단일 생성 규칙의 제거

단일 생성 규칙이란 생성 규칙 중 A->B와 같이 생성 슈칙의 오른쪽이 단 하나의 논터미널 기호로만 구성된 생성규칙이 존재하는 경우를 말함

좌인수분해

하향식 구문분석 방법에서 사용

좌인수 분해 - 같은 기호들을 접두사로 갖는 2개 이상의 생성 규칙이 있을 때 인수분해 함

-> 공통된 접두사 a를 인수분해 함으로써 이 문제를 해결

Example

S -> cAd

일 경우

S -> cAd A -> aA’ A’ -> ε | b

로 인수분해 하면 됨

좌재귀

하향식 구문 분석 시에 같은 생성규칙이 반복적으로 적용되 무한루프에 빠지게 되 구문 분석을 어렵게 함

좌재귀를 우재귀로 변환 시킨다

즉 A=>Aa 같은 과정을 A=>aA로 변환

푸시다운 오토마타

푸시다운 오토마타에 의한 인식

확장(입력을 모두 집어 넣음)