en
de

Diesel, Part 3: Bootstrapping Diesel

20 Mai 2015
| |
Lesezeit: 18 Minutes

Mit Interesse habe ich die Versuche der Kollegen verfolgt, einen leichtgewichtigen DSL-Ansatz mittels LL(1)-Parser in Ruby umzusetzen. Daniel Mölle hat in seinem Blog-Post eindrucksvoll gezeigt, wie einfach sich etwa eine simple Melody-DSL mit dem „Diesel“ getauften Ansatz implementieren lässt. Nach dieser Lektüre lies mich die Frage nicht mehr los, ob sich diese Einfachheit auch für realistischere Aufgaben noch als Vorteil erweist. Die Melody-DSL ist mir als eine Art Hello-World-Beispiel nämlich noch zu simpel. Sobald ein Projekt komplex genug für eine DSL wird, rechne ich mit deutlich mehr Schlüsselworten und Sprachkonstrukten.

Auf der Suche nach einem realistischen Beispiel kam mir dann folgende Idee: Wieso nicht einen Diesel-Parser für eine beliebige LL(1)-Sprache mit Diesel generieren? Eine DSL, um Sprachen zu beschreiben, muss ich mir nicht erst ausdenken, das haben nämlich freundlicherweise die Herren John Backus und Peter Naur bereits getan. Mithilfe der sogenannten Extended Backus-Naur-Form (EBNF) von Niklaus Wirth lässt sich die Syntax von Programmiersprachen formal erfassen.

Aus dem Wikipedia-Artikel zur EBNF und einer dazu passenden Diskussion auf Stackoverflow habe ich recht schnell folgende LL(1)-Gramatik der EBNF zusammengebaut:

gramar = { rule };
rule = ID, "=", rhs, ";";
rhs = factor, { ",", factor };
factor = primary, { "|", primary };
primary = ID | terminal | optional | repeated | grouped;
terminal = ("'", ID | SYMBOL, "'") | ('"', ID | SYMBOL, '"');
optional = "[", rhs, "]";
repeated = "{", rhs, "}";
grouped = "(", rhs, ")";

EBNF-Parser einfach mit Diesel

Ein Parser für diese Gramatik ist mit Diesel ähnlich einfach wie das Melody-Beispiel. Etwas Copy’n’Paste hier, etwas Search’n’Replace dort… fertig. Erstaunlich. Mit dem folgenden Parser lässt sich das obig Beispiel parsen und heraus kommt ein Abstract-Syntax-Tree (AST) der EBNF selbst.

require_relative 'types'

module Diesel
    module Parser
        SYMBOLS = "[{[()]}\"'.:,;#*+~\/\\$%&=|?!-~"
        ID = /\w+/

        # Tokenizes and parses a complete input file.
        def parse_file(fn)
            # Tokenize and parse the input file.
            @history = Array.new
            tokens = tokenize_file(fn)
            begin
                root = expect_gramar_body(nil, tokens)
            rescue Exception => e
                fail_verbosely(e)
            end
            # Return the parse result.
            return root
        end

        private

        # Tokenizes an input file defined by its name.
        def tokenize_file(fn)
            tokens = Array.new
            File.readlines(fn).each do |line|
                linetokens = line.gsub(/([#{Regexp.quote(SYMBOLS)}])/, ' \1 ').split(/\s+/)
                linetokens.each do |linetoken|
                    strippedlinetoken = linetoken.strip
                    if !strippedlinetoken.empty? then
                        tokens.push(strippedlinetoken)
                    end
                end
            end
            return tokens
        end

        def append(field, value)
            return field unless value
            if field == nil
                return value
            elsif field.kind_of?(Array)
                return field.push(value)
            else
                return [ field, value ]
            end
        end

        # Parses all the tokens in the input stream.
        def expect_gramar_body(gramar, tokens)
            gramar = Gramar.new
            while (lambda {
                rule = accept_rule_body(gramar, tokens)
                gramar.rules = append(gramar.rules, rule)
                return rule
            }.call)
            end
            return gramar
        end

        # Parses the entire body of a "definition" statement.
        def accept_rule_body(gramar, tokens)
            lhs = accept_id(tokens)
            return nil unless lhs
            expect_keyword(tokens, "=")
            rhs = parse_rhs_body(gramar, tokens)
            expect_keyword(tokens, ";")
            return Rule.new(lhs, rhs)
        end

        # Parses the entire body of a "rhs" statement.
        def parse_rhs_body(gramar, tokens)
            rhs = RHS.new(Array.new)
            begin
                factor = parse_factor_body(gramar, tokens)
                raise "Unexpected '#{tokens[0]}' expecting factor while parsing rhs body" unless factor
                rhs.factors.push(factor)
            end while factor = accept_keyword(tokens, ",")
            return rhs
        end

        # Parses the entire body of a "factor" statement.
        def parse_factor_body(gramar, tokens)
            factor = Factor.new(Array.new)
            begin
                primary = parse_primary_body(gramar, tokens)
                raise "Unexpected '#{tokens[0]}' expecting primary while parsing factor body" unless primary
                factor.primaries.push(primary)
            end while primary = accept_keyword(tokens, "|")
            return factor
        end

        # Parses the entire body of a "primary" statement.
        def parse_primary_body(gramar, tokens)
            if (id = accept_id(tokens))
                return id
            elsif (terminal = parse_terminal_body(gramar, tokens))
                return terminal
            elsif (optional = parse_optional_body(gramar, tokens))
                return optional
            elsif (repeated = parse_repeated_body(gramar, tokens))
                return repeated
            elsif (grouped = parse_grouped_body(gramar, tokens))
                return grouped
            end
            return nil
        end

        # Parses the entire body of a "terminal" statement.
        def parse_terminal_body(gramar, tokens)
            if accept_keyword(tokens, "'")
                id = accept_id(tokens)
                symbol = expect_symbol(tokens) unless id
                expect_keyword(tokens, "'")
                return Terminal.new(id, symbol)
            elsif accept_keyword(tokens, '"')
                id = accept_id(tokens)
                symbol = expect_symbol(tokens) unless id
                expect_keyword(tokens, '"')
                return Terminal.new(id, symbol)
            end
            return nil
        end

        # Parses the entire body of a "optional" statement.
        def parse_optional_body(gramar, tokens)
            if accept_keyword(tokens, "[")
                rhs = parse_rhs_body(gramar, tokens)
                expect_keyword(tokens, "]")
                return Optional.new(rhs)
            end
            return nil
        end

        # Parses the entire body of a "repeated" statement.
        def parse_repeated_body(gramar, tokens)
            if accept_keyword(tokens, "{")
                rhs = parse_rhs_body(gramar, tokens)
                expect_keyword(tokens, "}")
                return Repeated.new(rhs)
            end
            return nil
        end

        # Parses the entire body of a "grouped" statement.
        def parse_grouped_body(gramar, tokens)
            if accept_keyword(tokens, "(")
                rhs = parse_rhs_body(gramar, tokens)
                expect_keyword(tokens, ")")
                return Grouped.new(rhs)
            end
            return nil
        end        

        # Extracts the next token from the token queue.
        def get_next(tokens)
            first = tokens.delete_at(0)
            @history.push({:token => first, :caller => caller})
            return first
        end

        def expect_id(tokens)
            id = accept_id(tokens)
            raise "Unexpected '#{tokens[0]}' (not ID)" unless id
            return id
        end

        def accept_id(tokens)
            return nil if tokens.empty?
            return get_next(tokens) if ID.match(tokens[0])
            return nil
        end

        def expect_symbol(tokens)
            symbol = accept_symbol(tokens)
            raise "Unexpected '#{tokens[0]}' (not SYMBOL)" unless symbol
            return symbol
        end

        def accept_symbol(tokens)
            return nil if tokens.empty?
            return get_next(tokens) if /([#{Regexp.quote(SYMBOLS)}])/.match(tokens[0])
            return nil
        end

        # Returns the given keyword if it happens to match the next token,
        # removing that token from the input queue in the process.
        # Otherwise, nil is returned, and the queue remains unchanged.
        def accept_keyword(tokens, keyword)
            return nil if tokens.empty?
            return get_next(tokens) if tokens[0] == keyword
            return nil
        end

        # Ensures that the given keyword happens to match the next token.
        # Returns the token on success.
        def expect_keyword(tokens, keyword)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Unexpected '#{token}' (not '#{keyword}')" unless token == keyword
            return token
        end

        # Ensures that the next token matches an entry in the given array.
        # On success, the respective token is returned.
        def expect_old(tokens, array)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Unknown identifier '#{token}'" unless array.include?(token)
            return token
        end

        # Ensures that the next token does NOT match an entry in the given array.
        # On success, the respective token is returned.
        def expect_new(tokens, array)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Identifier '#{token}' already in use" unless !array.include?(token)
            return token
        end

        # Parses the given string for a positive non-zero integer.
        def get_int(s)
            i = s.to_i
            raise "Failed to parse integer: '#{s}'" unless i > 0
            return i
        end

        # Parses the given string for a positive non-zero float.
        def get_float(s)
            f = s.to_f
            raise "Failed to parse float: '#{s}'" unless f > 0.0
            return f
        end

        # Parses the given string for a positive non-zero rational.
        def get_rational(s)
            r = s.to_r
            raise "Failed to parse rational: '#{s}'" unless r > 0
            return r
        end

        # Returns the plain array of names of an array of named items.
        def get_names(array)
            result = Array.new
            array.each do |item|
                result.push(item.name)
            end
            return result
        end

        # Augments an exception message with a token history.
        def fail_verbosely(msg)
            puts "Token history at point of error:"
            puts "================================"
            pp @history
            puts "================================"
            raise msg
        end
    end
end

Doch der spannende Teil kommt erst noch: Der Generator. Den ersten Parser für eine EBNF habe ich von Hand geschrieben, mich dabei stark an Daniel Mölles Melody- Parser orientiert und keinerlei Gedanken an die Generierbarkeit verwendet. Schnell muss ich feststellen, dass ich wohl nicht (jedenfalls nicht kurzfristig) in der Lage sein werde, einen Daniel’schen Generator zu bauen. Ich habe mich dann dazu durchgerungen auf die Eleganz zu verzichten und mich ausschließlich auf die Funktion zu konzentrieren.

Freie Wahl der Generator-Technologie

Im Unterschied zum Meolody-Beispiel (Puts-Generator) nutze ich diese Gelegenheit Embedded Ruby Templates (ERB) für den Generator zu testen. Hier zeigt sich direkt eine Stärke des Diesel-Ansatzes, der nicht auf eine spezifische Generator-Technologie festgelegt ist. Ich kann also je nach Anwendungsfall entscheiden, ob ich schnell einen Puts-Generator schreibe, oder eben für komplexere Fälle Templating-Engines wie beispielsweise ERB verwendet. Nach einigen Versuchen habe ich folgendes Template zusammengebaut:

require_relative 'types'

module
    module Parser
        SYMBOLS = "[{[()]}\"'.:,;#*+~\/\\$%&=|?!-~"
        ID = /\w+/

        # Tokenizes and parses a complete input file.
        def parse_file(fn)
            # Tokenize and parse the input file.
            @history = Array.new
            tokens = tokenize_file(fn)
            begin
                root = expect__body(nil, tokens)
            rescue Exception => e
                fail_verbosely(e)
            end
            # Return the parse result.
            return root
        end

        private

        # Tokenizes an input file defined by its name.
        def tokenize_file(fn)
            tokens = Array.new
            File.readlines(fn).each do |line|
                linetokens = line.gsub(/([#{Regexp.quote(SYMBOLS)}])/, ' \1 ').split(/\s+/)
                linetokens.each do |linetoken|
                    strippedlinetoken = linetoken.strip
                    if !strippedlinetoken.empty? then
                        tokens.push(strippedlinetoken)
                    end
                end
            end
            return tokens
        end

        def append(field, value)
            return field unless value
            if field == nil
                return value
            elsif field.kind_of?(Array)
                return field.push(value)
            else
                return [ field, value ]
            end
        end

            id = _id(tokens)
            .id = append(.id, id)
            return id
            symbol = _symbol(tokens)
            .symbol = append(.symbol, symbol)
            return symbol
            intNum = _int(tokens)
            .int = append(.int, intNum)
            return intNum
            floatNum = _float(tokens)
            .float = append(.float, floatNum)
            return floatNum
            token = __body(, tokens)
            . = append(., token)
            return token
            return _keyword(tokens, )
            while (lambda {
            }.call)
            end
            return  1 %>
            p = nil
            p = lambda {
            }.call unless p
            raise "Unexpected '#{tokens[0]}' while parsing " unless p
            return p
            return lambda {
            }.call
            f =
            f = lambda {
            }.call if f
            return f
        def accept__body(, tokens)
             = .new
            rhs = lambda {
            }.call
            return nil unless rhs
            return
        end

        def expect__body(, tokens)
             = .new
            rhs = lambda {
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing " unless rhs
            return
        end

        # Extracts the next token from the token queue.
        def get_next(tokens)
            first = tokens.delete_at(0)
            @history.push(first)
            return first
        end

        def expect_id(tokens)
            id = accept_id(tokens)
            raise "Unexpected '#{tokens[0]}' (not ID)" unless id
            return id
        end

        def accept_id(tokens)
            return nil if tokens.empty?
            return get_next(tokens) if ID.match(tokens[0])
            return nil
        end

        def expect_symbol(tokens)
            symbol = accept_symbol(tokens)
            raise "Unexpected '#{tokens[0]}' (not SYMBOL)" unless symbol
            return symbol
        end

        def accept_symbol(tokens)
            return nil if tokens.empty?
            return get_next(tokens) if /([#{Regexp.quote(SYMBOLS)}])/.match(tokens[0])
            return nil
        end

        def expect_int(tokens)
            return Integer(get_next(tokens))
        end

        def accept_int(tokens)
            begin
                Integer(tokens[0])
            rescue
                return nil
            end
            return expect_int(tokens)
        end

        def expect_float(tokens)
            return Float(get_next(tokens) + get_next(tokens) + get_next(tokens))
        end

        def accept_float(tokens)
            begin
                Float(tokens[0..2])
            rescue
                return nil
            end
            return expect_float(tokens)
        end

        # Returns the given keyword if it happens to match the next token,
        # removing that token from the input queue in the process.
        # Otherwise, nil is returned, and the queue remains unchanged.
        def accept_keyword(tokens, keyword)
            return nil if tokens.empty?
            return get_next(tokens) if tokens[0] == keyword
            return nil
        end

        # Ensures that the given keyword happens to match the next token.
        # Returns the token on success.
        def expect_keyword(tokens, keyword)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Unexpected '#{token}' (not '#{keyword}')" unless token == keyword
            return token
        end

        # Ensures that the next token matches an entry in the given array.
        # On success, the respective token is returned.
        def expect_old(tokens, array)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Unknown identifier '#{token}'" unless array.include?(token)
            return token
        end

        # Ensures that the next token does NOT match an entry in the given array.
        # On success, the respective token is returned.
        def expect_new(tokens, array)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Identifier '#{token}' already in use" unless !array.include?(token)
            return token
        end

        # Parses the given string for a positive non-zero integer.
        def get_int(s)
            i = s.to_i
            raise "Failed to parse integer: '#{s}'" unless i > 0
            return i
        end

        # Parses the given string for a positive non-zero float.
        def get_float(s)
            f = s.to_f
            raise "Failed to parse float: '#{s}'" unless f > 0.0
            return f
        end

        # Parses the given string for a positive non-zero rational.
        def get_rational(s)
            r = s.to_r
            raise "Failed to parse rational: '#{s}'" unless r > 0
            return r
        end

        # Returns the plain array of names of an array of named items.
        def get_names(array)
            result = Array.new
            array.each do |item|
                result.push(item.name)
            end
            return result
        end

        # Augments an exception message with a token history.
        def fail_verbosely(msg)
            puts "Token history at point of error:"
            puts "================================"
            pp @history
            puts "================================"
            raise msg
        end
    end
end

Für den EBNF-Parser-Generator erweisen sich die ERB-Templates als vorteilhaft gegenüber einem Puts-Generator: Ich kann Boiler-Plate-Anteile einfach direkt im Zielformat runterschreiben und gezielt variable Anteile per Ruby-Ausdrücken einbetten. Komplexere Aufgaben habe ich in eingebettete Funktionen zusammengefasst, sodass das Template nicht mehr linear abgearbeitet wird und dadurch schwerer zu lesen ist. Ich höre schon die Ruby-Gurus aufschreien. Das Template hat mit Sicherheit Potential nach oben.

ERB-Templates unkomfortabel

Im Rahmen dieses Blog-Posts interessiert mich aber mehr, ob denn das Generator-Ergebnis überhaupt funktioniert. Dazu muss das generator.rb von Daniel natürlich für die Ausführung eines ERB-Templates erweitert werden:

require 'erb'
require 'fileutils'
require 'ostruct'

require_relative 'types'

module Diesel
    module Generators
        class Values
            @name = nil
            @root = nil

            attr_accessor :name, :root

            def initialize(name, root)
                @name = name
                @root = root
            end

            def get_binding()
                return binding
            end
        end

        def generate_parser(name, gramar)
            values = Values.new(name.capitalize, gramar)
            indir = "./input"
            outdir = "./output"

            raise "Input directory #{indir} does not exist!" unless File.directory?(indir)
            FileUtils.mkdir_p(outdir) unless File.directory?(outdir)

            Dir.glob("#{indir}/*.erb") do |infile|
                outfile = "#{outdir}/#{File.basename(infile, '.erb')}"
                puts "Generating #{infile} => #{outfile} ..."
                erb = ERB.new(File.read("#{infile}"))
                File.open("#{outfile}", "w") { |f|
                    f.puts erb.result(values.get_binding)
                }
            end
        end
    end
end

Hier hatte ich ordentlich zu tüfteln, bis der ERB-Interpreter die Value-Bindings geschluckt hat. Der Umweg über die Values-Klasse erscheint mir eher wie eine notwendige Krücke, aber auch das akzeptiere ich hier für den Moment notgedrungen.

Diesel-generierter EBNF-Parser

Spannender ist für mich aktuell die erste Ausführung und ein Blick auf das Ergebnis: Der Diesel-generierte EBNF-Parser.

require_relative 'types'

module Diesel
    module Parser
        SYMBOLS = "[{[()]}\"'.:,;#*+~\/\\$%&=|?!-~"
        ID = /\w+/

        # Tokenizes and parses a complete input file.
        def parse_file(fn)
            # Tokenize and parse the input file.
            @history = Array.new
            tokens = tokenize_file(fn)
            begin
                root = expect_gramar_body(nil, tokens)
            rescue Exception => e
                fail_verbosely(e)
            end
            # Return the parse result.
            return root
        end

        private

        # Tokenizes an input file defined by its name.
        def tokenize_file(fn)
            tokens = Array.new
            File.readlines(fn).each do |line|
                linetokens = line.gsub(/([#{Regexp.quote(SYMBOLS)}])/, ' \1 ').split(/\s+/)
                linetokens.each do |linetoken|
                    strippedlinetoken = linetoken.strip
                    if !strippedlinetoken.empty? then
                        tokens.push(strippedlinetoken)
                    end
                end
            end
            return tokens
        end

        def append(field, value)
            return field unless value
            if field == nil
                return value
            elsif field.kind_of?(Array)
                return field.push(value)
            else
                return [ field, value ]
            end
        end

        def accept_gramar_body(gramar, tokens)
            gramar = Gramar.new
            rhs = lambda {
                f = gramar
                f = lambda {
                    return lambda {
                        while (lambda {
                            f = gramar
                            f = lambda {
                                return lambda {
                                    token = accept_rule_body(gramar, tokens)
                                    gramar.rule = append(gramar.rule, token)
                                    return token
                                }.call
                            }.call if f
                            return f
                        }.call)
                        end
                        return gramar
                    }.call
                }.call if f
                return f
            }.call
            return nil unless rhs
            return gramar
        end

        def expect_gramar_body(gramar, tokens)
            gramar = Gramar.new
            rhs = lambda {
                f = gramar
                f = lambda {
                    return lambda {
                        while (lambda {
                            f = gramar
                            f = lambda {
                                return lambda {
                                    token = accept_rule_body(gramar, tokens)
                                    gramar.rule = append(gramar.rule, token)
                                    return token
                                }.call
                            }.call if f
                            return f
                        }.call)
                        end
                        return gramar
                    }.call
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing gramar" unless rhs
            return gramar
        end

        def accept_rule_body(gramar, tokens)
            rule = Rule.new
            rhs = lambda {
                f = rule
                f = lambda {
                    return lambda {
                        id = accept_id(tokens)
                        rule.id = append(rule.id, id)
                        return id
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "=")
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        token = expect_rhs_body(gramar, tokens)
                        rule.rhs = append(rule.rhs, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, ";")
                    }.call
                }.call if f
                return f
            }.call
            return nil unless rhs
            return rule
        end

        def expect_rule_body(gramar, tokens)
            rule = Rule.new
            rhs = lambda {
                f = rule
                f = lambda {
                    return lambda {
                        id = expect_id(tokens)
                        rule.id = append(rule.id, id)
                        return id
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "=")
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        token = expect_rhs_body(gramar, tokens)
                        rule.rhs = append(rule.rhs, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, ";")
                    }.call
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing rule" unless rhs
            return rule
        end

        def accept_rhs_body(gramar, tokens)
            rhs = Rhs.new
            rhs = lambda {
                f = rhs
                f = lambda {
                    return lambda {
                        token = accept_factor_body(gramar, tokens)
                        rhs.factor = append(rhs.factor, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        while (lambda {
                            f = rhs
                            f = lambda {
                                return lambda {
                                    return accept_keyword(tokens, ",")
                                }.call
                            }.call if f
                            f = lambda {
                                return lambda {
                                    token = expect_factor_body(gramar, tokens)
                                    rhs.factor = append(rhs.factor, token)
                                    return token
                                }.call
                            }.call if f
                            return f
                        }.call)
                        end
                        return rhs
                    }.call
                }.call if f
                return f
            }.call
            return nil unless rhs
            return rhs
        end

        def expect_rhs_body(gramar, tokens)
            rhs = Rhs.new
            rhs = lambda {
                f = rhs
                f = lambda {
                    return lambda {
                        token = expect_factor_body(gramar, tokens)
                        rhs.factor = append(rhs.factor, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        while (lambda {
                            f = rhs
                            f = lambda {
                                return lambda {
                                    return accept_keyword(tokens, ",")
                                }.call
                            }.call if f
                            f = lambda {
                                return lambda {
                                    token = expect_factor_body(gramar, tokens)
                                    rhs.factor = append(rhs.factor, token)
                                    return token
                                }.call
                            }.call if f
                            return f
                        }.call)
                        end
                        return rhs
                    }.call
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing rhs" unless rhs
            return rhs
        end

        def accept_factor_body(gramar, tokens)
            factor = Factor.new
            rhs = lambda {
                f = factor
                f = lambda {
                    return lambda {
                        token = accept_primary_body(gramar, tokens)
                        factor.primary = append(factor.primary, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        while (lambda {
                            f = factor
                            f = lambda {
                                return lambda {
                                    return accept_keyword(tokens, "|")
                                }.call
                            }.call if f
                            f = lambda {
                                return lambda {
                                    token = expect_primary_body(gramar, tokens)
                                    factor.primary = append(factor.primary, token)
                                    return token
                                }.call
                            }.call if f
                            return f
                        }.call)
                        end
                        return factor
                    }.call
                }.call if f
                return f
            }.call
            return nil unless rhs
            return factor
        end

        def expect_factor_body(gramar, tokens)
            factor = Factor.new
            rhs = lambda {
                f = factor
                f = lambda {
                    return lambda {
                        token = expect_primary_body(gramar, tokens)
                        factor.primary = append(factor.primary, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        while (lambda {
                            f = factor
                            f = lambda {
                                return lambda {
                                    return accept_keyword(tokens, "|")
                                }.call
                            }.call if f
                            f = lambda {
                                return lambda {
                                    token = expect_primary_body(gramar, tokens)
                                    factor.primary = append(factor.primary, token)
                                    return token
                                }.call
                            }.call if f
                            return f
                        }.call)
                        end
                        return factor
                    }.call
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing factor" unless rhs
            return factor
        end

        def accept_primary_body(gramar, tokens)
            primary = Primary.new
            rhs = lambda {
                f = primary
                f = lambda {
                    p = nil
                    p = lambda {
                        id = accept_id(tokens)
                        primary.id = append(primary.id, id)
                        return id
                    }.call unless p
                    p = lambda {
                        token = accept_terminal_body(gramar, tokens)
                        primary.terminal = append(primary.terminal, token)
                        return token
                    }.call unless p
                    p = lambda {
                        token = accept_optional_body(gramar, tokens)
                        primary.optional = append(primary.optional, token)
                        return token
                    }.call unless p
                    p = lambda {
                        token = accept_repeated_body(gramar, tokens)
                        primary.repeated = append(primary.repeated, token)
                        return token
                    }.call unless p
                    p = lambda {
                        token = accept_grouped_body(gramar, tokens)
                        primary.grouped = append(primary.grouped, token)
                        return token
                    }.call unless p
                    return p
                }.call if f
                return f
            }.call
            return nil unless rhs
            return primary
        end

        def expect_primary_body(gramar, tokens)
            primary = Primary.new
            rhs = lambda {
                f = primary
                f = lambda {
                    p = nil
                    p = lambda {
                        id = accept_id(tokens)
                        primary.id = append(primary.id, id)
                        return id
                    }.call unless p
                    p = lambda {
                        token = accept_terminal_body(gramar, tokens)
                        primary.terminal = append(primary.terminal, token)
                        return token
                    }.call unless p
                    p = lambda {
                        token = accept_optional_body(gramar, tokens)
                        primary.optional = append(primary.optional, token)
                        return token
                    }.call unless p
                    p = lambda {
                        token = accept_repeated_body(gramar, tokens)
                        primary.repeated = append(primary.repeated, token)
                        return token
                    }.call unless p
                    p = lambda {
                        token = accept_grouped_body(gramar, tokens)
                        primary.grouped = append(primary.grouped, token)
                        return token
                    }.call unless p
                    raise "Unexpected '#{tokens[0]}' while parsing primary" unless p
                    return p
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing primary" unless rhs
            return primary
        end

        def accept_terminal_body(gramar, tokens)
            terminal = Terminal.new
            rhs = lambda {
                f = terminal
                f = lambda {
                    p = nil
                    p = lambda {
                        f = terminal
                        f = lambda {
                            return lambda {
                                return accept_keyword(tokens, "'")
                            }.call
                        }.call if f
                        f = lambda {
                            p = nil
                            p = lambda {
                                id = accept_id(tokens)
                                terminal.id = append(terminal.id, id)
                                return id
                            }.call unless p
                            p = lambda {
                                symbol = accept_symbol(tokens)
                                terminal.symbol = append(terminal.symbol, symbol)
                                return symbol
                            }.call unless p
                            raise "Unexpected '#{tokens[0]}' while parsing terminal" unless p
                            return p
                        }.call if f
                        f = lambda {
                            return lambda {
                                return expect_keyword(tokens, "'")
                            }.call
                        }.call if f
                        return f
                    }.call unless p
                    p = lambda {
                        f = terminal
                        f = lambda {
                            return lambda {
                                return accept_keyword(tokens, "\"")
                            }.call
                        }.call if f
                        f = lambda {
                            p = nil
                            p = lambda {
                                id = accept_id(tokens)
                                terminal.id = append(terminal.id, id)
                                return id
                            }.call unless p
                            p = lambda {
                                symbol = accept_symbol(tokens)
                                terminal.symbol = append(terminal.symbol, symbol)
                                return symbol
                            }.call unless p
                            raise "Unexpected '#{tokens[0]}' while parsing terminal" unless p
                            return p
                        }.call if f
                        f = lambda {
                            return lambda {
                                return expect_keyword(tokens, "\"")
                            }.call
                        }.call if f
                        return f
                    }.call unless p
                    return p
                }.call if f
                return f
            }.call
            return nil unless rhs
            return terminal
        end

        def expect_terminal_body(gramar, tokens)
            terminal = Terminal.new
            rhs = lambda {
                f = terminal
                f = lambda {
                    p = nil
                    p = lambda {
                        f = terminal
                        f = lambda {
                            return lambda {
                                return accept_keyword(tokens, "'")
                            }.call
                        }.call if f
                        f = lambda {
                            p = nil
                            p = lambda {
                                id = accept_id(tokens)
                                terminal.id = append(terminal.id, id)
                                return id
                            }.call unless p
                            p = lambda {
                                symbol = accept_symbol(tokens)
                                terminal.symbol = append(terminal.symbol, symbol)
                                return symbol
                            }.call unless p
                            raise "Unexpected '#{tokens[0]}' while parsing terminal" unless p
                            return p
                        }.call if f
                        f = lambda {
                            return lambda {
                                return expect_keyword(tokens, "'")
                            }.call
                        }.call if f
                        return f
                    }.call unless p
                    p = lambda {
                        f = terminal
                        f = lambda {
                            return lambda {
                                return accept_keyword(tokens, "\"")
                            }.call
                        }.call if f
                        f = lambda {
                            p = nil
                            p = lambda {
                                id = accept_id(tokens)
                                terminal.id = append(terminal.id, id)
                                return id
                            }.call unless p
                            p = lambda {
                                symbol = accept_symbol(tokens)
                                terminal.symbol = append(terminal.symbol, symbol)
                                return symbol
                            }.call unless p
                            raise "Unexpected '#{tokens[0]}' while parsing terminal" unless p
                            return p
                        }.call if f
                        f = lambda {
                            return lambda {
                                return expect_keyword(tokens, "\"")
                            }.call
                        }.call if f
                        return f
                    }.call unless p
                    raise "Unexpected '#{tokens[0]}' while parsing terminal" unless p
                    return p
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing terminal" unless rhs
            return terminal
        end

        def accept_optional_body(gramar, tokens)
            optional = Optional.new
            rhs = lambda {
                f = optional
                f = lambda {
                    return lambda {
                        return accept_keyword(tokens, "[")
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        token = expect_rhs_body(gramar, tokens)
                        optional.rhs = append(optional.rhs, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "]")
                    }.call
                }.call if f
                return f
            }.call
            return nil unless rhs
            return optional
        end

        def expect_optional_body(gramar, tokens)
            optional = Optional.new
            rhs = lambda {
                f = optional
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "[")
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        token = expect_rhs_body(gramar, tokens)
                        optional.rhs = append(optional.rhs, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "]")
                    }.call
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing optional" unless rhs
            return optional
        end

        def accept_repeated_body(gramar, tokens)
            repeated = Repeated.new
            rhs = lambda {
                f = repeated
                f = lambda {
                    return lambda {
                        return accept_keyword(tokens, "{")
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        token = expect_rhs_body(gramar, tokens)
                        repeated.rhs = append(repeated.rhs, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "}")
                    }.call
                }.call if f
                return f
            }.call
            return nil unless rhs
            return repeated
        end

        def expect_repeated_body(gramar, tokens)
            repeated = Repeated.new
            rhs = lambda {
                f = repeated
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "{")
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        token = expect_rhs_body(gramar, tokens)
                        repeated.rhs = append(repeated.rhs, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "}")
                    }.call
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing repeated" unless rhs
            return repeated
        end

        def accept_grouped_body(gramar, tokens)
            grouped = Grouped.new
            rhs = lambda {
                f = grouped
                f = lambda {
                    return lambda {
                        return accept_keyword(tokens, "(")
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        token = expect_rhs_body(gramar, tokens)
                        grouped.rhs = append(grouped.rhs, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, ")")
                    }.call
                }.call if f
                return f
            }.call
            return nil unless rhs
            return grouped
        end

        def expect_grouped_body(gramar, tokens)
            grouped = Grouped.new
            rhs = lambda {
                f = grouped
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, "(")
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        token = expect_rhs_body(gramar, tokens)
                        grouped.rhs = append(grouped.rhs, token)
                        return token
                    }.call
                }.call if f
                f = lambda {
                    return lambda {
                        return expect_keyword(tokens, ")")
                    }.call
                }.call if f
                return f
            }.call
            raise "Unexpected token '#{tokens[0]}' while parsing grouped" unless rhs
            return grouped
        end

        # Extracts the next token from the token queue.
        def get_next(tokens)
            first = tokens.delete_at(0)
            @history.push(first)
            return first
        end

        def expect_id(tokens)
            id = accept_id(tokens)
            raise "Unexpected '#{tokens[0]}' (not ID)" unless id
            return id
        end

        def accept_id(tokens)
            return nil if tokens.empty?
            return get_next(tokens) if ID.match(tokens[0])
            return nil
        end

        def expect_symbol(tokens)
            symbol = accept_symbol(tokens)
            raise "Unexpected '#{tokens[0]}' (not SYMBOL)" unless symbol
            return symbol
        end

        def accept_symbol(tokens)
            return nil if tokens.empty?
            return get_next(tokens) if /([#{Regexp.quote(SYMBOLS)}])/.match(tokens[0])
            return nil
        end

        def expect_int(tokens)
            return Integer(get_next(tokens))
        end

        def accept_int(tokens)
            begin
                Integer(tokens[0])
            rescue
                return nil
            end
            return expect_int(tokens)
        end

        def expect_float(tokens)
            return Float(get_next(tokens) + get_next(tokens) + get_next(tokens))
        end

        def accept_float(tokens)
            begin
                Float(tokens[0..2])
            rescue
                return nil
            end
            return expect_float(tokens)
        end

        # Returns the given keyword if it happens to match the next token,
        # removing that token from the input queue in the process.
        # Otherwise, nil is returned, and the queue remains unchanged.
        def accept_keyword(tokens, keyword)
            return nil if tokens.empty?
            return get_next(tokens) if tokens[0] == keyword
            return nil
        end

        # Ensures that the given keyword happens to match the next token.
        # Returns the token on success.
        def expect_keyword(tokens, keyword)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Unexpected '#{token}' (not '#{keyword}')" unless token == keyword
            return token
        end

        # Ensures that the next token matches an entry in the given array.
        # On success, the respective token is returned.
        def expect_old(tokens, array)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Unknown identifier '#{token}'" unless array.include?(token)
            return token
        end

        # Ensures that the next token does NOT match an entry in the given array.
        # On success, the respective token is returned.
        def expect_new(tokens, array)
            raise "Unexpected EOF" unless !tokens.empty?
            token = get_next(tokens)
            raise "Identifier '#{token}' already in use" unless !array.include?(token)
            return token
        end

        # Parses the given string for a positive non-zero integer.
        def get_int(s)
            i = s.to_i
            raise "Failed to parse integer: '#{s}'" unless i > 0
            return i
        end

        # Parses the given string for a positive non-zero float.
        def get_float(s)
            f = s.to_f
            raise "Failed to parse float: '#{s}'" unless f > 0.0
            return f
        end

        # Parses the given string for a positive non-zero rational.
        def get_rational(s)
            r = s.to_r
            raise "Failed to parse rational: '#{s}'" unless r > 0
            return r
        end

        # Returns the plain array of names of an array of named items.
        def get_names(array)
            result = Array.new
            array.each do |item|
                result.push(item.name)
            end
            return result
        end

        # Augments an exception message with a token history.
        def fail_verbosely(msg)
            puts "Token history at point of error:"
            puts "================================"
            pp @history
            puts "================================"
            raise msg
        end
    end
end

Wirklich elegant schaut das zwar noch nicht aus, aber zunächst soll es überhaupt einmal funktionieren. Der Härtetest folgt mit der zweiten Ausführung: der Diesel^2-generierte EBNF-Parser. Den Code wiederhole ich nicht, da er wie erwartet identisch zum ersten Ergebnis aussieht. Es ist vollbracht.

Zurück zur Melodie

Um den Kreis noch zu schließen, habe ich für Daniels Melody-DSL folgende EBNF-Syntax erstellt:

gramar = { note }, { melody };
note = "note", ID, FLOAT;
melody = "melody", ID, time, "at", bpm, "{", { bar } ,"}";
time = INT, "/", INT;
bpm = INT, "bpm";
bar = "bar", "{", { appliedNote },  "}";
appliedNote = time, ID;

Der zuvor generierte Diesel-Parser erzeugt zusammen mit dem Parser-Template einen korrekten Melody-Parser. Dieser wiederum angewendet auf Daniels ursprüngliches Melody-Beispiel, ergibt zusammen mit zwei neuen ERB-Templates für den zu generierenden C-Code einen wunderbaren WAV-Generator für Jingle Bells.

note C 261.63
note D 293.66
note E 329.63
note F 349.23
note G 392.00
note A 440.00
note B 493.38

melody JingleBells 4/4 at 125 bpm {
    bar { 1/4 E   1/4 E   1/2 E }
    bar { 1/4 E   1/4 E   1/2 E }
    bar { 1/4 E   1/4 G   3/8 C   1/8 D }
    bar { 1/1 E }
    bar { 1/4 F   1/4 F   3/8 F   1/8 F }
    bar { 1/4 F   1/4 E   1/4 E   1/8 E   1/8 E }
    bar { 1/4 E   1/4 D   1/4 D   1/4 E }
    bar { 1/2 D           1/2 G }
    bar { 1/4 E   1/4 E   1/2 E }
    bar { 1/4 E   1/4 E   1/2 E }
    bar { 1/4 E   1/4 G   3/8 C   1/8 D }
    bar { 1/1 E }
    bar { 1/4 F   1/4 F   1/4 F   1/4 F }
    bar { 1/4 F   1/4 E   1/4 E   1/8 E   1/8 E }
    bar { 1/4 G   1/4 G   1/4 F   1/4 D }
    bar { 1/1 C }
}

Hier zeigt sich, dass ERB-Templates durchaus eine gewisse Praxistauglichkeit für die Generierung von Code haben.

#ifndef MELODIES_H
#define MELODIES_H

typedef struct tag_TimeFreq_t {
    double time_s;
    double freq_hz;
} TimeFreq_t;

extern const TimeFreq_t [];

#endif /* MELODIES_H */
#include "melodies.h"

const TimeFreq_t [] = {

    /* Bar */
    { f, f }, /*  */
};

Diesel oder Diesel^2

Es ist spannend zu sehen, dass der Diesel-Ansatz hervorragend geeignet ist, um schnell und leichtgewichtig eine DSL samt Generatoren umzusetzen. Für komplexere Anwendungsfälle wird das händische Herunterschreiben (viel Copy’n’Paste) des Parsers aber eher zäh. Ein Diesel-Parser-Generator (Diesel^2) ist mit dem Diesel-Ansatz jedoch ebenfalls unkompliziert umsetzbar. Damit kann ich meine Sprachdefinition in EBNF-Notation dokumentieren und erhalte einen funktionstüchtigen Parser. Änderungen und Erweiterungen an der Sprache sind so schnell durchgeführt.

Allerdings verliere ich natürlich durch die Generierung wieder ein Stück der Kontrolle. Mit dem derzeitigen Diesel^2-Ansatz sind dem Parser etwa semantische Aspekte nicht beizubringen. Auch die Fehlermeldungen des Parsers fallen deutlich weniger spezifisch aus und erschweren potentiell die Fehlersuche. Diese Freiheiten habe ich zunächst nur, wenn ich den Parse von Hand schreibe.

Diesel und Diesel^2

Ich halte es für lohnenswert, in die genannten Nachteile noch etwas Arbeit zu investieren. An drei Stellen könnte man ansetzen:

  1. Die rudimentäre EBNF-Syntax könnte noch erweitert werden, um mehr Einfluss auf das Generator-Ergebnis zu ermöglichen.
  2. Der Parser-Generator könnte um Ansatzpunkte erweitert werden, um den Generator bei Bedarf punktuell anzupassen.
  3. Das Parser-Template könnte ebenfalls um Ansatzpunkte erweitert werden, um den generierten Parser mit manuellem Code ergänzen zu können.

Unberührt bleiben die weiteren Vorteile, die bereits Daniel formuliert hat:

  • Generatoren sind mit Ruby-Boardmitteln einfach zu erstellen.
  • Die Integration in Build-Systeme ist problemlos möglich.
  • Der insgesamt notwendige Ruby-Code ist äußerst überschaubar.

Ich freue mich auf den ersten Diesel-Projekteinsatz und die Ergebnisse der Bewährungsprobe im Alltag.

Kommentare (0)

×

Updates

Schreiben Sie sich jetzt ein für unsere zwei-wöchentlichen Updates per E-Mail.

This field is required
This field is required
This field is required

Mich interessiert

Select at least one category
You were signed up successfully.

Erhalten Sie regelmäßige Updates zu neuen Blogartikeln

Jetzt anmelden

Oder möchten Sie eine Projektanfrage mit uns besprechen? Kontakt aufnehmen »