프로그래밍/Compiler8

• [컴파일러] 3-1. 구문분석기 구조 구문분석이란 어휘분석기 단계에서의 output인 Token을 가지고 문법 구조를 해석하여 키워드, 식별자, 연산자 등이 유효한 구조를 형성하였는가를 확인하고, 올바르다면 구문 분석 트리를 출력하고, 올바르지 않다면 Error를 출력한다 파서 동작방식 하향식 파싱(Top Down parsing) 최상위 노드(Root 또는 Start Symbol)에서 말단 노드(Leaves 또는 단위 String)까지 파싱하는 방법 RD Parser(recursive descent parser), predictive parser 등이 있다. 상향식 파싱(Bottom Up parsing) 말단 노드(Leaves)를 결합하여 최상위 노드(Root) 까지 파싱 precedence parser, shift-reduce parser.. 프로그래밍/Compiler 2024. 4. 6.

• 

  [컴파일러] 2.5. Flex 사용하기 이전 단계에서 어휘 분석(토큰, 오토마타, 어휘분석 이론)에 대해 얘기를 하였는데 어휘분석기를 생성하는 스캐닝 도구(openSource) Flex를 사용해보자. Flex는 특정 패턴을 정의하면, 각 패턴에 해당하는 토큰을 생성해준다. 이후 Flex를 통한 결과물로 구문 분석, 언어 처리를 할 수 있다. Flex 구문 %option // flex문법의 옵션을 설정하는 부분 %{ /* Flex에 필요한 라이브러리, C코드 등을 정의 */ %} /* (정규식)규칙 정의 */ %% /* 매칭된 패턴이 있을 경우 C코드를 정의 */ %% Flex의 특수 변수& 함수 yytext - 매칭된 패턴의 문자열 yyleng - yytext의 길이 yylval - 토큰의 값을 반환 yylex() - 매칭된 패턴의 토큰을 반.. 프로그래밍/Compiler 2024. 3. 1.

• 

  [컴파일러] 2.4. 유한 오토마타 유한 오토마타란 어휘분석기로 바꾸는 방법을 고찰한 형식론으로 단순히 각 입력에 대해 "yes" or "no"로 대답한다. 유한 오토마타는 다음 다섯 가지의 요소로 구성된다. 1. 상태(State) 오토마타가 가질 수 있는 상태 집합 2. 입력 알파벳(Input Alphabet) 입력 문자의 집합으로 빈 스트링은 제외한다. 3. 전이함수(Transition Function) 상태 및 입력에 대한 다음 상태를 결정 4. 초기 상태(Initial State) 또는 시작 상태(Start State) 오토마타가 시작하는 상태로 하나여야 한다. 5. 수락 상태(Accepting State) 또는 종료 상태(Final State) 입력 문자열을 수락하는 상태의 집합 또한 전이도와 매우 유사한데, 유한 오토마타는 추상.. 프로그래밍/Compiler 2024. 2. 26.

• 

  [컴파일러] 2.3. 토큰의 인식 앞서 정규식을사용하여 패턴을 표현하는 방법을 배웠는데, 이번에는 입력 스트링에 대한 접두사를 찾는 코드를 확인한다. 먼저 토큰을 위한 패턴은 아래와 같다. digit [0-9] digits digit+ number digits (. digits)? 9E[+-]? digits)? letter [A-Za-z] id letter (letter | digit)* if if else else relop | = | = | 이중 number와 relop를 예제로 토큰 인식하는 방법을 확인한다. 어휘 분석기 구성의 중간단계로 먼저 패턴을 "전이도" (Transition Diagram) 라 불리는 정형화된 순서로 변환해본다. 전이도란 언어의 문법을 나타내는 데 사용되는 그래프 또는 다이어그램을 의미하는데 그래.. 프로그래밍/Compiler 2024. 2. 24.

• 

  [컴파일러] 2.2. 토큰의 명세 정규식이란 문자의 패턴을 명시하기 위한 형식언어이다. 어휘분석기 생성기에서 사용되며 이후 정규식을 특정 토큰의 인식을 수행하는 오토마타로 변환함으로써 어휘분석기를 구성하는 방법을 진행할텐데, 정규식 개념이 필요하다. 스트링에 관한 용어 용어 설명 예제 접두사(prefix) 스트링의 끝으로부터 0개 이상의 기호를 제거하여 얻어지는 스트링이다 "ban", "banana", ""는 banana의 접두사이다 접미사(suffix) 스트링의 앞에서부터 0개 이상의 기호를 제거하여 얻어지는 스트링이다 "nana", "banana", ""는 banana의 접미사이다 부분스트링(substring) 스트링의 접두사나 접미사를 제거하여 얻어지는 스트링이다 "nan", banana", ""는 banana의 부분스트링이다 진(.. 프로그래밍/Compiler 2024. 2. 20.

• [컴파일러] 2-1. 어휘 분석 역할 2-1. 어휘 분석 역할 어휘분석을 논의할 때 토큰, 패턴, 어휘항목 3가지 용어를 중점으로 사용한다. 토큰 토큰 이름과 선택적인 속성값으로 구성되는 쌍이다. 토큰 이름은 어휘 단위(키워드 또는 식별자)를 나타내는 추상기호 ex) 토큰 어휘 단위 예제 if if id pi, score(variable name) number 0, 1, 3.14 comparision ==, !=, 프로그래밍/Compiler 2024. 2. 17.

• 

  [컴파일러] 1-2. 컴퓨터의 구조 1-2. 컴파일러의 구조 컴파일러를 원시프로그램에서 목표프로그램으로 변환한다고 하였는데, 좀 더 자세히 설명하면 컴파일러는 분석과 통합을 한다는 것이다. 분석(전단부): 원시 프로그램을 구성요소들로 분리하여 그 정보를 심볼 테이블이라는 데이터 구조에 저장하고, 문법적인 구조를 부과한다. 이후 이 구조를 이용하여 원시 프로그램의 중간표현을 생성한다. 이 부분에서 원시프로그램이 구문적으로 잘못 작성 되었거나 의미적으로 불합리하다는 것을 탐지하면 유익한 메시지를 제공하여야 한다. 예를 들어 단어 단위로 끊어서 void는 타입, '='문자는 Assign, ';' 문자는 문장의 끝 등을 알리는 정보이고, 이 정보를 심볼테이블에 저장한다. 또한 타입 뒤에는 이름이 명시되어야 한다는 (int sum) 구조를 부과해야.. 프로그래밍/Compiler 2024. 2. 10.

• 

  [컴파일러] 1-1. 언어처리기 해당 카테고리는 컴파일러:원리, 기법, 도구에 대한 책을 기반으로 정리하면서 쓰여나갈 것임. Compilers: Principles, Techniques, and Tools (Dragon Book) (stanford.edu) 2판으로 900 페이지가 넘는다. 컴파일러란? 인간 위주의 프로그래밍 언어를 컴퓨터가 실행할 수 있는 형태로 변역해주는 것이 컴파일러이다. 1-1. 언어처리기 컴파일러는 원시 언어(source language)를 읽어 목표 언어(target language)로 번역하는 프로그램이다. 목표 프로그램이 실행 가능한 기계어(machine-language) 프로그램이라면 사용자에 의해서 호출되어 입력을 처리하고 출력을 생산할 수 있다. 인터프리터(interpreter)는 다른 종류의 일반적.. 프로그래밍/Compiler 2024. 2. 9.