[프로그래밍언어] - Context-Free grammar

📜 Parser

📢 Parser의 역할

• Parser는 scanner로부터 tokenized 된 word stream을 받아 syntax를 확인하고, 올바른 syntax라면 중간 표현(Intermediate Representation, IR)을 도출해내는 컴파일러 프론트엔드의 부분이다.

📢 Context-Free grammar

• 문맥에 상관없이 어떤 Non-Terminal이 들어와도 그에 대한 production-rule이 존재하는 문법을 Context-Free grammar(CFG)라고 한다.
• CFG는 각각 4개의 요소로 정의될 수 있는데, (CFG = <S, N, T, P>)

  1. Starting non-terminal : 문법을 시작하는 non-terminal이다.
  2. Non-terminal : 다른 표현으로 derivation 될 수 있는 표현
  3. Terminal : 다른 표현으로 derivation 되지 않고, input에 포함될 수 있는 표현
  4. Production Rule : derivation rule을 정의

📢 Derivation

• Non-terminal들을 적절한 production-rule을 사용하여 다른 표현으로 치환하는 것을 derivation이라고 하며, derivation은 몇번이고 반복 할 수 있다.
• 이 적절한 derivation을 찾는 과정을 Parsing이라고 한다.
• Derivation은 가장 왼쪽의 Non-terminal부터 치환하는 Leftmost Derivation과 가장 오른쪽의 Non-terminal부터 치환하는 Rightmost Derivation이 있다.

👍 Leftmost Derivation과 Rightmost Derivation은 결국에 같은 표현으로 derive하지만, Parse tree의 형태는 다르게 나타나고, 이는 곧 다른 evaluation order를 의미한다!

e.g). x - 2 * y; 를 해당 grammar로 파싱했을 때
1. Leftmost Derivation으로 parsing 했을 경우

2. Rightmost Derivation으로 parsing했을 경우
   

• 같은 grammar로 parsing 했지만 derivation 방향에 따라 parsing tree의 모양이 다르게 나타났다.
• Leftmost derivation의 경우, 먼저 계산해야 하는 2 y가 parse tree의 밑에 깔리게 된다. => dfs로 parse tree를 순회할 때, 2 y의 계산 값이 return된후 x - 를 계산해야 하므로 parse tree의 밑에 깔려야 우선적으로 계산이 된다.

vs 📢 Reduction?

• 추후 공부할 Bottom-up parsing 에서 사용하며, reduction은 derivation의 완벽한 역과정이다.

👍 Derivation: e.g) A를 aB로 치환 (terminal을 sentential expr로)
👍 Reduction: e.g) aB를 A로 치환 (Sentential expr를 terminal로)

📢 Precedence in Derivations

• Leftmost Derivation과 Rightmost Derivation은 모두 derivation 의 우선순위 을 지정해주지 않으면 parse tree가 다른 형태로 나오기 때문에 문제가 발생한다.
• Derivation의 우선순위를 지정해주는 방법에는 세가지가 있는데,

  1. 우선순위마다 non-terminal을 추가
  2. 문법 분리
  3. 우선순위에 있는 expression을 먼저 parsing하도록 parser 강제

• 해당 문법은 Non-terminal Term과 Factor를 추가해서 연산자끼리의 우선순위를 부여해 주었다. 우선순위가 높은 곱하기와 나누기 연산자가 parse tree의 밑에 깔리게 되고, 가장 먼저 계산이 될 수 있게 된다.
• 해당 문법으로 parsing한다면, leftmost/rightmost에 상관없이 똑같은 parsing tree가 나오게 된다. Why? Grammar에 우리가 필요한
  precedence를 적용해 주었기 때문!

📢 Ambiguous Grammar
📜 정의

• 특정 derivation의 방향으로 derivation을 진행 할 때, 특정 production rule이 적용되지 않고 여러개의 production rule을 적용해도 똑같이 parsing 될 때 ambiguous grammar라고 할 수 있다.

E -> E op E | x 인 grammar가 있다고 가정 할 때, 맨 앞의 E는 x 또는 E op E로 치환 될 수 있으며, 이때 어떤 production rule을 적용하더라도 똑같이 parsing에 성공하게 된다. 이때 이 grammar는 ambiguous하다고 할 수 있다.
👍 주의! Leftmost Derivation과 Rightmost Derivation으로 생성된 parse tree의 모양이 다른 것은 ambiguity와 관련이 없다. 이 특성은 precedence와 관련이 있다.

📜 Ambiguity의 예시: IF-THEN-ELSE(Dangling Else) 문제

IF E1 THEN IF E2 THEN S1 ELSE S2 라는 문장이 있다고 가정하면, 이는 두 가지 의미로 해석 될 수 있다.
📢 해석 1

IF E1:
THEN:
	IF E2: S1
ELSE: S2

📢 해석 2 - 참고) 대부분의 컴파일러는 이 방식을 채택함

IF E1:
THEN:
	IF E2: S1
	ELSE: S2

• 마지막 ELSE가 첫 번째 IF-THEN-ELSE 로 묶이는지, 아니면 첫 번째 THEN 안의 IF-ELSE로 묶이는지 확인이 불가능하다. (어떤 production rule을 써도 parsing이 가능하며 parse tree의 모양이 다르다. -> Ambiguous grammar
• Ambiguity를 없애는 방법은 grammar를 다시 쓰거나, precedence를 부여하면 해결할 수 있다...

📢 1. grammar를 다시 써보자

• 다시 쓴 grammar가 복잡해 보일 수 있으나, 해당 grammar의 핵심은 THEN과 ELSE 사이에는 IF-THEN-ELSE 구문만 들어 올 수 있다는 것이다.
• 이렇게 grammar를 다시 쓰게 되면 가장 마지막의 else는 해석 2와 같이 내부 if와 묶이게 된다.

📢 2. parsing precedence를 부여하자!

• 만일 derivation시 IF-THEN에 낮은 순위를 부여하고, reduction시 IF-THEN-ELSE에 높은 우선순위를 부여했다면?
  
• 위와 같이 reduction시 IF-THEN-ELSE에 우선순위를 부여하게 되면 자동적으로 else는 inner if와 묶이게 해석된다.