사용 개념: LL(1) 파싱 표. FIRST와 FOLLOW를 구하는 연습은 FIRST·FOLLOW 예제 사다리에 있고, 문제 1~3은 그 문서와 같은 문법을 쓴다.

“이 문법의 LL(1) 파싱 표를 만들어라”는 문제는 같은 하위목표의 되풀이다.

① FIRST와 FOLLOW: 모든 비단말 기호에 대해 구한다.
② 규칙 오른쪽의 FIRST: 규칙 \(A \to \alpha\)마다 \(First(\alpha)\)를 구한다.
③ FIRST 칸 채우기: \(First(\alpha)\)의 단말 기호 \(x\)마다 \([A, x]\)에 \(\alpha\)를 적는다.
④ ε 규칙을 FOLLOW 칸에: \(\epsilon \in First(\alpha)\)이면 \(Follow(A)\)의 \(x\)마다 \([A, x]\)에 \(\alpha\)를 적는다.
⑤ 판정: 한 칸에 규칙이 둘 든 곳이 있는지 본다. 없으면 LL(1) 문법이다.

문제 1 · 완전한 풀이

\(S \to (\,L\,) \mid a\), \(\ L \to S\,L'\), \(\ L' \to ,\ S\,L' \mid \epsilon\)

  1. FIRST와 FOLLOW: \(First(S) = First(L) = \{(, a\}\), \(First(L') = \{,\ ,\ \epsilon\}\)(쉼표와 \(\epsilon\)). \(Follow(S) = \{\$,\ ,\ ,\ )\}\), \(Follow(L) = Follow(L') = \{)\}\).
  2. 규칙 오른쪽의 FIRST:
규칙 \(First(\alpha)\)
\(S \to (L)\) (
\(S \to a\) \(a\)
\(L \to SL'\) (, \(a\)
\(L' \to ,SL'\) ,
\(L' \to \epsilon\) \(\epsilon\)
  1. FIRST 칸 채우기: 위 표대로 \([S, (]\), \([S, a]\), \([L, (]\), \([L, a]\), \([L', ,]\)의 다섯 칸.
  2. ε 규칙을 FOLLOW 칸에: \(L' \to \epsilon\)을 \(Follow(L') = \{)\}\)의 칸 \([L', )]\)에 적는다.
  3. 판정: 겹치는 칸이 없다. LL(1) 문법이다.
  ( ) , \(a\) \(\\)$
\(S\) \((L)\)     \(a\)  
\(L\) \(SL'\)     \(SL'\)  
\(L'\)   \(\epsilon\) \(,SL'\)    
검증 — 20_ll1-table-ladder_p4.py

문제 2 · 마지막 하위목표만 빈칸

\(S \to A\,B\), \(\ A \to a\,A \mid \epsilon\), \(\ B \to b\,B \mid c\)

  1. FIRST와 FOLLOW: \(First(S) = \{a, b, c\}\), \(First(A) = \{a, \epsilon\}\), \(First(B) = \{b, c\}\). \(Follow(S) = \{\$\}\), \(Follow(A) = \{b, c\}\), \(Follow(B) = \{\$\}\).
  2. 규칙 오른쪽의 FIRST: \(First(AB) = \{a, b, c\}\), \(First(aA) = \{a\}\), \(First(\epsilon) = \{\epsilon\}\), \(First(bB) = \{b\}\), \(First(c) = \{c\}\).
  3. FIRST 칸 채우기: \([S, a] = [S, b] = [S, c] = AB\), \(\ [A, a] = aA\), \(\ [B, b] = bB\), \(\ [B, c] = c\).
  4. ε 규칙을 FOLLOW 칸에, 그리고 판정: __
답

\(A \to \epsilon\)을 \(Follow(A) = \{b, c\}\)의 두 칸 \([A, b]\), \([A, c]\)에 적는다.

  \(a\) \(b\) \(c\) \(\\)$
\(S\) \(AB\) \(AB\) \(AB\)  
\(A\) \(aA\) \(\epsilon\) \(\epsilon\)  
\(B\)   \(bB\) \(c\)  

겹치는 칸이 없어 LL(1) 문법이다. \(\\)$ 열은 모두 빈칸이다. 이 문법의 문장은 반드시 \(c\)로 끝나므로, 무엇을 펼치려는 순간에 입력이 끝나 있으면 늘 오류다.

문제 3 · 하위목표 절반이 빈칸

\(S \to a\,B\,D\,h\), \(\ B \to c\,C\), \(\ C \to b\,C \mid \epsilon\), \(\ D \to E\,F\), \(\ E \to g \mid \epsilon\), \(\ F \to f \mid \epsilon\)

  1. FIRST와 FOLLOW: \(First(D) = \{g, f, \epsilon\}\), \(First(C) = \{b, \epsilon\}\), \(First(E) = \{g, \epsilon\}\), \(First(F) = \{f, \epsilon\}\). \(Follow(C) = \{g, f, h\}\), \(Follow(D) = \{h\}\), \(Follow(E) = \{f, h\}\), \(Follow(F) = \{h\}\).
  2. 규칙 오른쪽의 FIRST: \(First(EF) =\) __. 나머지는 첫 기호가 단말 기호이거나 \(\epsilon\)이다.
  3. FIRST 칸 채우기: \([S, a] = aBDh\), \(\ [B, c] = cC\), \(\ [C, b] = bC\), \(\ [E, g] = g\), \(\ [F, f] = f\), 그리고 \(D\) 줄은 __
  4. ε 규칙을 FOLLOW 칸에: \(C \to \epsilon\)은 \([C, g]\), \([C, f]\), \([C, h]\)에. \(E \to \epsilon\)은 __. \(F \to \epsilon\)은 __. \(D \to EF\)는 __
  5. 판정: 겹치는 칸이 없다. LL(1) 문법이다.
답
  1. \(First(EF) = \{g, f, \epsilon\}\). \(E\)가 사라질 수 있어 \(F\)까지 보고, 둘 다 사라질 수 있어 \(\epsilon\)이 든다.
  2. \([D, g] = EF\), \([D, f] = EF\).
  3. \(E \to \epsilon\)은 \(Follow(E) = \{f, h\}\)의 \([E, f]\), \([E, h]\)에. \(F \to \epsilon\)은 \(Follow(F) = \{h\}\)의 \([F, h]\)에. \(D \to EF\)도 \(\epsilon \in First(EF)\)이므로 \(Follow(D) = \{h\}\)의 \([D, h]\)에 적는다.
  \(a\) \(b\) \(c\) \(f\) \(g\) \(h\) \(\\)$
\(S\) \(aBDh\)            
\(B\)     \(cC\)        
\(C\)   \(bC\)   \(\epsilon\) \(\epsilon\) \(\epsilon\)  
\(D\)       \(EF\) \(EF\) \(EF\)  
\(E\)       \(\epsilon\) \(g\) \(\epsilon\)  
\(F\)       \(f\)   \(\epsilon\)  

놓치기 쉬운 칸은 \([D, h]\)다. 오른쪽이 \(\epsilon\)이라고 적힌 규칙만 FOLLOW 칸에 가는 것이 아니다. \(EF\)처럼 끝까지 풀면 빈 문자열이 될 수 있는 규칙도 간다.

검증 — 20_ll1-table-ladder_p4.py

문제 4 · 독립 문제

if 문 문법을 좌인수분해한 것이다. \(i\)는 if, \(t\)는 then, \(e\)는 else, \(a\)는 다른 문장, \(b\)는 조건이다.

\[S \to i\,E\,t\,S\,S' \mid a \qquad S' \to e\,S \mid \epsilon \qquad E \to b\]

LL(1) 파싱 표를 만들고, LL(1) 문법인지 판정하라. 아니라면 까닭을 문법의 성질로 설명하라.

답

\(First(S) = \{i, a\}\), \(First(S') = \{e, \epsilon\}\), \(First(E) = \{b\}\). \(Follow(S) = \{\$, e\}\), \(Follow(S') = \{\$, e\}\), \(Follow(E) = \{t\}\).

  \(a\) \(b\) \(e\) \(i\) \(t\) \(\\)$
\(S\) \(a\)     \(iEtSS'\)    
\(S'\)     \(eS\) 와 \(\epsilon\)     \(\epsilon\)
\(E\)   \(b\)        

\([S', e]\)에 규칙이 둘 든다. \(S' \to eS\)는 \(First(eS) = \{e\}\) 때문에, \(S' \to \epsilon\)은 \(e \in Follow(S')\) 때문에 같은 칸에 간다. LL(1) 문법이 아니다.
까닭은 문법이 모호해서다. \(i\,b\,t\,i\,b\,t\,a\,e\,a\)에서 \(e\)를 안쪽 if에 붙일 수도(\(S' \to eS\)) 바깥 if에 붙이려고 안쪽을 끝낼 수도(\(S' \to \epsilon\)) 있다. 좌인수분해는 공통 접두사만 없애고 이 모호함은 그대로 둔다.
\(Follow(S)\)에 \(e\)가 드는 까닭: \(S \to iEtSS'\)에서 \(S\) 뒤가 \(S'\)이고 \(First(S') - \{\epsilon\} = \{e\}\)다.

검증 — 20_ll1-table-ladder_p4.py