[cocoa][swift]作譜用言語PL/0 表駆動の構文解析 #Swift

『Algorithms + Data Structures = Programs』は、ニクラウス・ヴィルト氏の著名な書籍で、翻訳された書籍の表題は『アルゴリズム＋データ構造＝プログラム』だ。サンプルは、Pascalで記述され構造化プログラミングのバイブル的な書籍だ。

その次の版は、『アルゴリズムとデータ構造』と『翻訳系構成法序論』の二冊に分かれ、Modula-2で記述されている。その次の版は、Oberonで記述されているらしいが、残念ながら入手は困難だ。

ニクラウス・ヴィルト氏は、AppleのObject Pascalの開発にも関与したという話を聞いたことがある。

『翻訳系構成法序論』の感想は、最少限度の知識のみを必要とし、簡素な内容となっていて、初学者の教科書としては理想的ではないかと思っている。

それでは、続きを始める。

前回は、ゴリゴリと記述していたコードを「表駆動の構文解析」では、汎用的なコードを処理するという内容だ。

読み取った記号が終端記号か非終端記号か、そして、次の処理に移動するのか、if分の条件分岐のように、別候補に移動するのかを保持する表、Swiftでは構造体やクラスがそれに対応するので、実装してみる。

class Node {
    public var successor: Node? = nil
    public var alternative: Node? = nil
    public var terminal: Bool = true
    public var terminalSymbol: Character = "\0"
    public var nonterminalSymbol: Header? = nil
}

上記では未定義だった見出しに相当するのが以下だ。

class Header {
    public var symbol: Character = "\0"
    public var entry: Node? = nil
}

これを使いと前回の分析子の処理は以下となる。

func parse(goal: Header, match: inout Bool) {
    var s: Node? = goal.entry
    repeat {
        if s!.terminal {
            if s!.terminalSymbol == ch {
                match = true
                readChar()
            }
            else {
                if s!.terminalSymbol == empty {
                    match = true
                }
                else {
                    match = false
                }
            }
        }
        else {
            parse(goal: s!.nonterminalSymbol!, match: &match)
        }
        if match {
            s = s!.successor
        }
        else {
            s = s!.alternative
        }
    } while s != nil
}

ソースコード
GitHubからどうぞ。

https://github.com/murakami/workbook/tree/master/mac/pl0 - GitHub