Parser 역할

scanner(lexical analysis)를 통해 소스 프로그램이 토큰 단위로 나뉘어져 symbol table에 관리된다. 이제 parser는 각 토큰을 가지고 syntax tree를 만든다. syntax는 문장의 형태와 관련있다.

프로그램 구문을 검사하는 역할을 한다. 검사를 하고 syntax error가 있다면 보고하고 handling까지 한다.

에러의 종류는 뭐가 있을까?

• lexical errors: id, 키워드나 연산자의 미스스펠링
• syntax errors: 세미콜론이나 괄호의 잘못된 위치, switch없는 case
• semantic errors: 의미상 문제. 타입 미스매치
• logical errors: if문 안에 =과 == 사용, 사실 이 부분의 에러는 발견하기 어려움

에러의 종류는 위와 같고 파서는 syntax error를 찾아내고 handling한다. 정확하게 문제를 찾아내고 수정해주는 일은 간결하고 시간을 크게 들이지 않아야 한다.

Context free grammar

소개

렉서에 대해 알아볼 때 DFA를 통과하는 필요충분 조건의 언어를 regular language라고 했다. 파서에서도 프로그래밍 언어의 syntax 구조를 쉽게 파악할 수 있는 문법 정의가 필요하다.

그게 바로 CFG(Context Free Grammar)이다. CFG역시 BNF(Backus Naur Form)을 기저로 한다. 그리고 regular language와는 다음과 같은 관계를 가진다.

Regular language $\subset$ Context Free Grammar

표현방법

$G=(V,T,S,P)$

다음과 같이 표현하고 V는 variable, T는 terminal, S는 start symbol, P는 production rule이다. regular grammar와 별다른 차이는 없다. 다만 나타낼 수 있는 규칙에 있어 차이가 있다.

Regular grammar

$A\rarr Bx\ \vert \ x$ or $A\rarr xB\ \vert \ x$
(where A, B $\in$ V, x $\in$ $T^*$)

CFG

$A\rarr \alpha$
(where A $\in$ V, $\alpha \in$ $\{V\cup T\}^*$)

보면 알겠지만 regular grammar는 non terminal인 variable이 가장 오른쪽이나 가장 왼쪽에만 등장할 수 있다. 하지만 CFG는 variable의 위치가 중간이어도 상관이 없다.

참고로 앞으로 사용하는 영어 대문자는 vairable, 영어 소문자는 terminal을 의미한다.

Derivations

Production rule을 통해 만들어낼 수 있는, 유도할 수 있는 형태들이다.

Sentential forms

문장의 형태를 의미하면 start symbol인 S는 sentential form이라 한다. 반대로 터미널로만 이루어진 형태를 sentence라고 한다.

Context free languages

CFG를 G라고 했을 때 이 문법을 따르는 언어 L(G)를 context free language라고 표현한다. string의 모음인데 CFG를 통해 터미널로만 나타낼 수 있는 모든 값의 집합이다.