[PLT/프로그래밍언어론] 03. PL Principle 2

 

03. Principle 2

#PLT

이전 시간에 컴파일 Step에 대해 배웠다. 그 중 Syntax Analysis를 자세히 살펴보자.

문법 vs. 의미론 vs. 화용론

• 문법(Syntax)은 프로그램의 형식에 관한 것이다.
• 의미론(Semantics)은 프로그램의 의미에 관한 것이다.
• 화용론(Pragmatics)은 특정 맥락에서 프로그램의 의미를 다룬다.

예시: 톰과 제리

• 문법:
  • "쥐가 고양이를 차고 있다." ➞ 올바름!
  • "쥐 고양이를 차고 있다." ➞ 잘못됨!
• 의미론:
  • "쥐가 고양이를 차고 있다." ➞ "음, 잠깐만… 뭐라고?"
• 화용론:
  • "쥐는 제리, 고양이는 톰이다." ➞ "아하! 가능하군."

문법에 중점

• 세 가지 중, 이 강의에서는 문법에 더 중점을 둔다.
• 다른 것들에 대해 논의하기 전에, 프로그래밍 언어를 어떻게 정의할지 알아야 한다.
• 프로그램의 의미를 논하기 위해서는 먼저 올바르게 작성된 프로그램이 무엇인지 말할 수 있어야 한다.

형식 언어와 백우스-나우르 형식(BNF)

Formal Language and Backus Naur Form

형식 언어

• 현재 우리는 프로그램의 형식을 어떻게 정의할지에 더 관심이 있다.
• 프로그래밍 언어(PL)의 무엇이 올바르고 잘못된 것인지 어떻게 결정할 수 있는가?
• 주어진 코드가 PL에서 올바르게 작성되었는지 어떻게 알 수 있는가?
  • 즉, 주어진 코드에 문법 오류가 있는지 여부를 판단한다.
• 형식 언어(formal language)는 프로그래밍 언어의 일반적 특성을 추상화한 것이다.
• 형식 언어는 기호 집합(alphabet)과 이러한 기호를 결합하는 규칙(production rules)으로 구성된다.
  • 우리가 평소에 사용하는 한글, 영어… 랑 비슷함
• 이들은 형식 언어의 문법(grammar)으로 정의된다.
  

  E → E + E | E * E | N, N → 0N | 1N | λ
  

  
  
  • E 변수(lhs)를 E + E(rhs)로 Replace
  • | 는 OR 기호
  • 람다는 empty string을 의미
  • E => E + E => N + E => 0N + E => 0 + E => 0 + 1
    • 이 문법, 규칙은 binary number equation으로 나타낼 수 있다.

백우스-나우르 형식(Backus Naur Form, BNF)

• 원래는 백우스 정규형(Backus Normal Form)으로, 존 백우스(John Backus)가 개발했다.
  • Normal Form 이었다.
• 피터 나우르(Peter Naur)가 이를 확장해 사용하면서 백우스-나우르 형식(Backus-Naur Form)으로 이름이 변경되었고, 이는 도널드 크누스(Donald Knuth)가 제안했다.
  • Backus-Naur Form은 Normal Form은 아님
• 문맥 자유 문법(context-free grammer)을 위한 표기법이다.
  • context-free grammer : 프로그래밍 언어의 문법을 정의하기 위해 사용됨
• 언어 문법 기술(description)은 종종 BNF와 유사한 방법으로 제공된다.

BNF

• Variable(or nonterminals): 꺾쇠 괄호 <, >로 둘러싸인다.
  • 예시: <expression>, <term>, <operator>
  • 보통 lhs에 오는 것들.
• Terminal symbols(단말 기호): 아무런 표식 없이 나타낸다.
  • 예시: int, void, for
• ->를 대신 ::=를 사용해 표현한다.
  • 예시: A->B; 를 <A> ::= <B>;로 나타낸다
• |는 ‘or’을 나타낸다.
  • 예시: <bool-literal> ::= true | false는 파이썬에서 True | False임.

실수(Real Number) 예시

• <real-num> ::= <int-part>.<frac-part>
• <int-part> ::= <digit> | <int-part><digit>
• <frac-part> ::= <digit> | <digit><frac-part>
  • <frac-part> ::= <digit> | <frac-part><digit>으로 나타내도 결과는 똑같다.
• <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
• 시작 비단말기(start nonterminal)는 <real-num>이다.
• 시작 비단말기(start nonterminal)를 단말기 문자열(string of terminals)로 변환하는 과정을 파생(derivation)라고 한다.

좌측 유도(Left-most Derivation)

둘 이상의 논터미널이 있는 경우 항상 가장 왼쪽의 논터미널을 교체

예시: 3.14

<real-num> ⇒ <int-part>.<frac-part>
          ⇒ <digit>.<frac-part>
          ⇒ 3.<frac-part>
          ⇒ 3.1<frac-part>
          ⇒ 3.14

우측 유도(Right-most Derivation)

둘 이상의 논터미널이 있는 경우 항상 가장 오른쪽 논터미널을 교체

예시: (()) (프로그래밍 언어에서 { { } } 요런거에 해당. 우측 괄호 하나만 빠져도 문법적 오류가 발생한다.)

<balanced> ::= (<balanced>)<balanced> | ε // | 왼쪽거는 ( ( ) ) ( ( ) )에 해당
										// 입실론은 람다라고 생각하면 된다.
<balanced> ⇒ (<balanced>)<balanced>
           ⇒ (<balanced>)ε
           ⇒ (<balanced>)
           ⇒ ((<balanced>)<balanced>)
           ⇒ ((<balanced>)ε)
           ⇒ ((<balanced>))
           ⇒ ((ε))
           ⇒ (())

Extended BNF (EBNF)

• 간단히 말하면, EBNF는 BNF와 동일한 표현력을 갖지만 훨씬 더 간단하다.
• 추가 표기법을 사용한다.
  • {X}, [X], *, +, (X) 등.
• 장황하고 복잡한 BNF 표현식을 간략하게 만들어 이해를 돕는다.

EBNF 표기법

• {X}: X를 0번 이상 반복한다.

예시: BNF의 ::= ; | ε | ;를 EBNF로 표기

<statements> ::= {<statement>;} // 이렇게 간단하게 나타낼 수 있다.
<statements> =>* <statements>; ... <statements>;
<statements> =>* <statements>;
<statements> =>* ε

• [X]: X는 선택적이다. 정규 표현식 스타일로 '?'를 사용할 수 있다.

예시:

<signed> ::= [‘-’]<num>
<signed> ::= ‘-’?<num>
<num> ::= 1|2|3|4
<singed> =>* 1 <signed> =>* -1
<singed> =>* 2 <signed> =>* -4
...

• * 또는 +와 같은 정규 표현식도 사용할 수 있다.
  • 굳이 요건 외울 필요는 없음

예시:

<digits> ::= <digit>* // *: repeat 0 or more
	<digits> ::= {<digit>}
	<digits> =>* ε
	<digits> =>* <digit><digit>....<digit>
<digits> ::= <digit>+ // +: repeat at least once
	<digits> ::= <digit>{<digit>} // <digit> 1번 + {<digit>} 0번 이상 = 1번 이상

• (X): 그룹핑을 위해 사용된다. 기호들은 그룹 전체에 적용된다.

<eq> ::= <digits>(‘+’<digits>|-<digits>)+(‘ = ’<eq>)*

주의! ’+’와 그냥 +를 구분하자. terminal symbol인지!

• +, -는 0번 이상 반복된다.(?? 이해가 안감)
• 각 반복 시, + 또는 -를 선택할 수 있다.

예시:

<digits> + <digits> - <digits> + <digits>...

• 그 후, 또 다른 <eq>와 =으로 연결된 다른 식으로 계속할 수 있다.
  예시:

  <digits>+<digits> = <eq> = <eq>...
  

  • + 만 있어도 valid
  • + = 만 있어도 valid
  • + = = 만 있어도 valid

실수 다시 살펴보기 (BNF)

• BNF에서 실수(real number)의 전체 명세를 다시 살펴보자.
  

  <real-num> ::= ‘-’<num>|<num>
  <num> ::= <digits>|<digits>.<digits>
  <digits> ::= <digit>|<digit><digits>
  <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  

• EBNF에서는 실수의 표현을 다음과 같이 간단하게 나타낼 수 있다.
  

  <real-num> ::= [‘-’] <digit>+ [‘.’<digit>+]
  <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  

  • 실수를 나타낼 때 정수부에 최소 1개의 숫자는 필요하기 때문에 뒤에 +가 붙는다.
  • 소수부 .뒤에 나오는 뒤에 +가 붙는 이유도 마찬가지

참고) EBNF보다 훨씬 Extended 것도 있다.

• EBNF는 BNF보다 훨씬 간단하다.
• ?를 사용하여 선택적 요소를 나타낼 수 있다.
  

  <real-num> ::= ‘-’? <digit>+ (‘.’<digit>+)?
  

  • ‘.’은 terminal, 은 nonterminal

구문 분석과 모호성(Parsing and Ambiguity)

구문 분석(Parsing)

• 지금까지는 문법의 생성적 측면에 대해 이야기했다.
  • 주어진 문법 G에서 어떤 문자열 집합이 G에 의해 유도될 수 있는가?
• 주어진 문자열 s가 L(G)에 포함되는지 여부를 알고 싶다면 어떻게 할 것인가?
  • 우리가 코드로 문자열 s를 작성했을 때, valid 한지
• 구문 분석은 w ∈ L(G)가 어떻게 유도되는지에 대한 생성 규칙 시퀀스를 찾는 과정이다.
• 즉, w가 G에 의해 유도될 수 있는지 여부를 결정한다.
• 구문 분석 트리, 상향식 구문 분석, 하향식 구문 분석(Parse tree, top-down parsing, bottom-up parsing) 등이 이에 포함된다.

구문 분석 트리(Parse Tree)

• 표현식(또는 문자열)이 주어진 문법에 의해 유도될 수 있는지 확인하기 위해 구문 분석 트리를 만들 수 있다.
• 구문 분석 트리는 다음 조건을 만족해야 한다.
  • 모든 터미널 노드(리프 노드)는 터미널이거나 𝜀이어야 한다.
  • 모든 중간 노드는 비터미널이어야 한다.
  • 각 비터미널은 왼쪽 규칙에 위치하며, 오른쪽 규칙에 있는 항목들은 그 비터미널의 자식 노드가 된다.
  • 루트 노드는 시작 비터미널이다.

구문 분석 예시: 3.14

3.14 구문 분석 트리 생성 과정:

 

<int-part><digit>.<frac-part>는 3.14를 만족하지 못한다. <digit>.<frac-part>를 사용하자.

 

• 리프 노드를 연결하면 3.14를 얻는다.
• Internal node는 모두 nonterminal이다.
• 루트 노드는 non-terminal로 시작한다.

<real-num> ⇒ <int-part>.<frac-part>
            ⇒ <digit>.<frac-part>
            ⇒ 3.<frac-part>
            ⇒ 3.<digit><frac-part>
            ⇒ 3.1<frac-part>
            ⇒ 3.1<digit>
            ⇒ 3.14

하향식 구문 분석

• 하향식 구문 분석은 시작 비터미널(즉, 루트)에서 시작한다.
• 각 라운드에서 비터미널에 적용할 수 있는 모든 규칙을 확인한다.
• 그래서 모든 가능성을 시도하는 구문 분석(exhaustive search parsing)이라고도 한다.

예시:

<int-part> ::= <digit> | <int-part><digit>
<int-part>.<frac-part> ⇒ <digit>.<frac-part>
<int-part>.<frac-part> ⇒ <int-part><digit>.<frac-part>

하향식 구문 분석의 문제점

• 매우 지루한 작업이다.
  • 컴파일러에게 올바른 규칙을 찾을 때까지 모든 가능성을 시도하라고 요청하는 방식이므로, 비효율적이다.
  • 무한 루프에 빠질 가능성도 있다.
• 주어진 문자열이 주어진 문법으로 유도될 수 없을 때, 구문 분석이 끝나지 않을 수 있다.

상향식 구문 분석

• 반대로, 주어진 문자열의 터미널을 비터미널로 줄여나가는 방식이다.
• 예시: 3.14를 구문 분석할 때,
  • 3.14 ⇐ <digit>.14처럼 터미널을 비터미널로 줄여나간다.
• 보통 왼쪽부터 오른쪽으로 input을 읽으면서 nonterminal을 찾고 terminal로 대체한다.
  • 이 방식은 컴파일러에서 주로 사용된다.

3.14의 상향식 구문 분석

3.14 ⇐ <digit>.14 ⇐ <int-part>.14 ⇐ <int-part>.<frac-part>

• <digit> 을 <int-part>로 바꿀 때 애매한 점이 존재한다. 아래에서 자세히 알아보고, 일단 먼저 과정을 쭉 살펴보자

<int-part> ::= <digit> | <int-part><digit>
<frac-part> ::= <digit> | <digit><frac-part>

 

 

 

모호성(Ambiguity)

• 만약 두 개 이상의 생성 규칙이 존재할 때, 어느 규칙을 적용해야 할까?
  • 예시: 3.14에서 <digit>은 두 가지 비터미널로 축소될 수 있다.
  
  

  <int-part> ::= <digit> | <int-part><digit>
  <frac-part> ::= <digit> | <digit><frac-part>
  

• 이 경우, <int-part>를 선택해야만 주어진 문자열을 구문 분석할 수 있다.
  • 만약 두 선택이 모두 문자열을 구문 분석할 수 있게 만든다면 어떻게 될까?

모호성 예시

다른 예를 생각해보자:

<expr> ::= <expr> + <expr> | <expr> * <expr> | a | b | c

 

• a + b * c를 구문 분석할 때, 먼저 <expr> + <expr>를 적용할지 <expr> * <expr>를 적용할지에 따라 두 개의 구문 분석 트리가 생긴다.

• 만약 PL이 같은 input에 대해 1개보다 많은 Parse tree를 가진다면, ‘ambigous’ 라고 부른다

• 모호성을 해결하는 한 가지 방법은 문법을 재작성하는 것이다.
• 예시에서 a + b * c의 경우, 연산자 우선순위를 고려해야 한다.
  • 이 방식은 문법이 아닌 의미론에 속하며, 문법적으로 올바른 문장이 의미론적으로도 올바르게 설계되어야 한다.

모호성 해결 예시

모호성을 해결하는 한 가지 방법은 문법을 재작성하는 것이다.

a + b * c 예시를 다시 생각해보자.

<expr> ::= <expr> + <expr>
		| <expr> * <expr>
		| a | b | c

우리는 +와 * 중 어떤 것을 먼저 고려해야 할 지에 따라서 이 표현식이 두 개의 parse tree를 가지는 것을 안다.

새로운 비터미널을 도입하여 모호성을 해결할 수 있다.

<expr> ::= <expr> + <term> | <term>
<term> ::= <term> * <var> | <var>
<var> ::= a | b | c

• 이 예시는 모호성을 해결하기 그리 어렵지 않지만, 대부분의 경우 문법이 모호한지 여부를 판단하고 해결하는 것은 매우 어려운 일이다.
  • 의미론적인 레벨에서 연산자 우선순위를 고려하는 이유이다.

 

정리

문법(Syntax)은 프로그램의 형식에 관한 것이다.
의미론(Semantics)은 프로그램의 의미에 관한 것이다.
화용론(Pragmatics)은 특정 맥락에서 프로그램의 의미를 다룬다.

올바르게 작성된 프로그램인지 확인하기 위해 Syntax 오류가 있는지 확인해야 한다.

형식 언어(formal language)는 프로그래밍 언어의 일반적 특성을 추상화한 것이다.
백우스 형식 언어를 확장한게 BNF이다.

백우스-나우르 형식(Backus Naur Form, BNF)는 문맥 자유 문법(context-free grammars)을 위한 표기법이다.

• Variable(or nonterminals): 꺾쇠 괄호 <, >로 둘러싸인다.
  • , ,
• Terminal symbols: 아무런 표식 없이 나타낸다.
  • int, void, for…
• ->를 대신 ::=를 사용해 표현한다. (치환)
  • <논터미널 기호> ::= 대체될 문자열
• |는 ‘or’을 나타낸다. (선택)
  • ::= "abc"와 ::= "def"  ::= "abc" | "def"
• “”는 공문자열 입실론(or 람다)와 같음

파생(derivation)

start nonterminal를 string of terminals로 변환하는 과정

Left-most Derivation(좌측우선 유도)
둘 이상의 논터미널이 있는 경우 항상 가장 왼쪽의 논터미널을 교체

Right-most Derivation(우측우선 유도)
둘 이상의 논터미널이 있는 경우 항상 가장 오른쪽의 논터미널을 교체

Extended BNF (EBNF)
BNF와 동일한 표현력을 갖지만 훨씬 더 간단하다.
{X}, *: X를 0번 이상 반복한다.
[X]: X는 선택적이다. 정규 표현식 스타일로 '?'를 사용할 수 있다.
(X): 그룹핑을 위해 사용된다. 기호들은 그룹 전체에 적용된다.
+ : 1번 이상 반복
[] ? : 선택사항임. 0 또는 1번

EBNF로 변환할 때 주의점

1. 대부분의 |는 제거된다.
2. 중복되는 요소가 하는 일이 오직 조건을 구체화하는 것이라면, 그것들은 제거된다.
3. 대부분의 재귀적 요소는 제거되고 { } 루프로 대체된다.
4. null을 뜻하는 입실론(ε)이 없어진다.

Parsing
Parsing은 w ∈ L(G)가 어떻게 유도되는지에 대한 생성 규칙 시퀀스를 찾으면서 w가 G에 의해 유도될 수 있는지 여부를 결정한다. 이를 위해 Parse Tree를 사용한다.

Parse Tree는 다음 조건을 만족해야 한다.

• 모든 터미널 노드(리프 노드)는 터미널이거나 𝜀이어야 한다.
• 모든 중간 노드는 비터미널이어야 한다.
• 각 비터미널은 왼쪽에 위치하며, 오른쪽에 있는 항목들은 그 비터미널의 자식 노드가 된다.
• 루트 노드는 시작 비터미널이다.

Top-down Parsing

• Top-down Parsing은 시작 비터미널(즉, 루트)에서 시작한다.
• 각 라운드에서 비터미널에 적용할 수 있는 모든 규칙을 확인한다.
• 그래서 모든 가능성을 시도하는 구문 분석(exhaustive search parsing)이라고도 한다.

Top-down Parsing의 문제점

• 컴파일러에게 올바른 규칙을 찾을 때까지 모든 가능성을 시도하라고 요청하는 방식이므로, 비효율적이다.
• 무한 루프에 빠질 가능성도 있다.
  • 주어진 문자열이 주어진 문법으로 유도될 수 없을 때, 구문 분석이 끝나지 않을 수 있다.

Bottom-up Parsing

• 반대로, 주어진 문자열의 터미널을 비터미널로 줄여나가는 방식이다.
• 보통 왼쪽부터 오른쪽으로 input을 읽으면서 nonterminal을 찾고 terminal로 대체한다.

Ambiguity (in Bottom-up parsing)
만약 두 개 이상의 생성 규칙이 존재할 때, 어느 규칙을 적용해야 할까?
만약 PL이 같은 input에 대해 2개 이상의 Parse tree를 가진다면, ‘ambigous’ 라고 부른다

• 모호성을 해결하는 한 가지 방법은 문법을 재작성하는 것이다.
  • ex) 새로운 비터미널을 도입하여 모호성을 해결할 수 있다.
  • 이 방법은 매우 비효율적임 —> 의미론적 레벨로 넘어간다.