Book 61

4. Lexical and Syntax Analysis

4.1 Introduction 컴파일러 설계의 필수 단계컴파일러를 제대로 배우려면 한 학기 정도의 집중적인 설계·구현 경험이 필요하다.그 과정의 첫 파트가 어휘 분석(lexical analysis)·구문 분석(syntax analysis)이다.특히 구문 분석기(parser)는 컴파일러의 “심장” 역할을 하며, 이후 단계인 의미 분석기(semantic analyzer)와 중간 코드 생성기가 파서의 결과에 의존한다.⇒ 핵심 개념: 컴파일 파이프라인에서 파서가 전체 흐름을 주도한다.프로그래밍 언어 교재에서 컴파일러 단원을 다루는 이유문법(grammar)의 자연스러운 응용: 3장에서 배운 BNF 등 문법 이론을 실제로 쓰는 가장 직접적인 예시가 파서 설계이다.응용 범위의 확장성: 컴파일러를 쓰지 않는 프로그램(..

Chapter3: Describing Syntax and Semantics

3.1 Introduction (서론) 프로그래밍 언어를 간결하면서도 이해하기 쉽게 기술하는 작업은 매우 어렵지만, 그 언어의 성공을 위해 반드시 필요하다.과거 ALGOL 60과 ALGOL 68이라는 언어는 매우 간결하고 형식적인 설명을 사용했으나, 당시 사람들에게 익숙하지 않은 새로운 표기법(notation) 때문에 오히려 이해하기가 어려웠고 그 결과 두 언어 모두 널리 받아들여지지 못했다. 반대로, 어떤 언어는 너무 간략하고 비형식적인 설명 때문에 조금씩 다른 여러 방언(dialect)이 생겨 혼란이 발생하기도 했다. 언어를 설명하는 과정에서 중요한 어려움 중 하나는 이 언어 설명을 읽고 이해해야 하는 사람들이 매우 다양하다는 점이다. • 초기 평가자(initial evaluators)언어의 초기 평..

CH8. More Computational Complexity: The Searching Problem

8.1 Lower Bounds for Searching Only by Comparisons of Keys 이 섹션에서는 키 비교만을 사용하여 배열에서 특정 키를 검색할 때 소모되는 최악의 경우 비교 횟수의 하한을 다룹니다.특히, Binary Search와 Sequential Search의 의사결정 트리(Decision Tree)를 사용하여 검색 과정의 효율성을 분석합니다. 의사결정 트리 (Decision Tree) • 정의:의사결정 트리는 키 를 배열에서 검색하는 과정에서 발생하는 모든 비교를 나타냅니다. • 각 내부 노드는 키 비교를 나타냅니다. • 각 리프 노드는 검색 결과를 나타냅니다 (성공적으로 검색된 위치 또는 실패). • 예시: • Figure 8.1: 정렬된 배열에서 이진 탐색(Binary ..

CH7. Introduction to Computational Complexity: The Sorting Problem

7.1 Computational Complexity 계산 복잡도란?  • **계산 복잡도(Computational Complexity)**는 특정 문제를 해결할 수 있는 모든 가능한 알고리즘의 효율성을 분석하는 학문이다. • 주로 다음 두 가지를 분석한다:  1. 시간 복잡도(Time Complexity): 알고리즘이 실행되는 데 필요한 시간. 2. 공간 복잡도(Space Complexity): 알고리즘이 사용하는 메모리 양. 여기서 중요한 것은 알고리즘을 개별적으로 분석하는 것이 아니라 문제 자체의 본질적인 복잡도를 분석한다는 점이다.예를 들어, 행렬 곱셈 문제에서는 최선의 알고리즘이라도 Θ(n²) 이상의 시간 복잡도를 가지며,이를 문제의 **하한(Lower Bound)**이라고 한다. 정렬 문제의 계..

6.4 Switched Local Area Networks

스위치 기반 LAN은 데이터 링크 계층에서 작동하며, IP 주소 대신 **링크 계층 주소(MAC 주소)**를 사용하여 데이터를 전달한다. 그림 6.15: 캠퍼스 네트워크 예시 이 그림은 스위치 네 개로 연결된 캠퍼스 네트워크의 예를 보여준다. 각 학과(예: 전기공학, 컴퓨터 공학 등)와 서버, 라우터가 스위치를 통해 연결되어 있다. 1. 네트워크 구성 요소: • 스위치: 데이터가 효율적으로 전달될 수 있도록 트래픽을 관리. • 서버: 메일 서버, 웹 서버 등. • 라우터: 외부 인터넷과 연결. 2. 연결 속도: • 서버와 라우터는 스위치와 1Gbps로 연결. • 학과 건물은 스위치와 100Mbps로 연결. • 학과 내부 네트워크는 혼합 속도(10Mbps~1Gbps)로 운영. 스위치가 연결된 각 네트워크는..

6.3 Multiple Access Links And Protocols

Point-to-Point Links  • 하나의 송신 노드와 하나의 수신 노드로 구성된 링크이다. • PPP(Point-to-Point Protocol)와 HDLC(High-Level Data Link Control)과 같은 프로토콜이 이 범주에 속한다. Broadcast Links  • 여러 송수신 노드가 단일 링크를 공유하며 데이터를 주고받는 구조이다. • 이 링크에서 송신된 데이터는 모든 연결된 노드에 전송된다. • Ethernet과 Wireless LAN(Wi-Fi)이 대표적인 Broadcast Links의 예이다. Figure 6.8은 다양한 Broadcast Links의 예를 보여준다. 이 그림은 Shared Wire(케이블 네트워크), Shared Wireless(Wi-Fi), Satell..

6.2 Error-Detection and Correction Techniques

오류 검출 및 수정의 개요 링크 계층은 데이터 전송 과정에서 발생할 수 있는 비트 수준의 오류를 검출하고 수정하는 기능을 제공한다. 이는 데이터의 무결성을 보장하기 위해 매우 중요한 과정이다. 이 섹션에서는 오류를 검출하고 수정하는 몇 가지 기법과, 이러한 기법이 실질적으로 어떻게 동작하는지 살펴본다. Figure 6.3: 오류 검출 및 수정 시나리오설명  • 그림은 송신 노드와 수신 노드 간의 데이터 전송 시 발생할 수 있는 오류 검출 과정을 보여준다.  1. 송신 노드에서 원래 데이터 D에 **오류 검출 및 수정 코드(EDC)**를 추가한다. 이 데이터와 EDC는 프레임에 포함되어 전송된다. 2. 전송 중 비트 오류가 발생하여 수신 노드에서 데이터 **D’**와 EDC’**로 수신될 수 있다. 3. ..

CH6.The Link Layer and LANs(6.1 Introduction od the Link Layer)

링크 계층의 주요 개념 1. Node와 Link의 정의  • Node는 링크 계층 프로토콜을 실행하는 모든 장치를 의미한다. 예를 들어 호스트, 라우터, 스위치, WiFi 액세스 포인트 등이 Node에 해당한다. • Link는 인접 노드 간의 통신 경로를 의미한다. 데이터그램이 소스에서 목적지로 이동하기 위해 여러 링크를 거쳐야 한다. 2. 링크 계층의 역할 링크 계층은 데이터그램을 **링크 계층 프레임(frame)**으로 캡슐화하고 각 링크를 통해 전송하는 역할을 한다.이를 비유적으로 설명하면, 여행자가 여러 교통 수단(자동차, 비행기, 기차)을 이용하여 목적지에 도달하는 과정과 유사하다.이 비유에서 각 교통 수단은 링크 계층 프로토콜에 해당하고, 여행 경로를 계획하는 여행사는 라우팅 프로토콜과 같다...

5.8 Summary

SECTION 5.1R1. What is meant by a control plane that is based on per-router control?In such cases, when we say the network control and data planes are implemented “monolithically,” what do we mean?R1. Per-router control plane이란?해설:각 라우터가 독립적으로 라우팅 정보를 계산하고 업데이트를 수행하는 방식입니다. “Monolithically”는 제어 평면과 데이터 평면이 단일 장치 안에서 결합되어 있다는 의미입니다. R2. What is meant by a control plane that is based on logically ..

5.7 Network Management and SNMP,NETCONF/YANG

네트워크 관리의 목적은 대규모 네트워크가 안정적이고 효율적으로 운영될 수 있도록 장치와 서비스를 제어, 구성, 모니터링하는 것이다. 네트워크 관리의 정의 네트워크 관리는 다음을 포함한다: • 하드웨어 및 소프트웨어 배포: 네트워크 장치를 추가하거나 교체. • 통합 및 조정: 네트워크 자원 간의 상호작용 최적화. • 모니터링 및 제어: 네트워크 상태를 감시하고 필요한 경우 문제를 해결. • QoS 보장: 서비스 품질 유지. 5.7.1 네트워크 관리 프레임워크네트워크 관리 프레임워크는 여러 주요 구성 요소로 이루어져 있다 (Figure 5.20 참조): 1. 관리 서버(Managing Server)  • 네트워크 운영 센터(NOC)에 위치. • 데이터를 수집, 처리, 분석하며, 명령을 내려 네트워크 장치를 ..