Parsing Expression Grammars(PEGs)

이번 포스팅에서는 Parsing Expression Grammars(PEGs)에 대해 알아보는 시간을 갖도록 하겠습니다.

들어가기에 앞서

예전에 Lex와 YACC을 사용해서 간단한 파서를 만드는 과제를 해본 경험이 있으시죠? 컴파일러 시간에 ᅟ정규표현식과 Context-free grammars(CFGs)등을 배우면서 말지요. 이 과정에서 BNF와 비슷한 표기법으로 우리가 파싱하고자 하는 언어의 문법을 정의했던 기억이 납니다. PEGs도 CFGs와 비슷한 것이라고 보시면 됩니다.

PEGs란?

PEGs는 CFGs와 비슷하지만, 몇 가지 차이점이 있습니다. 그중 가장 큰 차이점은 순차 선택(ordered choice)에 있습니다. CFGs에서 아래와 같이 C언어 스타일의 if/then/else 문장을 정의하면

S ← 'if' C 'then' S 'else' S | 'if' C 'then' S

if then if then else와 같은 구문 분석시 else문이  어느 if문에 해당하는지 모호(ambiguous)해집니다. 반면 PEGs에서 같은 문장을 정의하면

S ← 'if' C 'then' S 'else' S / 'if' C 'then' S

와 같이 '/'를 통해 순서대로 매치하도록 합니다. 그래서 if then if then else 구문을 (if then (if then else))와 같이 분석합니다. 그 외에 a &b와 같이 b가 나와야만 a와 매치한다던지, a !b와 같이 b가 나오지 않아야만 a와 매치한다던지 하는 추가적인 문법도 있습니다.

PEGs는 자연언어처리보다 컴퓨터가 처리할 DSL(Doman Specific Language) 구현에 더 용이하다고 합니다. 자세한 사항은 참고의 링크들을 읽어보세요.

참고

Parsing expression grammar - Wikipedia

The Packrat Parsing and Parsing Expression Grammars Page

PEG paper

Posted by Bitnine(비트나인)