Book/Concepts of Programming Language

4. Lexical and Syntax Analysis

S0LL 2025. 4. 5. 23:58

4.1 Introduction

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

프로그래밍 언어 구현 방식 3가지방식특징대표 활용

Compilation	전체 소스 → 기계어로 번역 후 실행	대규모 시스템(C/C++ 등)
Pure Interpretation	번역 없이 인터프리터가 원본 소스를 직접 실행	스크립트·내장 스크립트(JavaScript in HTML)
Hybrid Implementation	소스 → 중간 형태로 변환 후 인터프리트	Java, .NET 등 (JIT 컴파일 시 지연 컴파일형태)

세 방식 모두 어휘·구문 분석 단계를 공통적으로 사용한다는 점이 중요하다.

구문 분석기의 이론적 기반 – BNF
- 파서는 대부분 BNF(Backus–Naur Form) 같은 형식 문법에 기반한다.
- BNF 사용 이점
  1. 명확성: 사람·소프트웨어 모두 이해하기 쉬움.
  2. 직접 활용: BNF 자체가 파서 생성기의 입력이 됨.
  3. 모듈성: 문법이 모듈화되어 유지보수가 용이.
어휘 분석 vs. 구문 분석의 분리
- 어휘 분석기(lexer): 토큰 단위(식별자, 숫자 리터럴 등)처럼 소규모 요소를 처리.
- 구문 분석기(parser): 표현식·문장·프로그램 단위의 대규모 구조를 처리.
- 교재 구조: 4.2 (lexer) → 4.3–4.5 (parser) 순서로 상세 설명.
어휘 분석을 별도 모듈로 두는 3가지 이유
1. 단순성 – 렉서 기술은 파서보다 단순하므로 분리 시 파서가 작고 이해하기 쉬워진다.
2. 효율성 – 전체 컴파일 시간 중 상당 부분이 렉서에 쓰이므로, 파서와 독립적으로 최적화하기 좋다.
3. 이식성 – 렉서는 파일 입출력·버퍼링 등 플랫폼 의존 요소가 많다. 이를 분리하면 파서는 플랫폼 독립적으로 유지할 수 있다.

언어를 해석하는 과정을 인간 언어에 빗대면,
1. 어휘 분석은 문장을 단어(토큰)로 띄어쓰기 하는 단계,
2. 구문 분석은 단어들을 문법 규칙에 따라 문장 구조로 묶어 의미 단위를 파악하는 단계이다.
JIT(Just‑in‑Time) 컴파일러는 하이브리드 시스템의 단점을 보완하기 위해, “필요한 순간”에만 바이트코드→기계어 번역을 수행하여 실행 속도를 끌어올린다.

4.2 Lexical Analysis

🔹 서론 (Introduction)

Lexical analyzer의 개념

Lexical analyzer (어휘 분석기, 렉서)는 본질적으로 패턴 매칭기(pattern matcher)이다.
입력된 문자열에서 특정한 문자 패턴과 일치하는 하위 문자열(substring)을 찾는 역할을 한다.
패턴 매칭은 컴퓨팅에서 오래된 전통적인 기법이며, 초창기 Unix의 ed 편집기에서도 사용되었고 Perl, JavaScript 등의 언어에도 포함되어 있다.

🔹 Lexical Analyzer의 역할

어휘 분석기의 기능적 위치

어휘 분석기는 Syntax analyzer(구문 분석기)의 앞단(front-end)에 위치하여, 프로그램 구조의 가장 낮은 수준(lowest level)의 분석을 수행한다.
컴파일러 입장에서는 전체 프로그램이 단순히 문자(character)의 나열로 보인다.
어휘 분석기는 이 문자들을 모아서 의미 있는 그룹(lexeme)으로 구분하고, 내부적으로 코드화(token)하여 분류한다.

핵심 용어의 구분

Lexeme (렉심): 문법적으로 의미 있는 최소 단위의 문자 집합.
Token (토큰): 렉심의 분류(category)에 대한 내부적 코드.

🔹 예시를 통한 개념 이해

다음 예시를 통해 렉심과 토큰의 차이를 이해할 수 있다.

예시 코드:

result = oldsum - value / 100;

토큰과 렉심:

TokenLexeme

IDENT	result
ASSIGN_OP	=
IDENT	oldsum
SUB_OP	-
IDENT	value
DIV_OP	/
INT_LIT	100
SEMICOLON	;

위의 예시에서 "result"라는 문자열이 하나의 렉심이며, 이 렉심의 토큰은 식별자(IDENT)로 분류된다.
마찬가지로 연산자와 정수 리터럴도 각각의 렉심과 토큰으로 분류된다.

🔹 Lexical Analyzer의 동작 방식

초기에는 어휘 분석기가 프로그램 전체를 한 번에 처리하여 모든 토큰과 렉심을 미리 뽑아냈다. 그러나 현대 컴파일러는 다음과 같은 방식으로 동작한다.

어휘 분석기가 한 번 호출될 때마다 입력에서 다음 하나의 렉심만 찾아서 그에 대응하는 토큰을 구문 분석기에게 반환한다.
따라서 구문 분석기가 보는 입력은 토큰의 연속으로 구성된다.

어휘 분석기는 주석(comment)이나 공백(space)과 같이 의미 없는 문자들은 건너뛴다. 또한, 사용자 정의 식별자(user-defined identifier)는 이후의 컴파일러 단계에서 사용되는 심볼 테이블(symbol table)에 저장한다.

🔹 Lexical Analyzer 구축 방법 (3가지 접근법)

어휘 분석기를 설계하는 대표적 방법은 다음 세 가지다.

정규 표현식(regular expression)을 이용한 자동화
- 대표적 도구: Unix의 lex
- 토큰 패턴을 정의하면 소프트웨어가 자동으로 어휘 분석기를 생성해 준다.
상태 전이 다이어그램(state transition diagram)을 설계 후, 이를 코드로 구현하는 방법
상태 전이 다이어그램을 설계 후, 테이블(table-driven)로 직접 구현하는 방법

🔹 상태 다이어그램 (State Diagram)

상태 다이어그램은 어휘 분석기가 문자 입력을 처리하면서 상태를 변화시킬 때의 흐름을 시각적으로 나타낸다.

노드는 상태(state), 화살표는 문자 입력(input)을 나타낸다.
상태 다이어그램은 이론적으로 유한 오토마타(Finite Automata) 에 해당하며, 이는 정규 언어(Regular Language)를 인식하는 기계이다.

[그림 4.1] 간단한 상태 다이어그램

Letter 입력으로 시작하면 id(식별자), Digit 입력으로 시작하면 int(정수 리터럴) 상태로 전환된다.
알파벳/숫자 조합으로 식별자나 정수 리터럴을 계속 읽고, 그 외 문자는 즉시 토큰을 반환하고 종료한다.

🔹 예제 코드 분석 (C 구현)

교재에서는 상태 다이어그램을 C로 구현한 실제 예제 코드(front.c)를 제시했다.

/* Function declarations */
void addChar();
void getChar();
void getNonBlank();
int lex();
/* Character classes */
#define LETTER 0
#define DIGIT 1
#define UNKNOWN 99
/* Token codes */
#define INT_LIT 10
#define IDENT 11
#define ASSIGN_OP 20
#define ADD_OP 21
#define SUB_OP 22
#define MULT_OP 23
#define DIV_OP 24
#define LEFT_PAREN 25
#define RIGHT_PAREN 26

/******************************************************/
/* main driver */
main() {
  /* Open the input data file and process its contents */
  if ((in_fp = fopen("front.in", "r")) == NULL)
    printf("ERROR - cannot open front.in \n");
  else {
    getChar();
    do {
      lex();
    } while (nextToken != EOF);
  }
}
/*****************************************************/
/* lookup - a function to lookup operators and parentheses
and return the token */
int lookup(char ch) {
  switch (ch) {
    case '(':
      addChar();
      nextToken = LEFT_PAREN;
      break;
    case ')':
      addChar();
      nextToken = RIGHT_PAREN;
      break;
    case '+':
      addChar();
      nextToken = ADD_OP;
      break;
    case '-':
      addChar();
      nextToken = SUB_OP;
      break;
    case '*':
      addChar();
      nextToken = MULT_OP;
      break;
    case '/':
      addChar();
      nextToken = DIV_OP;
      break;
    default:
      addChar();
      nextToken = EOF;
      break;
  }
  return nextToken;
}
/*****************************************************/
/* addChar - a function to add nextChar to lexeme */
void addChar() {
  if (lexLen <= 98) {
    lexeme[lexLen++] = nextChar;
    lexeme[lexLen] = 0;
  } else
    printf("Error - lexeme is too long \n");
}
/*****************************************************/
/* getChar - a function to get the next character of
input and determine its character class */
void getChar() {
  if ((nextChar = getc(in_fp)) = EOF) {
    if (isalpha(nextChar))
      charClass = LETTER;
    else if (isdigit(nextChar))
      charClass = DIGIT;
    else
      charClass = UNKNOWN;
  } else
    charClass = EOF;
}
/*****************************************************/
/* getNonBlank - a function to call getChar until it
returns a non-whitespace character */
void getNonBlank() {
  while (isspace(nextChar)) getChar();
}
/ *****************************************************/
    /* lex - a simple lexical analyzer for arithmetic
    expressions */
    int lex() {
  lexLen = 0;
  getNonBlank();
  switch (charClass) {
    /* Parse identifiers */
    case LETTER:
      addChar();
      getChar();
      while (charClass == LETTER || charClass == DIGIT) {
        addChar();
        getChar();
      }
      nextToken = IDENT;
      break;
    /* Parse integer literals */
    case DIGIT:
      addChar();
      getChar();
      while (charClass == DIGIT) {
        addChar();
        getChar();
      }
      nextToken = INT_LIT;
      break;
    /* Parentheses and operators */
    case UNKNOWN:
      lookup(nextChar);
      getChar();
      break;
    /* EOF */
    case EOF:
      nextToken = EOF;
      lexeme[0] = 'E';
      lexeme[1] = 'O';
      lexeme[2] = 'F';
      lexeme[3] = 0;
      break;
  } /* End of switch */
  printf("Next token is: %d, Next lexeme is %s\n", nextToken, lexeme);
  return nextToken;
} /* End of function lex */

주요 함수의 역할을 요약하면 다음과 같다.

getChar(): 다음 문자를 입력에서 읽어오고 문자의 클래스(letter/digit/unknown)를 정한다.
addChar(): 현재 문자를 렉심 배열에 추가한다.
getNonBlank(): 공백 문자를 건너뛰고 다음 의미 있는 문자를 찾는다.
lookup(): 연산자나 괄호 같은 단일 문자 토큰을 식별하여 반환한다.
lex(): 메인 분석 함수로, 입력된 문자 클래스를 확인하여 렉심을 구성하고 적절한 토큰을 결정한다.

실행 예시:

입력: (sum + 47) / total

출력:

Next token is: LEFT_PAREN    Lexeme is (
Next token is: IDENT         Lexeme is sum
Next token is: ADD_OP        Lexeme is +
Next token is: INT_LIT       Lexeme is 47
Next token is: RIGHT_PAREN   Lexeme is )
Next token is: DIV_OP        Lexeme is /
Next token is: IDENT         Lexeme is total
Next token is: EOF           Lexeme is EOF

🔹 예약어(Reserved Word) 처리와 심볼 테이블

프로그램의 이름(변수명 등)과 예약어(if, else 등)는 패턴이 유사하다. 모든 예약어를 각각 별도로 상태 다이어그램에 넣으면 복잡해진다.
따라서 이름과 예약어는 일단 같은 방식으로 인식하고, 이후 심볼 테이블에 저장된 예약어 테이블에서 확인하여 구분한다.
심볼 테이블(Symbol Table): 변수 이름과 그 속성(예: 자료형 등)을 저장하여 이후 컴파일 단계에서 활용하는 데이터베이스이다.

🔹 요약 및 정리

Lexical Analysis(어휘 분석)는 프로그램의 텍스트에서 문자를 읽어 의미 있는 최소단위(Lexeme)로 나누고, 이를 추상화된 분류(Token)로 변환하는 작업이다.
Lexical Analyzer는 컴파일러의 front-end로서 패턴 매칭을 기반으로 작동하며, 유한 오토마타 형태의 상태 전이 다이어그램으로 모델링된다.
실무에서는 도구를 사용하거나 정규 표현식을 기반으로 어휘 분석기를 구축하고 관리한다.

📚 4.3 The Parsing Problem (구문 분석 문제)

프로그래밍 언어의 구문을 분석하는 작업을 흔히 구문 분석(parsing)이라고 부른다.
구문 분석이란 프로그래밍 언어의 문법적 구조를 확인하고 분석하여 의미를 이해할 수 있도록 트리를 생성하는 과정이다.
이 섹션에서는 구문 분석 문제를 다루며, 주요 알고리즘 종류와 그 복잡도를 소개한다.

📖 4.3.1 Introduction to Parsing (구문 분석 소개)

프로그래밍 언어를 위한 파서는 입력된 프로그램에 대해 구문 트리(parse tree) 를 구성한다.

때때로 구문 트리를 명시적으로 만들지 않고, 트리를 순회(traversal)하는 과정만으로 충분한 경우도 있다.
하지만 어떤 방식으로든 파서는 반드시 구문 트리를 만들거나, 최소한 그 구조 정보를 파악해야 한다.

구문 분석의 목적은 크게 두 가지로 나뉜다.

① 입력된 프로그램이 문법적으로 올바른지 확인하기

문법 오류를 발견하면, 진단 메시지를 출력하고 분석을 계속 진행할 수 있도록 정상 상태로 복구(recovery)해야 한다.
잘 만든 구문 분석기는 한 번의 분석에서 최대한 많은 오류를 찾아내야 효율적이다.

② 문법적으로 올바른 입력에 대해서 구문 트리를 생성(혹은 트리의 구조를 추적)하기

이렇게 만들어진 구문 트리(혹은 그 흔적)는 이후 번역 과정(translation)의 기반이 된다.

구문 분석 알고리즘은 트리를 구축하는 방향에 따라 두 가지로 나눌 수 있다.

하향식 (Top-down): 루트에서부터 출발하여 잎(leaf) 노드까지 내려가면서 트리를 구축한다.
상향식 (Bottom-up): 잎(leaf) 노드에서부터 출발하여 루트 노드로 올라가면서 트리를 구축한다.

이 섹션에서 사용되는 기호 규칙을 명확하게 설명해두고 있다.

구분표기방식예시

종단 기호 (Terminal)	소문자 (a, b, …)	a, b, c
비종단 기호 (Nonterminal)	대문자 (A, B, …)	A, B, C
종단 또는 비종단 기호	대문자 (W, X, Y, Z)	X, Y
종단 기호의 문자열	소문자 (w, x, y, z)	xyz
혼합 문자열	소문자 그리스 문자 (α, β, γ, δ)	α, β

📖 4.3.2 Top-Down Parsers (하향식 파서)

하향식 파서는 전위 순회(preorder traversal) 방식으로 구문 트리를 구축한다.
즉, 루트 노드부터 시작해서 가지(branch)를 탐색하기 전에 각 노드를 방문한다.

하향식 파서의 기본적인 원리는 다음과 같다.

Leftmost derivation (좌측 최우선 유도)
좌측 최우선 유도는 항상 가장 왼쪽에 위치한 비종단(nonterminal) 기호를 확장(expand)하면서 진행한다.
하향식 파서가 해결해야 할 핵심 문제는 바로 "어떤 문법 규칙을 다음에 적용할지 선택하는 것"이다.
- 주어진 sentential form(문장 형태, 문법 기호들로 이루어진 문자열)에서 가장 왼쪽에 위치한 비종단 기호가 선택의 기준이 된다.
- 일반적으로 다음 입력 토큰을 보고 어떤 규칙(RHS)을 선택할지 결정한다. 이러한 방식의 하향식 파서를 LL 파서라 부른다.
  - LL: Left-to-right(왼쪽에서 오른쪽 입력 탐색), Leftmost derivation(좌측 최우선 유도) 방식.
- 가장 흔히 쓰이는 하향식 파서의 구현 방식은 재귀 하강(recursive-descent) 파서이며, 이것은 주어진 문법의 BNF(Backus-Naur Form) 정의를 거의 그대로 코드로 구현한다.

📖 4.3.3 Bottom-Up Parsers (상향식 파서)

상향식 파서는 하향식 파서와 반대로, 구문 트리를 아래쪽 잎 노드에서 시작하여 위로 루트까지 올라가며 구축한다.
구체적으로 말하면, 우측 최우선 유도(rightmost derivation) 를 역방향으로 수행한다.

상향식 파서의 핵심 아이디어는 다음과 같다.

Handle(핸들) 찾기:
- 문장 형태(오른쪽 최우선 유도된 형태)에서 문법 규칙의 우측(RHS)에 정확히 매칭되는 하위 문자열을 찾는다.
- 찾은 핸들을 문법 규칙의 좌측(LHS)으로 축약(reduce)하며, 이를 반복하여 문장 형태를 최종적으로 시작 기호(start symbol)로 되돌린다.
- 예를 들어, 주어진 문장 형태에서 어떤 부분 문자열이 규칙의 RHS에 대응하는지 정확히 찾아야 한다. 이것을 handle이라고 하며, 이 handle을 LHS로 대체하는 과정이 reduction(축약)이다.
상향식 파서의 대표적 구현 방식은 LR 파서이다.
- LR: Left-to-right(왼쪽에서 오른쪽 입력 탐색), Rightmost derivation(우측 최우선 유도) 방식.
- LR 계열 파서는 대부분의 실제 상용 컴파일러에서 널리 쓰이는 방식이다.

📖 4.3.4 The Complexity of Parsing (구문 분석의 복잡도)

모든 가능한 문법(특히 모호하지 않은 문법)을 파싱할 수 있는 알고리즘의 복잡도는 일반적으로 O(n³) 이다.
이런 높은 복잡도는 알고리즘이 오류가 발생했을 때 문장을 반복적으로 되돌아가면서 재분석(reparse)을 해야하기 때문이다.

하지만 실제로 많이 쓰이는 문법을 사용하는 컴파일러의 구문 분석 알고리즘은 대부분 **O(n)**의 복잡도를 가진다.
즉, 입력 문자열의 길이에 비례하는 시간만큼 걸리며, 이로 인해 매우 효율적이다.

실무에서 효율성을 중시하기 때문에, 실제 컴파일러 구현에서는 모든 문법을 다루는 범용적인 알고리즘보다 효율적인 특수 목적의 알고리즘이 주로 선택된다.

📌 정리 및 핵심 개념:

구문 분석(parsing)이란 문법 구조를 트리 형태로 분석하여 의미적 처리를 돕는 과정.
하향식 파서(LL)는 루트에서 잎으로, 상향식 파서(LR)는 잎에서 루트로 트리를 구성.
실무적으로 사용되는 구문 분석 알고리즘의 효율은 선형 시간 O(n).

4.4 Recursive-Descent Parsing (재귀 하향식 파싱)

4.4.1 The Recursive-Descent Parsing Process (재귀 하향식 파싱 과정)

재귀 하향식 파서(recursive-descent parser)는 이름 그대로 재귀 호출(recursion)을 이용하여 문법 규칙(grammar rules)을 구현하는 방식이다.

특징 및 이유:

프로그래밍 언어는 종종 중첩(nested)된 구조(예: if문 내부의 if문 또는 중첩된 괄호 표현식)를 가지는데, 이런 구조를 표현하기에 가장 적합한 문법 형식이 바로 재귀적인 문법(recursive grammar rules)이다.
Extended BNF(EBNF)는 재귀 하향식 파서를 구현할 때 자주 사용되는데, 이는 선택적(optional)이고 반복되는 구조(repeated)를 편하게 표현할 수 있기 때문이다. 예를 들어, {}는 0회 이상 반복을 의미하고, []는 선택적(optional)을 의미한다.

예시 문법:

<if_statement> → if <logic_expr> <statement> [else <statement>]
<ident_list> → ident {, ident}

위의 첫 문법에서 else는 옵션이며, 두 번째 문법에서 식별자는 하나 이상 쉼표로 반복된다.

재귀 하향식 파서 동작 원리

재귀 하향식 파서는 문법에서 정의된 각 비단말 기호(nonterminal)마다 서브프로그램(함수)을 작성하여 파싱한다. 파싱 과정은 다음과 같다:

입력 문자열이 주어지면 해당 문자열을 문법의 규칙에 따라 **재귀적으로 분석하여 파스 트리(parse tree)**를 생성한다.
이 때, 각 서브프로그램은 해당 비단말 기호로 시작하는 문자열 집합을 분석할 수 있는 파서 역할을 한다.

다음은 간단한 산술 표현식(arithmetic expression)의 EBNF 문법 예시이다:

<expr> → <term> {( + | - ) <term>}
<term> → <factor> {( * | / ) <factor>}
<factor> → id | int_constant | ( <expr> )

이 문법은 *산술 표현식을 +, -, , / 연산자를 포함해 표현한 것이다.

코드 예시 및 설명

실제 코드로 구현할 때 다음과 같이 작성한다.

① <expr> 파싱 함수:

void expr() {
    printf("Enter <expr>\n");
    term();
    while (nextToken == ADD_OP || nextToken == SUB_OP) {
        lex(); // 토큰을 하나 가져온다.
        term();
    }
    printf("Exit <expr>\n");
}

이 코드는 <expr>을 분석하며, <term>을 최소 한번 호출하고, 그 뒤에 연속적인 + 또는 - 가 나오는 동안 계속 <term>을 호출한다.

② <term> 파싱 함수:

void term() {
    printf("Enter <term>\n");
    factor();
    while (nextToken == MULT_OP || nextToken == DIV_OP) {
        lex();
        factor();
    }
    printf("Exit <term>\n");
}

<term>은 <factor>를 최소 한 번 호출하고, 이후 * 또는 / 연산자가 있는 경우 반복해서 호출한다.

③ <factor> 파싱 함수:

void factor() {
    printf("Enter <factor>\n");
    if (nextToken == IDENT || nextToken == INT_LIT) {
        lex();
    }
    else if (nextToken == LEFT_PAREN) {
        lex();
        expr();
        if (nextToken == RIGHT_PAREN) lex();
        else error();
    }
    else error();
    printf("Exit <factor>\n");
}

<factor>는 변수 이름이나 정수 상수, 혹은 괄호로 감싸진 표현식을 처리한다. 에러 처리를 명확히 수행한다.

예제 파싱 결과 (Trace)

표현식 (sum + 47) / total 의 파싱 과정을 예시(trace)로 제공하였다. 여기서 핵심은 파서가 재귀적으로 문법 규칙을 따라가면서 분석한다는 것이다. trace의 각 "Enter"와 "Exit" 메시지는 서브프로그램이 호출되고 종료될 때 찍히는 로그이다.

또한 trace에 따라 생성된 파스 트리도 나타나 있다. 트리는 분석 과정에서 어떤 규칙이 적용되었는지 명확하게 나타낸다.

추가 예시 (if 문 예제)

추가적으로 자바의 if문을 표현한 문법과 재귀 하향식 서브프로그램을 예로 들고 있다. 여기서도 같은 재귀 하향식 접근법으로 각 비단말 기호를 파싱한다.

4.4.2 The LL Grammar Class (LL 문법 클래스)

재귀 하향식 파싱(Recursive-descent parsing)은 LL 파서 범주에 속하며, LL 문법 규칙에 적합해야 한다.

LL 파싱 문제: 왼쪽 재귀(Left Recursion)

LL 파서는 왼쪽 재귀(Left recursion)가 포함된 문법을 파싱할 수 없다.
왼쪽 재귀란 문법의 규칙에서 자기 자신을 제일 처음에 호출하는 규칙을 의미한다. 예를 들어:

A → A + B

이 경우 파싱 함수가 무한 재귀에 빠진다.

해결 방법으로는 왼쪽 재귀 제거(Left recursion elimination)를 수행한다. 이를 위해 다음과 같이 문법을 재구성한다.

A → β1A' | β2A' | ... | βnA'
A' → α1A' | α2A' | ... | αmA' | ε

여기서 ε는 empty(빈 문자열)이다. 이런 변형을 통해 문법이 LL 문법으로 바뀐다.

Pairwise Disjointness Test (쌍별로 분리성 테스트)

LL 파서의 다른 조건은 각 규칙의 오른쪽 부분(RHS)이 서로 분리(disjoint)되어야 한다는 것이다. 즉, 다음과 같은 두 규칙이 있다고 할 때:

A → α | β

두 규칙 α와 β가 시작하는 첫 토큰의 집합이 겹치지 않아야 한다.

Left Factoring (왼쪽 인수분해)

위에서 설명한 Pairwise Disjointness 조건을 만족시키기 위해 문법을 수정하는 것이 Left Factoring이다. 이는 공통된 앞부분을 따로 떼어내 새로운 비단말을 만드는 과정이다. 예:

변경 전:
<variable> → identifier | identifier[<expression>]

변경 후 (Left Factoring 적용):
<variable> → identifier <new>
<new> → ε | [<expression>]

4.5 Bottom-Up Parsing (상향식 파싱)

4.5.1 The Parsing Problem for Bottom-Up Parsers (상향식 파서의 파싱 문제)

상향식 파싱의 개념

상향식 파서는 오른쪽 최단 유도(rightmost derivation)를 역으로 진행하면서 파싱을 수행한다. 즉, 주어진 입력에서부터 시작하여 점진적으로 문법의 시작 심볼(start symbol)로 역추적하는 방식이다.

예시 문법 (산술 표현식):

E → E + T | T
T → T * F | F
F → (E) | id

이 문법은 앞서 본 재귀 하향식 파싱 문법과 동일한 표현식을 생성하지만, **좌측 재귀(left recursion)**를 포함하여 상향식 파싱에 적합하도록 작성된 문법이다. 이때 사용된 유도 과정은 오른쪽 최단 유도이며, 역순으로 따라가면 바로 상향식 파싱 과정이다.

Handle의 개념과 정의

상향식 파싱의 핵심 개념 중 하나는 핸들(handle) 이다.

핸들(handle)이란?

주어진 sentential form(유도된 문자열)에서 다음으로 축소(reduce)될 부분 문자열이다.
공식적 정의는 다음과 같다.

정의: β가 sentential form γ의 핸들(handle)인 경우는 다음과 같다.
S ⇒*rm αAw ⇒rm αβw

이 정의는 '핸들'이란 특정 부분(β)을 축소하면 이전 형태(sentential form)로 돌아갈 수 있는 유일한 문자열을 의미한다.

Phrase와 Simple Phrase

Phrase: sentential form에서 하나 이상의 유도 과정을 거쳐서 나타난 비단말 기호로부터 생성된 문자열이다.
Simple Phrase: 오직 한 단계의 유도만을 거쳐서 생성된 phrase이다.
핸들은 항상 가장 왼쪽의 simple phrase이다.

예시 파스트리(Parse Tree)를 통해 이해할 수 있다.

Phrase: 파스트리의 하위 트리에서 생성된 문자열 전체
Simple Phrase: 파스트리에서 단 한 단계의 유도만 거쳐 나온 문자열 (예: id)

4.5.2 Shift-Reduce Algorithms (Shift-Reduce 알고리즘)

상향식 파서는 흔히 Shift-Reduce 알고리즘으로 불린다. 두 가지 기본 동작을 수행하기 때문이다.

Shift: 입력에서 다음 토큰을 파서의 스택으로 옮김.
Reduce: 스택 상단의 핸들(RHS, 우측 부분)을 축소하여 해당하는 문법 규칙의 LHS(좌측 부분)으로 변경함.

Pushdown Automaton (푸시다운 오토마타, PDA)

모든 파서는 일종의 푸시다운 오토마타(PDA)이며, 상향식 파서 역시 PDA로 볼 수 있다.

PDA는 입력 심볼을 왼쪽에서 오른쪽으로 한 번씩만 스캔하며 스택을 사용하여 처리하는 단순한 기계이다.
상향식 파서는 입력 문자열을 왼쪽에서 오른쪽으로 순차적으로 읽으며 핸들을 찾아 축소한다.

4.5.3 LR Parsers (LR 파서)

상향식 파싱 알고리즘은 다양하지만, 대표적으로 LR 알고리즘 계열이 있다.
LR은 다음의 의미를 가진다:

Left-to-right scanning (좌에서 우로 스캔)
Rightmost derivation (오른쪽 최단 유도)

LR 알고리즘은 Donald Knuth에 의해 개발되었으며, LR parsing table을 기반으로 한다.

LR Parsing의 장점:

대부분의 프로그래밍 언어 문법에 적용 가능하다.
구문 오류(syntax error)를 신속히 찾아낼 수 있다.
LL 문법보다 더 넓은 문법 클래스(LR 문법 클래스)를 지원한다.

LR 파서 구조

LR 파서는 다음과 같은 형태의 스택을 사용한다.

S₀ X₁ S₁ X₂ S₂ ... Xₘ Sₘ

S는 상태(state), X는 문법 심볼(grammar symbol)이다.
상태(state)는 파싱 테이블(parsing table)에서의 위치를 나타내며, 심볼은 실제 문법에서 등장하는 토큰이나 비단말 기호이다.

LR 파서 동작 구조 (그림 4.4 참고)

Parse Stack       Input
| S₀ X₁ S₁ ... Xₘ Sₘ | aᵢ aᵢ₊₁ ... aₙ $ |

파서는 다음 구성요소를 갖는다:

Parsing Table: 파싱을 제어하는 ACTION과 GOTO 테이블로 구성.
Parser Code: 파싱 테이블의 내용을 이용하여 입력을 분석하는 코드.

LR Parsing Table (LR 파싱 테이블)

LR 파싱 테이블은 다음 두 부분으로 구성된다:

ACTION 테이블: 현재 상태(state)와 입력 토큰(token)에 따라 다음 행동을 결정한다 (shift, reduce, accept, error).
GOTO 테이블: reduce 후 어떤 상태로 이동할지를 결정한다.

LR 파서의 행동(action):

Shift: 입력에서 토큰을 하나 스택으로 옮기고 새 상태로 전환.
Reduce: 핸들을 스택에서 제거하고 LHS로 축소한 뒤, 해당 상태로 이동.
Accept: 입력이 성공적으로 파싱됨을 의미.
Error: 구문 오류가 발생하여 오류 처리 루틴 호출.

예시 문법을 통한 실제 파싱 테이블이 제공된다(그림 4.5 참고).

LR Parsing 예시 (예시 문자열: id + id * id)

실제 LR 테이블을 이용해 입력 문자열을 파싱하는 과정 예시(trace)를 보여준다.
스택(Stack), 입력(Input), 행동(Action)을 단계별로 추적하여 최종적으로 Accept 상태에 이르는 과정을 명확히 보여준다.

Parsing Table 자동 생성

실제 프로그래밍 언어를 위한 문법의 LR 테이블을 손으로 만드는 것은 비효율적이다. 따라서, yacc와 같은 자동화된 소프트웨어 도구를 사용하여 자동으로 생성한다.

Summary

구문 분석(Syntax analysis) 은 프로그래밍 언어 구현에 필수적인 요소이며, 보통 언어의 문법(grammar)을 기반으로 이루어진다.
- 문법은 대부분 BNF(Backus-Naur Form) 형태로 나타낸다.
- 문법 분석은 보통 Lexical analysis(어휘 분석) 와 Syntax analysis(구문 분석) 로 나눈다.
- 이유는 단순성, 효율성, 이식성 때문이다.
어휘 분석기(Lexical Analyzer) 는 소스코드를 토큰(Token)으로 나누는 작업을 한다.
- 토큰은 식별자, 리터럴 등으로 나누며, 각 토큰은 숫자 코드(token code)로 표현된다.
- 어휘 분석기를 만드는 방법은 세 가지가 있다.
  - 자동 생성 소프트웨어 도구 사용 (예: lex)
  - 수동으로 상태 전이표(State transition table)를 구성하여 제작
  - 상태 다이어그램(State diagram)을 직접 코드로 구현
구문 분석기(Syntax Analyzer) 는 두 가지 목표가 있다:
- 문장의 구문 오류를 찾아내는 것
- 파스트리(Parse Tree)를 만들어내는 것
파싱 방법 은 크게 **하향식(Top-down)**과 **상향식(Bottom-up)**으로 나뉜다.
- 하향식은 문법의 왼쪽에서 오른쪽으로 전개하며, 파스트리를 위에서 아래로 만든다.
- 상향식은 오른쪽 유도(rightmost derivation)를 역순으로 진행하며, 파스트리를 아래에서 위로 만든다.
재귀 하향식 파서(Recursive-descent parser) 는 EBNF 문법을 기반으로 만들어진 LL 파서이다.
- 각 비단말(nonterminal)에 대응되는 서브 프로그램을 만들어 처리한다.
- 왼쪽 재귀(Left recursion)와 pairwise disjointness(서로 구분 가능한 RHS) 문제가 있을 수 있다.
- 왼쪽 재귀는 제거가 가능하고, pairwise disjointness 문제는 left factoring(왼쪽 인수분해)을 통해 해결 가능하다.
상향식 파싱(Bottom-up parsing) 은 핸들(Handle)을 찾아 문법의 왼쪽 부분(LHS)으로 축소(Reduce)하는 과정을 반복한다.
- LR 알고리즘은 대표적인 상향식 파서이며, 상태 스택과 파싱 테이블을 사용하여 효율적이다.
- LR 파서 테이블은 ACTION과 GOTO로 구성되며 shift와 reduce를 사용한다.

Review Questions

1. BNF가 비공식적 설명보다 장점이 있는 이유

정확성, 명료성, 일관성 때문. 비공식적 설명은 애매할 수 있지만 BNF는 모호성을 없앤 형식적인 방법이기 때문이다.

2. 어휘 분석기가 구문 분석기의 프론트 엔드인 이유

어휘 분석기는 원시 코드를 의미 있는 토큰으로 미리 나누어 이후 구문 분석기가 쉽게 처리할 수 있도록 준비하는 역할을 한다.

3. Finite automata와 Regular grammar의 정의

Finite Automata: 유한한 개수의 상태(state)를 가진 기계로, 입력 문자열을 읽으며 상태 전이를 통해 입력 문자열의 유효성을 검사한다.
Regular grammar: 정규 언어를 생성하는 가장 간단한 형태의 문법으로, 하나의 비단말 기호에서 단말 기호 또는 단말 기호와 비단말 기호의 결합 형태로 표현된다.

4. 상태 다이어그램을 이용한 어휘 분석기 구축 방법

토큰을 인식하는 각 상태를 다이어그램으로 표현하고 이를 프로그램 코드로 변환하여 작성한다.

5. 어휘 분석기 구축의 세 가지 접근법

자동화 도구 사용 (예: lex)
상태 전이표 수동 작성
상태 다이어그램 직접 코드화

6. 형식 언어의 다양한 문법 심볼

**비단말(nonterminal)**과 단말(terminal) 심볼이 있다. 비단말은 추가로 전개 가능한 문법 요소이며, 단말은 최종적으로 코드에 직접 등장하는 요소이다.

7. 상태 다이어그램에서 개별 문자 대신 문자 클래스를 사용하는 이유

문자 개별적으로 상태 전이를 설정하면 복잡해지기 때문에 유사한 문자를 하나의 클래스(예: 숫자, 문자 등)로 묶어 단순화한다.

8. 구문 분석의 두 가지 목표

구문 오류의 탐지
파스 트리 생성

9. 파싱 알고리즘의 복잡도 설명

일반적으로 문법의 복잡도는 O(n³)이지만, 프로그래밍 언어에 쓰이는 문법은 O(n)으로 더 효율적이다.

10. 재귀 하향식 파서 설명

각 비단말마다 재귀적으로 호출되는 파서이며 EBNF와 잘 맞는다.

11. LL 알고리즘의 두 L의 의미

Left-to-right scan(왼쪽부터 읽기)과 Leftmost derivation(왼쪽부터 유도 전개)을 의미한다.

12. 재귀 하향식 서브프로그램 작성 규칙

서브프로그램이 시작할 때 다음 입력 토큰(nextToken)이 항상 미리 준비되어 있다고 가정하고 시작한다.

13. 토큰 코드로 숫자 대신 이름 붙인 상수를 쓰는 이유

읽기 쉽고 유지보수가 용이하며 코드의 명료성을 높이기 때문이다.

14. 하나의 RHS를 가진 규칙의 재귀 하향식 서브프로그램 작성법

RHS의 심볼을 차례로 비교 및 호출하며, 일치하지 않으면 구문 오류를 리턴한다.

15. 하향식 파서를 어렵게 하는 두 가지 문법적 특징

왼쪽 재귀(left recursion), pairwise disjointness 조건 위배이다.

16. 직접 왼쪽 재귀 정의

문법 규칙의 왼쪽에서 자기 자신을 바로 다시 호출하는 형태 (예: A → A α)이다.

17. Pairwise disjointness 테스트 설명

하나의 nonterminal의 각 RHS의 첫 번째 심볼 집합이 겹치지 않아야 하는 조건이다.

18. Left factoring의 한계

모든 pairwise disjointness 문제를 해결하지는 못한다.

19~20. Phrase와 Simple Phrase 정의 및 차이

Phrase는 파스트리의 한 노드에서 나온 모든 문자열, Simple Phrase는 오직 한 단계만의 유도로 생성된 phrase이다.

21. Handle의 특징

항상 sentential form에서 가장 왼쪽에 위치한 simple phrase이다.

22. 모든 파서의 기반이 되는 수학적 기계

Pushdown Automaton(PDA)이다.

23. LR 파서의 단점

수동으로 파싱 테이블 제작이 어렵다.

24. 상향식 파서를 Shift-Reduce 알고리즘이라 하는 이유

shift와 reduce 동작을 주로 수행하기 때문이다.

25. LR 파서에서 Parse stack의 목적

파싱 중 파서의 상태와 문법 심볼을 기록 및 관리한다.

26. Canonical LR 파싱 테이블 변형의 속성

계산 자원을 덜 소모하며, 특정한 제한된 문법 클래스에서 동작한다.

27. 모든 프로그래밍 언어 파서가 PDA인 이유

스택을 이용한 구문 처리 능력을 제공하기 때문이다.

'Book > Concepts of Programming Language' 카테고리의 다른 글

Chapter3: Describing Syntax and Semantics (0)	2025.04.03

현재글4. Lexical and Syntax Analysis

솔

c++기반 개발 공부기록 블로그입니다.

Algorithm, Computer Network, RISC-V, c++, AVL, 컴퓨터, 네트워크, computernetwork, binaryTree, assembly, Computer, 컴퓨터네트워크, Computer Architecture, 컴퓨터구조, 알고리즘, network, c, computer organization, DataStructure, 백준,

Today :
Yesterday :

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

2025. 04
일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30