5일만에 뚝딱 스크립트 언어 만들기 PGLight (3/5)

Posted by 적분 ∫2tdt=t²+c
2013.06.17 21:29 프로그래밍/PG어




어 벌써 3번째 글인데 아직 진도가 파싱밖에 못나가서 조금 당황스럽네요. 이거 길어질지도...

저번에 추상문법트리 구조체를 짜는것까지 했습니다. 이제 본격적으로 파서를 짜면 되는데요, 파서 짜는건 정말로 간단합니다. 1일차에서 짰던 BNF를 일부만 가지고 올게요.


<s> ::= <sentence>* <eof>


<sentence> ::= <if>
    | <for>

<if> ::= "if" "(" <expr> ")" "{" <sentence>* "}"
    ("else" "if" "(" <expr> ")" "{" <sentence>* "}")*
    ("else" "{" <sentence>* "}")?


<while> ::= "while" "(" <simple_sentence> ")"
    "{" <sentence>* "}"
    ("done" "{" <sentence>* "}")?
    ("else" "{" <sentence>* "}")?

전체 문법은 수 십개의 규칙으로 이루어질텐데요, 이 각각의 규칙은 하나의 함수로 바뀌게 됩니다. 그리고 제일 꼭대기에 있는 규칙에서부터 차례로 확장해 나가며 전체 토큰을 일치시키는 구조를 찾는것이죠. 이 방식을 Top-down방식(전체적인 구조에서 시작하여 세부적인 부분을 일치시켜나가는 기법. 짜기 쉬워요) 말로 설명하면 복잡할테니 이야기로 쓸게요. (길어서 닫아놓겠습니다. 볼사람만 펼쳐보세요)


위 설명을 보면 알수 있듯이, 파싱단계는 규칙이 다른 규칙을 부르면서 토큰을 확인하는 과정으로 이루어집니다. 규칙을 함수로 생각하고, 토큰 목록을 인자로 생각하면, 파싱이란 작업은 토큰 목록을 인수로하는 함수들의 재귀적인 호출로 치환될수 있다는거죠.


각각의 규칙을 함수로 만들어 볼까요?


함수를 무지 많이 선언했어요.

Tokit은 vector<Token>의 이터레이터 타입입니다. 자주 쓸거니깐 짧게 줄여놓은거죠. 하나의 규칙은 대게 하나의 함수와 대응돼요. P_s는 <s>를 파싱하고, P_sentence는 <sentence>를 파싱하며, P_if는 <if>를 파싱하는 식인거죠.

인자로 넘겨주는 놈은 죄다 같습니다. Tokit begin, Tokit end는 토큰의 시작과 끝을 넘겨주는 거에요. (토큰 목록 전체를 vector로 넘겨주고 받으면 낭비가 심하니깐 이렇게 한거에요.) 세번째 인자 out은 파싱의 결과로 뱉어내는 추상문법트리이구요, 마지막 err는 파싱이 실패했을때 에러메세지를 모아두는 것입니다. 에러 메세지가 친절해야 코딩할 맛이나니깐요.

그리고 이 함수들은 성공하면 일치한 토큰의 개수를 반환하고, 실패하면 음수를 반환한다고 약속을 잡아놨습니다.



이런 구조로 파싱이 이뤄지는 겁니다.

각각의 규칙을 짤때는 그 규칙만 생각하면 됩니다. <if>짤때 아 <expr>도 파싱해야하는데.. 이런 고민말고, 그냥 P_expr를 호출해서 expr를 파싱할 책임을 넘겨버리는 센스가 필요해요. 함수만 잘 분할하면, 파싱에서 하는 일이 그저 if문으로 토큰 타입이 일치하는지 확인하고, 아니면 에러 메세지 추가하고 실패하는게 전부가 됩니다. 할일은 많지만 단순한 작업들이지요.

또다른 함수로 <add_expr>를 파싱하는 코드입니다.

주석에도 나와있듯이 <add_expr> ::= (<add_expr> (" " | "-"))? <mul_expr> 에 따라 함수를 작성할 경우, Top-down 방식에 왼쪽에서부터 토큰을 일치시켜나간다는 특징때문에, 무한루프에 빠지게 됩니다. 이해가 안되면 아래를 펼쳐보세요.


그래서 연산자 우선순위와 결합 순서를 반영해서 규칙을 세울때 유의할 필요가 있습니다. 다음 BNF 규칙은 연산자 우선순위를 [] () . 연산 > ^ 연산 > - 연산(부호) > * / % 연산 > - 연산 > 비교연산 > and 연산 > or 연산 > not 연산로 하여 작성된겁니다. 참고하시면 좋을거에요.

<expr> ::= <not_expr>

<not_expr> ::= <or_expr>
    | "not" <not_expr>

<or_expr> ::= <and_expr> ("or" <and_expr>)*

<and_expr> ::= <cmp_expr> ("and" <cmp_expr>)*

<cmp_op> ::= "=="
    | "!="
    | ">"
    | "<"
    | ">="
    | "<="

<cmp_expr> ::= <add_expr> ( <cmp_op> <add_expr>)?

<add_expr> ::= <mul_expr> ( (" " | "-") <mul_expr>)*

<mul_expr> ::= <sign_expr> ( ("*" | "/" | "%")  <sign_expr>)*

<sign_expr> ::= <pow_expr>
    | "-"? <sign_exp>

<pow_expr> ::= (<a_expr> "^")* <a_expr>

<a_expr> ::= <par_expr>
    ( ("[" <expr> "]") | ("." <identifier>) | ( "(" ( <expr> ("," <expr>)* )? ")" ))*

<par_expr> ::= <literal> | <identifier> | "this"
    | '(' <expr> ')' | <lambda_expr> | <function_expr>


아, 설명안하고 지나왔는데 에러 메세지를 담는 ErrorCnt클래스는 그냥 단순하게 vector를 래핑한 클래스입니다.

지금와서 생각해보니, 굳이 만들필요 없었던거같기도해요. 그냥 vector<Error>를 써도 될법합니다.


전체 코드가 보고 싶은 분들 계시겠지요? 주석도 안 달리고 난잡하지만, 혹시나 해서 올려둡니다. (대따길어요)


자, 이렇게 단순하고도 긴 파싱작업을 마쳤습니다.

다음에는 기본적인 인터프리터(혹은 좀더 고급스럽게 가상머신)을 설계해보도록 할거에요.



Tags
이 댓글을 비밀 댓글로
    • 2016.08.09 19:55
    비밀댓글입니다
    • 어 죄송합니다. 코드를 올리는 과정에서 실수가 있었나봅니다. TokenType::plus인 경우에는 PGL_add_expr을, minus인 경우에는 PGL_minus_expr를 생성하는게 맞습니다. PGL_expr는 표현식을 나타내는 클래스들의 조상이 되는 추상클래스여서 아무 생성자도 없는게 맞지요. make_shared<PGL_expr>을 make_shared<PGL_add_expr>, make_shared<PGL_sub_expr>로 각각 고치는게 맞습니다.

      지적 감사합니다.