LL 파서
(LL parser)는
文脈 自由 文法
의 一部를
파싱
할 수 있는
下向式 파서
이다. LL 파서는 入力 文字列의 왼쪽(Left)에서부터 파싱을 始作하여, 左側誘導(Leftmost derivation) 方式으로 動作한다. LL 派서로 파싱이 可能한 文法은 LL 文法이라고 부른다.
萬若 LL 파서가 lookahead에 最大 k個의 토큰(token)을 使用한다면, 그 파서는 LL(k) 파서라고 부른다. LL(k) 派서로 파싱이 可能한 文法은 LL(k) 文法이라고 부른다.
파서의 構造
[
編輯
]
LL 파서는 普通 다음과 같은 構造로 이루어져 있다.
- 入力 버퍼: 파싱할 文字列을 貯藏한다.
- 스택
: 파싱 中인 토큰을 貯藏하는 데에 使用한다.
- 파싱 테이블: 各 토큰에 對해, 어떤 파싱 規則을 使用해야 하는지를 整理해놓은 票로, 파싱 文法에 따라 決定된다.
스택의 初期 狀態에는 가장 위쪽에 始作 文字 S가 들어있고, 그 밑에 스택의 바닥을 表示하는 特殊 文字 $街 들어있다. LL 파서에서는 스택에 들어있는 토큰들에 對해, 파싱 테이블을 利用하여 토큰을 다른 토큰들로 바꾸거나, 或은 파싱이 完了된 文字를 出力 스트림에 出力한다.
예제
[
編輯
]
다음과 같은 文法에 對해서:
- S → F
- S →
(
S
+
F
)
- F →
a
( a + a )
라는 文字列을 LL(1) 파서 方式으로 파싱하는 過程은 다음과 같다. 于先 該當 文法에 對한 파싱 테이블을 다음과 같이 準備한다.
|
(
|
)
|
a
|
+
|
$
|
| S
|
2
|
-
|
1
|
-
|
-
|
| F
|
-
|
-
|
3
|
-
|
-
|
스택의 初期 狀態는 다음과 같다. (왼쪽이 가장 위, 오른쪽이 가장 아래의 狀況)
S $
이제 스택의 가장 위에 있는 토큰을 確認하고 該當 토큰을 다른 토큰으로 交替하는 作業을 反復한다.
| 段階
|
動作 說明
|
動作 後 스택
|
動作 後 入力 文字列
|
| 1
|
初期 狀態
|
S $
|
( a + a )
|
| 2
|
入力 文字列에서
(
를 읽고, 스택의 가장 위에 있는 文字 S를 確認한다. 파싱 테이블에 依하여 規則 2를 適用한다.
|
(
S
+
F
)
$
|
( a + a )
|
| 3
|
入力 文字列에서
(
를 읽고, 스택의 가장 위에 있는 文字
(
를 確認한다. 두 文字가 같으므로 削除한다.
|
S
+
F
)
$
|
a + a )
|
| 4
|
入力 文字列에서
a
를 읽고, 스택의 가장 위에 있는 文字 S를 確認한다. 파싱 테이블에 依하여 規則 1을 適用한다.
|
F
+
F
)
$
|
a + a )
|
| 5
|
入力 文字列에서
a
를 읽고, 스택의 가장 위에 있는 文字 F를 確認한다. 파싱 테이블에 依하여 規則 3을 適用한다.
|
a
+
F
)
$
|
a + a )
|
| 6
|
入力 文字列에서
a
를 읽고, 스택의 가장 위에 있는 文字
a
를 確認한다. 두 文字가 같으므로 削除한다.
|
+
F
)
$
|
+ a )
|
| 7
|
入力 文字列에서
+
를 읽고, 스택의 가장 위에 있는 文字
+
를 確認한다. 두 文字가 같으므로 削除한다.
|
F
)
$
|
a )
|
| 8
|
入力 文字列에서
a
를 읽고, 스택의 가장 위에 있는 文字 F를 確認한다. 파싱 테이블에 依하여 規則 3을 適用한다.
|
a
)
$
|
a )
|
| 9
|
入力 文字列에서
a
를 읽고, 스택의 가장 위에 있는 文字
a
를 確認한다. 두 文字가 같으므로 削除한다.
|
)
$
|
)
|
| 10
|
入力 文字列에서
)
를 읽고, 스택의 가장 위에 있는 文字
)
를 確認한다. 두 文字가 같으므로 削除한다.
|
$
|
|
| 11
|
入力 文字列과 스택 모두 빈 것을 確認하고 作動을 終了한다.
|
$
|
|
파싱 過程에서 使用한 規則은 順序대로 2, 1, 3, 3이다. 卽,
( a + a )
는 다음과 같이 파싱된다.
- S →
(
S
+
F
)
→
(
F
+
F
)
→
( a +
F
)
→
( a + a )
같이 보기
[
編輯
]
