건빵의 블로그

출처 : JFlex 매뉴얼 Java Cup을 실행하여 xxx.cup을 java파일로 변환한다. 이 단계에서 symbol table이 생성된다. JFlex를 이용하여 xxx.flex를 java파일로 변환한다. 두 단계에서 만들어진 클래스를 이용하는 메인 클래스를 만들고 컴파일 한다. 이 단계만으로 컴파일러의 Front-end 실행이 가능하다.

모든 data type의 design issue 1. variable의 reference syntax는? 2. operation은? Character String Types Implementation - Static Length - Limited dynamic length : run time descriptor 필요 - Dynamic Length Ordinal Types(user defined) : possible value의 range를 positive integer의 set과 쉽게 연관시킴 1. Enumeration type : 심볼릭 상수로 값 나열 2. Subrange Type : ordinal type의 순서있는 연속된 subsequence Array : homogeneous data eleme..

keyword : 특정한 context에서만 특별한 word reserved word : user-defined name으로 사용될 수 없는 special word Variable을 나타내는 주요 특징 6가지 : name, address, value, type, lifetime, scope Address : variable이 연관된 주소 - 두개의 variable name이 같은 메모리 위치를 가리키는 경우, aliase라고 함 Type : variable의 값의 range와 그 variable에 적용되는 set of operation을 결정한다. Value : variable이 연관된 위치의 값 * binding : attribute와 entity, 또는 operation과 symbol의 associa..

Chapter 3 Syntax - expression, statement, 프로그램 유닛의 form 또는 structure Semantics - 위의 것의 meaning Context Free Grammars - natural language의 syntax를 나타내는 데 사용되는 Language Generator Backus Normal Form(BNF) - CFG를 나타내는데 사용. - CFG와 equvialent Derivation : start symbol에서 시작하여 sentence(terminal symbol)로 끝나는 반복적인 rule의 적용 - leftmost derivation : 각 sentential form에서 가장 왼쪽의 nonterminal을 expand 하는 것 Parse tre..

출처 : http://protospv.tistory.com/29 Knuth-Morris-Pratt 알고리즘, 곧 KMP 알고리즘입니다. 지금까지 알려진 중 가장 최저의 시간복잡도가 필요한, 즉 가장 최신의 알고리즘입니다. 일단, 짚고 넘어가자면 KMP 알고리즘의 평균 수행 속도는 O(N + K)(N과 K는 비교할 문자열의 길이)입니다. 매칭을 하려면 최소한 원문 문자열과 검색 문자열을 한번씩은 읽어봐야 할 테니, 가장 최적의 복잡도인 것입니다(사실 소스로 구현하기에 따라 약간씩 커질수도 있습니다). 이름에서 알 수 있듯이 Knuth, Morris, Pratt 세 사람이 완성한 알고리즘입니다. 기존의 문차열 매칭 방식인 '오토마타' 의 문제점을 극복하기 위해 만들어졌고, 그 결과 뛰어난 시/공간 복잡도를 ..

동기화에서의 전통적 문제. (1) Bounded Buffer Problem (2) Readers and Writers Problem (3) Dining Philosophers Problem (1) Bounded Buffer Problem Producer-Consumer Process로 Producer는 버퍼에 데이터를 넣고 Consumer는 읽어온다. 동기화를 사용하지 않을 경우 한번씩 실행되는 것을 보장할 수 없으므로 버퍼가 넘칠 수 있다. 동기화 메커니즘을 이용해 해결 가능하다. semaphore mutex : 값 1 semaphore full : 값 0 semaphore empty : 값 N -Producer Process do{ // produce wait(empty); wait(mutex); /..

Race Condition : 여러 프로세스가 같은 데이터에 동시에 접근하며 조작하고 프로세스의 실행의 결과가 프로세스 실행 순서에 의존하는 상황 Critical Section : 공유 자원에 여러 프로세스가 접근하여 race condition을 야기할 수 있는 공유 데이터를 접근하는 코드의 일부분 Process Synchronization : 레이스 컨디션의 발생을 막기 위한 방법 Synchronization의 Desired Solution(완벽한 동기화를 위한 세 가지 조건) -Mutual Exclusion : 오직 프로세스 1개만 CS에 접근 가능하다. -Progress : CS에 있는 프로세스가 없고 한 프로세스만 CS에 진입하려 한다면 바로 진입 -Bounded Waiting : 유한시간 대기 ..

출처 : internet512.chonbuk.ac.kr/.../AVL/avl.html 높이 균형 트리(Hieght-Balanced Tree)라고도 부르며, 탐색 시간을 줄이기 위해서 좌,우측 부 트리의 높이가 1 이상 차이가 나지 않도록 균형을 유지해 주는 이진 트리로 동적 탐색 트리(Dynamic Search Tree)이다. 탐색시 비교 횟수가 작고, 노드 삽입시 트리의 균형이 크게 변하지 않는 성질을 만족하는 트리이다. T가 좌측과 우측 부트리인 TL과 TR을 가진 이진 트리라 할 때 아래의 조건을 만족하면 T는 높이가 균형을 이룬다. TL과 TR의 높이가 균형을 이루며 |HL-HR| ≤ 1 (HL, HR은 TL과 TR의 높이) AVL 트리 AVL 트리가 아닌 경우 높이 균형 트리를 구성하는데 있어서..

10.2 Access Methods 파일 정보 접근 방법 10.2.1 Sequential Access 순서대로 읽는다. 10.2.2 Direct Access 파일은 logical records로 이루어져 있고 번호를 이용해 프로그램을 빠르게 읽고 쓸수 있도록 한다. 순서에 제한이 없다. 이 방법은 많은 양의 즉각적인 접근에 유용하다.(예> db) 이 방법에서는 파일 오퍼레이션에 block number가 파라미터로 들어가야 한다. 일반적으로 os에서 사용자에게 제공되는 block number는 relative block number이다. 파일의 시작에서부터 상대적 위치이다. 모든 시스템이 sequential과 direct access를 허용하는 것은 아니다. 10.2.3 Other Access Method..

9.7.1 Basic Mechanism 파일 메모리 맵핑은 디스크 블락을 메모리의 페이지에 매핑시킨다. 파일에 대한 read write는 일반적인 메모리 접근과 같이 다뤄지기 때문에 파일 접근과 사용을 간략화시킬 수 있다. 파일 업데이트는 modify되었는지 체크하여 os가 주기적으로 점검할 수 있다. 여러 프로세스에서 같은 파일을 접근한다면 data sharing이 가능하며 각 페이지가 frame에 연결 될 수 있다. 만약 수정이 일어나면 cow 메커니즘이 적용되어서 새로운 프레임을 할당받는다. Memory mapping file을 공유하는 것은 공유 메모리와 비슷하지만 다른 시스템콜과 같은것을 사용한다. 하지만 어떤 os에서는 shared memory가 memory mapping file로 구현된다...