지난 포스팅에서는 코드의 구조를 검사하는 파싱(Parsing)의 개념과 그 결과물인 파스 트리(Parse Tree), 그리고 문법의 모호성 문제에 대해 다루었다. 파싱이 '문법에 맞는지 검사하는 과정'이라는 점은 이제 명확해졌다.그렇다면 다음 질문은 이것이다. "컴퓨터는 '어떻게' 이 파싱을 수행하는가?" 오늘은 파스 트리를 구축하는 두 가지 대표적인 전략, 하향식 파싱(Top-Down Parsing)과 상향식 파싱(Bottom-Up Parsing)의 원리와 특징을 알아볼 것이다.1. 하향식 파싱 (Top-Down Parsing)하향식 파싱은 이름 그대로 파스 트리의 최상단(Top)에서 시작하여 아래(Down)로 내려가는 방식이다. 즉, 문법의 시작 기호(Start Symbol)에서 출발하여 입력된 코드..
지난 시간에는 프로그래밍 언어의 규칙을 정의하는 '설계도', 즉 형식 문법(Formal Grammar)과 그 종류를 나누는 촘스키 계층에 대해 알아보았다. 설계도가 있다는 것은 알겠는데, 그렇다면 컴파일러는 이 설계도를 가지고 우리가 실제로 지은 집(작성한 코드)이 규칙에 맞게 잘 지어졌는지 어떻게 검사하는 것일까?오늘은 컴파일러가 문법을 기반으로 코드의 구조를 분석하고 이해하는 핵심 과정인 파싱(Parsing)과 그 결과물인 파스 트리(Parse Tree)에 대해 깊이 있게 탐구해 볼 것이다.1. 파싱(Parsing)이란 무엇인가? 문법 검사기파싱(Parsing) 또는 구문 분석(Syntax Analysis)은 주어진 문자열(소스 코드)이 특정 문법(Grammar)의 규칙에 따라 생성될 수 있는지를 확..
"컴파일러는 우리가 작성한 코드를 어떻게 '언어'로 인식하고, 문법이 맞았는지 틀렸는지 판단할 수 있을까?" 지난 주에는 컴파일러의 전체적인 구조를 훑어봤다. 이번에는 구문 분석(Parsing)의 이론적 뼈대가 되는 형식 문법(Formal Grammar)에 대해 알아볼 것이다. 왜 갑자기 '수학'부터 시작할까?컴파일러가 다루는 프로그래밍 언어는 우리가 사용하는 자연어와 근본적인 차이가 있다. 그것은 바로 모호성(Ambiguity)이 없다는 점이다. 모든 코드는 단 하나의 의미로만 해석되어야 한다. 이러한 엄밀함과 명확성을 보장하는 도구가 수학이며, 컴퓨터 과학자들은 프로그래밍 언어를 정의하기 위해 수학적 도구들을 도입했다. 그 첫 번째가 바로 집합(Set)이다. 집합 (Set): 원소들의 모임이며, 소..
이번 주에는 프로그래밍 언어를 다양한 관점에서 분류해보고, 우리가 작성한 코드를 컴퓨터가 이해할 수 있는 언어로 바꿔주는 '컴파일러'가 어떤 구조로 이루어져 있는지 깊이 있게 다뤄봤다. ##Part 1: Generation of Language 프로그래밍 언어는 그 특징과 등장 시기에 따라 여러 세대로 나눌 수 있다. 1세대: 기계어 (Machine Language) - 컴퓨터가 직접 이해할 수 있는 0과 1로 이루어진 언어이다. 아주 오래전에는 16진수 키보드로 직접 기계어를 입력해서 코딩하기도 했다. 2세대: 어셈블리어 (Assembly Language) - 기계어와 1:1로 대응되는 명령어로 이루어져 있어, 기계어보다는 조금 더 사람이 이해하기 쉬운 형태이다. '어셈블러'라는 번역기를 통해 기계어로..
백엔드 개발을 하다 보면 데이터베이스(DB)에 있는 정보를 클라이언트(브라우저나 앱)에게 보내줘야 할 때가 많다. 그런데 여기서 궁금증이 생겼다.DB는 데이터를 엑셀 시트처럼 '표(Table)' 형태로 가지고 있는데, 이걸 대체 어떤 모양으로 포장해서 보내줘야 클라이언트가 깔끔하게 알아들을 수 있을까? 그때 등장하는 게 바로 JSON이다. 쉽게 말해, JSON은 DB에 있는 데이터를 누가 봐도 이해하기 쉬운 '명함' 형태로 만들어주는 방식이라고 생각하면 좋다.DB에 아래와 같은 '가게 정보' 표가 있다고 상상해보자. 데이터베이스 테이블 예시 (가게 정보)idnameratinglocation1Pizza Heaven4.7Busan2Burger World4.5Seoul 여기서 'Pizza Heaven'..
정보검색 Chapter 19: Web Search Basics
1. 웹 문서의 특성과 규모웹 문서 컬렉션의 특징분산적 생성: 웹은 중앙에서 관리되는 게 아니라 전 세계 사용자들이 자유롭게 생성한다.내용 다양성: 사실과 거짓, 오래된 정보, 상반된 주장 등이 섞여 있다.언어 다양성: 전 세계 다양한 언어와 문체가 섞여 있어 언어처리(stemming 등)가 복잡해진다.구조 다양성: 비구조적(HTML), 반구조적(XML), 구조적(DB) 문서들이 존재한다.규모: 초창기(예: Altavista가 1995년에 3천만 페이지 크롤링)부터 지금까지 폭발적인 증가. 2. 웹 정보 검색 방식 검색 방식의 변화초기: 키워드 기반 검색 (Altavista, Excite 등)분류 기반: 디렉토리 기반의 Yahoo 스타일 (taxonomy 사용, 수작업 분류)과제:사용자와 편집자 간 분류..