[컴파일러설계] 5. Syntax Analysis - 2

Top-Down Parsing input string에 대해 parse tree를 생성하는 한 가지 방법은 Top-down parsing이다. 이는 input string에 대한 leftmost derivation을 찾는 과정으로 볼 수 있다. top-down parsing에서는 start symbol부터 production rule을 적용하며 token string을 왼쪽부터 생성하게 된다.(즉, 왼쪽부터 parsed part가 하나씩 늘어난다.)   Recursive Descent Parsing Recursive descent parsing에서는 non-terminal을 본다면 production rule을 순차적으로 적용한다. 그리고 만약 틀렸다면 backtraking을 허용한다. 모두 순회하였는데..

• format_list_bulleted CS/컴파일러설계
• · 2024. 10. 24.
• textsms

[컴파일러설계] 4. Syntax Analysis - 1

Syntax Analysis란?  컴파일러의 두 번째 단계는 syntax analysis 혹은 parsing이라 불린다. parser는 lexical analyzer가 생성한 token의 abstract symbol을 사용하여 token 스트림의 문법적 구조를 나타내는 parse tree를 생성한다. tree로 표현할 수 없다면 그 프로그램은 invalid하다고 본다. tree를 표현하기 위해선 syntex tree가 주로 이용되는데, 이 tree에서 각 내부 노드는 하나의 연산을 나타내고, 그 자식 노드들은 연산의 인자를 나타낸다.    Specification, Recognition, and Automation in Parser  syntax analysis 단계에서는 token을 특정 tree 형태..

• format_list_bulleted CS/컴파일러설계
• · 2024. 10. 23.
• textsms

[컴파일러설계] 3. Lexical Analysis - 2

Thompson's construction(RE → NFA) Thompson's construction algorithm은 자동으로 RE를 NFA로 변환한다. 이 알고리즘은 RE를 가장 단순한 요소로 나누고, 그 요소에 해당하는 NFA를 만들어 결합해 나감으로써 최종적인 NFA를 생성한다. 결합은 ε 전이를 통해 이루어질 수 있다. 저번 글에서 RE를 정의하기 위한 5가지 규칙(a, ε, concat, alteration, closure)에 대해 알아보았다. 이에 대한 NFA는 아래와 같다.  ExerciseQ. (+|-)?d+에 대해 NFA를 생성하라. A. (+|-)?, d, d*에 대해 NFA를 만들고 ε로 이어준다. 더보기  Subset construction(NFA → DFA) NFA를 만들었으..

• format_list_bulleted CS/컴파일러설계
• · 2024. 10. 1.
• textsms

[컴파일러설계] 2. Lexical Analysis - 1

Lexical Analysis란? 컴파일러의 첫 번째 단계는 lexical analysis 혹은 scanning이라 불린다. lexical analyzer는 소스 코드의 문자 스트림을 읽고 문자를 의미 있는 시퀀스인 lexemes로 그룹화한다. 각 lexeme에 대하여, lexical analyzer는 다음 단계인 syntax analysis로 전달될 token-name, attribute-value> 형식의 token을 output으로 생성하게 된다. 여기서 token-name은 syntax analysis에서 사용될 abstract symbol이며, attribute-value는 이 token이 코드 내에서 구체적으로 무엇을 나타내는지를 저장하는 정보이다. 즉, symbol table에 있는 실제 값..

• format_list_bulleted CS/컴파일러설계
• · 2024. 9. 28.
• textsms

[컴파일러설계] 1. Compiler Construction

컴파일러란? 컴파일러(compiler)는 특정 프로그래밍 언어로 쓰여 있는 코드를 컴퓨터에서 실행 가능한 형태로 번역해주는 프로그램을 의미한다. int a = 3; int b = 7; int c = a - b; 와 같은 코드를 바로 실행할 수는 없으며, 컴파일러를 통해 기계어로 번역되고 나서야 컴퓨터가 이해할 수 있다. 즉, 컴파일러는 소프트웨어와 하드웨어의 갭을 줄여주는 역할을 한다고 볼 수 있다.   Compiler vs Interpreter 번역을 하는 방식에는 컴파일러와 인터프리터, 이렇게 두 가지가 있다.  컴파일러 : 프로그램 전체를 스캔하고, 실행 가능한 형태(object file)로 변경한다. 그 후 input 데이터를 받아 output 데이터를 산출할 수 있다. 대표적인 언어로는 C, C..

• format_list_bulleted CS/컴파일러설계
• · 2024. 9. 26.
• textsms