파싱

#!if 넘어옴1 != null
'''파서'''{{{#!if 넘어옴2 == null
{{{#!if 넘어옴1[넘어옴1.length - 1] >= 0xAC00 && 넘어옴1[넘어옴1.length - 1] <= 0xD7A3
{{{#!if ((넘어옴1[넘어옴1.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴1[넘어옴1.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴1[넘어옴1.length - 1] < 0xAC00 || 넘어옴1[넘어옴1.length - 1] > 0xD7A3
은(는)}}}}}}{{{#!if 넘어옴2 != null
, ''''''{{{#!if 넘어옴3 == null
{{{#!if 넘어옴2[넘어옴2.length - 1] >= 0xAC00 && 넘어옴2[넘어옴2.length - 1] <= 0xD7A3
{{{#!if ((넘어옴2[넘어옴2.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴2[넘어옴2.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴2[넘어옴2.length - 1] < 0xAC00 || 넘어옴2[넘어옴2.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴3 != null
, ''''''{{{#!if 넘어옴4 == null
{{{#!if 넘어옴3[넘어옴3.length - 1] >= 0xAC00 && 넘어옴3[넘어옴3.length - 1] <= 0xD7A3
{{{#!if ((넘어옴3[넘어옴3.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴3[넘어옴3.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴3[넘어옴3.length - 1] < 0xAC00 || 넘어옴3[넘어옴3.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴4 != null
, ''''''{{{#!if 넘어옴5 == null
{{{#!if 넘어옴4[넘어옴4.length - 1] >= 0xAC00 && 넘어옴4[넘어옴4.length - 1] <= 0xD7A3
{{{#!if ((넘어옴4[넘어옴4.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴4[넘어옴4.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴4[넘어옴4.length - 1] < 0xAC00 || 넘어옴4[넘어옴4.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴5 != null
, ''''''{{{#!if 넘어옴6 == null
{{{#!if 넘어옴5[넘어옴5.length - 1] >= 0xAC00 && 넘어옴5[넘어옴5.length - 1] <= 0xD7A3
{{{#!if ((넘어옴5[넘어옴5.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴5[넘어옴5.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴5[넘어옴5.length - 1] < 0xAC00 || 넘어옴5[넘어옴5.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴6 != null
, ''''''{{{#!if 넘어옴7 == null
{{{#!if 넘어옴6[넘어옴6.length - 1] >= 0xAC00 && 넘어옴6[넘어옴6.length - 1] <= 0xD7A3
{{{#!if ((넘어옴6[넘어옴6.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴6[넘어옴6.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴6[넘어옴6.length - 1] < 0xAC00 || 넘어옴6[넘어옴6.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴7 != null
, ''''''{{{#!if 넘어옴8 == null
{{{#!if 넘어옴7[넘어옴7.length - 1] >= 0xAC00 && 넘어옴7[넘어옴7.length - 1] <= 0xD7A3
{{{#!if ((넘어옴7[넘어옴7.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴7[넘어옴7.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴7[넘어옴7.length - 1] < 0xAC00 || 넘어옴7[넘어옴7.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴8 != null
, ''''''{{{#!if 넘어옴9 == null
{{{#!if 넘어옴8[넘어옴8.length - 1] >= 0xAC00 && 넘어옴8[넘어옴8.length - 1] <= 0xD7A3
{{{#!if ((넘어옴8[넘어옴8.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴8[넘어옴8.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴8[넘어옴8.length - 1] < 0xAC00 || 넘어옴8[넘어옴8.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴9 != null
, ''''''{{{#!if 넘어옴10 == null
{{{#!if 넘어옴9[넘어옴9.length - 1] >= 0xAC00 && 넘어옴9[넘어옴9.length - 1] <= 0xD7A3
{{{#!if ((넘어옴9[넘어옴9.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴9[넘어옴9.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴9[넘어옴9.length - 1] < 0xAC00 || 넘어옴9[넘어옴9.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴10 != null
, ''''''{{{#!if 넘어옴10[넘어옴10.length - 1] >= 0xAC00 && 넘어옴10[넘어옴10.length - 1] <= 0xD7A3
{{{#!if ((넘어옴10[넘어옴10.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴10[넘어옴10.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴10[넘어옴10.length - 1] < 0xAC00 || 넘어옴10[넘어옴10.length - 1] > 0xD7A3
은(는)}}}}}} 여기로 연결됩니다. 

#!if 설명 == null && 리스트 == null
{{{#!if 설명1 == null
다른 뜻에 대한 내용은 아래 문서를}}}{{{#!if 설명1 != null
{{{#!html 파서(巴西)}}}에 대한 내용은 [[브라질]] 문서{{{#!if (문단1 == null) == (앵커1 == null)
를}}}{{{#!if 문단1 != null & 앵커1 == null
의 [[브라질#s-|]]번 문단을}}}{{{#!if 문단1 == null & 앵커1 != null
의 [[브라질#|]] 부분을}}}}}}{{{#!if 설명2 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단2 == null) == (앵커2 == null)
를}}}{{{#!if 문단2 != null & 앵커2 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단2 == null & 앵커2 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명3 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단3 == null) == (앵커3 == null)
를}}}{{{#!if 문단3 != null & 앵커3 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단3 == null & 앵커3 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명4 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단4 == null) == (앵커4 == null)
를}}}{{{#!if 문단4 != null & 앵커4 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단4 == null & 앵커4 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명5 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단5 == null) == (앵커5 == null)
를}}}{{{#!if 문단5 != null & 앵커5 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단5 == null & 앵커5 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명6 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단6 == null) == (앵커6 == null)
를}}}{{{#!if 문단6 != null & 앵커6 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단6 == null & 앵커6 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명7 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단7 == null) == (앵커7 == null)
를}}}{{{#!if 문단7 != null & 앵커7 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단7 == null & 앵커7 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명8 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단8 == null) == (앵커8 == null)
를}}}{{{#!if 문단8 != null & 앵커8 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단8 == null & 앵커8 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명9 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단9 == null) == (앵커9 == null)
를}}}{{{#!if 문단9 != null & 앵커9 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단9 == null & 앵커9 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명10 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단10 == null) == (앵커10 == null)
를}}}{{{#!if 문단10 != null & 앵커10 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단10 == null & 앵커10 != null
의 [[#|]] 부분을}}}}}}

#!if 설명 == null
{{{#!if 리스트 != null
다른 뜻에 대한 내용은 아래 문서를}}} 참고하십시오.

#!if 리스트 != null
{{{#!if 문서명1 != null
 * {{{#!if 설명1 != null
파서(巴西): }}}[[브라질]] {{{#!if 문단1 != null & 앵커1 == null
문서의 [[브라질#s-|]]번 문단}}}{{{#!if 문단1 == null & 앵커1 != null
문서의 [[브라질#|]] 부분}}}}}}{{{#!if 문서명2 != null
 * {{{#!if 설명2 != null
: }}}[[]] {{{#!if 문단2 != null & 앵커2 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단2 == null & 앵커2 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명3 != null
 * {{{#!if 설명3 != null
: }}}[[]] {{{#!if 문단3 != null & 앵커3 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단3 == null & 앵커3 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명4 != null
 * {{{#!if 설명4 != null
: }}}[[]] {{{#!if 문단4 != null & 앵커4 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단4 == null & 앵커4 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명5 != null
 * {{{#!if 설명5 != null
: }}}[[]] {{{#!if 문단5 != null & 앵커5 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단5 == null & 앵커5 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명6 != null
 * {{{#!if 설명6 != null
: }}}[[]] {{{#!if 문단6 != null & 앵커6 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단6 == null & 앵커6 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명7 != null
 * {{{#!if 설명7 != null
: }}}[[]] {{{#!if 문단7 != null & 앵커7 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단7 == null & 앵커7 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명8 != null
 * {{{#!if 설명8 != null
: }}}[[]] {{{#!if 문단8 != null & 앵커8 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단8 == null & 앵커8 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명9 != null
 * {{{#!if 설명9 != null
: }}}[[]] {{{#!if 문단9 != null & 앵커9 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단9 == null & 앵커9 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명10 != null
 * {{{#!if 설명10 != null
: }}}[[]] {{{#!if 문단10 != null & 앵커10 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단10 == null & 앵커10 != null
문서의 [[#|]] 부분}}}}}}

1. 개요

2. 과정

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

2.1. 어휘 분석(lexing)

#!syntax cpp
int x = 2 + 3;
int y = x - 5;

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[어휘 분석#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
의 [[어휘 분석#|]] 부분을

2.2. 구문 분석(parsing)

2.2.1. 예시

#!syntax java
<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'

2.3. 파스 트리(parse tree)

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[구문 트리#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
의 [[구문 트리#완전 구문 트리|완전 구문 트리]] 부분을

3. 모호성(ambiguity)

#!syntax java
<expr> ::= <expr> '+' <expr> | <expr> '-' <expr> | <number> // 시작 non-terminal
<number> ::= <digit> | <digit> <number> // <number>는 예시 부분과 동일

좌측 유도	파스 트리
[math( \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})]

우측 유도

파스 트리

[math( \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} )]

3.1. 모호성 해결 방법

• 문법 수정을 위해서 각 연산자마다 새로운 non-terminal을 만들고 시작 non-terminal부터 가장 낮은 우선순위를 가진 연산자를 적용한다.
• 결합 법칙 상으로는 좌측 결합이면 left recursion, 우측 결합이 되면 right recursion을 적용한다. 예를 들어 모호성 문단의 BNF는 +, - 연산자가 동일한 우선순위를 가지며 좌측 결합이고, **를 Python의 제곱 연산자라고 하면, +, -보다 높은 우선순위를 가지며 우측결합이다. 이를 기반으로 BNF를 다음과 같이 수정하면, 모호성이 해결된다.
  {{{#!syntax java
  <expr> ::= <expr> '+' <term> | <expr> '-' <term> | <term> // +, -은 좌측 결합이므로 left recursion 적용

#!syntax java
<expr> ::= <expr> '++'
       | '++' <expr>
       | '*' <expr>
       | <expr> '+' <expr>
       | id

[풀이]

----

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

이 연산자 우선 순위와 결합 방향을 정리하면 다음과 같이 나온다.

#!syntax java
<expr>        ::= <expr> '+' <unary_expr> | <unary_expr>
<unary_expr>  ::= '++' <unary_expr> | '*' <unary_expr> | <postfix_expr>
<postfix_expr>::= <postfix_expr> '++' | id

#!syntax java
<stmt> ::= 'if' <expr> 'then' <stmt>
         | 'if' <expr> 'then' <stmt> 'else' <stmt>

[풀이]

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

#!syntax java
<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

Bottom-up

4.1. 하향식 파서(Top-down Parser)

• Recursive Descent Parser
• Predictive Parser
• LL(1)
• LL(k)
• LL(*): ANTLR4에서 사용하는 파싱 방식이다.

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[파싱/하향식#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
의 [[파싱/하향식#|]] 부분을

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. 관련 문서

• 배커스-나우르 표기법
• 오토마타
• 유한 상태 기계
• 푸시다운 오토마타
• 컴파일러
• 프로그래밍 언어론
• 직접 관련된 개념
• FIRST와 FOLLOW 집합