htk_parser.rb

require "strscan"

class Command
end

class Name < Command
  attr_reader :name

  def initialize(name)
    @name = name
  end

  def to_s
    @name
  end
end

class Or < Command
  attr_reader :commands

  def initialize(commands)
    @commands = commands
  end

  def to_s
    "( #{commands.join ' | '} )"
  end
end

class WrapperCommand < Command
  attr_reader :command

  def initialize(command)
    @command = command
  end
end

class Optional < WrapperCommand
  def to_s
    "[ #{command} ]"
  end
end

class ZeroOrMore < WrapperCommand
  def to_s
    "{ #{command} }"
  end
end

class OneOrMore < WrapperCommand
  def to_s
    "< #{command} >"
  end
end

class Concat < Command
  attr_reader :commands

  def initialize(commands)
    @commands = commands
  end

  def to_s
    "#{commands.join ' '}"
  end
end

class Lexer < StringScanner
  def initialize(string)
    super
  end

  def next_token
    skip(/\s+/)

    if eos?
      @token = nil
    elsif match = scan(/\(|\)|\[|\]|\{|\}|\<|\>|\|/)
      @token = match.to_sym
    elsif match = scan(/(\w|\$)+/)
      @token = match
    else
      raise "Unexpected token: #{rest}"
    end
  end
end

class Parser < Lexer
  def self.parse(string)
    new(string).parse
  end

  def parse
    next_token
    parse_or
  end

  def parse_or
    commands = []
    while true
      commands << parse_command
      if @token == :'|'
        next_token
      else
        break
      end
    end
    commands.length == 1 ? commands[0] : Or.new(commands)
  end

  def parse_command(recursive = true)
    case @token
    when :'('
      next_token
      commands = parse_or
      check :')'
      command = commands
    when :'['
      next_token
      commands = parse_or
      check :']'
      command = Optional.new(commands)
    when :'{'
      next_token
      commands = parse_or
      check :'}'
      command = ZeroOrMore.new(commands)
    when :'<'
      next_token
      commands = parse_or
      check :'>'
      command = OneOrMore.new(commands)
    when String
      name = Name.new(@token)
      next_token
      command = name
    when nil
      raise "Unexpected end of file"
    end

    return command unless recursive

    commands = [command]
    while true
      case @token
      when :'|', :'}', :']', :'>', :')', nil
        return commands.length == 1 ? commands[0] : Concat.new(commands)
      else
        commands << parse_command(false)
      end
    end
  end

  def check(token)
    raise "Expecting '#{token}', not '#{@token}'" unless @token == token
    next_token
  end
end

puts Parser.parse("FOO")
puts Parser.parse("FOO | BAR")
puts Parser.parse("(FOO | BAR) BAZ")
puts Parser.parse("{FILLER [FOO | BAR] BAZ | ANDREW | {BECAUSE | BOSTON | BUDGET} | DOLLARS | DUKAKIS | GOVERNOR | HEALTH | HUNDRED | MASSACHUSETTS | MILLION | NINETEEN | OFFICIALS | {PEOPLE | ALGO} | [PERCENT] | <REPORTS> | SCHOOL | STATES | THOUSAND | YESTERDAY}")
puts Parser.parse("sil { venti | trenti | cuarenti } <uno | dos | tres | cuatro> sil")