1
\$\begingroup\$

After having rewritten this lexer for the Nth time, I finally feel confident enough to show it publicly. I'm looking for advices to improve my code.

The lexer you are going to see is the first step of a WIP 3-step parser for my "Obganism" language:

  1. Lexing: from String to List<Token>.
  2. Refining: from List<Token> to a reduced List<Token>.
  3. Parsing: from List<Token> to List<Object>.

The Parsed Language

The language being parsed is designed to describe objects, thoses being seen as a bag of properties, operations, and events. Depending on where you come from, it may remind you a JSON schema, or a C++ structure header:

potato {
   color: string -- ( one of("yellow", "orange", "purple") )
   firmness: float -- ( range(0.0, 1.0) )
   is peeled: bool -- ( default(false) )
   ----
   peel(): void
}

In this example, potato is a type of object — diclaimer: I'm not a potato domain expert.

Here is an express guide to the syntax:

  • Everything related to this type seats in the body of its definition, surrounded by { and }.
  • color, firmness and is peeled — spaces are allowed in names — are properties of a potato.
  • They are respectively of type string, float and bool; types are introduced using :.
  • -- introduces a list of modifiers, i.e. metadata.
  • ---- is the section separator; the first section is for properties, and the second section is for operations.
  • peel is an operation, i.e. a method callable on a potato object.

Another tricky thing you may want to know is that commas (,) and line breaks are both considered as breaks, i.e. separators in the scope of a section; thus, the color property above could have been written in a multiline fashion:

color: string -- ( one of(
   "yellow"
   "orange"
   "purple"
) )

The Lexer Code

I am voluntarily excluding package declaration & imports since everything is in the same package, as well as the Token type, which is a Kotlin sealed class, similar to an enumeration with values in Swift.

// CR FYI: 180 lines, 45 blank lines, 20 functions.

val Char.isSpace: Boolean
   get() = this in " \t"

val Char.isBreak: Boolean
   get() = this in "\n,\r"

val Char.isNumeric: Boolean
   get() = this in "0123456789-."

val Char.isAlphaNumeric: Boolean
   get() = this.toLowerCase() in "etaoinsrhdlucmfywgpbvkxqjz2301456789"

val Char.isEscaper: Boolean
   get() = this == '\\'

class CharCursor(val source: String) {
   var index: Int = 0

   fun canPick(count: Int): Boolean = index + count <= source.length
   fun pick(count: Int): String = source.substring(index, index + count)
   val pick: Char get() = source[index]

   fun canNext(count: Int): Boolean = index + 1 + count <= source.length
   fun next(count: Int): String = source.substring(index + 1, index + 1 + count)
   val next: Char get() = source[index + 1]

   fun pickIs(guess: String): Boolean = canPick(guess.length) && pick(guess.length) == guess
   fun pickIs(guess: Char): Boolean = canPick(1) && pick == guess

   fun nextIs(guess: String): Boolean = canNext(guess.length) && next(guess.length) == guess
   fun nextIs(guess: Char): Boolean = canNext(1) && next == guess

   fun move(count: Int) { index += count }

   fun skipWhile(predicate: (Char) -> Boolean): String {
      val start = index

      while (canPick(1) && predicate(pick)) {
         move(1)
      }

      val end = index

      return source.substring(start, end)
   }

   fun skipUntil(predicate: (Char) -> Boolean): String {
      return skipWhile { !predicate(it) }
   }
}

fun String.lex(): List<Token> {
   if (this.isEmpty() || all { it.isSpace }) {
      return emptyList()
   }

   val cursor = CharCursor(this)
   val tokens = mutableListOf<Token>()

   var token = cursor.lex()
   while (token != null) {
      tokens += token
      token = cursor.lex()
   }

   return tokens
}

fun CharCursor.lex(): Token? {
   skipWhile { it.isSpace }

   return if (canPick(1)) when {
      pick == ':' -> { move(1); Token.TypeIntroducer }
      pick == '{' -> { move(1); Token.BlockStart }
      pick == '}' -> { move(1); Token.BlockEnd }
      pick == '(' -> { move(1); Token.ListStart }
      pick == ')' -> { move(1); Token.ListEnd }

      pick.isBreak -> { move(1); Token.Break }

      pickIs("----") -> { move(4); Token.SectionSeparator }
      pickIs("--") -> { move(2); Token.ModifierListIntroducer }

      pick.isNumeric -> lexNumber()
      pick.isAlphaNumeric -> lexWord()
      pick.isEscaper -> lexEscapedOfKeyword()

      pick == '"' -> lexString()
      pick == '/' -> lexRegExp()

      else -> throw ParsingException("Encountered invalid symbol: `${pick}`.")
   } else {
      null
   }
}

fun CharCursor.lexString(): Token = Token.String(readDelimited('"'))
fun CharCursor.lexRegExp(): Token = Token.RegExp(readDelimited('/'))

fun CharCursor.readDelimited(delimiter: Char): String {
   move(1) // Skip first delimiter.

   val content = StringBuilder()

   do {
      val chunk = skipUntil { it == delimiter || it.isEscaper }

      content.append(chunk)

      if (canPick(1)) {
         if (pick == delimiter) {
            break
         } else when { // Pick is escaper by skipUntil.
            nextIs('\\')      -> { move(2); content.append('\\') }
            nextIs(delimiter) -> { move(2); content.append(delimiter) }
            canNext(1)        -> { move(1); content.append('\\') }

            else -> throw ParsingException("Encountered end of code snippet too early.")
         }
      } else {
         throw ParsingException("Encountered end of code snippet too early.")
      }
   } while (true)

   move(1) // Skip last delimiter.

   return content.toString()
}

fun CharCursor.lexWord(): Token {
   val word = skipWhile { it.isAlphaNumeric }

   return when (word) {
      "of", "Of", "oF", "OF" -> Token.Word.OfKeyword
      else -> Token.Word.NamePart(word)
   }
}

fun CharCursor.lexEscapedOfKeyword(): Token {
   move(1) // Skip escaper.
   skipWhile { it.isSpace || it.isBreak }

   if (canPick(2)) {
      val word = skipWhile { it.isAlphaNumeric }

      if (word == "of") {
         return Token.Word.NamePart("of")
      } else {
         throw ParsingException("Encountered invalid item: `\\` can only be used to escape the `of` keyword.")
      }
   } else {
      throw ParsingException("Encountered end of code snippet too early.")
   }
}

fun CharCursor.lexNumber(): Token {
   val number = skipWhile { it.isNumeric }.toNumber()

   return if (number is Int) {
      Token.Integer(number)
   } else {
      Token.Real(number.toFloat())
   }
}

fun String.toNumber(): Number = try {
   if (this.matches(Regex("""^-?\d+\.\d+$"""))) {
      val floatValue = this.toFloat()

      if (floatValue == Float.POSITIVE_INFINITY || floatValue == Float.NEGATIVE_INFINITY) {
         throw ParsingException("Encountered invalid number: `${this}` is too large to be stored.")
      }

      floatValue
   } else {
      this.toInt()
   }
} catch (error: NumberFormatException) {
   throw ParsingException("Encountered invalid number: `${this}`.", error)
}

See also

\$\endgroup\$
  • \$\begingroup\$ I feel like is peeled: bool -- ( default(false) ) should look more like this: peeled: bool. The initialization syntax being used when not initializing to the default value. \$\endgroup\$ – T145 Oct 6 '18 at 16:41
  • \$\begingroup\$ @Mr.Vix I was thinking about programming languages that don't have such default values, e.g. C. I recognize this isn't the best example for a default modifier... Why would you remove the is prefix? \$\endgroup\$ – Odepax Oct 6 '18 at 17:48
  • \$\begingroup\$ Removed is b/c we know that the object is a boolean. You can have is_peeled, but peeled is just my preference. \$\endgroup\$ – T145 Oct 6 '18 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.