[소소하게2] 9월 16일 수요일 소소한 공부

컴파일러 싸강 들었다.

How to describe the Syntax

CFG (Context Free Grammar)

- 언어의 문법을 정의하는 일반적인 방법

- 간단하고 이해하기 쉬움

- 표현된 문법으로부터 자동적으로 인식기를 구현 가능

- 중첩된 구조를 표현하기 위해서 CFG 사용

 

terminal symbol

- a, b, c와 같은 알파벳 시작 부분의 소문자와 숫자 0, 1, ..., 9

- +, - 와 같은 연산자 기호와 세미콜론, 콤마, 괄호와 같은 구분자

- 'if' 또는 'then' 과 같이 따옴표 사이에 표기된 문법 심볼

 

non-terminal symbol

- A, B, C와 같은 알파벳 시작 부분의 대문자로 나타낸다.

- S는 보통 start symbol을 나타낸다.

- <>로 묶어서 나타내기도 한다.

 

생성규칙(P)

- terminal symbol과 non-terminal symbol로 이루어져 있는 문법에 대한 규칙

 

How to determine if the input token stream satisfies the syntax description?

유도 Derivation

- 문법에서 문장을 생성하기

- 생성 규칙을 연속적으로 적용하여 Non-terminal symbol을 확장함으로써 얻음

- 유도 트리 : 유도 경로를 추상화 시켜 표현한 것

- 좌측 유도 : 가장 왼쪽에 있는 Non-terminal symbol 먼저 대치

- 우측 유도 : 가장 오른쪽에 있는 Non-terminal symbol 먼저 대치

- 두 경우의 유도 트리는 같다.

 

#문법에서는 -> 를 사용하고 유도에서는 => 를 사용한다!!!#

 

모호성 Ambiguity

-  문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도 트리를 갖는다면 문법 G는 모호하다.

 

모호성 해결

1. 연산자 우선순위 도입

2. 결합 법칙 도입

 

구문 분석 방법

구문 분석 = Parse

- 주어진 문자열이 정의된 문법에 의해 생성될 수 있는지의 여부를 결정하는 과정

- 유도가 되는지 보면된다.

- 파스 트리 : 문장 구조를 나타내는 트리. 문법을 나타내는 생성 규칙을 적용한 유도 트리와 같은 모양

                 루트 노드 : 정의된 문법의 start symbol

                 중간 노드 : 각 생성 규칙의 좌측 non-terminal symbol

                 단말 노드 : 주어진 문자열을 생성하는 terminal symbol

- Top-down 방식 : 루트 노드로부터 시작하여 단말 노드를 생성하며 확인. 

  좌측 유도와 같은 순서의 생성 규칙 적용

  좌파스 : 좌측 유도 중 적용된 생성 규칙들의 리스트

 

- Bottom-up 방식 : 단말 노드로부터 루트 노드를 향하여 위로 생성하며 확인.

  우측 유도의 역순의 생성 규칙 적용과 같다.

  우파스 : 우측 유도 중 적용된 생성 규칙들의 리스트의 역순