둘 다 토큰열을 왼쪽에서 오른쪽으로 한 번 읽으며 파스 트리를 만든다. 가르는 질문은 “어느 규칙을 쓸지를 언제 정하는가”다. LL은 규칙의 오른쪽을 보기 전에 다음 토큰 하나로 정한다. LR은 규칙의 오른쪽을 다 본 뒤에 정한다. 이 차이가 트리를 쌓는 방향, 받아 주는 문법의 넓이, 손으로 짜기 쉬운 정도를 함께 정한다.
어느 쪽일까
C1 (가) 문법 \(E \to E + T \mid T\), \(T \to id\)를 고치지 않고 그대로 쓰고 싶다. (나) 작은 설정 파일 언어의 파서를 도구 없이 손으로 빨리 짜고 싶다. 어느 쪽인가?
답: (가) LR. 이 문법은 왼쪽 기호가 자기 오른쪽의 맨 앞에 다시 나온다(좌재귀). LL은 E를 펼치려고 다시 E를 펼치게 되어 쓸 수 없고, LL(1) 표에서는 (E, id) 칸에 두 규칙이 겹친다. SLR 표에는 충돌이 없다. (나) LL. 재귀 하강 파서는 이해하기 쉽고 손으로 짜기 쉽다.
이유: (가)에서 LL을 쓰려면 먼저 좌재귀를 없애야 한다.
C2 (다) 문법 \(E \to T + E \mid T\), \(T \to F * T \mid F\), \(F \to (E) \mid id\)를 고치지 않고 쓴다. (라) 파서가 쓴 규칙을 순서대로 적었더니 id * id에 대해 \(F \to id\)가 맨 먼저, \(E \to T\)가 맨 나중에 나왔다. 각각 어느 쪽인가?
답: (다) LR. \(E \to T + E\)와 \(E \to T\)는 둘 다 T로 시작해 다음 토큰 하나로는 가를 수 없다. LL(1)로 쓰려면 좌인수분해가 필요하다. SLR은 T를 다 본 뒤 다음 토큰이 +인지 보고 정하므로 그대로 된다. (라) LR. 잎에서 가까운 규칙부터 쓰고 시작 기호의 규칙을 맨 나중에 쓴다. LL이면 \(E \to T\)가 맨 먼저다.
이유: (라)에서 LL의 순서는 \(E \to T\), \(T \to F * T\), \(F \to id\), \(T \to F\), \(F \to id\)이고 LR의 순서는 \(F \to id\), \(F \to id\), \(T \to F\), \(T \to F * T\), \(E \to T\)다.
결정적 차이
| LL (위에서 아래로) | LR (아래에서 위로) | |
|---|---|---|
| 트리를 쌓는 방향 | 뿌리(시작 기호)에서 잎으로 | 잎(입력)에서 뿌리로 |
| 만드는 유도 | 왼쪽 끝 유도를 순서대로 | 오른쪽 끝 유도를 거꾸로(환원) |
| 이름의 뜻 | Left-to-right로 읽고 Leftmost 유도 | Left-to-right로 읽고 Rightmost 유도를 거꾸로1 |
| 규칙을 정하는 때 | 규칙의 오른쪽을 보기 전. 다음 토큰으로 미리 찍는다(예측) | 규칙의 오른쪽을 다 쌓은 뒤. 다음 토큰은 확인용으로만 본다 |
| 막히는 자리 | 어느 규칙으로 펼칠지 | 이동할지 환원할지, 어느 규칙으로 환원할지 |
| 문법에 바라는 것 | 모호하지 않다, 좌재귀가 없다, 좌인수분해가 되어 있다 | 표에 충돌이 없다. 좌재귀와 같은 앞부분은 그대로 둬도 된다 |
| 표 | 줄 = 논터미널, 칸 = 쓸 규칙 | 줄 = 상태, 칸 = 이동·환원 |
| 스택에 든 것 | 앞으로 봐야 할 기호 | 지금까지 본 것을 읽은 상태 |
| 손으로 짜기 | 쉽다(재귀 하강) | 어렵다. 표를 도구로 만든다 |
선택을 가르는 줄은 “규칙을 정하는 때”다. 나머지 줄은 거기서 따라 나온다. 일찍 정해야 하니 LL은 문법을 손봐야 하고, 늦게 정해도 되니 LR은 더 많은 문법을 그대로 받는다. 대신 LR은 “다 본 것”을 기억할 상태가 많이 필요해 표가 크고 손으로 만들기 힘들다1.
id) 칸이 겹치고 SLR 표에는 충돌이 없음, 좌인수분해한 문법은 LL(1)과 SLR 둘 다 충돌 없음, id * id에서 두 파서가 규칙을 쓰는 순서 — 29_ll-vs-lr_verify.py둘 다 아닐 때
C3 LL(1)도 SLR도 그대로는 못 쓰는 문법의 예를 들고, 그때 할 수 있는 일 두 가지를 쓰라.
답: 모호한 문법 \(E \to E + E \mid E * E \mid id\). LL은 모호하지 않은 문법을 바라고, SLR 표에는 충돌이 남는다. 할 수 있는 일: ① 문법을 모호하지 않게 고쳐 쓴다(모호한 문법). ② 문법은 두고 “*가 +보다 우선순위가 높다”고 선언해 충돌 칸에서 고를 쪽을 정해 준다(SLR 파싱).
이유: 모호하지 않은데도 SLR 표에 충돌이 남는 문법도 있다. 그때는 다음 토큰을 FOLLOW보다 더 정밀하게 따지는 LR 방식(LALR(1), LR(1))을 쓴다2.