문자 입력은 처리가 필요함
예로 HTML, XML, Numeric expressions(3+4/5), Regular expressions 가 있음

Lexing

extension String
{
    subscript (i: Int) -> Character
    {
        return self[index(startIndex, offsetBy: i)]
    }
    
    var isNumber : Bool
    {
        get {
            return !self.isEmpty && (self.rangeOfCharacter(from: CharacterSet.decimalDigits.inverted) == nil)
        }
    }
}

struct Token : CustomStringConvertible
{
    enum TokenType
    {
        case integer
        case plus
        case minus
        case lparen
        case rparen
    }
    
    var tokenType: TokenType
    var text: String
    
    init(_ tokenType: TokenType, _ text: String)
    {
        self.tokenType = tokenType
        self.text = text
    }
    
    var description: String
    {
        return "`\(text)`"
    }
}

func lex(_ input: String) -> [Token]
{
    var result = [Token]()
    
    var i = 0
    while i < input.count
    {
        switch input[i]
        {
        case "+" :
            result.append(Token(.plus, "+"))
        case "-" :
            result.append(Token(.minus, "-"))
        case "(" :
            result.append(Token(.lparen, "("))
        case ")" :
            result.append(Token(.rparen, ")"))
        default :

            var s = String(input[i])
            for j in (i+1)..<input.count
            {
                if String(input[j]).isNumber
                {
                    s.append(input[j])
                    i += 1
                }
                else
                {
                    result.append(Token(.integer, s))
                    break
                }
            }
        }
        i += 1
    }
    
    return result
}

func main()
{
    let input = "(13+14)-(12-1)"
    let tokens = lex(input)
    print(tokens)
}

Parsing

protocol Element
{
    var value: Int { get }
}

class Integer : Element
{
    var value: Int
    init(_ value: Int){
        self.value = value
    }
}

class BinaryOperation: Element
{
    enum OpType
    {
        case addition
        case substraction
    }
    
    var opType: OpType
    var left: Element
    var right: Element
    
    init() {
        opType = OpType.addition
        left = Integer(0)
        right = Integer(0)
    }
    init(_ left: Element, _ right: Element, _ opType: Element)
    {
        self.opType = OpType.addition
        self.left = left
        self.right = right
    }
    
    var value : Int
    {
        switch opType {
        case .addition:
            return left.value + right.value
        case .substraction:
            return left.value - right.value
        }
    }
    
}

func parse(_ tokens: [Token]) -> Element
{
    let result = BinaryOperation()
    var haveLHS = false
    
    var i = 0
    while i < tokens.count
    {
        let token = tokens[i]
        
        switch token.tokenType
        {
        case .integer :
            let integer = Integer(Int(token.text)!)
            if !haveLHS
            {
                result.left = integer
                haveLHS = true
            }
            else
            {
                result.right = integer
            }
        case .plus :
            result.opType = .addition
        case .minus :
            result.opType = .substraction
        case .lparen :
            var j = i
            while j < tokens.count
            {
                if tokens[j].tokenType == Token.TokenType.rparen
                {
                    break
                }
                j += 1
            }
            // process subexpression without opening
            let subexpression = tokens[(i+1)..<j]
            let element = parse(Array(subexpression))
            if !haveLHS
            {
                result.left = element
                haveLHS = true
            }
            else
            {
                result.right = element
            }
            i = j
        default : break
        }
        i += 1
    }
    
    return result
}


func main()
{
    let input = "(13+14)-(12-1)"
    let tokens = lex(input)
    print(tokens)
    
    let parse = parse(tokens)
    print("\(input) = \(parse.value)")
}

정리

• Lexing 은 텍스트를 토큰으로 만드는 것이고
• Parsing 은 토큰을 하나의 의미 있는 구조로 만드는 것이다