Programming Syntax 2

프로그래밍을 명시할 때는 specification과 implementation을 담아내야 한다.

specification에는 defenition, syntax, semantics를 명시해야 한다

implementation은 실행 방법에 대한 가이드라인(자바는 컴파일이 아닌 VM 기반에서)을 명시한다

 

syntax(formal grammer) : 프로그램의 구조와 형태

- token, expression, statement, Digit ...

 

문법의 작동방식

parse tree를 설계하여 문법의 규칙을 정한다

<NP>: 명사, <V> : 동사,  <S>:sentence

=> <S> -> <NP> <V> <NP>

 

Context Free Grammer (CFG) 문맥자유문법

왼쪽에 심볼 하나, 오른쪽에 심볼 하나 이상

terminal symbol = token, non-terminal (확장 가능) -> 이 둘을 잘 구분할 줄 알아야 함

start symbol 등 각 심볼이 무엇인지 구분할 수 있어야 함

+) <Empty> : non-terminal Symbol

BNF

(extended) backus-naur form : 세계 최초의 프언인 포트란 만든 사람

좌우는 같은 내용

빨간색 밑줄은 token

Parse Tree

parsing == parse tree 그리기

위쪽부터 순서 대로 3,2,(3,6),(4,5) 규칙을 적용

각 항목을 node라고 함

leaf 노드부터 위로 올라가면서 문법이 해석된다. 그래서 leaf 노드에는 항상 terminal symbol이어야 한다

(오른쪽 창은 파이썬은 nltk에서 nltk.app.rdparser()를 실행하면 나옴)

(그러니까 항상 위쪽에서는 선을 길게 쭉쭉 그리면서 시작합시다. 아니면 leaf node부터 명시하고 올라가던가)

문제) 아래 4개의 식을 parse tree로 표현해보자

 

- a*b+c

- (a+b)

- (a+(b))

- a*(b+c)*c

문법 생성하자

Divde and Quanquer

float a;
boolean a,b,c;
int a=1, b, c=1+2;

여러 개를 나열하여 적어야 할 때는 재귀적인 표현을 사용하자

Structure : Lexical, Phrase

Lexical : 텍스트 파일을 토큰으로 나누는 법

Phrase : 토큰의 나열로 프로그램이 지어지는 방법

 

초창기에는 이 둘을 섞어 쓰기도 함

<white-space>까지 억지로 쓰기도...

 

이제는 lexical 스타일로 넘어가면서

토큰에 대한 정의도 이뤄진다 (separate grammar)

이렇게 각각 나눠서 정의함

이들은 분리되어 컴파일러를 통과한다

- scanner은 입력 파일을 읽어서 토큰 단위로 나눈다. 공백 및 주석 삭제

- parser : parse tree를 생성하여 일련의 과정을 거친다.

 

Other Grammar forms

 

- BNF variation

- EBNF variation

Anything that extends BNF this way is called an Extended BNF: EBNF

- Syntax diagrams (railroad diagram)

Start with an EBNF grammar

 "chain of boxes (for nonterminals)" and "ovals (for terminals)"

[ ]는 그 안의 내용을 bypass할 수 있음을 의미

 

Loop & Branching

 

자연언어처리에서는 문법을 (formal language and automata)

소문자는 토큰, 대문자는 non-terminal, empty는 집합포함글자로 표현함