Writing a Grammar

Lexical Versus Syntactic Analysis

• 어차피 regular expression은 다 grammar로 표현이 가능한데, 그러면 regular expression 왜씀? -> 이유:
  1. lexical and non-lexical로 나누는 것이 모듈화에 더 편리하다.
  2. lexical rules는 간단한 편이라서 grammar를 쓸 필요까지는 없다.
  3. grammar보다 token에 대해서 더 정확하고 이해하기 쉬운 notation을 가지고 있다.
  4. 더 효율적인 lexical analyzer는 grammar보다 regular expression으로부터 자동적으로 만들어질 수 있다.
• 예를 들면, balanced parentheses, if-then-else문 등과 같은 nested structure를 표현하는데에 grammar가 유리하다.

Elimination Ambiguity

• Ambiguity example
  
  위와 같은 grammar가 존재할 때, 아래의 문장은 여러 parse tree로 해석될 수 있다.
  
  
  • 그래서 보통은 else를 가장 가까운 then과 매치를 시켜주는 편이다.
  • 위 문법의 수정 버전 :
    
    • 아이디어 : then과 else 사이에는 if-then-else처럼 match된 구문만 올 수 있다.

Elimination of Left Recursion

• grammar : $left$ $recursive$ if it has a nonterminal $A$ such that there is a derivation $A$ $\overset{+}\Rightarrow$ $A\alpha$ for some string $\alpha$.

• Top-down parsing 방법은 left-recursive grammar를 다룰 수 없기 때문에, left recursion을 없애주어야 한다.

• immediate left recursion을 없애는 방법
  Group the productions as
  
  where no $\beta_i$ begins with an $A$.
  Replace the $A$-productions by
  
  이러고 나면, 실제로 표현하는 string은 동일하지만 left recursive하지는 않다.
  하지만 이 방법이 과연 진짜로 모든 left recursive를 없애줄까?

• 반례
  

  • $S$는 immediate left recursive는 아니지만, 구성 과정을 보면 $S$ $\Rightarrow$ $Aa$ $\Rightarrow$ $Sda$로, 실제로는 left recursive이다.

• Algorithm 4.19 : left recursion 없애기

  • INPUT : Grammar $G$ with no cycles or $\epsilon$-productions
  • OUTPUT : left recursion이 없어진 동일한 grammar
  • METHOD : 아래의 알고리즘을 $G$에 적용시킨다. Note that the resulting non-left-recursive grammar may have $\epsilon$-productions.
    
    • 당연히 이것만 보면 도대체 뭔 소리인지 모르겠다..
    • 하지만 induction의 관점에서 생각하면 이해하기가 편하다!
    • i = 1인 경우를 보면 내부 for문이 돌지 않게 되고, immediate left recursion만 제거되게 된다 -> $A_1\rightarrow A_j$, where j > 1의 꼴이 된다.
    • i = k인 경우를 보면 induction hypothesis에 의해 i <= k - 1인 경우 $A_i\rightarrow A_j$, where j > i인 상태이다.
      이 상태에서 내부 for문을 한번 돌 때마다 $A_k$는 $A_2$이상으로 생성되고, 또 한 번 돌면 $A_3$이상, 계속 반복하고 나면 $A_k$이상으로 생성되게 된다.
      그 이후에 $A_k$-production에서 left recursion을 제거하게 되면 $A_k$는 k + 1 이상으로 생성되게 된다.
    • 이 과정이 모두 끝나고 나면 모든 i에 대해 $A_i$는 $A_j$로 생성되는데, 이 때 j > i이다. 그러므로 left recursion은 발생하지 않게 된다.

Left Factoring

• Left-Factoring : predictive, 또는 top-down parsing을 위해 유용한 grammar 바꾸는 방법이다.
• Algorithm 4.21 : Left factoring a grammar
  • INPUT : Grammar $G$
  • OUTPUT : An equivalent left-factored grammar.
  • 
    이 방법을 어떠한 nonterminal이라도 common prefix를 갖지 않을 때 까지 반복하면 된다.

Non-Context-Free Language Constructs

• 일반적인 programming language는 grammar 하나로만 표현이 불가능하다.