JParser (3) CDG 사용 팁

이번 포스팅에서는 앞서 살펴본 CDG로 문법을 정의할 때 쓸 수 있는 몇가지 팁을 살펴보겠다.

공백(whitespace)

내가 아는 모든 프로그래밍 언어에는 공백(whitespace)이 들어갈 수 있다. 공백은 보통 스페이스바를 눌러서 입력하는 띄어쓰기 문자, 탭 문자, 줄바꿈 문자, 그리고 주석(comment)등이 포함된다.

lex와 yacc을 이용해 파서를 구성하는 경우, 일반적으로 lex에서 공백은 제거하고 토큰의 시퀀스를 yacc으로 전달한다. 그래서 yacc에서는 공백에 대해 신경을 쓸 필요가 없다. 하지만 CDG는 입력된 스트링의 모든 글자의 해석에 필요한 정보가 모두 들어가야 하기 때문에 공백에 대한 내용이 문법 정의에 반드시 포함되어야 한다.

나는 CDG 문법 정의에 보통 공백을 위한 별도의 넌터미널을 정의하고, 그 이름을 White Space의 약자로 WS라고 한다. WS는 흔히 다음과 같은 형태를 갖는다.

WS = (' \n\r\t' | Comment)*
Comment = LineComment | BlockComment

LineComment는 C나 자바에서 //로 시작하는 줄 주석을 의미하고 BlockComment는 /*와 */로 둘러싸인 블럭 주석을 의미한다. LineComment를 다음과 같이 쓸 수 있을 것이다.

LineComment = "//" (.-'\n')* '\n'

하지만 이렇게만 쓰면 소스 코드의 가장 마지막 줄에 LineComment가 나오고 그 뒤에 개행문자(\n)가 없으면 그 주석을 인식할 수 없다. 그래서 다음과 같이 EOF(End of file) 심볼을 추가해서 사용한다.

LineComment = "//" (.-'\n')* ('\n' | EOF)
EOF = !.

이렇게 쓰면 EOF는 현재 위치 이후에 어떤 문자라도 나오면 매칭되지 않게 되는 lookahead except 심볼이기 때문에 end of file, 즉 파일의 끝(혹은 입력의 끝)을 나타내게 되어 소스 코드의 마지막 줄에 개행 문자 없이 줄 주석을 적어도 문제 없이 동작한다.

파이썬 등의 언어에서처럼 주석 시작 표시를 //가 아니라 #로 하고 싶으면 간단하게 수정할 수 있을 것이다.

블럭 주석은 다음과 같이 정의할 수 있다.

BlockComment = "/*" ((. !"*/")* .)? "*/"

중간에 등장하는 !"*/"라는 심볼은 . 뒤에 */라는 패턴이 바로 이어서 등장하지 않도록 하는 lookahead except 심볼이다. 만약 이런 조치가 없이 "/*" .* "*/"와 같은 형태로 정의하면 블럭 코멘트가 끝나는 위치를 정확히 알 수 없다. 예를 들어 /* hello! */*/와 같은 입력이 들어오면 블럭 주석은 /* hello! */까지이고 이어지는 */는 파싱 오류를 발생시켜야 하지만 lookahead except 심볼이 없으면 이어지는 */까지 블럭 주석으로 이해하게 되어 원하는대로 동작하지 않게 된다.

스트링

\n, \t 등과 같은 이스케이프 문자를 포함하는 스트링은 다음과 같이 적을 수 있다.

StringLiteral = '"' StringElem* '"'
StringElem: StringElem = StringChar
  | EscapeChar
StringChar = .-'\\"'
EscapeChar = '\\' 'nbrt$\\"'

Token

이전 포스팅에서 join 심볼을 설명하면서 &Name라는 조건을 붙여서 모호성을 해결했던 적이 있다. 비슷한 패턴으로, 나는 다음과 같이 Tk(Token의 줄임말) 넌터미널을 정의해 두고 적절한 때에 &Tk 조건을 붙여서 사용하는 경우가 많다. 물론 Tk 심볼의 정의는 언어에 따라 달라질 것이다.

Tk = <'a-zA-Z0-9_'+> | <'+\-*/!|&=<>'+>

예를 들어, 이 Tk 심볼은 아래와 같이 쓸 수 있다.

ClassDef = "class"&Tk WS ClassName (WS "extends"&Tk WS ClassName)? WS '{' (WS ClassElems)? WS '}'

이렇게 쓰면 “classxyz”와 같은 단어가 나왔을 때 이 단어를 “class”라는 키워드와 이어지는 “xyz”로 해석한다거나 하는 문제를 해결할 수 있다. 만약 위의 ClassDef 넌터미널의 정의에서 "class"&Tk라고 쓰지 않고 "class"라고만 썼다면 “xyz”를 ClassName으로 해석하게 되었을 것인데, 이는 일반적으로 우리가 원하는 동작이 아니다.

컴마로 구분된 요소들

[1, 2, 3]과 같은 리스트나 {hello: 1, world: 2}와 같은 오브젝트 문법은 다음과 같이 적을 수 있다. (Expr이라는 심볼은 별도로 정의되어 있다고 가정하자)

List = '[' WS Expr (WS ',' WS Expr)* WS ']'
     | '[' WS ']'

중간중간 WS 심볼이 사용된 것에 유의하자. RHS가 두 개로 구성된 이유는 빈 리스트, 즉 []와 같은 리스트 때문이다. 이게 보기 싫다면 ? 기능을 이용해서 다음과 같이 적을 수도 있다. 의미는 동일하다.

List = '[' (WS Expr (WS ',' WS Expr)*)? WS ']'

오브젝트 문법은 아래와 같이 적을 수 있을 것이다. (Expr과 Name 심볼은 별도로 정의되어 있다고 가정하자)

Object = '{' WS ObjectElem (WS ',' WS ObjectElem)* WS '}'
       | '{' WS '}'
ObjectElem = Name WS ':' WS Expr

이번에도 마찬가지로 Object의 RHS가 두개로 나뉘어진건 빈 오브젝트, 즉 {}와 같은 경우 때문이다. 이게 싫으면 아래와 같이 적어도 된다.

Object = '{' (WS ObjectElem (WS ',' WS ObjectElem)*)? WS '}'

조금 더 현실적인 예제

Expr: Expr = IfExpr | AssignExpr | Literal | Identifier
IfExpr = "if"&Keyword WS '(' WS Expr WS ')' WS Expr WS "else"&Keyword WS Expr
AssignExpr = Identifier WS '=' WS Expr
Literal = "true"&Keyword | "false"&Keyword | IntLiteral
IntLiteral = '0' | '1-9' '0-9'*
Token = Identifier | Keyword
Identifier = Word-Keyword
Keyword = ("if" | "else" | "true" | "false")&Word
Word = <'a-zA-Z_' 'a-zA-Z0-9_'*>
WS = ' '*

키워드가 등장하는 지점에 &Keyword 혹은 &Token을 붙여주었다.

CDG로 쓴 CDG 문법

새로운 언어를 만들 때 중요한 마일스톤중 하나가 새로운 언어로 새로운 언어의 컴파일러를 만들 수 있게 되는 것이다. 비슷하게 CDG라는 새로운 언어가 기능적으로 충분한지 증명하려면 CDG로 CDG를 정의할 수 있는지 확인해야 할 것이다.

지금까지 설명한 CDG의 문법을 CDG로 적으면 아래와 같이 적을 수 있다.

Grammar = WS Def (WSNL Def)* WS
Def = Rule

Rule = LHS WS '=' WS RHS (WS '|' WS RHS)*
LHS = Nonterminal
RHS = Sequence
Sequence = Symbol (WS Symbol)*

// Symbol
Symbol = BinSymbol
BinSymbol = BinSymbol WS '&' WS PreUnSymbol
  | BinSymbol WS '-' WS PreUnSymbol
  | PreUnSymbol
PreUnSymbol = '^' WS PreUnSymbol
  | '!' WS PreUnSymbol
  | PostUnSymbol
PostUnSymbol = PostUnSymbol WS '?'
  | PostUnSymbol WS '*'
  | PostUnSymbol WS '+'
  | AtomSymbol
AtomSymbol = Terminal
  | TerminalChoice
  | StringSymbol
  | Nonterminal
  | '(' WS InPlaceChoices WS ')'
  | Longest
  | EmptySequence
Terminal = '\'' TerminalChar '\''
  | '.'
TerminalChoice = '\'' TerminalChoiceElem TerminalChoiceElem+ '\''
  | '\'' TerminalChoiceRange '\''
TerminalChoiceElem = TerminalChoiceChar
  | TerminalChoiceRange
TerminalChoiceRange = TerminalChoiceChar '-' TerminalChoiceChar
StringSymbol = '"' StringChar* '"'
Nonterminal = NonterminalName
InPlaceChoices = Sequence (WS '|' WS Sequence)*
Longest = '<' WS InPlaceChoices WS '>'
EmptySequence = '#'

TerminalChar = .-'\\'
  | '\\' '\'\\bnrt'
  | UnicodeChar
TerminalChoiceChar = .-'\'\-\\'
  | '\\' '\'\-\\bnrt'
  | UnicodeChar
StringChar = .-'"\\'
  | '\\' '"\\bnrt'
  | UnicodeChar
UnicodeChar = '\\' 'u' '0-9A-Fa-f' '0-9A-Fa-f' '0-9A-Fa-f' '0-9A-Fa-f'

NonterminalName = Id | '`' Id '`'

Id = <'a-zA-Z_' 'a-zA-Z0-9_'*>
WS = (' \n\r\t' | Comment)*
WSNL = <(' \r\t' | Comment)* '\n' WS>
Comment = LineComment | BlockComment
LineComment = "//" (.-'\n')* (EOF | '\n')
BlockComment = "/*" ((. !"*/")* .)? "*/"
EOF = !.

전체 목차:

이어지는 포스팅에서는 CDG를 실제로 파싱을 할 수 있는 알고리즘에 대해 이야기해 보자.

이 페이지에서 오류나 문제점을 발견하시면 이메일로 알려주시면 감사하겠습니다.
뒤로