[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<br />

【関連情報】
- Cocoa.swift 2019-02
- Cocoa.swift
- Cocoa勉強会 関東
- MOSA
- Cocoa練習帳
- Qiita