저번에 알아봤던 탑다운 파싱에 대해 자세히 알아보자 탑다운 형식에서 만들어진 파싱 트리는 스타팅 노드에서 밑으로 내려가는데, 어휘가 서술 가능할 경우 그냥 내려가면 끝이지만, 불가능하게 노드가 끝날 경우 되는 경우를 찾기 위하여 다시 윗 노드로 올라가야 하는데 이를 백트래킹이라고 한다. 이 백트래킹은 중복되고 시간이 오래걸리기 때문에 최소화 하는 방법을 알아야 한다. S -> aAd S -> aB A -> b A -> c B -> ccd 이와 같은 식이 주어졌다고 했을 때, input : accd가 올바른 구문인지 검증을 top-down 방식으로 진행해보자 1. S -> aAd pointer : (a)ccd aAd에서, 포인터인 a가 적절한지 검사한다. 일단 첫 a가 동일하므로 a까지는 적합한 문구라고 ..

어휘 분석을 마치고 구문 분석을 이야기한다. Syntax Analysis란? - 한줄 한줄 입력된 코드가 유효한지 검사한다. - 전체를 파싱하여 트리로 만들어 낸다. - 크게 탑다운 파싱과 바텀업 파싱으로 나뉜다. Syntax 1) S -> XY 2) X -> aX 3) X -> b 4) Y -> aY 5) Y -> c Top-down Parsing 탑다운 파싱은 루트 노드부터 터미널 노드까지 파싱하는 방법이다. 파싱 순서는 1 -> 2 -> 3 -> 4 -> 5 순으로 되며, 스타트 지점인 S 부터 하나씩 풀어 나간다. Bottom-up Parsing 바텀업은 터미널 노드로 부터 루트 노드까지 파싱하는 방법이다. 파싱 순서는 3 -> 2 -> 5 -> 4 -> 1 터미널인 a b a c로 부터 non-..

Syntax analysis를 위한 코드의 표현방법으로, BNF 표현법이라고 한다. BNF는 만든 사람이 Backus-Naur Form 이라 BNF이다. 화살표를 ::=와 같이 표기하며, Formal language랑 유사하다. ::= | ::= 'a'|'b'|'c'... |'z' ::= '0'|'1'|...|'9' 이와 같이 표현된다. 하지만 반복되는 방식을 다 적어야 하는데, 이를 개선한것이 EBNF이다. ::= ',' | 를 ::= {','} 로 표기할 수 있다. formal language의 *와 같이 한번이상부터 무한대까지 나올 수 있다는 이야기이다. Syntax Diagram 이 문법을 다이어그램으로 표기하면, 터미널일 경우 동그라미, 터미널이 아닐경우 네모로 표기한다. A ::= B | C ..

어제 유도 트리를 만들면서, 사용하지 않는 터미널을 제거하는 과정이다. 사용하지 않는 production Rules 제거 Non-Terminal 중에서, Terminal 로 갈 수 있는 것들을 Terminating Non-terminal 이라고 하고, 이 Termination Non-terminal을 제외하고 모두 제거해야한다. 그리고, 존재하지만 갈 수 없는 경우의 수가 있다. 접근 가능한 터미널들을 Accessible Symbol이라고 하고 해당하지 않는건 제거해야한다. Termination Non-terminal S -> A S -> B B -> a 이와 같은 식이 있다. 여기서 termination non-terminal은, 마무리가 terminal이 되야한다는 뜻이다. S -> B -> a 이기..

유도 과정을 통해 유도 트리를 만들어보자 먼저 유도 트리를 만들기 위해서는 유도에 관한 개념을 알아야한다. Define Derivation (a + a)에서 nonterminal E는 E -> E + E | E * E | (E) | a가 될 수 있다. 따라서 E 에서 (a + a)로 도출되려면 E -> (E) -> (E +E) -> (a + E) -> (a + a)가 된다. 위는 leftmost 유도할 경우이고, rightmost에서는 반대로 E -> (E) -> (E +E) -> (E + a) -> (a + a) 가 된다. 이제 a + a * a를 윧ㅎ해보자. leftmost일 경우 E -> ( E ) -> E + E -> E + E * E 로, 맨 왼쪽 E부터 a로 바뀐다. 그렇게 되면 연산이 덧셈부..

이번엔, analyzer를 통해 정제된 데이터중 ID를 Finite Automata로 변환해 보자. ID (변수명)은 첫번째가 letter이여야 하고 그 이후에는 Digit 또는 letter이여야 한다. ID to Automata 이를 오토마타로 바꾸면, 가 된다. 식으로 나타내기 위해 편의상 letter는 l로 digit은 d로 표기하도록 하자 S = lA A = lA + dA + epsilon 이 된다. A로 묶으면 A = (l + d)A + epsilon이 되고, 정리하면 A = (l + d)* 가 된다. A를 S식에 대입하면 최종으로 S = l(l + d)* 이 된다. 해석해보면 처음엔 letter, 그 이후로는 l 또는 d가 무작위로 나올 수 있다는 뜻이다. Integer to Automata ..