์นด์ผ๋ฃจ์, ๋: ํ์ (1)
์ ๋ฒ ๊ธ์์ ์นด์ผ๋ฃจ์๊ฐ ์ ๋ง๋ค์ด์ก๋์ง, ๊ทธ๋ฆฌ๊ณ ์ด๊ธฐ ์ค๊ณ๊ฐ ์ด๋ ํ๋์ง์ ๋ํด์ ๊ฐ๋ตํ ์ค๋ช ํ๋ค. ๋ง์ ์ธ์ด๊ฐ ๊ทธ๋ ๋ฏ, ์นด์ผ๋ฃจ์ ๋ํ ์ค์ ๋ก ์์ฑ๋ ์ฒซ ์ฝ๋๋ ํ์์๋ค. ์ด๋ฒ ๊ธ์์๋ ์นด์ผ๋ฃจ์์ ํ์๊ฐ ์ด๋ป๊ฒ ๋ฐ์ ํ๋์ง๋ฅผ ์ด์ผ๊ธฐํด ๋ณด๊ธฐ๋ก ํ๋ค.
์ ๋ฌ์คํธ๋ฅผ?
๋ชจ๋๊ฐ ์๊ณ ์๋ฏ ์นด์ผ๋ฃจ์๋ ๋ฌ์คํธ๋ก ์์ฑ๋์ด ์๋ค. ๊ฝค ๋ง์ ๋ฃจ์ ํ์ ์์คํ ์ด๋ ๋ฃจ์ ํ์ฅ ์ธ์ด๊ฐ ๋ฃจ์๋ก ์์ฑ๋ ๊ฒ๊ณผ๋ ๋์กฐ์ ์ธ๋ฐ, ์ฌ๋ฌ ์ด์ ๊ฐ ์๋ค.
๋ด๊ฐ ์์ฑํ๊ธฐ ํธํ๋ค. ์ด์ฐจํผ ์ด๊ฑธ ๋ฌด์จ ์ธ์ด๋ก ์ง๋ ๊ฑด๋ค ์ ์๋ ์ฌ๋์ ๋ ๋ฐ์ ์์ ๊ฒ์ด๋ค(โฆ).
ํ์ ์์คํ ์ด ๊ฐํ๊ณ ๋์์ ์๋ฃํ(algebraic data type)์ด ์๋ ์ธ์ด๋ ๋ณดํต ์ธ์ด ๊ตฌํ ์ง๊ธฐ ํธ๋ฆฌํ๋ค.
์ ์ ํ ํฌ๊ธฐ์ ๋ค์ดํฐ๋ธ ๋ฐ์ด๋๋ฆฌ๊ฐ ํ๋ ํญ ํ์ด๋์ค๋ฉด ๋ฐฐํฌ๊ฐ ํธ๋ฆฌํ๋ค.
์์งํ ๋งํด์ ์ด๊ฑธ ๋ฃจ์๋ก ์ง๋ผ๊ณ ํ๋ฉด ๊ทธ๋ฅ ํ ๊นจ๋ฌผ๊ณ ์ฃฝ์ ๊ฒ์ด๋ค.
๋ด๊ฐ ํ ๋ฌ์คํธ ๋น ํ๊ธด ํ์ง๋ง(โฆ) ์นด์ผ๋ฃจ์ ์์ ์ ํ๋ฉด์ ํ ๊ฐ์ง ๋ ๋๋ผ๊ฒ ๋ ๊ฒ์ ๋ฐ๋ก ์ด๊ฒ์ด๋ค.
๋ฌ์คํธ ์ฝ๋๋ ๋งค์ฐ ๋ฆฌํฉํ ๋งํ๊ธฐ ์ข๋ค. ๋ฆฌํฉํ ๋ง ๊ณผ์ ์์ ์ปดํ์ผ ์ค๋ฅ๋ฅผ ์ก๋ ๊ฑด ๋ฌผ๋ก ํด์ผ ํ์ง๋ง, ๋ฆฌํฉํ ๋ง๋ ๊ฒฐ๊ณผ๊ฐ ์ด์ ๊ณผ ๋ค๋ฅด์ง ์๋ค๋ ๊ฑธ ํ์ ์์คํ ์ ์ฌ์ฉํด์ ์ฆ๋ช ํ๊ธฐ๊ฐ ๋งค์ฐ ์์ํ๋ค.
ํ์ฌ์ ์นด์ผ๋ฃจ์ ์ฝ๋๋ ์๋นํ ์ ๊ธฐ์ ์ผ๋ก ๋ง๋ค์ด์ง ์ฝ๋๋ผ์, ํฌ๋ ์ดํธ๊ฐ 10๊ฐ๋ก ์ชผ๊ฐ์ ธ ์๊ธด ํ์ง๋ง ์ฌ๊ธฐ ์ ๊ธฐ ์ด์ํ ๊ตฌ์์ด ๋ง์ด ๋จ์ ์๋ค. ์ ๊ธฐ์ ์ผ๋ก ๋ง๋ค ์ ๋ฐ์ ์๋ ๊ฒ์ ์ค๊ณ๋ฅผ ์ฌ๋ฌ ์ฐจ๋ก ๋ณ๊ฒฝํ๋ฉด์ ์ํคํ ์ฒ๋ ํจ๊ป ๋ฐ๊ฟ์ผ ํ๋ ๊ฒฝ์ฐ๊ฐ ๋ง์๊ธฐ ๋๋ฌธ์ธ๋ฐ, ๊ทธ๋ผ์๋ ๋ถ๊ตฌํ๊ณ ํ์ ๋ ๋ค์ด๊ณ ๋ฆฌํฉํ ๋ง์ ํ ์ ์์๋ ๋๋ถ์ ๊ทธ ์ ๋๋ก ํ๋ ์์ ์ ์๋์๋ค. ์ข ๋ ํ์ ์ฐ๋ฉด ํ์ ์์คํ ์์ค์์ ์ด์ํ ๊ตฌ์๋ค์ ๋ง์ด ์ก์ ์ ์๊ฒ ์ง๋ง ์ฌ๋ฌ ๊ฐ์ง ์ด์ ๋ก (์๊ฐ ๋ฌธ์ ๋ ์๊ณ , ๊ทธ๋ ๊ฒ ํด์ ์ป๋ ์ด๋์ด ํฌ์ง ์๋ค๊ณ ํ๋จํ์ฌ) ํ์ง ์์๋ค.
LALRPOP
์ฝ๋๋ฅผ ์คํ์์ค๋ก ๊ณต๊ฐํ๋ฉด ์ข์ ๊ฒ์ด ์ด๋ ๊ฒ ์ด์ฐฝ๊ธฐ ์ฝ๋๋ฅผ ๊ทธ๋๋ก ๋งํฌํด์ ๋ณด์ฌ ์ค ์ ์๋ค๋ ๊ฒ์ด๋ค. ์ด ์ฝ๋๋ ๋ ์ง๋ฅผ ๋ณด๋ฉด ์ ์ ์์ง๋ง ์ค๊ณ์ ์์ ๋น ๋ฅด๊ฒ ํ ์คํธ๋ก ๊ตฌํํ ํ ํฐํ ์ฝ๋์ด๊ณ , ์ ํ์ ์ธ ์ถ์ ๋ฌธ๋ฒ ํธ๋ฆฌ(AST) ์ฝ๋์ ํจ๊ป LALRPOP์ผ๋ก ์์ฑ๋ ๊ฐ๋จํ ํ ์คํธ ํ์๊ฐ ๋ค์ด ์๋ค.
ํ ํฐํ ๊ณผ์ ์ ๊ทธ๋ค์ง ๋ณ๋ก ํน์ดํ ์ ์ ์๋ค. ํ์ฌ ์ฝ๋์ ๋น๊ตํด๋ ํฐ ์ฐจ์ด๊ฐ ์๋๋ฐ, ์ถ๊ฐ๋ ์ ์ ์ค๋ฅ ๋ณด๊ณ ์, ์นด์ผ๋ฃจ์ ์ ์ฉ ํ ํฐ์ ํด์ํ ์ ์๋๋ก ํ๋ค๋ ๊ฒ, ๊ทธ๋ฆฌ๊ณ ์ด ๊ธ์ ๋ค์์ ์ค๋ช ํ๊ฒ ์ง๋ง ํ ํฐ ์ด์ ์ ํ ๋จ๊ณ๊ฐ ๋ ์ถ๊ฐ๋ ์ ์ด ์๋ค. ํ ํฐํ ์์ฒด๋ u8 ๋ฐ์ดํธ ๋ฐ๋ณต์๋ก๋ถํฐ Tok ๊ฐ ๋ฐ๋ณต์๋ฅผ ๋ง๋ค์ด ๋ด๋ ์ด๋ํฐ๋ก ๊ตฌํ๋์๋๋ฐ ์ด๋ ๊ฒ ํ๋ค ๋ณด๋ ์ค๋ฅ ๋ณต๊ตฌ๊ฐ ๋ฏธ๋ฌํด์ง ๋ถ๋ถ์ด ์๊ธด ํ๋ค. (์ต์ข ์ ์ผ๋ก ๋ชจ๋ฅด๋ ๋ฌธ์๊ฐ ๋์ค๋ฉด ์๋ ๋ฌธ์๊ฐ ๋์ฌ ๋๊น์ง ์คํตํ๊ณ ํ๋์ ์ค๋ฅ๋ฅผ ๋ณด๊ณ ํ๋๋ก ํ๊ธฐ ๋๋ฌธ์ ํ ํฐํ ๊ณผ์ ์์ ๋ณต๊ตฌ ๋ถ๊ฐ๋ฅํ ์ค๋ฅ๋ ๋์ฌ ์ ์๊ฒ ๋์๋ค.)
ํฌ๊ฒ ๋ฌ๋ผ์ง ๊ฒ์ ํ์์ด๋ค. LALRPOP์ ์ฌ์ ํ ๊ฝค ์คํ์ ์ธ ๋ผ์ด๋ธ๋ฌ๋ฆฌ ๊ฐ์ง๋ง 2015๋ 11์ ๋น์์๋ ์ ๋ง ์คํ์ ์ธ ๋ผ์ด๋ธ๋ฌ๋ฆฌ์๋ค. ๋ด๊ฐ LALRPOP์ ์จ ๋ณด๋ฉด์ ๋๋ ๊ฐ์ฅ ํฐ ๋ฌธ์ ๋ ๋ ๊ฐ์ง์ธ๋ฐ, ํ๋๋ ์์ฑ๋ ํ์ผ์ด ๋๋ฌด ํฌ๋ค๋ ๊ฒ์ด์๋ค. ๋ช ์ค ์ ๋๋ parser.lalrpop์ผ๋ก๋ถํฐ ์์ฑ๋ parser.rs ํ์ผ์ด ์ด๋ฏธ 2์ฒ์ค์ด ๋์ด๊ฐ๋ค! ์ค์ ๋ก๋ do์ break๋ง ํ์ฑํ๋ ์์ฃผ ๊ฐ๋จํ ๋ฌผ๊ฑด์ธ๋ฐ๋ ๋ง์ด๋ค. ๊ทธ๋๋ ๋ญ ์ฝ๋ฉ์ด ํธํ๋๊น ํฐ ๋ฌธ์ ์๊ฒ ์ง ํ๊ณ ์์ ์ ํ๊ธด ํ์๋๋ฐโฆ ๋ฃจ์ ๋ฌธ๋ฒ์ ๊ฑฐ์ง ๋ค ๊ตฌํํ๊ณ ๋๋ ๋ฌธ๋ฒ์ 200์ฌ์ค ๋จ์งํ๋๋ฐ ์์ฑ๋ ํ์ผ์ 20๋ง์ค์ ๋๋ ์ํฉ์ด ๋ฒ์ด์ก๋ค. ์ด ์ ๋ ๋๋ฉด ์ปดํ์ผํ๋ ๋ฐ ๋ช ๋ถ ๊ฑธ๋ฆฌ๊ณ ๋๋ฆฌ๊ฐ ๋๋ค. (๋น์ ๋ฌ์คํธ ์ปดํ์ผ๋ฌ๋ ๋ ๋๋ ธ๋ค๋ ์ ์ ์๊ฐํด ๋ณด์.) ์ด๋ฐ ์ํฉ์ด ๋ฒ์ด์ง ๊ฒ์ ๋น์ LALRPOP์ด LR/LALR ํ์๋ฅผ ๊ตฌํํ ๋ ์ปดํฉํธํ ํ ์ด๋ธ์ ๋ง๋ ๊ฒ ์๋๋ผ ๋ชจ์กฐ๋ฆฌ match๋ก ๋๋ ค ๋ฐ์์์๊ณ , ์ง๊ธ์ ์ํฉ์ด ๊ฐ์ ๋ ๊ฒ์ผ๋ก ์๊ณ ์๋ค(์ง์์ปจ๋ ๋น์ ํ์๋ฅผ ์ง๊ธ LALRPOP๋ก ์ปดํ์ผํ๋ฉด 1/10 ์ ๋ ๋์ค์ง ์์๊น ์ถ๋ค). ์ด์จ๋ ๋น์์๋ ์ดํฐ๋ ์ด์ ์ด ๋๋ฌด ๋๋ฆฌ๋ค๋ ๊ฒ ์์ฒด๋ง์ผ๋ก ์๋นํ ์คํธ๋ ์ค์๋ค.
๋ค๋ฅธ ๋ฌธ์ ๋ ์ข ๋ ๋ณธ์ง์ ์ธ๋ฐ, LALRPOP์ shift-reduce ์ถฉ๋์ ์ ์ดํ ๋ฐฉ๋ฒ์ ์ง์ํ์ง ์๋๋ค. ํ์ ๋ฌธ๋ฒ์ด ๋ญ์ง ์๋ค๋ ์ ์ ํ์ ์ ๊น ํ์ฑ ์ด๋ก ์ ๊ฐ๋ณ๊ฒ(?) ๋ค์ด ๊ฐ๋ฉด, LR ๊ณ์ด ํ์๋ ํ์ฌ๊น์ง ์ฝ์ ํ ํฐ๋ค(42, foo, = ๋ฐ์)์ด ์ด๋ค ๋น๋จ๋ง(non-terminal) ๊ธฐํธ(๋ฃจ์์ ๊ฒฝ์ฐ exp, chunk ๋ฐ์)๋ค์ ํฌํจ๋๋์ง๋ฅผ ์คํ์ ์ง์ด ๋ฃ๊ณ , ๊ฐ์ฅ ์์ชฝ์ ์๋ ๋น๋ง๋จ ๊ธฐํธ๊ฐ ๋๋์ ์คํ์์ ๋ฝํ์ผ ํ๋์ง(โreduceโ), ๋๋ ๋ค์ ํ ํฐ์ ์ฝ์ด์ผ ๊ฒฐ์ ํ ์ ์๋์ง(โshiftโ)๋ฅผ ์ํ ๊ธฐ๊ณ๋ก ๋ง๋ค์ด์ ํ์ฑ์ ์ํํ๋ค. ์ด๋ฅผํ ๋ฉด ๋ค์๊ณผ ๊ฐ์ด local x = 42 + 54 * f() return x๋ผ๋ ์ฝ๋๊ฐ ์๋๋ฐ +๊น์ง ์ฝ์๋ค๋ฉดโฆ
| ์ด๋ ค ์๋ ๋น๋จ๋ง ๊ธฐํธ๋ค | | <----| - - - -> exp <--------------| - - - -> stmt <--------------| - - - - - - - - > chunk local x = 42 + | 54 * f() return x | ํ์ฌ๊น์ง ์ฝ์ ์์น
โฆ๊ทธ๋ผ ํ์ฌ ์์น์์ ์ด๋ ค ์๋ ๋น๋จ๋ง ๊ธฐํธ๋ ์์ชฝ๋ถํฐ ์์๋๋ก ์์์ ๋ํ๋ด๋ exp, ๋ฌธ์ฅ์ ๋ํ๋ด๋ stmt, ๊ทธ๋ฆฌ๊ณ ์คํ ๊ฐ๋ฅํ ์ฝ๋ ๋ญ์น๋ฅผ ๋ํ๋ด๋ chunk ์ธ ๊ฐ๊ฐ ์๋ค. 42 ๋ํ ์์์ด๊ณ , ๋งจ ์์ x๋ ๋ฌธ๋ฒ๊ณผ ๋์กฐํด ๋ณด๋ฉด ๋์ ๋ฌธ ์ข๋ณ์ ๋ํ๋ด๋ var์ ๋์ํ๊ฒ ์ง๋ง ํ์ฌ ์์น์์๋ ๋ ์ด์ ์ํฅ์ ์ค ์ ์์ผ๋ฏ๋ก ์คํ์ ์๋ ๊ฒ์ ์ ๋ ํ์. ์ง๊ด์ ์ผ๋ก ์๊ฐํด ๋ณด๋ฉด ์ด ์ํ์์๋ ์ด๋ค ๋น๋จ๋ง ๊ธฐํธ๋ ๋๋ง์น ์ ์๊ณ , ๋ฐ๋ผ์ ๋ค์ ๊ธฐํธ๋ฅผ ์ฝ์ด์ผ๋ง ๋ญ ํ ์ง๋ฅผ ๊ฒฐ์ ํ ์ ์๋ค. ๋ฐ๋ก ์ด ๊ณผ์ ์ ์ํ ๊ธฐ๊ณ๋ก ํํํ ๊ฒ์ด LR ํ์์ธ ๊ฒ์ด๋ค. LR ํ์ ์์์๋ SLR, GLR, LALR ๋ฑ์ ๋ค์ํ ๋ฐ๋ฆฌ์์ด์ ์ด ์๊ธด ํ์ง๋ง ๊ธฐ๋ณธ์ ์ธ ๊ตฌ์กฐ๋ ๋ค ๋๊ฐ๋ค.
๊ทผ๋ฐ ๋ญ๊ฐ ๋ฌธ์ ๋๊ณ ? ์นด์ผ๋ฃจ์ ํ์ฑ ํ ์คํธ์ ๋ค์ด ์๋ ๋ค์ ์ฝ๋๋ฅผ ์๊ฐํด ๋ณด์.
a = b + c (print or io.write)('done')
์ด๊ฑด ๋ฌธ์ฅ ํ๋์ผ๊น ๋ ๊ฐ์ผ๊น? ๋ ์ค๋ก ๋๋์ด ์๋ ๊ฑด ์๋ฌด ์๋ฏธ๋ ์๋ค. ๋ฃจ์์์ ๊ฐํ๋ฌธ์๋ ๊ณต๋ฐฑ๊ณผ ์์ ํ ๋๊ฐ๋ค(๋น์ทํ๊ฒ ์ธ๋ฏธ์ฝ๋ก ์ ์๋ต ๊ฐ๋ฅํ ์๋ฐ์คํฌ๋ฆฝํธ์๋ ์ด ์ ์์ ๋ค๋ฅด๋ค). ๋ฃจ์ ๋ฌธ์์ ๋ฐ๋ฅด๋ฉด ์ด๋ ํ ๋ฌธ์ฅ์ผ๋ก, c(...)๋ ํจ์ ํธ์ถ๋ก ํด์๋๋ค. ๋ณด์ด๋ ๊ฒ๊ณผ ๋น์ทํ๊ฒ ๋ ๋ฌธ์ฅ์ผ๋ก ๋ฐ๊พธ๋ ค๋ฉด ์ค๊ฐ์ ์ธ๋ฏธ์ฝ๋ก ์ ๋ฃ์ด์ผ๋ง ํ๋ค.
a = b + c; (print or io.write)('done')
ํ์ง๋ง ์ด๋ฐ ์์ผ๋ก ๋ฌธ๋ฒ์ด ๊ตฌ์ฑ๋์ด ์์ผ๋ฉด c๋ฅผ ์ฝ์ ์์ ์์ ํ์ฌ ์ด๋ ค ์๋ ์์(exp)์ด๋ ๋ฌธ์ฅ(stmt) ๋ฐ์๋ฅผ reduce, ์ฆ ๋ง๋ฌด๋ฆฌ์ง๊ณ ๋ค์ ๋ฌธ์ฅ์ผ๋ก ์งํํด์ผ ํ ์ง, ์๋๋ฉด ๋ค์ ํ ํฐ์ shift, ์ฆ ๋ ์ฝ์ด ๋ด์ผ ํ ์ง๋ฅผ ๊ฒฐ์ ํ ์ ์๋ค. ์ด๋ฅผ shift-reduce ์ถฉ๋์ด๋ผ๊ณ ํ๋ค. ์ด๋ฐ ๋ฅ์ ์ถฉ๋์ ์๊ทผ ํํด์ C์ ์กฐ๊ฑด๋ฌธ์์๋ ๋น์ทํ ์ฌ๋ก๊ฐ ์๋ค. ์ด๊ฑธ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ ํฌ๊ฒ ๋ ๊ฐ์ง๊ฐ ์๋ค.
ํด๋น ์ํฉ์์ shift๋ฅผ ํ ์ง reduce๋ฅผ ํ ์ง๋ฅผ ๋ช ์์ ์ผ๋ก ์ง์ ํ๋ค. ๊ฝค ๋ง์ ํ์ ์์ฑ๊ธฐ๋ ์ด ์ํฉ์์ ์ต์ ์ ์ฃผ๋ฉด ๊ฐ์ ๋ก shift๋ฅผ ํ๊ฒ ํ๋ ๊ธฐ๋ฅ์ด ์์ด์, ์ด ๊ฒฝ์ฐ์๋ shift๋ฅผ ํ๊ฒ ํ๋ฉด ๋ฌธ์ ๊ฐ ํด๊ฒฐ๋๋ค. ๊ทผ๋ฐ LALRPOP์๋ ์ด๊ฒ ์๋ค.
๋ฌธ๋ฒ์ ๋ฏ์ด ๊ณ ์ณ์ ์ถฉ๋์ด ๋ถ๊ฐ๋ฅํ๊ฒ ๋ง๋ ๋ค. ๋ฃจ์ ๋ฌธ๋ฒ ๊ฐ์ ๊ฒฝ์ฐ ์์์ผ๋ก ๋๋ ์ ์๋ ๋ชจ๋ ๋ฌธ์ฅ ๋ค์๋ (๋ก ์์ํ ์ ์๋ ๋ฌธ์ฅ(์ค์ง์ ์ผ๋ก ๋ค๋ฅธ ๋์ ๋ฌธ์ด๋ ํจ์ ํธ์ถ๋ก ์ ํ๋ ๊ฒ์ด๋ค)์ด ์ฌ ์ ์๋๋ก ๋ฌธ๋ฒ์ ๊ฐ์ ์น์ฐ๋ฉด ๋๋ค.
LALRPOP์ ์ ์๊ฐ ์ด ์๊ฐ๊ธ์ ๋ฐ๋ฅด๋ฉด s-r ์ถฉ๋์ ๋ณดํต ๋ฌธ๋ฒ ์์ฑ์์ ์ค์๋ก ์๊ธฐ๋ ๊ฒฝ์ฐ๊ฐ ๋ง๊ณ , ๋ฐ๋ผ์ ์ค์๋ฅผ ์ ์ก์ ์ ์๊ฒ ํ๋ ค๋ฉด s-r ์ถฉ๋์ ๋ด๋ฒ๋ ค ๋๋ ๊ฒ ์๋๋ผ ๋ฌธ๋ฒ์ ๊ณ ์ณ์ ์ถฉ๋์ ์ก๊ธฐ๊ฐ ๋ ์ฝ๊ฒ ๋ง๋ค์ด์ผ ํ๋ค๊ณ ์๊ฐํ์ฌ ์ด๋ฐ ๊ฒฐ์ ์ ๋ด๋ ธ๋ค๊ณ ํ๋ค. ๋๋ ์ด ์๊ฐ์ ์ด๋ ์ ๋ ์ผ๋ฆฌ๊ฐ ์๋ค๊ณ ๋ ๋ณด์ง๋ง, ๋ฌธ์ ๋ ์ด ๊ฒฝ์ฐ์๋ ์ถฉ๋์ ์ก์ผ๋ ค๋ฉด ๊ฑฐ์ ๋ชจ๋ ๋น๋จ๋ง ๊ธฐํธ๊ฐ ์ค๋ณต๋์ด์ผ ํ๋ค! ์ด๋ ์ถฉ๋์ด exp์ var ์ฌ์ด์์ ์ผ์ด๋๊ณ , exp๊ฐ ๋ํธ๋จธ๋ฆฌ์ ๋ฑ์ฅํ์ง ์๋ ๋ฌธ๋ฒ ์์๋ ๊ฑฐ์ ์์๊ธฐ ๋๋ฌธ์ด๋ค. (ํ๋ค๋ชปํด stmt์กฐ์ฐจ๋ repeat โฆ until โฆ ๋ฌธ๋ฒ ๋๋ฌธ์ ์ค๋ณต์ด ํ์ํ๋ค.) ๋ฌผ๋ก ์ด๋ป๊ฒ๋ ๊ณ ์น๋ฉด ๋์๊ฐ๊ฒ ๋ง๋ค ์ ์์์ง๋ง, ์ด๋ฐ ์ํฉ์์ ์ปดํ์ผ๋ ์ค๋ ๊ฑธ๋ฆฌ๊ณ ์๋ค ๋ณด๋ ์ดํ ์ ๋ ์ก๊ณ ๊ณ ์ณ ๋ณด๋ค๊ฐ ๋๋ ค์น๊ณ ์ ํ์๋ก ์ ํํ๋ค.
๊ทธ๋ฆฌํ์ฌ, ํ์ฌ์ ์นด์ผ๋ฃจ์ ํ์๋ ๊ฑฐ๋ํ ์ฌ๊ท ๊ฐํ(recursive descent) ํ์๊ฐ ๋์๋ค. ์ค๊ฐ์ ์์ ์ฒ๋ฆฌ๋ฅผ ๋ ๋น ๋ฅด๊ฒ ํ๊ณ ์คํ์ ๋ ์ฐ๊ธฐ ์ํด์ ์ฐ์ฐ์ ์ฐ์ ์์ ํ์๋ฅผ ์ถ๊ฐ์ ์ผ๋ก ๊ตฌํํ๊ธด ํ๋๋ฐ, ์ด๊ฑด ์ฑ๋ฅ ์ธ์๋ ๋ฃจ์๊ฐ ์ด๋ฏธ ๋๊ฐ์ ์ฝ๋๋ฅผ ์ฐ๊ณ ์์ด์ ๊ฑฐ๊ธฐ์ ๋ง์ถ๋ ค๊ณ ํ ๊ฒ๋ ์๋ค. ๊ทธ๋ฆฌ๊ณ ์์์ ์ธ๊ธ๋์๋ฏ ์ ํ์๊ฐ ์ค์ํ ๊ฐ๋ฅ์ฑ์ด ์์ง ์์ง๋ง, ์ด๋ฏธ ํ์๋ฅผ ๋ช ๋ฒ ์ง ๋ดค๊ณ , ๋์ ๋ฌธ๋ฒ์ด ๊ทนํ ๋ณต์กํ ๊ฒ ์๋๋ฉฐ(LALR(1)๋ก ํ์ฑ์ด ์ ๋๋ ์์ค์ด๋ผ๊ฑฐ๋โฆ), ์ ์ ํ ์ ์ง๋ณด์ ๊ฐ๋ฅํ๊ฒ ์ง์ฌ์ก๊ณ ํ ์คํธ๊ฐ ๋๋ ์ํฉ์ด๋ผ๋ฉด ์ ํ์๋ฅผ ๊ตณ์ด ๊ธฐํผํ ์ด์ ๋ ์์๋ค. ํน์ LALRPOP์ด ๋ ๋ง์ด ๋ฐ์ ํด์ PEG ๊ฐ์ ๊ฑธ ์ง์ํ๊ธฐ ์์ํ๋ฉด ๋ชจ๋ฅด๊ฒ ๋ค.
์ ๋ ฅ ์์ค์ ์์น ์ถ์
์ ํ์๋ก ๋ชจ๋ ๊ฑธ ๊ฐ์ ์น์ด ๋ค, ๊ทธ ๋ค์์ผ๋ก ํ์ ๊ตฌ์กฐ๊ฐ ํฌ๊ฒ ๋ฐ๋ ๋๋ ์ค๋ฅ ๋ณด๊ณ ๋ฅผ ์ฒ์ ์ค๊ณํ ๋์๋ค. ์ค๋ฅ ๋ณด๊ณ ์ ๋ํด์๋ ๋์ค์ ๋ ์์ธํ ์ค๋ช ํ๊ฒ ์ง๋ง, ์ผ๋จ์ ์ค๋ฅ ๋ณด๊ณ ์๋ ๊ธฐ๋ณธ์ ์ผ๋ก ์ด ๋จ์๊น์ง ์์น ์ ๋ณด๊ฐ ๋ค์ด๊ฐ ์ ์๋ค๊ณ ๋ง ์์ ๋์. ๋ฌผ๋ก ๋์๋๋ ์ฝ๋๋ ํจ๊ป ํ์๋์ด์ผ ํ๋ค(IDE์์๋ ๊ทธ๋ด ํ์๊ฐ ์์ง๋ง, ์นด์ผ๋ฃจ์๋ ์๋ ๋ช ๋ น์ค ์ฒด์ปค์๋ค).
์ด ๋จ์๊น์ง ์์น ์ ๋ณด๊ฐ ๋ค์ด๊ฐ๋ค๋ ์๊ธฐ๋ ํ์๊ฐ ๋ฑ์ด ๋ด๋ AST์๋ ๊ทธ ์์ค์ ์์น ์ ๋ณด๊ฐ ๋ชจ๋ ๋ค์ด ์์ด์ผ ํ๋ค๋ ์๋ฆฌ์ ๋์ผํ๋ค. ์ด๋ฐ ๋ฅ์ ์์น ์ ๋ณด๋ ์ ๋ง ์๋ฌด ๋ฐ๋ ๋ค์ด๊ฐ ์ ์๊ธฐ ๋๋ฌธ์ ์ผ๋ฐํ(generic) ํ์ ์ด ์๋ ๊ฒ ์ ์ ํ๋ฐ, ๋ฌ์คํธ ์ปดํ์ผ๋ฌ์์ ์ด ์ญํ ์ ํ๋ ์๋ฃ๊ตฌ์กฐ์ ์ด๋ฆ์ Spanned๋ผ๊ณ ๋ถ์๊ธฐ ๋๋ฌธ์ ์นด์ผ๋ฃจ์์์๋ ๋ง์ฐฌ๊ฐ์ง๋ก Spanned<T>๋ผ๋ ์ด๋ฆ์ ์ผ๋ค. ์ด ํ์ ์ด ๊ฐ์ง๊ณ ์๋ ์์น ์ ๋ณด(Span)๋ ํฌ๊ฒ ์ธ ๊ฐ์ง๋ก ๊ตฌ์ฑ๋๋ค.
์ด๋ ํ์ผ์์ ์ ๋ํ ์์น ์ ๋ณด์ธ๊ฐ? ๋ฌผ๋ก ๊ผญ ํ์ผ์ผ ํ์๋ ์๋ค. ํ์๋ ์ฒด์ปค๊ฐ ํ์ํด์ ์์ฑํ ๊ฒฝ์ฐ๋ ์๊ณ , ๋ด์ฅ ์ ์ธ์์ ์ ๋ํ ๊ฒฝ์ฐ๋ ์์ ์ ์๋ค. ์นด์ผ๋ฃจ์์์๋ ์ด๋ค ์ ๋ณด๋ฅผ ๋ชจ๋ ํ์ณ์ Unit์ด๋ผ๋ ํ์ ์ผ๋ก ๋ง๋ค์ด ๋์๋ค.
์์์ ์ด ํ์ผ์ ์ด๋ ์์น์ธ๊ฐ?
๋์ ์ด ํ์ผ์ ์ด๋ ์์น์ธ๊ฐ? ์ค์ ๋ฒ์์ ๋์ ์ด ํฌํจ๋๋ ์ ๋๋๋ ๋๋ถ๋ถ ํธ์ ๋ฌธ์ ์ธ๋ฐ ์นด์ผ๋ฃจ์์์๋ ํฌํจ๋์ง ์๋๋ค.
๊ทธ๋ฆฌ๊ณ ๊ฐ ํ๋ ๋ณ๋ก 32๋นํธ์ฉ 12๋ฐ์ดํธ๊ฐ ํ ๋น๋์๋ค. Unit๋ 32๋นํธ๋ผ๋ ์ ์์ ์ ์ ์๋ฏ์ด ์ด ๋ฐ์ดํฐ๋ฅผ ์ ๋ง๋ก ํด์ํ๋ ค๋ฉด Source๋ผ ํ๋, ์ ๋ ฅ ์์ค๋ฅผ ์ํ ๋ณ๋์ ํ์ ์ด ํ์ํ๋ค. ์ข ๋ ์ ํํ๋ Unit์ ๋ง๋๋ ์ฃผ์ฒด๊ฐ Source๋ผ๊ณ ํด์ผ ํ ๊ฒ์ด๋ค. ์์น ๊ฐ์ ๋ฐ์ดํธ ๋จ์๊ฑฐ๋, (ํ์ ํ๋ฏ) ์๋ ๋จ์๋ก ์ด๋ ์ชฝ์ด ์ฐ์ด๋๋๋ ํ์ผ์ ๋ฐ๋ผ ๊ฒฐ์ ๋๋ค.
๊ณผ์ฐ ์ด๊ฒ ์ ์ผํ ์ค๊ณ์ธ๊ฐ ํ๋ฉด, ๋น์ฐํ ๊ทธ๋ด ๋ฆฌ๊ฐ. Source๋ฅผ ์์ ๋ ๋ฐฉ๋ฒ(Unit์ ์ฐธ์กฐ ์นด์ดํ ์ ํ๋ ์ค๋งํธ ํฌ์ธํฐ๋ก ๊ฐ์ ์น์ฐ๋ฉด ๋๋ค)์ด๋ผ๊ฑฐ๋, ์คํ์ ์ ํ์ผ ์ ๋ณด๋ฅผ ํฉ์ณ ๋ฒ๋ฆฌ๊ฑฐ๋, ์ฌ์ง์ด ๋ ๋ง์ ์ ๋ณด๋ฅผ Source์ ๋์ ธ ์ฃผ๊ณ ์๋ฌด ์ ๋ณด ์๋ ์ธ๋ฑ์ค๋ง ๋จ๊ธฐ๊ฑฐ๋ ํ๋ ๋์์ด ์กด์ฌํ๋ค. ๋ด๊ฐ ์์ ์ค๊ณ๋ฅผ ์ฑํํ ๊ฒ์ ๊ธฐ๋ณธ์ ์ผ๋ก i) ๊ตฌํํ๊ธฐ ์ฝ๊ณ ii) ๋จผ ํ๋ Source ๊ฐ์ด ์์น ์ ๋ณด๊ฐ ํ์ํ ๋ ๋ฌด์กฐ๊ฑด ํ์ํ ๋ ๋ค๋ฅธ ๋งฅ๋ฝ์ด ๋ค์ด๊ฐ ๋ ๊ธฐ์กด์ ์กด์ฌํ๋ ๋งฅ๋ฝ์ด ์๋ ๊ฒ ํธํด์์๋๋ฐ, ๋์ค์ ๋ณด๋ ๋ด ์๊ฐ์ด ์์ฃผ ํ๋ฆฌ์ง ์์์ง๋ง ์๋ฒฝํ ๊ฒ๋ ์๋์๋ค. ๋ค๋ฅธ ์ค๊ณ์ ์ฅ๋จ์ ์ ๋ํด ์ ์ ์ดํด ๋ณด๊ธฐ๋ก ํ์.
Source๊ฐ ์๋ ์ค๊ณ๋ ๋ ์ด์ Unit์ด ์ด๋ AST์์๋ ์ฌ์ฉ๋์ง ์์ ๋ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์๋์ผ๋ก ํด์ ํด ์ค๋ค๋ ์์ ์ด ์๊ณ , ๋ฉํฐ์ค๋ ๋ ํ๊ฒฝ์์ ์ข ๋ ์ฌ์ฉํ๊ธฐ ์ฝ๋ค(๊ธฐ์กด ์ค๊ณ์์๋ Source์ ์ ์ ํ ๋ฝ์ ๊ฑธ์ด์ผ ํ๋ค). ํ์ง๋ง ์ด๋ฐ ์ํฉ์ด ์๊ฐ๋ณด๋ค ํํ์ง ์์๊ณ , ์ด์ฐจํผ ํ์ ํ IDE์์ ์ฐ๋์ด ๋ค์ด๊ฐ๋ฉด ์ด ์ค๊ณ์ ์ฅ์ ์ด ํฌ์ง ์๋ค. ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ ๋ง์ด ์ธ ์ ์๊ณ ์ฐธ์กฐ ์นด์ดํธ์ ๋ถํ๊ฐ ์์ ์๋ ์๋ค๋ ๊ฒ๋ ๊ฑธ๋ฆผ๋์ด์๋ค.
์คํ์ ์ ํ์ผ ์ ๋ณด๋ฅผ ํฌํจํ๋ ์ค๊ณ๋ ๋ค๋ฅด๊ฒ ๋งํ๋ฉด ํ์ผ ์ ๋ณด๊ฐ ์์ด ๊ฑฐ๋ํ ๋ฒํผ์๋ค๊ฐ ๋ชจ๋ ํ์ผ์ ๋ด์ฉ์ ์ง์ด ๋ฃ๊ณ ๊ทธ ๋ฒํผ์์์ ์ธ๋ฑ์ค๋ฅผ ์์น ์ ๋ณด๋ก ์ฐ๊ฒ ๋ค๋ ๋ป์ด๋ค. (๋ฌผ๋ก ๋์ค์ ์ฐธ์กฐ๋ฅผ ์ํด์ ํ์ผ ์ ๋ณด๋ฅผ ๋ฐ๋ก ๋ ์ ์๊ฒ ์ง๋ง.) ์ด ์ค๊ณ๋ฅผ ์ ์ ๊ณ ๋ฏผํ๋ค๊ฐ ์ ์ ๊ฐ์ฅ ํฐ ์ด์ ๋ ํ์ผ์ด ๋ณ๊ฒฝ๋ ๊ฐ๋ฅ์ฑ์ ๋ฐฐ์ ํ ์ ์์๊ธฐ ๋๋ฌธ์ด๋ค. IDE์์ ์ผ๋ถ ํ์ผ๋ง ์์ ๋ ๊ฑธ ์๋ก ์ฒดํฌํ๋ ๊ฒฝ์ฐ๋ ํํ ์ผ์ด๋ค.
๋ชจ๋ ์์น ์ ๋ณด๋ฅผ Source์ ์์กดํ๋ ํธ๋ค๋ก ๋ง๋๋ ์ค๊ณ๋ ์๊ฐ๋ณด๋ค ํ ๋งํ ์๋ ์๋ค. ๋ณธ๋ ์ด๊ฑธ ์ฑํํ์ง ์์ ์ด์ ๋ ์์น ์ ๋ณด๊ฐ ์๋ฌด๋ฆฌ ๋ถํฌ๋ช ํด๋ ๋ Span์ ํฌํจํ๋ ํ๋์ Span์ ๊ณ์ฐํ๋ค๊ฑฐ๋ ํ๋ ์ ๋์ ์ฐ์ฐ์ ํ ์ ์๊ณ , ๊ทธ๋ผ ๊ทธ๊ฑธ ํ ๋๋ง๋ค Source๋ฅผ ์๊ตฌํ๋ ๊ฑด ์ข์ง ์๋ค๊ณ ์๊ฐํ๊ธฐ ๋๋ฌธ์ธ๋ฐ, ๋คํํ ๊ทธ๋ค์ง ํํ ์ผ์ ์๋์๋ค. ๊ทธ๋ฌ๋ ๋๋ฒ๊น ๊ณผ์ ์์ ์์น ์ ๋ณด๋ฅผ ๋ณผ ์ผ์ด ๊ฝค ๋ง์๋ฐ, Source๊ฐ ์๋ ๋งฅ๋ฝ์์ ํธ๋ค ๋ฒํธ๋ง ๋ณด์ด๋ ๊ฑด ๋ณ๋ก ์ ์พํ ๊ฒฝํ์ ์๋๋ผ1 ์ฌ์ ํ ๊ทธ๋ค์ง ๋ดํค์ง ์๋๋ค.
ํํธ์ผ๋ก IDE์ ์ฐ๋์ ํด ๋ณด๋ค ๋ณด๋๊น Source ์์ฒด์๋ ์ค๊ณ ๋ณ๊ฒฝ์ด ํ์ํ๋ค. ํ๋๋ UTF-16(์ฒ๋ผ ์๊ธด) ๋ฌธ์์ด์ ์กด์ฌ๋ก, ๋น์ฃผ์ผ ์คํ๋์ค(C#)๋ ๋น์ฅฌ์ผ ์คํ๋์ค ์ฝ๋(JavaScript)๋ 2๋ฐ์ดํธ ์๋๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ํ๋ ๋ฌธ์์ด์ ์ธํฐํ์ด์ค์์ ๊ฐ์ ํ๊ณ ์๊ธฐ ๋๋ฌธ์ Source์์๋ ์ด๋ฅผ ๋ฐ๋ผ์ผ ํ๋ค. ๊ฒฐ๊ณผ์ ์ผ๋ก Span์ ์ธ๋ฑ์ค๋ ํ์ผ์ด ์ด๋์ ์๋๋์ ๋ฐ๋ผ์ ๋ฐ์ดํธ ์ธ๋ฑ์ค๊ฑฐ๋ ์๋ ์ธ๋ฑ์ค๋๊ฐ ๊ฒฐ์ ๋๊ณ , ๊ฐ๋ณ ๋ฌธ์๋ 8๋นํธ ๋ฐ์ดํธ์ผ ์๋ 16๋นํธ ์๋์ผ ์๋ ์๊ฒ ๋์๋ค(๋คํํ ๋ฃจ์์ ๋ชจ๋ ๋ฌธ๋ฒ ์์๋ 7๋นํธ ๊ทธ๋ํฝ ๋ฌธ์์ ํฌํจ๋๋ค). ๋ฌผ๋ก ์ธ์ฝ๋ฉ ์ ๋ณด๊ฐ ์ด๋ ์๋ ๊ฑด ๋ ์๋๊ธฐ ๋๋ฌธ์, 8๋นํธ ๋ฐ์ดํธ ํ์ผ์ด๋ผ๋ฉด UTF-8์ด๊ฑฐ๋ MBCS2๋ก ๊ฐ์ ํ๊ณ , 16๋นํธ ์๋ ํ์ผ์ด๋ผ๋ฉด UTF-16์ผ๋ก ๊ฐ์ ํ๋ ์์ผ๋ก ์ฒ๋ฆฌํ ๋ค, ํ์ฑ ํ์๋ UTF-16์ UTF-8๋ก ๋ณํํ์ฌ ๋ฐ์ดํธ ๋ฌธ์์ด๋ก ์ ๊ทํํ๋โฆ ๋ญ ๊ทธ๋ฐ ๋ ธ๊ฐ๋ค๋ฅผ ํด์ผ ํ๋ค.
๋ ํ๋๋ Source๊ฐ ๋จ์ํ ๋ณ๊ฒฝ ๊ฐ๋ฅํ ์์ค ๋ฟ๋ง ์๋๋ผ ๋ฒ์ ๋์ด ๊ฐ๋ฅํด์ผ ํ๋ค๋ ์ ์ด์๋ค. ์ด ์ค๊ณ์ ์กด์ฌ๋ฅผ ์๊ฒ ๋ ๊ฒ์ VS ํ์ฅ์ ๋ง๋ค ์์ ์ด์๋๋ฐ, ํ์ฑ์ ํ๊ฑฐ๋ ์ฒดํน์ ํ ๋ ์ฌ์ฉํ ์์ค ์ฝ๋์ ํ์ฌ์ ์์ค ์ฝ๋์ ๋ค๋ฅผ ์ ์๊ธฐ ๋๋ฌธ์, ์์ค ์ฝ๋๊ฐ ๋ณ๊ฒฝ๋ ๋๋ง๋ค ๋ค๋ฅธ ๋ฒ์ ์ ๋ถ์ด๊ณ Span(์ ๋์ํ๋ ํ์ )์ ๋ฒ์ ๋ค ์ฌ์ด์์ ์๋ก ๋ณํ ๊ฐ๋ฅํ๊ฒ ํ๋ ๊ฒ์ด์๋ค. ๋คํํ ํ์ฌ ์นด์ผ๋ฃจ์ ์ค๊ณ๋ ํ์ผ์ด ์ถ๊ฐ ์ญ์ ๋๋ ๊ฒ์๋ ๋์๋์ด ์์ผ๋๊น ๊ธฐ์ ์ ์ผ๋ก๋ ์ ํ์ผ์ด ์ถ๊ฐ๋ ๊ฒ์ฒ๋ผ ๊ตฌํํ๋ฉด ๋์ง๋ง, ์ด๋ค โํ์ผโ๋ค์ด ์ค์ ๋ก๋ ๊ฐ์ ํ์ผ์ ๋ค๋ฅธ ๋ฒ์ ์ ๊ฐ๋ฆฌํค๋์ง, ๊ทธ๋ฆฌ๊ณ ์ด๋ค ์ฌ์ด์์ Span์ด ์ด๋ป๊ฒ ๋ณํ๋๋์ง๋ ์์ง ๊ตฌํํ ๊ฒ ์๋ค. ๋ฐ๋ผ์ ํ์ฌ๋โฆ ๋ณ๊ฒฝ์ด ์ผ์ด๋๊ฒ ๋๋ฉด ๊ทธ๋ฅ ๋ฝ์ ๊ฑด๋ค. ์ฅ๊ธฐ์ ์ผ๋ก๋ ๋ฒ์ ๋์ ๊ตฌํํด์ผ ํ ๊ฑฐ๋ผ ๋ณธ๋ค.
์ฐจํ ์๊ณ
๋ณธ๋๋ ํ์์ ์ค๋ฅ ๋ณต๊ตฌ๋ฅผ ์ด๋ฒ ๊ธ์ ์ฐ๋ ค๊ณ ํ๋๋ฐโฆ ํ์ ์๊ธฐ๋ฅผ ์ฐ๋ค ๋ณด๋๊น ๋๋ฌด ๊ธธ์ด์ ธ์ ํด๋น ๋ถ๋ถ์ ๋ค์ ๊ธ๋ก ๋๊ธฐ๊ธฐ๋ก ํ๋ค.
์นด์ผ๋ฃจ์์๋ ์ค์ ๋ก ์ด๋ฐ ์์ผ๋ก ๋ด๋ถ์ ์ผ๋ก๋ ํธ๋ค๋ก๋ง ๋ณด์ด๋ ๊ฐ์ด ํ๋ ์กด์ฌํ๋ค. ๋ฐ๋ก ScopedId๋ผ๊ณ ๋ถ๋ฅด๋ ์ง์ญ ๋ณ์ ์ธ๋ฑ์ค์ธ๋ฐ, ์ด๋ฆ์ด ์ ๋์ค๋ ๊ฑด ์ข ๊ท์ฐฎ์ง๋ง ํด ๋ณด๋ค ๋ณด๋๊น ๊ฒฐ๊ตญ ์ง์ญ ๋ณ์ ์ธ๋ฑ์ค๋ฅผ ํ ๋นํ๋ ๋ก๊ทธ๋ฅผ ์ฐ์ผ๋ฉด ๊ฒ์์ผ๋ก ์์๋ผ ์ ์์ด์ ๋๋ฒ๊น ํ ๋ ๋ฌธ์ ๊ฐ ํฌ์ง ์์๋ค. ํ์ง๋ง ์์น ์ ๋ณด๋ฅผ ์ด๋ฐ ์์ผ๋ก ๋ก๊ทธ์ ๋งค๋ฒ ์ฐ์ด ์ค ์๋ ์๋ ๋ ธ๋ฆ์ด๋ค.ย โฉ๏ธ
๋๋ถ๋ถ์ ๋ ๊ฑฐ์ ๋ฌธ์ ์ธ์ฝ๋ฉ์ด ํฌํจ๋๋ค. ์ปฌ๋ผ ๊ณ์ฐํ ๋ ๋ฐ์ดํธ ์ธ๋ฑ์ค๊ฐ ์ปฌ๋ผ ์ธ๋ฑ์ค์ ์ฌ์ค์ ๊ฐ๋ค๋ ๋งค์ฐ ์ค์ํ ์ฅ์ ์ด ์๋ค. ๋ฌผ๋ก GB 18030 ๊ฐ์ ๋ณ์ข ์ด ์๊ธด ํ์ง๋งโฆย โฉ๏ธ





