Let's start by defining the rules of production and post-production, in which all elements are implemented with Swift.
Production and Post-production rules, context-free grammar
::= <> Backus-Naur Form
Context Free <A> ::= 0 | <A><B>
A => 0
A => AB
Is a set of production rules that describe all posible strings,
defined as simple replacements
::= "Separate replacement symbols"
Terminal -> Simple replacement, only one rule
<NON TERMINAL> -> Multiple replacement, set of rules
with context free (position of symbols in text)
<letter> ::= A-Z,a-z
<var> ::= [<letter>]
<var> ::= <E>
<Number> ::= <Decimal>
<Operator> ::= + | - | * | /
<Decimal> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | <Decimal <Decimal>
<E> ::= <Number> | <Number> <Operator> <E> | (<E>)
Recursive Decent Parsing (no left recursion)
Parser without backtracking, allows to decide which production to use
by examining only the next n tokens of input.
Utilities
This set of helpers are mainly for the node
Helpers.swift
import Foundation
var identifiers: [String: Float] = [:]
extension Float: Node {
public func interpret() throws -> Float {
return self
}
}
extension String: Node {
public func interpret() throws -> Float {
guard let value = identifiers[self] else {
throw Parser.Error.undefined(self)
}
return value
}
}
extension String {
func getPrefix(regex: String) -> String? {
let expression = try! NSRegularExpression(pattern: "^\(regex)", options: [])
let range = expression.rangeOfFirstMatch(in: self, options: [], range: NSRange(location: 0, length: self.utf16.count))
if range.location == 0 {
return (self as NSString).substring(with: range)
}
return nil
}
mutating func trimLeadingWhitespace() {
let i = startIndex
while i < endIndex {
guard CharacterSet.whitespacesAndNewlines.contains(self[i].unicodeScalars.first!) else {
return
}
self.remove(at: i)
}
}
}
Token
Each token represents a pattern within the chain of characters, let it be data types, symbols, identifiers, etc.
Token.swift
import Foundation
public enum Token {
case `var`
case equals
case op(String)
case number(Int)
case parenthesesOpen
case parenthesesClose
case identifier(String)
typealias Generator = (String) -> Token?
static var generators: [String: Generator] {
return [
"\\=": { _ in .equals },
"\\+|\\-|\\*|\\/": { .op($0) },
"\\(": { _ in .parenthesesOpen },
"\\)": { _ in .parenthesesClose },
"\\-?([1-9][0-9]*)": { .number(Int($0)!) },
"[a-zA-Z][a-zA-Z_0-9]*": {
guard $0 != "var" else { return .var }
return .identifier($0)
},
//"\\-?([1-9]*\\.[0-9]+|[0-9]+)": { .number(Float($0)!) } //FLOAT
]
}
}
Lexer
Process the input String that it receives as argument and outputs a collection of tokens.
Lexer.swift
import Foundation
public class Lexer {
public let tokens: [Token]
public init(code: String) {
var code = code
code.trimLeadingWhitespace()
var tokens: [Token] = []
while let next = Lexer.getNextPrefix(code: code) {
let (regex, prefix) = next
code = String(code[prefix.endIndex...])
code.trimLeadingWhitespace()
guard let generator = Token.generators[regex],
let token = generator(prefix) else {
fatalError()
}
tokens.append(token)
}
self.tokens = tokens
}
public static func getNextPrefix(code: String) -> (regex: String, prefix: String)? {
let keyValue = Token.generators
.first(where: { regex, generator in
code.getPrefix(regex: regex) != nil
})
guard let regex = keyValue?.key,
keyValue?.value != nil else {
return nil
}
return (regex, code.getPrefix(regex: regex)!)
}
}
Parser
From the collection of tokens returned by the Lexer the Parser generates a tree which holds a syntactic structure of the source code of the programming language. At this level is possible to return information about any errors that may be found.
Parser.swift
import Foundation
public class Parser {
enum Error: Swift.Error {
case expected(String)
case undefined(String)
case expectedNumber
case expectedOperator
case expectedIdentifier
case expectedExpression
}
var index = 0
let tokens: [Token]
var canPop: Bool {
return index < tokens.count
}
public init(tokens: [Token]) {
self.tokens = tokens
}
func peek() -> Token {
return tokens[index]
}
func peekPrecedence() throws -> Int {
guard canPop, case let .op(op) = peek() else {
return -1
}
switch op {
case "+", "-": return 1
case "*", "/": return 2
default: return 0
}
}
func popToken() -> Token {
let token = tokens[index]
index += 1
return token
}
func parseNumber() throws -> Float {
guard case let .number(float) = popToken() else {
throw Error.expectedNumber
}
return Float(float)
}
func parseParentheses() throws -> Node {
guard case .parenthesesOpen = popToken() else {
throw Error.expected("(")
}
let expressionNode = try parseExpression()
guard case .parenthesesClose = popToken() else {
throw Error.expected(")")
}
return expressionNode
}
func parseIdentifier() throws -> Node {
guard case let .identifier(name) = popToken() else {
throw Error.expectedIdentifier
}
return name
}
func parseValue() throws -> Node {
switch (peek()) {
case .number:
return try parseNumber()
case .identifier:
return try parseIdentifier()
case .parenthesesOpen:
return try parseParentheses()
default:
throw Error.expected("<Expression> not valid")
}
}
public func parseExpression() throws -> Node {
guard canPop else { throw Error.expectedExpression }
let node = try parseValue()
return try ast(node: node)
}
func parseVariableDeclaration() throws -> Node {
guard case .var = popToken() else {
throw Error.expected("\"var\" in variable declaration")
}
guard case let .identifier(name) = popToken() else {
throw Error.expectedIdentifier
}
guard case .equals = popToken() else {
throw Error.expected("= not found for variable <\(name)>")
}
let expression = try parseExpression()
return VariableDeclaration(name: name, value: expression)
}
func parse() throws -> Node {
var nodes: [Node] = []
while canPop {
let token = peek()
switch token {
case .var:
let declaration = try parseVariableDeclaration()
nodes.append(declaration)
default:
let expression = try parseExpression()
nodes.append(expression)
}
}
return Block(nodes: nodes)
}
func ast(node: Node, nodePrecedence: Int = 0) throws -> Node { //Abstract Syntax Tree
var leftNode = node
while let precedence = try peekPrecedence() as Int?, precedence >= nodePrecedence {
guard case let .op(op) = popToken() else {
throw Error.expectedOperator
}
let rightNode = try parseValue()
/*
// ************************** PRECEDENCE ************************** //
var rightNode = try parseValue()
let nextPrecedence = try peekPrecedence()
if precedence < nextPrecedence {
rightNode = try ast(node: rightNode, nodePrecedence: precedence + 1)
}
// ************************** PRECEDENCE ************************** //
*/
leftNode = InfixOperation(lhs: leftNode, rhs: rightNode, op: op)
}
return leftNode
}
}
The Parser returns an AST (Abstract Syntax Tree) that has to be interpreted, and it's composed by Nodes
Node
Nodes define the structure for the declaration of variables with a keyword or for any INFIX operation that are characterized by an operator between two operands like 2+2 and blocks like (1 + 2) - 2 as well.
Either side of the operator can contain different operations
Node.swift
import Foundation
public protocol Node {
func interpret() throws -> Float
}
struct VariableDeclaration: Node {
let name: String
let value: Node
func interpret() throws -> Float {
let val = try value.interpret()
identifiers[name] = val
return val
}
}
public struct InfixOperation: Node {
let lhs: Node
let rhs: Node
let op: String
public func interpret() throws -> Float {
let left = try lhs.interpret()
let right = try rhs.interpret()
switch op {
case "+": return left + right
case "-": return left - right
case "*": return left * right
case "+/": return left / right
default: return 0
}
}
}
// Node wrapper around multiple nodes
struct Block: Node {
let nodes: [Node]
func interpret() throws -> Float {
for line in nodes[0..<(nodes.endIndex - 1)] {
_ = try line.interpret()
}
guard let last = nodes.last else {
throw Parser.Error.expectedExpression
}
// All nodes have been interpreted before returning
return try last.interpret()
}
}
Interpeter
Is the implementation of arithmetic operations and the order of expressions based on their priority.
Main Program
Here we have some simple examples to test the Lexer and Parser according to the production and post-production rules.
main.swift
//let code = "(4+2)*4+6" //30
//let code = "(4/2)*4+2" //10
let code = "4+2*4+6" //18 with precedence, 30 no precedence
/*
var code = """
var a = 4
var b = 2
var c = 6
var z = a + b * a + c
"""
*/
let lexer = Lexer(code: code)
let parser = Parser(tokens: lexer.tokens)
do {
let ast = try parser.parse()
print(try ast.interpret())
}
catch {
print((error as? Parser.Error)!)
}
With such a simple example is easy to follow each stage and see what output is expected from each.