CPL 1 : Syntax and Parsing

목차

Parsing by Hand

Given the following grammar: 

 

(1 + 2) * (1 + 4)를 AST와 Node Version으로 변환.

 

Given the following Grammar:

 

pi * r * r을 AST와 Node Version으로 변환.

 

 

Given the following grammar:

AndC가 OrC보다 먼저.

false or true and (true or false)

 

 

Paret

context-free syntax

  Expr.NumExt       = INT      // integer literals
  Expr.TrueExt      = [true]
  Expr.FalseExt     = [false]

  Expr.UnOpExt      = [([UnOp] [Expr])]
  Expr.BinOpExt     = [([BinOp] [Expr] [Expr])]

  UnOp.MIN          = [-]
  UnOp.NOT          = [not]
  UnOp.HEAD         = [head]
  UnOp.TAIL         = [tail]
  UnOp.ISNIL        = [is-nil]
  UnOp.ISLIST       = [is-list]

  BinOp.PLUS        = [+]
  BinOp.MULT        = [*]
  BinOp.MINUS       = [-]
  BinOp.AND         = [and]
  BinOp.OR          = [or]
  BinOp.NUMEQ       = [num=]
  BinOp.NUMLT       = [num<]
  BinOp.NUMGT       = [num>]
  BinOp.CONS        = [cons]

  Expr.IfExt        = [(if [Expr] [Expr] [Expr])]
  Expr.NilExt       = [nil]
  Expr.ListExt      = [(list [Expr*])]

  Expr.CondExt      = [(cond [Branch+])]
  Expr.CondEExt     = [(cond [Branch+] (else [Expr]))]
  Branch.Branch     = [([Expr] [Expr])]

 

(+ (* 152 390) 23)

 

 

(if (num> (+ 2 3) 4)
    10
    2
)

 

 

(cons 1 (cons 2 (cons 3 nil)))

 

 

 

(is-nil (list 2 3 5 8 13))

 

 

 

(cond 
      ((num= 4 3) 0) 
      (false 1) 
      (else 3)
)

 

 

 

Mandatory Assignments

과제: Take an s-expression and returns an AST (ExprExt).

 

1. Basics

case SNum(n) => NumExt(n)
case SSym("true") => TrueExt()
case SSym("false") => FalseExt()
case SSym("nil") => NilExt()

 

 

2. Unary operators

case SList(SSym("-") :: l :: Nil) => UnOpExt("-", parse(l))
case SList(SSym("not") :: l :: Nil) => UnOpExt("not", parse(l))
case SList(SSym("head") :: l :: Nil) => UnOpExt("head", parse(l))
case SList(SSym("head") :: l :: Nil) => UnOpExt("head", parse(l))
case SList(SSym("tail") :: l :: Nil) => UnOpExt("tail", parse(l))
case SList(SSym("is-nil") :: l :: Nil) => UnOpExt("is-nil", parse(l))
case SList(SSym("is-list") :: l :: Nil) => UnOpExt("is-list", parse(l))

 

 

3. Binary Operators

case SList(SSym("+") :: l :: r :: Nil) => BinOpExt("+", parse(l), parse(r))
case SList(SSym("-") :: l :: r :: Nil) => BinOpExt("-", parse(l), parse(r))
case SList(SSym("*") :: l :: r :: Nil) => BinOpExt("*", parse(l), parse(r))
case SList(SSym("num=") :: l :: r :: Nil) => BinOpExt("num=", parse(l), parse(r))
case SList(SSym("num<") :: l :: r :: Nil) => BinOpExt("num<", parse(l), parse(r))
case SList(SSym("num>") :: l :: r :: Nil) => BinOpExt("num>", parse(l), parse(r))
case SList(SSym("and") :: l :: r :: Nil) => BinOpExt("and", parse(l), parse(r))
case SList(SSym("or") :: l :: r :: Nil) => BinOpExt("or", parse(l), parse(r))
case SList(SSym("cons") :: l :: r :: Nil) => BinOpExt("cons", parse(l), parse(r))

 

 

4. If statement

case SList(SSym("if") :: c :: t :: e :: Nil) => IfExt(parse(c), parse(t), parse(e))

 

 

5. List

case SList(SSym("list") :: Nil) => ListExt(Nil)
case SList(SSym("list") :: t) => ListExt(parseList(t))


def parseList(t: List[SExpr]) : List[ExprExt] = t match {
  case Nil => Nil
  case h :: t => parse(h) :: parseList(t)
}

 

우선 Empty List, 즉 SList(SSym("list) :: Nil)일 경우에는 ListExt(Nil) 반환.

만약에 empty list가 아닌 경우에는 helper function을 따로 만든다. 

 

 

6. Multi-Armed Conditional

Multi-Armed Conditional은 다음과 같은 형태가 있다. 

(cond (e00 e01) (e10 e11) ... (en0 en1))

(cond (e00 e01) (e10 e11) ... (en0 en1) (else e))

 

 

case SList(SSym("cond") :: t) => parseCond(t)

def parseCond(t: List[SExpr]) : ExprExt = t match {
  case Nil => throw new ParseExceptionImpl("")
  case SList(x :: y :: Nil) :: SList(SSym("else") :: z :: Nil) :: Nil => CondEExt(List((parse(x), parse(y))), parse(z))
  case SList(x :: y :: Nil) :: Nil => CondExt(List((parse(x), parse(y))))
  case SList(x :: y :: Nil) :: tail => parseCond(tail) match {
    case CondEExt(condition, e) => CondEExt((parse(x), parse(y)) :: condition, e)
    case CondExt(condition) => CondExt((parse(x), parse(y)) :: condition)
    case _ => throw new ParseExceptionImpl("")
  }
  case _ => throw new ParseExceptionImpl("")
}

 

1. (cond  (e00  e01)  (else e))일 경우:

parseCond에 두번째 condition

  case SList(x :: y :: Nil) :: SList(SSym("else") :: z :: Nil) :: Nil => CondEExt(List((parse(x), parse(y))), parse(z))

 

2. (cond  (e00  e01)일 경우:

case SList(x :: y :: Nil) :: Nil => CondExt(List((parse(x), parse(y))))

 

3. 만약에 condition이 하나가 아니라 여러개이면:

  case SList(x :: y :: Nil) :: tail => parseCond(tail) match {
    case CondEExt(condition, e) => CondEExt((parse(x), parse(y)) :: condition, e)
    case CondExt(condition) => CondExt((parse(x), parse(y)) :: condition)
    case _ => throw new ParseExceptionImpl("")
  }