Lisp parser. To run: $ ruby lisp.rb -e '(first (list 1 (+ 2 3) 9))'

lexer.rb

# frozen_string_literal: true

require 'strscan'
require './tokens'
require './token_stream'

class Lexer
  TOKEN_TYPES = [OpenParens, CloseParens, Name, IntegerToken, Whitespace].freeze

  def tokenize(code)
    tokens = TokenStream.new
    scanner = StringScanner.new(code)
    until scanner.eos?
      next_token = match_against_token_types(scanner)
      raise StandardError, "Token unknown at #{scanner.pos}" unless next_token
      tokens << next_token
    end
    tokens
  end

  private

  def match_against_token_types(scanner)
    position = scanner.pos
    TOKEN_TYPES.each do |type|
      token = type.match(scanner, position)
      return token if token
    end
    nil
  end
end

lisp.rb

#!/usr/bin/ruby
# frozen_string_literal: true

require 'pp'
require './lexer'
require './parser'

def main(code)
  tokens = Lexer.new.tokenize(code)
  syntax_tree = Parser.parse(tokens)
  puts 'Code'
  puts '----'
  puts code
  puts ''
  puts 'Abstract syntax tree'
  puts '--------------------'
  pp syntax_tree
end

if ARGV.length == 1
  code_filename = ARGV[0]
  File.open(code_filename) do |code_file|
    main(code_file.read)
  end
elsif ARGV.length == 2 && ARGV[0] == '-e'
  code = ARGV[1]
  main(code)
else
  puts 'Usage: ruby lisp.rb <lisp-code-file>'
  puts '       ruby lisp.rb -e <lisp-code>'
  exit 1
end

parser.rb

# frozen_string_literal: true

class Parser
  def self.parse(tokens)
    tokens_after_parse, list_node = ListNode.parse(tokens)
    list_node if tokens_after_parse&.empty?
  end
end

class IntegerNode
  def initialize(token)
    @token = token
  end

  def self.parse(tokens)
    tokens, next_token = tokens.next
    return nil unless next_token.is_a?(IntegerToken)
    [tokens, new(next_token)]
  end
end

class NameNode
  def initialize(token)
    @token = token
  end

  def self.parse(tokens)
    tokens, next_token = tokens.next
    return nil unless next_token.is_a?(Name)
    [tokens, new(next_token)]
  end
end

class ListNode
  ELEMENT_PRODUCTIONS = [ListNode, IntegerNode, NameNode].freeze

  def initialize(elements)
    @elements = elements
  end

  def self.parse(tokens)
    elements = []
    tokens, next_token = tokens.next
    return nil unless next_token.is_a?(OpenParens)
    until tokens.peek.is_a?(CloseParens) || tokens.empty?
      tokens, parse_node = next_parse_node(tokens)
      return nil unless parse_node
      elements << parse_node
    end
    tokens, next_token = tokens.next
    return nil unless next_token.is_a?(CloseParens)
    [tokens, new(elements)]
  end

  def self.next_parse_node(tokens)
    tokens_after_parse = nil
    parse_node = nil
    ELEMENT_PRODUCTIONS.each do |production|
      tokens_after_parse, parse_node = production.parse(tokens)
      break if parse_node
    end
    [tokens_after_parse, parse_node]
  end
end

token_stream.rb

# frozen_string_literal: true

class TokenStream
  def initialize(tokens: nil, head_index: nil)
    @tokens = tokens || []
    @head_index = head_index || 0
  end

  def empty?
    @head_index >= @tokens.size
  end

  def <<(token)
    @tokens << token unless token.is_a?(Whitespace)
  end

  def next
    next_token = @tokens[@head_index]
    new_stream = TokenStream.new(tokens: @tokens, head_index: @head_index + 1)
    [new_stream, next_token]
  end

  def peek
    @tokens[@head_index]
  end
end

tokens.rb

# frozen_string_literal: true

class Token
  attr_reader :string
  def initialize(string, index_in_code)
    @string = string
    @index_in_code = index_in_code
  end

  def length
    string.length
  end

  def self.match(scanner, position)
    token_string = scanner.scan(self::REGEX)
    new(token_string, position) if token_string
  end
end

class OpenParens < Token
  REGEX = /[(]/
end

class CloseParens < Token
  REGEX = /[)]/
end

class Name < Token
  REGEX = %r{([[:alpha:]][[:alnum:]-]*)|\+|-|\*|/}
end

class IntegerToken < Token
  REGEX = /-?[[:digit:]]+/
end

class Whitespace < Token
  REGEX = /[[:space:]]+/
end