Compiler 3 - Syntax analyzer & Context Free Language

Syntax analyzer(parser) : lexical analyzer에서 set of token을 받아 문법 확인. (validation of given set of token's structure) 만약 문법이 틀렸다면 에러를 사용자에게 알리고, 문법이 올바르다면 parse tree를 제작하여 token sequence의 grammatical structure를 나타낸다.

이런 과정은 Context free grammar를 통해 이루어진다. 이를 통해 valid token set의 rule을 정의하고, valid / invalid token set을 구분한다. (Lexical analyzer의 step과 동일)

Context free grammar
Regular expression으로 나타낼 수 없는 조금 더 복잡한 것들을 나타낼 수 있으므로 모든 문법적 규칙을 정의할 수 있다. (paren의 짝을 맞추는 등의 작업, 정의되지 않은 개수를 세는 등의 작업은 RL로 불가능)

CFG는 terminal(basic symbol, token, can't be replaced)과 non-terminal로 구분된다. 그리고 non-terminal 을 terminal로 분해하는 것이 production(parsing, replacement rules) 과정이 된다. 그리고 이런 parsing의 시작점은 start symbol이 된다.

A -> a : A는  non-terminal, a는 terminal/non-terminal/epsilon이 가능하다. 일반적으로 non-terminal은 대문자로, terminal은 소문자로, sequence of non-terminal/terminal/epsilon은 alpha, beta 등으로 표기한다.

- Derivation(=>) : sequence of replacement. 주어진 string에 대해 production rule을 적용하는 과정. star closure를 붙이면 여러 개의 replace를 요약하여 나타낼 수 있다.(=>*)
derivation은 어느 쪽의 non-terminal을 먼저 선택하느냐에 따라 leftmost와 rightmost로 구분된다.
(가장 왼쪽의 non terminal을 선택하여 replace하면 leftmost)
어느 방법을 사용하느냐에 따라서 top-down / bottom-up의 구현이 달라지게 된다.

- Sentinel form : 어떤 start symbol G에서 =>*를 통해 alpha로 도달하면 alpha는 G의 sentinel form이다.

- Sentence : 어떤 alpha가 terminal로만 이루어진 sentinel form일 경우 alpha는 CFG G의 sentence라 한다.

- Language : 어떤 CFG G에 의해 정의된 language는 G의 sentence alpha의 set이다.
따라서 어떤 input string이 L(G)에 있다면 해당 input string은 CFG G에서 valid하다고 말할 수 있다. 따라서 given token이 valid한지 밝혀 내려면 given token set이 CFG G에서 derive되는지를 확인하면 된다.

이는 derivation과정을 parse tree로 나타내면 된다. leaf node는 terminal이 되므로 inorder traversal을 하면 original string을 만들 수 있다. 이 때 주의할 점은 derivation 방법이 다르더라도 항상 동일한 parse tree가 나와야 한다는 것이다. (leftmost or rightmost derivation)

이런 parse tree가 syntax analyzer의 결과물이 되고, 이 값이 semantic analyzer로 들어가게 된다.


Efficient parsing
Non-ambiguous, no left recursion and only one choice for production steps (deterministic) 의 세 가지 특성을 가질 때 이를 good CFG로 정의하고, 효율적이고 정확한 파싱을 할 수 있다.

- Ambiguity
하나의 input string에 대해 서로 다른 parse tree를 가질 때, 이를 ambiguous하다고 한다. 왜냐하면 derivation 방법에 따라 서로 다른 parse tree가 만들어질 때, 동일한 input을 넣어도 상황에 따라 다른 것이 나올 수 있기 때문에 어느 것이 올바른지 알 수 없다.

모든 경우에 대해 이를 해결하는 알고리즘은 없기 때문에 모호한 grammar를 그렇지 않도록 고치는 작업이 필요하다.
그러나 일반적으로 arithmetic expression의 경우, operator의 priority가 존재하므로 이것을 이용하여 ambiguity를 해소할 수 있다.

* dangling-else ambiguity
가장 많이 발생하는 모호함 유형으로, if-else의 짝을 선택하는 방법에 따라 parse tree가 달라지는 경우가 발생한다. 이를 해결할 수 있는 한 방법은 각 else를 아직 매칭되지 않은 가장 가까운 if와 매칭하는 것이다.


- Left recursion
leftmost derivation를 사용하는 parser에 대해 left recursion(same non terminal in left)이 존재할 경우 무한루프에 빠지므로 이는 올바르지 않다. (top-down parsing의 경우, S -> Sa | b  leftmost derivation을 할 때 무한루프에 빠지게 된다) 이는 우리가 문자를 왼쪽부터 읽기 때문에 발생하는 문제로, bottom-up parser는 rightmost를 사용하긴 하지만 역시 우리가 문자를 읽는 일반적인 규칙에 따라 문자를 왼쪽부터 읽기 때문에 right recursive로 바꾼다고 해도 문제가 되지 않는다.

S -> Aa | b
A -> Sb

위와 같은 경우도 두 번의 production 후에 다시 S로 돌아오므로 (S->+ Sab) 여전히 left recursive이다.
이를 해결하는 알고리즘은 어떤 형태의 left recursion이 있을 때 두 개의 동등한 right recursion으로 분해하여 나타내는 것이다.

S -> Sa | b 형태의 left recursion은
S -> bA, S-> aA | epsilon 형태의 right recursion으로 풀어낼 수 있다.

- Left factoring
non-terminal의 production에 같은 input symbol로 시작하는 것이 여러 개 존재한다면, nondeterministic하므로 별로 좋지 않다. (어느 것이 올바른지 한 번 진행했다가 다시 돌아와야 한다.) 따라서 이를 해결하기 위해 하나의 production을 다른 symbol을 사용하여 분해하는 과정이 필요하다.

E -> T + E | T 의 예를 들어보면, 이를 분해하여
E -> TE'
E' -> +E | epsilon 와 같이 만드는 것이 더 효율적이다. 이 경우, 반드시 모든 경우에 대해 하나의 선택지 밖에 없으므로 한 번 갔다가 돌아오는 과정이 필요하지 않다.