Posted at

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

『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

【関連情報】

Cocoa.swift 2019-02


Cocoa.swift


Cocoa勉強会 関東


MOSA


Cocoa練習帳


Qiita