최근 변경최근 토론
특수 기능
 

파싱

최근 수정 시각:
5
편집
IP 우회 수단(프록시 서버, VPN, Tor 등)이나 IDC 대역 IP로 접속하셨습니다. (#14462228)
(VPN이나 iCloud의 비공개 릴레이를 사용 중인 경우 나타날 수 있습니다.)
잘못된 IDC 대역 차단이라고 생각하시는 경우 게시판에 문의하시길 바랍니다.
토론역사
분류
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
다른 뜻 아이콘   파서는 여기로 연결됩니다. 파서(巴西)에 대한 내용은 브라질 문서를 참고하십시오.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
이론 컴퓨터 과학
Theoretical Computer Science
[ 펼치기 · 접기 ]
이론
기본 대상
수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론
재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 · 디지털 물리학
오토마타 이론
FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론
점근 표기법 · 튜링 기계고전, 양자, 비결정론적, 병렬 임의접근 기계 · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법, 분할 정복 알고리즘)
정보이론
정보 엔트로피 · 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어론
프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타프로그래밍 · 람다 대수 · 타입 이론 · 프로그래밍 언어 의미론 · 어휘 분석 · 파싱 · 구문 트리(완전 구문 트리 · 추상 구문 트리) · 컴파일러 이론
주요 알고리즘 및 자료구조
기초
정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현
배열벡터 · 리스트연결 리스트 · 셋(set) · 트리이진 트리(레드-블랙 트리, 힙), B-트리, 피보나치 힙 · 큐 · 스택
수학적 최적화
조합 최적화
외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화
내부점 방법 · 경사하강법
선형계획법
심플렉스법
계산 수론 및 암호학
밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 · 난수생성
대칭키 암호화 방식
블록 암호 알고리즘(파이스텔 네트워크 · DES · AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식
공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학
볼록 껍질 · 들로네 삼각분할 및 보로노이 도형Fortune의 line-sweeping 알고리즘 · 범위 탐색vp-tree, R-tree · k-NN
그래프 이론
탐색BFS, DFS, 다익스트라 알고리즘, A* 알고리즘 · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학
[ 펼치기 · 접기 ]
기반 학문
수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(음운론 · 형태론 · 통사론 · 의미론 · 화용론) · 인지과학
하드웨어
SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품
기술
기계어 · 어셈블리어 · 바이오스 · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 함수형 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · LinuxBoot · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속
연구 및 기타
논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 카르노 맵 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영체제(멀티태스킹 · 프로세스 스케줄링 · 데드락 · 식사하는 철학자 문제 · 뮤텍스 · 세마포어 · 인터럽트) · 데이터베이스 · 컴퓨터 언어 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 어휘 분석 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 마크업 언어 · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크(네트워크 포트) · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론(애자일 · 워터폴) · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템) · 난수생성 · 놀람 최소화 원칙 · 프레임워크 · 라이브러리 · 모듈 · API · ABI · 이진 탐색
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. 개요2. 과정
2.1. 어휘 분석(lexing)2.2. 구문 분석(parsing)
2.2.1. 예시
2.3. 파스 트리(parse tree)
3. 모호성(ambiguity)
3.1. 모호성 해결 방법
3.1.1. 예제 13.1.2. 예제 2
4. 파싱 방식
4.1. 하향식 파서(Top-down Parser)4.2. 상향식 파서(Bottom-up Parser)
5. 관련 문서

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. 개요[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
parsing, 구문 분석

형식 언어 또는 컴퓨터 언어로 짠 코드를 실행하거나, 프로그램으로 변환시키기 위해서는 어휘 분석(lexing) 또는 토큰화(tokenize)를 통해 키워드, 식별자(identifier), 연산자(operator) 및 리터럴(literal) 같은 개별 토큰으로 변환한다. 이후 이 코드가 프로그래밍 언어의 문법에 맞는지 확인하는 과정을 파싱(parsing)이라고 한다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. 과정[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
HowToCheckSyntax
  • 어휘 분석(lexing) 과정에서는 코드 문자열은 개별 토큰으로 분리되며, 각 토큰은 코드의 기본적인 의미 단위로써 자료형, 식별자, 리터럴, 연산자 및 기타 구문 기호를 나타낸다. 이러한 과정을 토큰화(tokenize)라고 한다.
  • 구문 분석(parsing) 과정에서는 이러한 토큰들이 파스 트리(parse tree)로 재구성되어 소스 코드의 구조적 계층을 표현한다. 파스 트리의 각 노드는 코드의 구문적 관계를 나타낸다. 이러한 결과로 나온 파스 트리에서 단순한 구문적인 요소[1]를 제외하고 인터프리터를 위한 직접 실행할 요소나, 컴파일을 위해 필요한 구조만 가져와 AST를 형성한다.

이러한 처리 부분을 컴파일러에서 front-end라고 하며, AST로 변환 후 back-end 부분에서 semantics에 대해 바로 해석을 수행하는 경우 인터프리터, 추가 분석, 최적화 및 다른 언어로의 변환을 수행하게 되면 컴파일러라고 한다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.1. 어휘 분석(lexing)[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
코드 문자열을 어휘 단위로 쪼개어 토큰화를 수행하는 과정이다. 어휘 분석기로 진행되며, 정규 표현식과 유한 상태 기계를 통해 검사한다. 예를 들어 다음 코드 같은 경우
int x = 2 + 3; int y = x - 5;

아래와 같이 토큰화 될 수 있다.
TYPE_INT
IDENT("x")
OP_EQ
INT(2)
OP_ADD
INT(3)
SEMICOLON
TYPE_INT
IDENT("y")
OP_EQ
IDENT("x")
OP_MIN
INT(5)
SEMICOLON
상세 내용 아이콘   자세한 내용은 어휘 분석 문서를 참고하십시오.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.2. 구문 분석(parsing)[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
어휘 분석기에서 생성된 토큰들이 문법 규칙에 맞게 배열 되어있는지를 확인하고 그 구조를 파스 트리(parse tree)로 구성하는 과정이다. 이때 언어 규칙을 정의할 때 배커스-나우르 표기법(BNF)으로 기술하며, 이런 형식으로 표현되는 문법을 문맥 자유 문법(Context Free Grammar)라고 한다. 앞으로 서술할 내용은 BNF를 안다는 전제로 작성된다.

분석 과정을 간략히 적자면, 파서는 <숫자> + <숫자> 같은 토큰 뭉치를 보고, 언어 규칙 목록에서 <숫자> + <숫자> 꼴이 있는지를 확인한다. 예를 들어 <수식> ::= <숫자> + <숫자>라는 규칙을 발견하면, 이 토큰 뭉치를 <수식>이라는 더 큰 개념으로 바꿔버린다. 이렇게 규칙의 오른쪽(RHS)을 왼쪽(LHS)으로 바꾸는 걸 '축약(Reduction)'이라고 한다.

이 축약 과정을 계속 반복해서, 입력한 문자열이 시작 심볼 하나로 딱 줄어들면, 그 문자열은 '문법적으로 올바르다'고 결정된다. 이 상태를 '문자열 s가 문법 G가 정의하는 언어 L(G)에 속한다. (s∈L(G)s \in L(G))'라고 한다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.2.1. 예시[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
아래 문법에 대해 문자열 1+2∗31+2*3이 있다고 하자. 표기에 대한 자세한 설명은 배커스-나우르 표기법 참조.
<expr> ::= <term> | <expr> '+' <term> // 시작 non-terminal <term> ::= <factor> | <term> '*' <factor> <factor> ::= <number> <number> ::= <digit> | <digit> <number> <digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

문자열 1+2∗31+2*3에 대해 해당 문법을 기반으로 파싱하면 다음과 같이 될 것이다. 굵은 글씨는 non-terminal, 일반 텍스트는 terminal 노드다. 간략화를 위해 수를 <digit>에서 <number>로 변환하는 부분은 생략한다.
1+2∗3⇒P1+2∗number⇒P1+2∗factor⇒P1+number∗factor⇒P1+factor∗factor⇒P1+term∗factor⇒P1+term⇒Pnumber+ term⇒Pfactor+ term⇒Pterm+ term⇒Pexpr+term⇒Pexpr \begin{array}{c|l} 1 + 2 * 3 &\Rightarrow_P 1 + 2 * \textbf{number} \\ &\Rightarrow_P 1 + 2 * \textbf{factor} \\ &\Rightarrow_P 1 + \textbf{number} * \textbf{factor} \\ &\Rightarrow_P 1 + \textbf{factor} * \textbf{factor} \\ &\Rightarrow_P 1 + \textbf{term} * \textbf{factor} \\ &\Rightarrow_P 1 + \textbf{term} \\ &\Rightarrow_P \textbf{number} + \, \textbf{term} \\ &\Rightarrow_P \textbf{factor} + \, \textbf{term} \\ &\Rightarrow_P \textbf{term} + \, \textbf{term} \\ &\Rightarrow_P \textbf{expr} + \textbf{term} \\ &\Rightarrow_P \textbf{expr} \end{array}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.3. 파스 트리(parse tree)[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
상세 내용 아이콘   자세한 내용은 구문 트리 문서의 완전 구문 트리 부분을 참고하십시오.
parse tree 1
위는 파싱 예시를 기반으로 한 parse tree로, 문자열의 유도 과정을 나타내는 트리다. 루트 노드는 시작 non-terminal이며, 내부 노드 역시 non-terminal로 이루어진다. 단말 노드만이 문자열에 직접 나오는 terminal로 구성된다.

이 파스 트리를 루트에서 단말 노드까지 아래 방향으로 읽으면 문법 규칙에 따라 문자열을 생성하는 유도(derivation) 과정이 된다. 반대로 단말 노드에서 루트 방향까지 읽으면, 주어진 토큰들을 상위의 non-terminal로 변환하는 파싱(parsing) 과정이 된다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. 모호성(ambiguity)[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
아래 문법에 대해
<expr> ::= <expr> '+' <expr> | <expr> '-' <expr> | <number> // 시작 non-terminal <number> ::= <digit> | <digit> <number> // <number>는 예시 부분과 동일

문자열 3−2+13 - 2 + 1을 유도한다고 하자. 위의 BNF를 기반으로 좌측 유도(Leftmost derivation)와 우측 유도(Rightmost derivation)을 수행하면 아래와 같이 다른 형태의 파스 트리가 구성되는 것을 확인할 수 있다.
좌측 유도
파스 트리
expr⇒Dexpr−expr⇒Dnumber−expr⇒D3−expr⇒D3−expr + expr⇒D3−number+expr⇒D3−2+expr⇒D3−2+number⇒D3−2+1 \begin{array}{c|l} \textbf{expr} & \Rightarrow_D \textbf{expr} - \textbf{expr} \\ & \Rightarrow_D \textbf{number} - \textbf{expr} \\ & \Rightarrow_D3 - \textbf{expr} \\ & \Rightarrow_D 3 - \textbf{expr + expr}\\ & \Rightarrow_D 3 - \textbf{number} + \textbf{expr}\\ & \Rightarrow_D 3 - 2+\textbf{expr} \\ & \Rightarrow_D 3 - 2+\textbf{number} \\ & \Rightarrow_D 3 - 2+1 \\ \end{array}
leftmost parse
우측 유도
파스 트리
expr⇒Dexpr+expr⇒Dexpr+number⇒Dexpr+1⇒Dexpr−expr+1⇒Dexpr−number+1⇒Dexpr−2+1⇒Dnumber−2+1⇒D3−2+1 \begin{array}{c|l} \textbf{expr} & \Rightarrow_D \textbf{expr} + \textbf{expr} \\ & \Rightarrow_D \textbf{expr} + \textbf{number} \\ & \Rightarrow_D \textbf{expr} + 1 \\ & \Rightarrow_D \textbf{expr} - \textbf{expr} + 1 \\ & \Rightarrow_D \textbf{expr} - \textbf{number} + 1 \\ & \Rightarrow_D \textbf{expr} - 2 + 1 \\ & \Rightarrow_D \textbf{number} - 2 + 1 \\ & \Rightarrow_D 3 - 2 + 1 \\ \end{array}
rightmost parsep...

위와 같이 어떤 문법 GG에 대해 특정 문장이 2개 이상의 서로 다른 파스 트리를 가지면 문법 GG는 모호하다(ambiguous)고 한다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3.1. 모호성 해결 방법[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
연산자의 우선순위와 결합 법칙을 기반으로 파스 트리가 모호하지 않게 수정할 수 있다.
  • 문법 수정을 위해서 각 연산자마다 새로운 non-terminal을 만들고 시작 non-terminal부터 가장 낮은 우선순위를 가진 연산자를 적용한다.
  • 결합 법칙 상으로는 좌측 결합이면 left recursion, 우측 결합이 되면 right recursion을 적용한다. 예를 들어 모호성 문단의 BNF는 +, - 연산자가 동일한 우선순위를 가지며 좌측 결합이고, **를 Python의 제곱 연산자라고 하면, +, -보다 높은 우선순위를 가지며 우측결합이다. 이를 기반으로 BNF를 다음과 같이 수정하면, 모호성이 해결된다. 
    <expr> ::= <expr> '+' <term> | <expr> '-' <term> | <term> // +, -은 좌측 결합이므로 left recursion 적용 <term> ::= <number> '**' <term> | <number> // 제곱 연산은 우측 결합이므로 right recursion 적용 <number> ::= <digit> | <digit> <number> // <number>는 예시 부분과 동일
위 수정된 문법에 대해 문자열 3−2+13-2+1을 파스 트리로 구성하면, expr⇒Dexpr+term\textbf{expr} \Rightarrow_D \textbf{expr} +\textbf{term}으로 시작하는 경우만 해당 문자열로 유도되며 expr⇒Dexpr−term\textbf{expr} \Rightarrow_D \textbf{expr} - \textbf{term}으로 시작하는 경우는 유도되지 않는다. 식 1+2 ** 31+2 \text{ ** } 3도 이전 방법은 (1+2) ** 3(1+2)\text{ ** }3, 1+(2 ** 3)1+(2 \text{ ** } 3) 두 가지로 파스 트리가 구성될 수 있었지만 위와 같이 결합 법칙을 기반으로 수정하면 모호성이 해결된다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3.1.1. 예제 1[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

C언어의 포인터와 증가 연산자(++)에 대한 문법을 생각해보자.
<expr> ::= <expr> '++' | '++' <expr> | '*' <expr> | <expr> '+' <expr> | id

이 문법에 대해 *p++라는 표현식은 (*p)++인지 *(p++)인지에 따라 결과가 완전히 달라진다.[2] 아래의 우선순위를 가지며 문법이 모호하지 않도록 문법을 재작성해보자.
  • 후위 증가 연산자(id++)가 가장 높은 우선순위를 갖는다.
  • 전위 증가 연산자(++id)와 역참조 연산자(*)는 후위 연산자보다 낮고, 이항 연산자 +보다는 높은 우선순위를 갖는다.
  • 전위 증가 연산자와 역참조 연산자들은 서로 같은 우선순위 레벨에 있으며, 우측결합한다.
  • 이항 연산자 +는 가장 낮은 우선순위를 가지며 좌측결합한다.

[풀이]
  • 연산자 우선 순위는 (후위 증가 연산자 > 전위 증가 연산자 = 역참조 연산자 > 이항 연산자)다.
  • 좌측 결합하는 연산자는 후위 증가 연산자, 이항 연산자, 나머지는 우측 결합한다.

이 연산자 우선 순위와 결합 방향을 정리하면 다음과 같이 나온다. 
<expr> ::= <expr> '+' <unary_expr> | <unary_expr> <unary_expr> ::= '++' <unary_expr> | '*' <unary_expr> | <postfix_expr> <postfix_expr>::= <postfix_expr> '++' | id
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3.1.2. 예제 2[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

이 문법은 문자열 if E1 then if E2 then S1 else S2 에 대해
  • if E1 then (if E2 then S1 else S2)
  • if E1 then (if E2 then S1) else S2
두 가지로 해석될 수 있어서 모호하다.[3]

<stmt> ::= 'if' <expr> 'then' <stmt> | 'if' <expr> 'then' <stmt> 'else' <stmt>

이 문법을 수정해서 else가 가장 가까운 then과만 짝이 되어 유도되도록 해보자. 즉 if E1 then (if E2 then S1 else S2)으로만 유도되도록 해야 한다.

[풀이]

우선 if-then-else로 짝을 이루는 문장을 'matched statement', if-then으로 끝나는 문장을 else랑 매칭이 안 된 'unmatched statement'라고 하자. 이 두 statement에 대해 논터미널을 정의해서 문법을 다음과 같이 만들면 된다. 
<stmt> ::= <matched_stmt> | <unmatched_stmt> <matched_stmt> ::= 'if' <expr> 'then' <matched_stmt> 'else' <matched_stmt> <unmatched_stmt>::= 'if' <expr> 'then' <stmt> | 'if' <expr> 'then' <matched_stmt> 'else' <unmatched_stmt>

if 다음에 then이 오고, 그 뒤에는 반드시 <matched_stmt>만 올 수 있도록 강제하였다. if E1 then if E2 then S1 else S2 같은 문장은 if E1 then (if E2 then S1 else S2) 로만 해석될 수 있다. 안쪽의 if E2 then S1 else S2는 이미 else 절을 포함하여 완벽한 matched statement이기 때문이다.

이렇게 되면, if...then...else... 형태의 문장이 되려면, then 절에 들어가는 내용물 역시 else에 대한 모호함 없이 완전하게 된다. 만약 if E1 then ... 에서 then 뒤에 if E2 then S1 같은 짝 없는 문장이 온다면, 그건 if E1 then의 else를 잡아먹을 수 있는 가능성이 생길 것이다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4. 파싱 방식[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Top-down
topdown-intro-1
Bottom-up
bottomup-intro-0
파서의 구조는 크게 하향식(Top-down) 방식과 상향식(Bottom-up) 방식으로 나눌 수 있다. 상향식은 루트 노드에서부터 leaf 노드를 생성해나가는 방식이다. 좌측 유도 순서의 생성 규칙을 적용한다.

하향식은 leaf 노드들로부터 루트 노드 쪽으로 위로 생성해나가는 방식이다. 우측 유도의 역순의 생성규칙을 적용한다. 유도 자체는 우측부터 하지만 입력 문자열은 왼쪽부터 진행해 나가기 때문이다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.1. 하향식 파서(Top-down Parser)[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  • Recursive Descent Parser
  • Predictive Parser
    • LL(1)
    • LL(k)
    • LL(*): ANTLR4에서 사용하는 파싱 방식이다.
상세 내용 아이콘   자세한 내용은 파싱/하향식 문서를 참고하십시오.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.2. 상향식 파서(Bottom-up Parser)[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  • Shift-Reduce Parser
    • LR(0)
    • SLR(1), Simple LR(1)
    • CLR(1), Canonical LR(1)
    • LALR(1), LookAhead LR(1)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5. 관련 문서[편집]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
[1] 예를 들어 괄호, 세미콜론 등[2] 결과에 대한 내용은 해당 코드의 출력 참조[3] 이 문제를 흔히 'dangling else'라고 한다.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

크리에이티브 커먼즈 라이선스
이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외)
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.

나무위키는 백과사전이 아니며 검증되지 않았거나, 편향적이거나, 잘못된 서술이 있을 수 있습니다.
나무위키는 위키위키입니다. 여러분이 직접 문서를 고칠 수 있으며, 다른 사람의 의견을 원할 경우 직접 토론을 발제할 수 있습니다.

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
더 보기