CS/프로그래밍언어론

[프로그래밍언어론] 7. Parsing Problem

2024. 4. 19. 02:17
목차
  1. 탑 - 다운 파서
  2. 바텀 - 업 파서
  3. 파싱의 시간복잡도
반응형

파서의 목표는 소스코드를 받아서 파싱을 한 뒤, Parse Tree 를 만드는 것이다.

만약 파싱하다가 실패했다면 소스코드에서 문법에 맞지 않는 부분이 있었다는 뜻이므로,

파서는 syntax error 가 발생했다는 걸 알려줘야 한다.

 

잘 동작하는 파서는 파싱할 때 토큰 1개를 더 앞서 볼 수 있다. (look ahead, LA)

그래야 알맞는 BNF 문법을 체크할 수 있다.

 

파서에는 2가지 카테고리가 있다.

첫번째는 탑-다운 / 두번째는 바텀-업 이다.


탑 - 다운 파서

탑-다운 파서는 root 부터 시작해서 아래로 내려가면서 파스 트리를 만든다.

탑-다운 파서는 왼쪽에서부터 파고들어 본다. (즉 pre-order 순으로 파싱트리를 만든다.)

xAα 라는 sentential form 이 주어졌을 때, 파서는 적합한 A 규칙을 골라 다음 sentential form 을 얻어야 한다.

저 문법은 왼쪽에 있는 x 라는 논터미널은 A라는 규칙에 의해 α로 extend 된다는 의미이다.

탑다운 파서는 왼쪽부터 시작해서 x를 내게 한 다음, A가 만들어지는지 확인하는 과정을 반복하며 파싱한다.

(구체적인 내용은 컴파일러 과목에서 다룬다.)

 

탑다운 파싱 알고리즘은 대표적으로 2가지가 있다.

- Recursive descent

- LL Parser


 

바텀 - 업 파서

바텁-업 파서는 leaf 노드인 터미널부터 시작해서 거꾸로 올라오며 파싱트리를 만든다.

바텀-업 파서도 왼쪽에서부터 올라오며 만든다.

즉, 오른쪽의 sentential form 인 α가 주어졌을 때, 어떤 규칙을 적용해야 α가 오른쪽에 올 수 있을지 찾는 과정을 거친다.

 

바텀업 파싱 알고리즘은 LR Parser 계열을 주로 사용한다.


파싱의 시간복잡도

모호하지 않은 문법에 대해 파서는 보통 O(n^3) 의 시간복잡도를 갖는다.

(n = input length)

그래서 컴파일러는 그래머 전체를 갖고 파싱하는게 아니라, 일부 그래머를 가지고 파싱하도록 해서 O(n) 의 시간복잡도로 최적화 한다.

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'CS > 프로그래밍언어론' 카테고리의 다른 글

[ Lex/Yacc ] 내가 만든 테스트케이스 (테스트 파일 포함)  (0) 2024.05.08
[ lex / yacc ] error: 'AUTO' undeclared (first use in this function) 해결  (0) 2024.05.03
[프로그래밍언어론] 6. C언어의 BNF 문법과 파싱 예제  (0) 2024.04.17
[프로그래밍언어론] 5. Lexical and Syntax Analysis  (0) 2024.04.17
[프로그래밍언어론] 4. Semantics  (0) 2024.04.16
  1. 탑 - 다운 파서
  2. 바텀 - 업 파서
  3. 파싱의 시간복잡도
'CS/프로그래밍언어론' 카테고리의 다른 글
  • [ Lex/Yacc ] 내가 만든 테스트케이스 (테스트 파일 포함)
  • [ lex / yacc ] error: 'AUTO' undeclared (first use in this function) 해결
  • [프로그래밍언어론] 6. C언어의 BNF 문법과 파싱 예제
  • [프로그래밍언어론] 5. Lexical and Syntax Analysis
에버듀
에버듀
개발은 좋은데 뭘로 개발할까
에버듀
Blog. 에버듀
에버듀
전체
오늘
어제
  • 분류 전체보기 (594) N
    • 개인 프로젝트 (43)
      • [2020] 카카오톡 봇 (9)
      • [2021] 코드악보 공유APP (22)
      • [2022] 유튜브 뮤직 클론코딩 (9)
      • 간단한 프로젝트 (3)
    • 팀 프로젝트 (22)
      • [2020] 인공지능 숫자야구 (4)
      • [2022] OSAM 온라인 해커톤 (10)
      • [2024] GDSC 프로젝트 트랙 (6)
      • [2025] 큰소리 웹 페이지 (2)
    • 알고리즘 (PS) (107)
      • BOJ (101)
      • Programmers (5)
      • 알고리즘 이모저모 (1)
    • CS (318) N
      • 자료구조 (19)
      • 어셈블리 (41)
      • 멀티미디어응용수학 (7)
      • 컴퓨터 구조 (29)
      • 알고리즘 분석 (4)
      • 컴퓨터 네트워크 (38)
      • 프로그래밍언어론 (15)
      • HCI 윈도우즈프로그래밍 (26)
      • 기초데이터베이스 (29)
      • 운영체제 (23)
      • 오토마타 (24)
      • 문제해결기법 (11)
      • 블록체인 (22)
      • 소프트웨어공학 (18) N
      • 기계학습심화 (12)
      • 컴퓨터그래픽스와 메타버스 (0)
    • 자기계발 (36)
      • 동아리 (7)
      • 자격증 (2)
      • 코딩테스트, 대회 (8)
      • 생각 정리 (18)
      • 머니 스터디 (1)
    • WEB(BE) (5)
      • express.js (1)
      • flask (0)
      • Spring & Spring Boot (4)
    • WEB(FE) (2)
      • html, css, js (1)
      • React.js (1)
    • Tool & Language (6)
      • Edit Plus (1)
      • Git (1)
      • Python3 (2)
      • Java (2)
    • Infra (12)
      • AWS (1)
      • Oracle Cloud (8)
      • Firebase (2)
      • Network (1)
    • Android (18)
      • Java (6)
      • Flutter (12)
    • Window (2)
      • Visual Studio 없이 WPF (1)
      • MFC (1)
    • 독서 (14)
      • Inside Javascript (7)
      • Database Internals (6)
      • 한 글 후기 (1)
    • 인턴 (8)
      • 델파이 (7)
      • Oracle (1)

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.1.4
에버듀
[프로그래밍언어론] 7. Parsing Problem
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.