컴파일러 이론 - ChoDragon9/posts GitHub Wiki

1. 형식 언어

형식 언어는 유한한 종류의 문자로 이루어진 유한한 길이의 문자열의 집합을 말한다.

형식 언어는 수학, 논리학, 언어학, 정보 이론 등에서 사용하고 있으며, 또한 계산가능성 이론과 밀접하게 관련되어 있다.

각 형식 언어에는 그 언어에서 사용하는 문자의 집합이 있으며, 그 집합은 무한할 수도 있다. 그 형식 언어에 속하는 문자열은 문자들로 이루어진 유한한 길이의 수열로 정의된다.

형식 언어는 특정한 문자열의 집합이기 때문에, 다음과 같은 방식을 이용해 형식 언어를 만들 수도 있다.

특정한 형식 문법의 법칙에 따라 생성되는 문자열의 집합 특정한 정규 표현식이 만들어내는 문자열의 집합 특정한 오토마톤이 받아들이는 문자열. 오토마톤에는 튜링 기계, 유한 상태 기계 등이 있다. 판정 문제의 대상이 되는 예/아니오 질문 중 그 대답이 예인 것들의 집합. 추론의 결과.

2. 형식 문법

형식 문법(formal grammar)은 형식 언어를 정의하는 방법으로, 유한개의 규칙을 통해 어떤 문자열이 특정 언어에 포함되는지를 판단하거나, 그 문법으로부터 어떤 문자열을 생성해 낼지를 정한다.

형식 문법은 그 문법으로부터 문자열들을 생산해 내는 생성 문법(generative grammar)과, 문자열이 특정 언어에 포함되는지를 판단하는 해석 문법(analytic grammar)으로 나눌 수 있다.

생성 문법

생성 문법은 특정 문자열에서부터 시작하여 여러 생성 규칙에 따라 문자열을 생성해낸다. 예를 들어, 다음의 규칙으로 구성된 문법이 있다고 할 때:

S => aSb
S => ba

S로부터 시작하여 이 문법으로부터 생성되는 문자열은 ba, abab, aababb, aaababbb 등이 있다. 예를 들어, aababb는 S => aSb => aaSbb => aababb와 같은 방법을 통해 생성해낼 수 있다.

• 번역기 구성론
• 문법과 언어

3. 문맥 자유 문법

문맥 자유 문법(Context-free grammar, CFG), 문맥 무관 문법은 형식 문법의 한 종류로, 생성 규칙이 다음과 같은 문법을 의미한다.

V => w

여기에서 V는 비말단(비종결자) 기호이고, w는 비말단과 말단 기호들로 구성된 문자열이다. 즉, 문맥 자유 문법의 각 생성 규칙의 좌측에는 단 하나의 비말단 기호만 관계한다.

많은 프로그래밍 언어 문법은 문맥 자유 문법에 속하며, 따라서 이 문법은 컴파일러 등의 이론에 중요한 역할을 차지한다.

4. 문맥 의존 문법

문맥 의존 문법(Context-sensitive grammar, CSG), 문맥 민감 문법은 형식 문법의 한 종류로, 생성규칙에서 시작 부분과 끝부분을 나타내는 것을 포함하는 부분이다.

5. LL Parser

LL 파서(LL parser)는 문맥 자유 문법의 일부를 파싱할 수 있는 하향식 파서이다. LL 파서는 입력 문자열의 왼쪽(Left)에서부터 파싱을 시작하여, 좌측유도(Leftmost derivation) 방식으로 동작한다. LL 파서로 파싱이 가능한 문법은 LL 문법이라고 부른다.

만약 LL 파서가 lookahead에 최대 k개의 토큰(token)을 사용한다면, 그 파서는 LL(k) 파서라고 부른다. LL(k) 파서로 파싱이 가능한 문법은 LL(k) 문법이라고 부른다.

6. 추상 구문 트리

컴퓨터 과학에서 추상 구문 트리(abstract syntax tree, AST), 또는 간단히 구문 트리(syntax tree)는 프로그래밍 언어로 작성된 소스 코드의 추상 구문구조의 트리이다. 이 트리의 각 노드는 소스 코드에서 발생되는 구조체를 나타낸다. 구문이 추상적이라는 의미는 실제 구문에서 나타나는 모든 세세한 정보를 나타내지는 않는다는 것을 의미한다.

추상 구문 트리는 전통적인 파스 트리와는 구별한다.

추상 구문 트리는 프로그램 분석과 프로그램 변환시스템에도 사용된다.

추상 구문 트리는 컴파일러에 널리 사용되는 자료 구조인데, 이는 프로그램 코드의 구조를 표현하는 프로퍼티이기 때문이다. AST는 일반적으로 컴파일러의 구문 분석 단계의 결과물이다. 컴파일러가 요구하는 여러 단계를 통해 프로그램의 중간 표현의 역할을 하며 컴파일러의 최종 결과물에 대해 강력한 영향을 준다.