Tuuna Computer Science

BFS 방식 하나의 Start NonTerminal Symbol에서 한번의 유도과정을 거치고 token stream과 일치할 시 종료 그렇지 않으면 유도된 과정을 worklist에 추가하고 제일 앞을 꺼냄. 예시를 보자 grammr이 아래와 같이 있을 때 E→T E→T+E T→int T→(E) worklist → E 를 먼저 넣는다. 그리고 E를 꺼내온다. Start Symbol E는 T와 T+E로 유도가 가능하다. 이를 worklist에 넣는다. worklist→T→T+E 그리고 T를 꺼낸다. T는 int와 (E)로 유도가 가능하다. 이를 worklist에 넣는다. worklist → T+E → int → (E) T+E를 꺼낸다. T+E는 int+E, (E)+E, T+T, T+T+E로 유도가 가능하다...

[해결] 수정 계획 : 아래 grammar 실패작 곧 정상적인 grammar 들고올 예정 기존 마크다운은 #, ##, ###와 >, >>, >>> 등등의 grammar을 제공한다. 이번에는 이러한 grammar을 제쳐두고 새로운 grammar을 제시할 생각이다. #,##,###와 같은 Header은 H1->{"문자열"}, H2->{"문자열"}로 변경할 것이고 >, >>와 같은 Quote는 Quote->{"인용구"}로 Link와 Image는 Link->{"이름","링크 주소", "툴팁"}의 형태로 제공될 예정이다. 아래는 grammar에 대한 CFG이다. mddoc : paragraphs opt_terms ; paragraphs : /* None */ | paragraph | paragraphs terms..

[주의] 의역과 직역을 통한 해석 + 지식수준으로 인해 정확성이 떨어질 수 있음 Regular Expression and Nondeterministic Finite Automata 단어를 인식하는 것에는 regular expression이 존재하지만 nondeterministic nature한 특성 때문에 real machines에 적용하기에는 아직 거리가 있다. 예를 들어 ((x, y) | (x, z)) 라는 regular expression이 존재한다고 할 때 x라는 문자를 인식하고 다음 콤마(,) 문자를 인식하고 나서 다음 어떤 문자를 인식해야 할지 결정짓지 못하기 때문이다. 즉, 위 식은 x 뒤에 문자열을 입력하여 입력을 받아 들일 수 있는 방법은 2가지가 되기 때문이다. , ⇨ y ⬀ x ⬂ ,..

FIRST를 쓰는 이유 S -> cAd A -> bc | a input : cad 가 있을 떄 c를 읽고 다음 a를 읽을 때 논터미널 A는 bc또는 a로 구분된다. 하지만 이미 A에 대한 FISRT를 구해놨기 때문에 A의 FIRST인 a를 알고 있기때문에 bc로 한번 안빠지고 a로 바로 determine할 수 있다. 체킹 시점을 줄일 수 있다. 즉, 특정 Non Terminal Symbol이 어떤 Production을 생성시킬 수 있는지 알 수 있다면 BackTracking없이 바로 갈 수 있다. Follow가 필요한 이유 일단 아래 생성규칙을보자. S ->aAb A -> a | input : ab 가 있을 때 S -> aAb로 a를 일치시킨다. => (aAb, ab) => (Ab, b) 여기서 Non ..

LR(0) Isn’t Good Enough LR(0) is the simplest technique in the LR family. Although that makes it the easiest to learn, these parsers are too weak to be of practical use for anything but a very limited set of grammars. The examples given at the end of the LR(0) handout show how even small additions to an LR(0) grammar can introduce conflicts that make it no longer LR(0). The fundamental limitatio..

컴파일러가 기계어 코드를 만들어 내기까지의 단계에는 Lexical Analysis, Syntax Analysis, Semantic Analysis, IR Generation, IR Optimization, Code Generation, Optimization이 있다. Optimization 단계의 경우 최종적으로 만들어낸 기계어 코드를 바탕으로 최적화를 시키는데 예를 들어, Control Flow Analysis과 Data Flow Analysis을 바탕으로 최적화를 진행시킨다. 여기서 Data Flow Analysis의 경우 내가 잘 모르기때문에 일단 패스할 예정 (공부해서 추가할거임) Control Flow Analysis의 경우 프로그램의 제어흐름을 분석하는 것을 의미한다. 그럼 컴파일러는 Cont..