LoginSignup
15
13

More than 5 years have passed since last update.

D言語Advent Calendar 2014Day 10
@outlandkarasu@github(outlandkarasu)

D言語で構文解析器をつくる(3) アブストラクト・シンタックス・クリスマスツリー編

Last updated at Posted at 2014-12-24

はじめに

前回までのあらすじ

もうすぐクリスマスですね。












さて、前回まででPEGパーサー・コンビネーターを組み合わせ、解析結果に応じてアクションを実行するところまで辿り着きました。

今回は、解析結果をプログラムが処理しやすい抽象構文木(Abstract Syntax Tree = AST)を構築し、さらにはPEGによるPEG自身の構文解析まで行ってしまいます。

もくじ

  1. D言語で構文解析器をつくる(1) パーサー・コンビネーター編
  2. D言語で構文解析器をつくる(2) セマンティック・アクション編
  3. D言語で構文解析器をつくる(3) アブストラクト・シンタックス・クリスマスツリー編 (本記事)

今回つくるもの

PEG文法の文字列からPEGパーサー・コンビネーターを生成できるようにします。
以下は、PEGのPEG文法文字列からPEGのPEGパーサーを生成するPEGのPEGデモでPEG。

import std.stdio;

import yadc.peg;
import yadc.pegpeg;

import compile_time_unittest : enableCompileTimeUnittest;
mixin enableCompileTimeUnittest;

/// PEGの文法
enum PEG_GRAMMAR = q{
# PEG文法の定義

# 改行
:newLine: = '\r' '\n'? / '\n';

# 空白
space = [" \t\v\f"];

# 空白列
whiteSpaces = (newLine / space)+;

# コメント
comment = '#' (!newLine .)* (newLine / $);

# 空白
sp = (comment / whiteSpaces)*;

# 8進数
octDigit = ['0'..'7'];

# 16進数
hexDigit = ['0'..'9'] / ['a'..'f'] / ['A'..'F'];

# エスケープシーケンス文字
escChars = ["\'\"\?\\abfnrtv0"];

# 16進エスケープシーケンス文字
hexEscape = 'x' hexDigit hexDigit;

# 8進エスケープシーケンス文字
octEscape = octDigit octDigit? octDigit?;

# 16進数4文字
hex4Digit = hexDigit hexDigit hexDigit hexDigit;

# ユニコード16ビットエスケープシーケンス
unicode16Escape = 'u' hex4Digit;

# ユニコード32ビットエスケープシーケンス
unicode32Escape = 'U' hex4Digit hexDigit;

# エスケープシーケンス
escapeSequence = '\\' (
        escChars
        / hexEscape
        / octEscape
        / unicode16Escape
        / unicode32Escape);

# 文字リテラル
{CHAR} = '\'' (escapeSequence / !'\'' .) '\'';

# 文字列リテラル
{STRING} = '\"' (escapeSequence / !'\"' .)* '\"';

# 識別子の先頭文字
idHead = ['a'..'z'] / ['A'..'Z'] / '_';

# 識別子の尾部文字
idTail= idHead / ['0'..'9'];

# 識別子
{ID} = idHead idTail*;

# 文字範囲
{RANGE} = '[' sp CHAR sp ".." sp CHAR sp ']';

# 文字セット
{SET} = '[' sp STRING sp ']';

# 任意文字
{ANY} = '.';

# ソース終端
{END} = '$';

# 原始式
atom = ID / STRING / CHAR / ANY / END / RANGE / SET / '(' sp SELECT sp ')';

# 有るか無いか演算子
{OPTION} = atom sp '?';

# 0個以上演算子
{MORE0} = atom sp '*';

# 1個以上演算子
{MORE1} = atom sp '+';

# 後置演算子式
postfix = OPTION / MORE0 / MORE1 / atom;

# 有るかテスト演算子式
{AND} = '&' sp postfix;

# 無いかテスト演算子式
{NOT} = '!' sp postfix;

# 前置演算子式
prefix = AND / NOT / postfix;

# 連接式
{SEQUENCE} = prefix (sp prefix)*;

# 選択式
{SELECT} = SEQUENCE (sp '/' sp SEQUENCE)*;

# ノード識別子
{NODE_ID} = '{' sp ID sp '}';

# 改行ノード識別子
{NEW_LINE} = ':' sp ID sp ':';

# 定義式
{DEFINE} = (NODE_ID / NEW_LINE / ID) sp '=' sp SELECT sp ';';

# PEGソース
{ROOT} = (sp DEFINE)* sp $;
};

// PEG文法に従ってPEG構文解析器を生成してmixin
mixin(compilePeg!PegNode(PEG_GRAMMAR));

/// メイン関数
void main() {
    // PEG文法自身を自分自身で解析する
    auto s = pegSourceRange(PEG_GRAMMAR);
    auto result = ROOT(s);
    assert(result);

    // 解析結果を表示
    writefln("%s", s.ast.roots[0]);
}
実行結果。ASTの情報をプリント
ROOT [0..1800](1)
 DEFINE [18..48](5)
  NEW_LINE [18..27](5)
   ID [19..26](5)
  SELECT [30..47](5)
   SEQUENCE [30..40](5)
    CHAR [30..34](5)
    OPTION [35..40](5)
     CHAR [35..39](5)
   SEQUENCE [43..47](5)
    CHAR [43..47](5)
 DEFINE [55..75](8)
  ID [55..60](8)
  SELECT [63..74](8)
   SEQUENCE [63..74](8)
    SET [63..74](8)
     STRING [64..73](8)
 DEFINE [83..116](11)
  ID [83..94](11)
  SELECT [97..115](11)
   SEQUENCE [97..115](11)
    MORE1 [97..115](11)
     SELECT [98..113](11)
      SEQUENCE [98..105](11)
       ID [98..105](11)
      SEQUENCE [108..113](11)
       ID [108..113](11)
 DEFINE [125..167](14)
  ID [125..132](14)
  SELECT [135..166](14)
   SEQUENCE [135..166](14)
    CHAR [135..138](14)
    MORE0 [139..152](14)
     SELECT [140..150](14)
      SEQUENCE [140..150](14)
       NOT [140..148](14)
        ID [141..148](14)
       ANY [149..150](14)
    SELECT [154..165](14)
     SEQUENCE [154..161](14)
      ID [154..161](14)
     SEQUENCE [164..165](14)
      END [164..165](14)
 DEFINE [174..204](17)
  ID [174..176](17)
  SELECT [179..203](17)
   SEQUENCE [179..203](17)
    MORE0 [179..203](17)
     SELECT [180..201](17)
      SEQUENCE [180..187](17)
       ID [180..187](17)
      SEQUENCE [190..201](17)
       ID [190..201](17)
 DEFINE [212..234](20)
  ID [212..220](20)
  SELECT [223..233](20)
   SEQUENCE [223..233](20)
    RANGE [223..233](20)
     CHAR [224..227](20)
     CHAR [229..232](20)
 DEFINE [243..291](23)
  ID [243..251](23)
  SELECT [254..290](23)
   SEQUENCE [254..264](23)
    RANGE [254..264](23)
     CHAR [255..258](23)
     CHAR [260..263](23)
   SEQUENCE [267..277](23)
    RANGE [267..277](23)
     CHAR [268..271](23)
     CHAR [273..276](23)
   SEQUENCE [280..290](23)
    RANGE [280..290](23)
     CHAR [281..284](23)
     CHAR [286..289](23)
 DEFINE [308..340](26)
  ID [308..316](26)
  SELECT [319..339](26)
   SEQUENCE [319..339](26)
    SET [319..339](26)
     STRING [320..338](26)
 DEFINE [360..394](29)
  ID [360..369](29)
  SELECT [372..393](29)
   SEQUENCE [372..393](29)
    CHAR [372..375](29)
    ID [376..384](29)
    ID [385..393](29)
 DEFINE [413..454](32)
  ID [413..422](32)
  SELECT [425..453](32)
   SEQUENCE [425..453](32)
    ID [425..433](32)
    OPTION [434..443](32)
     ID [434..442](32)
    OPTION [444..453](32)
     ID [444..452](32)
 DEFINE [466..514](35)
  ID [466..475](35)
  SELECT [478..513](35)
   SEQUENCE [478..513](35)
    ID [478..486](35)
    ID [487..495](35)
    ID [496..504](35)
    ID [505..513](35)
 DEFINE [539..571](38)
  ID [539..554](38)
  SELECT [557..570](38)
   SEQUENCE [557..570](38)
    CHAR [557..560](38)
    ID [561..570](38)
 DEFINE [596..637](41)
  ID [596..611](41)
  SELECT [614..636](41)
   SEQUENCE [614..636](41)
    CHAR [614..617](41)
    ID [618..627](41)
    ID [628..636](41)
 DEFINE [652..786](44)
  ID [652..666](44)
  SELECT [669..785](44)
   SEQUENCE [669..785](44)
    CHAR [669..673](44)
    SELECT [684..784](45)
     SEQUENCE [684..692](45)
      ID [684..692](45)
     SEQUENCE [703..712](46)
      ID [703..712](46)
     SEQUENCE [723..732](47)
      ID [723..732](47)
     SEQUENCE [743..758](48)
      ID [743..758](48)
     SEQUENCE [769..784](49)
      ID [769..784](49)
 DEFINE [797..843](52)
  NODE_ID [797..803](52)
   ID [798..802](52)
  SELECT [806..842](52)
   SEQUENCE [806..842](52)
    CHAR [806..810](52)
    SELECT [812..836](52)
     SEQUENCE [812..826](52)
      ID [812..826](52)
     SEQUENCE [829..836](52)
      NOT [829..834](52)
       CHAR [830..834](52)
      ANY [835..836](52)
    CHAR [838..842](52)
 DEFINE [855..904](55)
  NODE_ID [855..863](55)
   ID [856..862](55)
  SELECT [866..903](55)
   SEQUENCE [866..903](55)
    CHAR [866..870](55)
    MORE0 [871..898](55)
     SELECT [872..896](55)
      SEQUENCE [872..886](55)
       ID [872..886](55)
      SEQUENCE [889..896](55)
       NOT [889..894](55)
        CHAR [890..894](55)
       ANY [895..896](55)
    CHAR [899..903](55)
 DEFINE [917..956](58)
  ID [917..923](58)
  SELECT [926..955](58)
   SEQUENCE [926..936](58)
    RANGE [926..936](58)
     CHAR [927..930](58)
     CHAR [932..935](58)
   SEQUENCE [939..949](58)
    RANGE [939..949](58)
     CHAR [940..943](58)
     CHAR [945..948](58)
   SEQUENCE [952..955](58)
    CHAR [952..955](58)
 DEFINE [969..997](61)
  ID [969..975](61)
  SELECT [977..996](61)
   SEQUENCE [977..983](61)
    ID [977..983](61)
   SEQUENCE [986..996](61)
    RANGE [986..996](61)
     CHAR [987..990](61)
     CHAR [992..995](61)
 DEFINE [1005..1027](64)
  NODE_ID [1005..1009](64)
   ID [1006..1008](64)
  SELECT [1012..1026](64)
   SEQUENCE [1012..1026](64)
    ID [1012..1018](64)
    MORE0 [1019..1026](64)
     ID [1019..1025](64)
 DEFINE [1036..1081](67)
  NODE_ID [1036..1043](67)
   ID [1037..1042](67)
  SELECT [1046..1080](67)
   SEQUENCE [1046..1080](67)
    CHAR [1046..1049](67)
    ID [1050..1052](67)
    ID [1053..1057](67)
    ID [1058..1060](67)
    STRING [1061..1065](67)
    ID [1066..1068](67)
    ID [1069..1073](67)
    ID [1074..1076](67)
    CHAR [1077..1080](67)
 DEFINE [1091..1120](70)
  NODE_ID [1091..1096](70)
   ID [1092..1095](70)
  SELECT [1099..1119](70)
   SEQUENCE [1099..1119](70)
    CHAR [1099..1102](70)
    ID [1103..1105](70)
    ID [1106..1112](70)
    ID [1113..1115](70)
    CHAR [1116..1119](70)
 DEFINE [1129..1141](73)
  NODE_ID [1129..1134](73)
   ID [1130..1133](73)
  SELECT [1137..1140](73)
   SEQUENCE [1137..1140](73)
    CHAR [1137..1140](73)
 DEFINE [1151..1163](76)
  NODE_ID [1151..1156](76)
   ID [1152..1155](76)
  SELECT [1159..1162](76)
   SEQUENCE [1159..1162](76)
    CHAR [1159..1162](76)
 DEFINE [1171..1246](79)
  ID [1171..1175](79)
  SELECT [1178..1245](79)
   SEQUENCE [1178..1180](79)
    ID [1178..1180](79)
   SEQUENCE [1183..1189](79)
    ID [1183..1189](79)
   SEQUENCE [1192..1196](79)
    ID [1192..1196](79)
   SEQUENCE [1199..1202](79)
    ID [1199..1202](79)
   SEQUENCE [1205..1208](79)
    ID [1205..1208](79)
   SEQUENCE [1211..1216](79)
    ID [1211..1216](79)
   SEQUENCE [1219..1222](79)
    ID [1219..1222](79)
   SEQUENCE [1225..1245](79)
    CHAR [1225..1228](79)
    ID [1229..1231](79)
    ID [1232..1238](79)
    ID [1239..1241](79)
    CHAR [1242..1245](79)
 DEFINE [1260..1283](82)
  NODE_ID [1260..1268](82)
   ID [1261..1267](82)
  SELECT [1271..1282](82)
   SEQUENCE [1271..1282](82)
    ID [1271..1275](82)
    ID [1276..1278](82)
    CHAR [1279..1282](82)
 DEFINE [1295..1317](85)
  NODE_ID [1295..1302](85)
   ID [1296..1301](85)
  SELECT [1305..1316](85)
   SEQUENCE [1305..1316](85)
    ID [1305..1309](85)
    ID [1310..1312](85)
    CHAR [1313..1316](85)
 DEFINE [1329..1351](88)
  NODE_ID [1329..1336](88)
   ID [1330..1335](88)
  SELECT [1339..1350](88)
   SEQUENCE [1339..1350](88)
    ID [1339..1343](88)
    ID [1344..1346](88)
    CHAR [1347..1350](88)
 DEFINE [1362..1402](91)
  ID [1362..1369](91)
  SELECT [1372..1401](91)
   SEQUENCE [1372..1378](91)
    ID [1372..1378](91)
   SEQUENCE [1381..1386](91)
    ID [1381..1386](91)
   SEQUENCE [1389..1394](91)
    ID [1389..1394](91)
   SEQUENCE [1397..1401](91)
    ID [1397..1401](91)
 DEFINE [1417..1440](94)
  NODE_ID [1417..1422](94)
   ID [1418..1421](94)
  SELECT [1425..1439](94)
   SEQUENCE [1425..1439](94)
    CHAR [1425..1428](94)
    ID [1429..1431](94)
    ID [1432..1439](94)
 DEFINE [1455..1478](97)
  NODE_ID [1455..1460](97)
   ID [1456..1459](97)
  SELECT [1463..1477](97)
   SEQUENCE [1463..1477](97)
    CHAR [1463..1466](97)
    ID [1467..1469](97)
    ID [1470..1477](97)
 DEFINE [1489..1518](100)
  ID [1489..1495](100)
  SELECT [1498..1517](100)
   SEQUENCE [1498..1501](100)
    ID [1498..1501](100)
   SEQUENCE [1504..1507](100)
    ID [1504..1507](100)
   SEQUENCE [1510..1517](100)
    ID [1510..1517](100)
 DEFINE [1526..1559](103)
  NODE_ID [1526..1536](103)
   ID [1527..1535](103)
  SELECT [1539..1558](103)
   SEQUENCE [1539..1558](103)
    ID [1539..1545](103)
    MORE0 [1546..1558](103)
     SELECT [1547..1556](103)
      SEQUENCE [1547..1556](103)
       ID [1547..1549](103)
       ID [1550..1556](103)
 DEFINE [1567..1609](106)
  NODE_ID [1567..1575](106)
   ID [1568..1574](106)
  SELECT [1578..1608](106)
   SEQUENCE [1578..1608](106)
    ID [1578..1586](106)
    MORE0 [1587..1608](106)
     SELECT [1588..1606](106)
      SEQUENCE [1588..1606](106)
       ID [1588..1590](106)
       CHAR [1591..1594](106)
       ID [1595..1597](106)
       ID [1598..1606](106)
 DEFINE [1620..1649](109)
  NODE_ID [1620..1629](109)
   ID [1621..1628](109)
  SELECT [1632..1648](109)
   SEQUENCE [1632..1648](109)
    CHAR [1632..1635](109)
    ID [1636..1638](109)
    ID [1639..1641](109)
    ID [1642..1644](109)
    CHAR [1645..1648](109)
 DEFINE [1662..1692](112)
  NODE_ID [1662..1672](112)
   ID [1663..1671](112)
  SELECT [1675..1691](112)
   SEQUENCE [1675..1691](112)
    CHAR [1675..1678](112)
    ID [1679..1681](112)
    ID [1682..1684](112)
    ID [1685..1687](112)
    CHAR [1688..1691](112)
 DEFINE [1700..1761](115)
  NODE_ID [1700..1708](115)
   ID [1701..1707](115)
  SELECT [1711..1760](115)
   SEQUENCE [1711..1760](115)
    SELECT [1712..1735](115)
     SEQUENCE [1712..1719](115)
      ID [1712..1719](115)
     SEQUENCE [1722..1730](115)
      ID [1722..1730](115)
     SEQUENCE [1733..1735](115)
      ID [1733..1735](115)
    ID [1737..1739](115)
    CHAR [1740..1743](115)
    ID [1744..1746](115)
    ID [1747..1753](115)
    ID [1754..1756](115)
    CHAR [1757..1760](115)
 DEFINE [1772..1799](118)
  NODE_ID [1772..1778](118)
   ID [1773..1777](118)
  SELECT [1781..1798](118)
   SEQUENCE [1781..1798](118)
    MORE0 [1781..1793](118)
     SELECT [1782..1791](118)
      SEQUENCE [1782..1791](118)
       ID [1782..1784](118)
       ID [1785..1791](118)
    ID [1794..1796](118)
    END [1797..1798](118)

Github

今回やること

  • 前回までのパーサー・コンビネーターに抽象構文木(AST)構築機能を追加する
  • PEG文法を読み込み、パーサー・コンビネーターのD言語ソースを生成できるようにする。

抽象構文木(AST)の構築

抽象構文木(AST)とは

抽象構文木(AST)とは、リンク先を読めば何もかも済む話なのですが、要は構文解析の結果で出来る木構造です。

例えばこんな数式があった場合
a = 1 + 2 * 3;

きっと多分おそらくASTはこんな感じになります。

代入式
  左辺式
    識別子 "a"
  右辺式
    加算式
      項
        整数 1
      項
        乗算
          整数 2
          整数 3

このASTの中には、空白や行末を示す;は出てきません。
そういった処理には要らない情報を捨てて、必要なものだけを抽象した木構造のデータとなっています。

上で「代入式」や「項」と書いた部分は、ASTのノード(node)と呼ばれます。
ノードは複数の子ノードを含み、その子ノードがさらに複数の子を……といった入れ子(再帰)構造になっています。
こういった入れ子構造は、木の根っこから各要素を辿って自然な順序で処理を行うことができます。
加算より先に乗算を行うといった演算子の優先順位の問題なども、データの構造をなぞるだけで無意識に解決できます。

今回、こんなASTを作れるようにパーサー・コンビネーターを拡張します。
ASTさえ作れれば、解析結果を別言語に変換したり、コンパイラじみたことをやらせるまであと一歩です。

検討

で、ASTをどう構築するかです。

まず、ASTを何で表現するかを決める必要があります。
ASTは木構造なので、自分と同じ型の子へのポインタが持てる・子の種類が外から分かることが必須条件です。
そういったものの表現のためにD言語で使える道具はこんな感じです。

  • 配列
  • クラス
  • 構造体
  • テンプレート

配列はどう考えても木構造に向かないので除外します。
テンプレートは、実は結構木構造を作るのに使えます。
今回のパーサー・コンビネーターなどはテンプレートで木構造を作っている例になっています。
しかし、基本的には型を定義するためのもので、動的なデータ処理には向かないので除外します。

(実は、テンプレートの世界と動的なデータ構造の世界を橋渡しできるのがD言語のすごいところなのです。その点はすぐ後で出てきます)

さて、残りは普通のクラスと構造体です。

D言語では、クラスも構造体も割と同じように使えるのですが、以下のようなところが違います。

  • クラスは参照が基本、構造体は値が基本
  • クラスのインスタンスはヒープから確保するのが基本、構造体はスタックに配置されるのが基本
  • クラスのインスタンスは共有されるのが基本、構造体は値がコピーされていくのが基本

D言語の表現力をもってすればどちらでも十分ASTを作れるのですが、今回は以下の理由によりクラスを採用したいと思います。

  • ASTは構文解析時に1度だけ作られ、その後様々な場所で共有される。そのため、共有が基本のクラスの方が合っている。
  • ASTはかなり大規模なデータ構造になるため、ヒープに配置する方が良い。
  • ASTに今後動作を追加する場合、クラスの拡張でそれが行えるかもしれない。

ASTクラス

方針が決まったところで実装を行います。

AST(のノード)に絶対必要なのは、

  • 複数の子へのポインタ
  • ノードの種類を示す値

この2つです。
おまけで行番号や位置情報が分かると後から便利です。

データ部分だけをざっと定義すると、下記のようになります。

/// ASTクラス。Tはノードの種類を示す値の型(enumなど)
class AST(T) {
    /// ノードクラス
    static class Node {
        /// ノードの種類
        T type;

        /// 子ノード。サイズが0の場合もある
        Node[] children;
    }

    /// 根のノード
    Node[] roots;
}

データとしては、本質的な部分は以上です。
何か処理をしたい場合は、AST.rootsから処理を開始してchildrenを順に辿ることになります。

データ構造は単純ですが、これをどう構築するかは、なかなか難しい問題です。

ASTノードパーサー

ASTのノードを構築するにあたって、考えなければならない点がいくつかあります。

  • ノードを作るのはパーサーの解析成功時になるだろう。
  • ノードを作ったとき、親ノードがあればその子として追加する必要がある。
  • しかし、子ノードが全部出来てからでないと親ノードは作れない。
  • 親ノードが解析失敗したとき、子ノードもまとめて捨てる必要がある。

数式の例で考えてみます。

a = 1 + 2 * 3;

木構造をカッコ"()"で表すと、以下のようになります。

((a) = ((1) + ((2) * (3))));

なんかLISPっぽいですね。
これを見ると、次のようなことが分かります。

  • 同レベルのカッコはお互いの範囲が重ならない。
    • 前のカッコが閉じられない限り次のカッコが始まることはない。開閉が必ず対応している。
  • 親と子の範囲が交差することもない。
    • 必ず子のカッコが閉じ切ってから親のカッコが閉じられる。

これから、

  • 同レベルの子ノードを集めていくのは、単純に動的配列に積んでいけば良さそう。
  • 子ノードの解析が完了した時点で、動的配列に積まれた子ノードを集めて親ノードを作れば良さそう。
  • 上記を再帰的に行えば、木構造ができそう。

といったことがよく考えると分かります。
それで私なりに色々考えた結果、以下のような実装を行うに至りました。

class AST(T) {

// Nodeの定義は省略

    /**
     *  ノードを開始する
     *
     *  Params:
     *      type = 開始したノード
     */
    void beginNode(T type) @safe {
        // 状態スタックに新しいノードの開始状態を積む
        stack_ ~= State(type);
    }

    /**
     *  最後のノードを終了する
     */
    void endNode() @safe {
        // スタックの一番上からノードの状態を取り出し、ノードを作る
        auto state = stack_[$ - 1];
        auto node = new immutable(Node)(state.type, state.children);
        --stack_.length;

        // スタックが空になったらルートノードと見なす
        // そうでなければ親ノードの子として追加する
        if(stack_.empty) {
            roots_ ~= node;
        } else {
            stack_[$ - 1].children ~= node;
        }
    }

    /**
     *  最後に開始したノードを元に戻す
     */
    void backtrack() @safe {
        --stack_.length;
    }

private:

    /// ノードの開始状態
    struct State {
        T type;
        immutable(Node)[] children;
    }

    /// 解析状態のスタック
    State[] stack_;

    /// ルートノード
    immutable(Node)[] roots_;
}

(実際にはpositionやlineを持たせたり、もう少しチェックを入れていたりします。詳しくはGithubのソース参照)

あとはこのbeginNode・endNode・backtrackをパーサーの解析に合わせて呼ぶだけです。

/**
 *  ノード生成パーサー
 *
 *  Params:
 *      Tag = ノードのタグの値
 *      P = 内部パーサー
 *      R = ソースの型
 *      r = ソース
 *  Returns:
 *      解析成功しノードが生成されればtrue。
 */
template node(alias Tag, alias P) {
    bool node(R)(ref ASTRange!(R, typeof(Tag)) r) {
        // ノードの開始。
        r.ast.beginNode(r.position, r.line, Tag);
        {
            // 解析中・ノード生成中に例外が出たらバックトラック
            scope(failure) r.ast.backtrack();

            // 解析成功すればノード生成
            if(P(r)) {
                r.ast.endNode(r.position);
                return true;
            }
        }

        // 解析失敗のためバックトラック
        r.ast.backtrack();
        return false;
    }
}

ASTRangeは、単にASTを保持しているRangeです。
このASTRangeとnodeパーサーを既存のパーサー・コンビネーターと組み合わせて使うことで、構文解析結果から木構造が生成できるようになります。

unittest {
    // 適当なノードの型
    enum NodeType {
        NODE1,
        NODE2,
        NODE3,
    }

    // NODE1が根となるノードで、NODE2・NODE3は兄弟関係になる。
    alias node!(NodeType.NODE3, str!"stt") node3;
    alias node!(NodeType.NODE2, sel!(str!"te", str!"st")) node2;
    alias node!(NodeType.NODE1, seq!(node2, sel!(node3, node2))) node1;

    // 全体の解析
    auto s = astRange!NodeType("test");
    assert(node1(s));

    // ルートノードの取得
    auto root = s.ast.roots[0];
    assert(root.type == NodeType.NODE1);
    assert(root.children.length == 2);

    // ノード2の取得
    auto node2_1 = root.children[0];
    assert(node2_1.type == NodeType.NODE2);
    assert(node2_1.children.length == 0);

    // ノード2の取得
    auto node2_2 = root.children[1];
    assert(node2_2.type == NodeType.NODE2);
    assert(node2_2.children.length == 0);
}

PEG文法の定義

上記でASTの生成が行えるようになりました。
私の時間の都合で説明が全然足りていないので、ぶっちゃっけよくわからないと思います。
よって、ここからは勢いでPEG自身の構文解析器を実装して乗り切ろうと思います。

文法の概要

今までstr!とかch!とかしていたものを、全て分かりやすい正規表現的な文法の形で表現します。

# #から行末まではコメント

# 原始式
'a' # 文字リテラル。この文字にマッチする。
"abc" # 文字列リテラル。この文字列にマッチする。
['a'..'z'] # 文字範囲。この文字範囲以内の文字にマッチする。終端も含む
["abcdef"] # 文字集合。この文字の中にある文字1つにマッチする。
. # 任意文字。何かしら1文字にマッチする。
$ # 終端文字。ソースの最後にマッチする。
a # 識別子。別に定義されているパーサーを呼び出す。
(a b c) # カッコ式。カッコ内のパーサー式を呼び出す。

# 後置演算子
a? # 前のパーサーにマッチする要素があるかないか。
a* # 前のパーサーにマッチする要素が0個以上。
a+ # 前のパーサーにマッチする要素が1個以上。

# 前置演算子
&a # あるかテスト。
!a # 無いかテスト

# 連接
a b c # a・b・c全てあればマッチ

# 選択
a b / c d # a bまたはc dがあればマッチ

# 定義
a = 'a' 'b'; # aは 'a' 'b' にマッチするという定義。末尾の;は定義の終了を表す。
{a} = 'a' 'b'; # 左辺を{}でくくった定義はASTノードを生成する。
:a: = '¥r' '¥n' / '¥r' / '¥n'; # 左辺を::でくくった定義は改行を表し、行番号をカウントアップする。

ノードの一覧はこちら

/// PEGノードの型
enum PegNode {
    STRING,   /// リテラル文字列
    CHAR,     /// リテラル文字
    ID,       /// 識別子
    NODE_ID,  /// ノード識別子
    NEW_LINE, /// 改行ノード
    ANY,      /// 任意の1文字
    RANGE,    /// 文字範囲
    SET,      /// 文字集合
    END,      /// 終端
    OPTION,   /// 有るか無いか
    AND,      /// 有るかテスト
    NOT,      /// 無いかテスト
    MORE0,    /// 0個以上
    MORE1,    /// 1個以上
    SELECT,   /// 選択
    SEQUENCE, /// 連接
    DEFINE,   /// 定義
    ROOT,     /// ルートノード
}

方針

  • なるべくD言語の字句に近い字句を使用する。
  • 行コメントを除いて改行・空白は自由に入れてよくする。
  • エラー処理はしない。

リテラル類(面倒なので実装とかスキップ)

D言語の文字リテラル・文字列リテラルは、文字実体参照を除いてそれなりに使えます。

原始式

/// 識別子の先頭文字
alias sel!(rng!('a', 'z'), rng!('A', 'Z'), ch!'_') idHead;

/// 識別子の尾部の文字
alias sel!(idHead, rng!('0', '9')) idTail;

/// 識別子
alias node!(PegNode.ID, seq!(idHead, more0!idTail)) pegIdentifier;

/// 文字リテラルパーサー
alias node!(PegNode.CHAR, charLiteral) pegCharLiteral;

/// 文字列リテラルパーサー
alias node!(PegNode.STRING, stringLiteral) pegStringLiteral;

/// 文字範囲
alias node!(PegNode.RANGE, seq!(ch!'[', sp, pegCharLiteral, sp, str!"..", sp, pegCharLiteral, sp, ch!']')) pegCharRange;

/// 文字集合
alias node!(PegNode.SET, seq!(ch!'[', sp, pegStringLiteral, sp, ch!']')) pegCharSet;

/// 任意文字
alias node!(PegNode.ANY, ch!'.') pegAny;

/// 終端
alias node!(PegNode.END, ch!'$') pegEnd;

/// PEG原始式
alias sel!(
    pegIdentifier,
    pegStringLiteral,
    pegCharLiteral,
    pegAny,
    pegEnd,
    pegCharRange,
    pegCharSet,
    seq!(ch!'(', sp, pegSelect, sp, ch!')')) pegAtom;

後置演算子式

/// 有るか無いか演算子
alias node!(PegNode.OPTION, seq!(pegAtom, sp, ch!'?')) pegOption;

/// 0個以上演算子
alias node!(PegNode.MORE0, seq!(pegAtom, sp, ch!'*')) pegMore0;

/// 1個以上演算子
alias node!(PegNode.MORE1, seq!(pegAtom, sp, ch!'+')) pegMore1;

/// PEG後置演算子色
alias sel!(pegOption, pegMore0, pegMore1, pegAtom) pegPostfix;

前置演算子式

/// 有るかテスト演算子
alias node!(PegNode.AND, seq!(ch!'&', sp, pegPostfix)) pegTest;

/// 無いかテスト演算子
alias node!(PegNode.NOT, seq!(ch!'!', sp, pegPostfix)) pegNotTest;

/// 前置演算子式
alias sel!(pegTest, pegNotTest, pegPostfix) pegPrefix;

連接・選択式

/// 連接式
alias node!(PegNode.SEQUENCE, seq!(pegPrefix, more0!(seq!(sp, pegPrefix)))) pegSequence;

/// 選択式(再帰的定義のために関数にする)
bool pegSelect(R)(ref R src) {
    return node!(PegNode.SELECT, seq!(pegSequence, more0!(seq!(sp, ch!'/', sp, pegSequence))))(src);
}

定義式

/// ノード識別子式
alias node!(PegNode.NODE_ID, seq!(ch!'{', sp, pegIdentifier, sp, ch!'}')) pegNodeIdentifier;

/// 改行ノード識別子式
alias node!(PegNode.NEW_LINE, seq!(ch!':', sp, pegIdentifier, sp, ch!':')) pegNewLine;

/// 定義式
alias node!(PegNode.DEFINE, seq!(sel!(pegNodeIdentifier, pegNewLine, pegIdentifier), sp, ch!'=', sp, pegSelect, sp, ch!';')) pegDefine;

/// PEGソース
alias node!(PegNode.ROOT, seq!(more0!(seq!(sp, pegDefine)), sp, end)) pegSource;

コード生成

PEG文法をASTに解析しただけでは何もなりません。
ASTからD言語ソースを生成し、構文解析器として使用できるようにしなければなりません。
AST.Nodeを再帰的に下り、今回のパーサー・コンビネーターを使ったソースコードを生成するようにします。

/**
 *  PEGの構文木からD言語ソースをコンパイルする
 *
 *  Params:
 *      T = ノードタグ型
 *      src = ソース文字列
 *      node = ノード
 *  Returns:
 *      PEGのD言語ソース
 */
string compilePeg(T)(string src, const(AST!PegNode.Node) node) {
    alias typeof(node) Node;

    // ノード範囲の文字列を切り出す
    string source(Node n) {return src[n.begin .. n.end];}

    // ノードをコンパイルする
    string compile(Node child) {return compilePeg!T(src, child);}

    // 子ノードをコンパイルし、カンマで連結する
    string compileChildren(Node parent, string sep) {
        auto result = "";
        foreach(n; parent.children) {
            if(!result.empty) {
                result ~= sep;
            }
            result ~= compile(n);
        }
        return result;
    }

    final switch(node.type) {
    case PegNode.STRING:
        return "str!(" ~ source(node) ~ ")";
    case PegNode.CHAR:
        return "ch!(" ~ source(node) ~ ")";
    case PegNode.ID:
        return source(node);
    case PegNode.ANY:
        return "any";
    case PegNode.RANGE:
        assert(node.length == 2);
        assert(node[0].type == PegNode.CHAR);
        assert(node[1].type == PegNode.CHAR);
        return "rng!(" ~ source(node[0]) ~ "," ~ source(node[1]) ~ ")";
    case PegNode.SET:
        assert(node.length == 1);
        assert(node[0].type == PegNode.STRING);
        return "set!(" ~ source(node[0]) ~ ")";
    case PegNode.END:
        return "end";
    case PegNode.OPTION:
        assert(node.length == 1);
        return "opt!(" ~ compile(node[0]) ~ ")";
    case PegNode.AND:
        assert(node.length == 1);
        return "and!(" ~ compile(node[0]) ~ ")";
    case PegNode.NOT:
        assert(node.length == 1);
        return "not!(" ~ compile(node[0]) ~ ")";
    case PegNode.MORE0:
        assert(node.length == 1);
        return "more0!(" ~ compile(node[0]) ~ ")";
    case PegNode.MORE1:
        assert(node.length == 1);
        return "more1!(" ~ compile(node[0]) ~ ")";
    case PegNode.SELECT:
        if(node.length == 1) {
            return compile(node[0]);
        } else {
            return "sel!(" ~ compileChildren(node, ",") ~ ")";
        }
    case PegNode.SEQUENCE:
        if(node.length == 1) {
            return compile(node[0]);
        } else {
            return "seq!(" ~ compileChildren(node, ",") ~ ")";
        }
    case PegNode.DEFINE:
        {
            assert(node.length == 2);
            assert(node[1].type == PegNode.SELECT);
            auto exp = compile(node[1]);
            if(node[0].type == PegNode.ID) {
                auto id = source(node[0]);
                return "bool " ~ id ~ "(R)(ref R s){return " ~ exp ~ "(s);}";
            } else if(node[0].type == PegNode.NODE_ID) {
                assert(node[0].length == 1);
                auto id = source(node[0][0]);
                return "bool " ~ id ~ "(R)(ref R s){return node!(" ~ T.stringof ~ "." ~ id ~ "," ~ exp ~ ")(s);}";
            } else if(node[0].type == PegNode.NEW_LINE) {
                assert(node[0].length == 1);
                auto id = source(node[0][0]);
                return "bool " ~ id ~ "(R)(ref R s){return addLine!(" ~ exp ~ ")(s);}";
            } else {
                assert(false, "unexpected node type");
            }
        }
    case PegNode.ROOT:
        return compileChildren(node, "\n");
    case PegNode.NODE_ID:
        assert(false, "unexpected NODE_ID");
    case PegNode.NEW_LINE:
        assert(false, "unexpected NEW_LINE");
    }
}

/**
 *  PEGソースをD言語にコンパイルする
 *
 *  Params:
 *      T = ノードタグ型
 *      src = PEGソース
 *  Returns:
 *      D言語ソース
 */
string compilePeg(T)(string src) {
    // 諸般の事情によりubyte[]にする。
    auto s = pegSourceRange(cast(ubyte[])src);
    if(!pegSource(s) || s.ast.roots.length < 1) {
        throw new Exception("PEG compile error!");
    }   
    return compilePeg!T(src, s.ast.roots[0]);
}

コンパイルタイムにテスト・実行

ぜえぜえ……。

さて、上記まででPEG文法がD言語ソースにできるところまでできました。

できたのです。

しかしながら、わざわざプログラムでD言語ソースを吐かせてファイルにしてもう一度それをコンパイルするなんて、いにしえのyaccでも出来る芸当です。
21世紀に生きる我々としては、そんな手間は掛けずに一度のコンパイルで手軽に済ませたいです。
そのためには、D言語の高レベル暗黒超魔法CTFEを使用する必要があるのですが……。

ところで、冒頭のソースの頭にこんな記述があったと思います。

import compile_time_unittest : enableCompileTimeUnittest;
mixin enableCompileTimeUnittest;

今まで黙っていましたが、実はこれは@youxkeiさんが作ったコンパイル時単体テストです。

これを書いておくことで、モジュールのすべてのunittestがコンパイル時にも実行されることになります。

つまり……

今まで私が書いてきてunittestされているコードは全て、CTFEで動作します。

// PEG文法に従ってPEG構文解析器を生成してmixin
mixin(compilePeg!PegNode(PEG_GRAMMAR));

/// メイン関数
void main() {
    // PEG文法自身を自分自身で解析する
    auto s = pegSourceRange(PEG_GRAMMAR);
    auto result = ROOT(s);
    assert(result);

    // 解析結果を表示
    writefln("%s", s.ast.roots[0]);
}

当たり前のように動作しました。
実行結果は冒頭のデモの通りです。

生成されたコードを見てみる

さて、PEG文法と出来たD言語ソースをそれぞれ見てみましょう。

// 前略
// コンパイル時にメッセージ表示
pragma(msg, PEG_GRAMMAR);
pragma(msg, compilePeg!PegNode(PEG_GRAMMAR));

/// メイン関数
void main() {
    writefln("HELLO,WORLD!");
}
実行結果
parser: ["parser"]
Building parser configuration "application", build type debug.
Compiling...

# PEG文法の定義

# 改行
:newLine: = '\r' '\n'? / '\n';

# 空白
space = [" \t\v\f"];

# 空白列
whiteSpaces = (newLine / space)+;

# コメント
comment = '#' (!newLine .)* (newLine / $);

# 空白
sp = (comment / whiteSpaces)*;

# 8進数
octDigit = ['0'..'7'];

# 16進数
hexDigit = ['0'..'9'] / ['a'..'f'] / ['A'..'F'];

# エスケープシーケンス文字
escChars = ["\'\"\?\\abfnrtv0"];

# 16進エスケープシーケンス文字
hexEscape = 'x' hexDigit hexDigit;

# 8進エスケープシーケンス文字
octEscape = octDigit octDigit? octDigit?;

# 16進数4文字
hex4Digit = hexDigit hexDigit hexDigit hexDigit;

# ユニコード16ビットエスケープシーケンス
unicode16Escape = 'u' hex4Digit;

# ユニコード32ビットエスケープシーケンス
unicode32Escape = 'U' hex4Digit hexDigit;

# エスケープシーケンス
escapeSequence = '\\' (
        escChars
        / hexEscape
        / octEscape
        / unicode16Escape
        / unicode32Escape);

# 文字リテラル
{CHAR} = '\'' (escapeSequence / !'\'' .) '\'';

# 文字列リテラル
{STRING} = '\"' (escapeSequence / !'\"' .)* '\"';

# 識別子の先頭文字
idHead = ['a'..'z'] / ['A'..'Z'] / '_';

# 識別子の尾部文字
idTail= idHead / ['0'..'9'];

# 識別子
{ID} = idHead idTail*;

# 文字範囲
{RANGE} = '[' sp CHAR sp ".." sp CHAR sp ']';

# 文字セット
{SET} = '[' sp STRING sp ']';

# 任意文字
{ANY} = '.';

# ソース終端
{END} = '$';

# 原始式
atom = ID / STRING / CHAR / ANY / END / RANGE / SET / '(' sp SELECT sp ')';

# 有るか無いか演算子
{OPTION} = atom sp '?';

# 0個以上演算子
{MORE0} = atom sp '*';

# 1個以上演算子
{MORE1} = atom sp '+';

# 後置演算子式
postfix = OPTION / MORE0 / MORE1 / atom;

# 有るかテスト演算子式
{AND} = '&' sp postfix;

# 無いかテスト演算子式
{NOT} = '!' sp postfix;

# 前置演算子式
prefix = AND / NOT / postfix;

# 連接式
{SEQUENCE} = prefix (sp prefix)*;

# 選択式
{SELECT} = SEQUENCE (sp '/' sp SEQUENCE)*;

# ノード識別子
{NODE_ID} = '{' sp ID sp '}';

# 改行ノード識別子
{NEW_LINE} = ':' sp ID sp ':';

# 定義式
{DEFINE} = (NODE_ID / NEW_LINE / ID) sp '=' sp SELECT sp ';';

# PEGソース
{ROOT} = (sp DEFINE)* sp $;

bool newLine(R)(ref R s){return addLine!(sel!(seq!(ch!('\r'),opt!(ch!('\n'))),ch!('\n')))(s);}
bool space(R)(ref R s){return set!(" \t\v\f")(s);}
bool whiteSpaces(R)(ref R s){return more1!(sel!(newLine,space))(s);}
bool comment(R)(ref R s){return seq!(ch!('#'),more0!(seq!(not!(newLine),any)),sel!(newLine,end))(s);}
bool sp(R)(ref R s){return more0!(sel!(comment,whiteSpaces))(s);}
bool octDigit(R)(ref R s){return rng!('0','7')(s);}
bool hexDigit(R)(ref R s){return sel!(rng!('0','9'),rng!('a','f'),rng!('A','F'))(s);}
bool escChars(R)(ref R s){return set!("\'\"\?\\abfnrtv0")(s);}
bool hexEscape(R)(ref R s){return seq!(ch!('x'),hexDigit,hexDigit)(s);}
bool octEscape(R)(ref R s){return seq!(octDigit,opt!(octDigit),opt!(octDigit))(s);}
bool hex4Digit(R)(ref R s){return seq!(hexDigit,hexDigit,hexDigit,hexDigit)(s);}
bool unicode16Escape(R)(ref R s){return seq!(ch!('u'),hex4Digit)(s);}
bool unicode32Escape(R)(ref R s){return seq!(ch!('U'),hex4Digit,hexDigit)(s);}
bool escapeSequence(R)(ref R s){return seq!(ch!('\\'),sel!(escChars,hexEscape,octEscape,unicode16Escape,unicode32Escape))(s);}
bool CHAR(R)(ref R s){return node!(PegNode.CHAR,seq!(ch!('\''),sel!(escapeSequence,seq!(not!(ch!('\'')),any)),ch!('\'')))(s);}
bool STRING(R)(ref R s){return node!(PegNode.STRING,seq!(ch!('\"'),more0!(sel!(escapeSequence,seq!(not!(ch!('\"')),any))),ch!('\"')))(s);}
bool idHead(R)(ref R s){return sel!(rng!('a','z'),rng!('A','Z'),ch!('_'))(s);}
bool idTail(R)(ref R s){return sel!(idHead,rng!('0','9'))(s);}
bool ID(R)(ref R s){return node!(PegNode.ID,seq!(idHead,more0!(idTail)))(s);}
bool RANGE(R)(ref R s){return node!(PegNode.RANGE,seq!(ch!('['),sp,CHAR,sp,str!(".."),sp,CHAR,sp,ch!(']')))(s);}
bool SET(R)(ref R s){return node!(PegNode.SET,seq!(ch!('['),sp,STRING,sp,ch!(']')))(s);}
bool ANY(R)(ref R s){return node!(PegNode.ANY,ch!('.'))(s);}
bool END(R)(ref R s){return node!(PegNode.END,ch!('$'))(s);}
bool atom(R)(ref R s){return sel!(ID,STRING,CHAR,ANY,END,RANGE,SET,seq!(ch!('('),sp,SELECT,sp,ch!(')')))(s);}
bool OPTION(R)(ref R s){return node!(PegNode.OPTION,seq!(atom,sp,ch!('?')))(s);}
bool MORE0(R)(ref R s){return node!(PegNode.MORE0,seq!(atom,sp,ch!('*')))(s);}
bool MORE1(R)(ref R s){return node!(PegNode.MORE1,seq!(atom,sp,ch!('+')))(s);}
bool postfix(R)(ref R s){return sel!(OPTION,MORE0,MORE1,atom)(s);}
bool AND(R)(ref R s){return node!(PegNode.AND,seq!(ch!('&'),sp,postfix))(s);}
bool NOT(R)(ref R s){return node!(PegNode.NOT,seq!(ch!('!'),sp,postfix))(s);}
bool prefix(R)(ref R s){return sel!(AND,NOT,postfix)(s);}
bool SEQUENCE(R)(ref R s){return node!(PegNode.SEQUENCE,seq!(prefix,more0!(seq!(sp,prefix))))(s);}
bool SELECT(R)(ref R s){return node!(PegNode.SELECT,seq!(SEQUENCE,more0!(seq!(sp,ch!('/'),sp,SEQUENCE))))(s);}
bool NODE_ID(R)(ref R s){return node!(PegNode.NODE_ID,seq!(ch!('{'),sp,ID,sp,ch!('}')))(s);}
bool NEW_LINE(R)(ref R s){return node!(PegNode.NEW_LINE,seq!(ch!(':'),sp,ID,sp,ch!(':')))(s);}
bool DEFINE(R)(ref R s){return node!(PegNode.DEFINE,seq!(sel!(NODE_ID,NEW_LINE,ID),sp,ch!('='),sp,SELECT,sp,ch!(';')))(s);}
bool ROOT(R)(ref R s){return node!(PegNode.ROOT,seq!(more0!(seq!(sp,DEFINE)),sp,end))(s);}
Linking...
Running ./parser 
HELLO,WORLD!

ちゃんとD言語ソースができていますね。スゴイですね。

ちょっと前なら「CTFEだぜ！やってやったぜ！D言語マンセー！！」といったものだったのですが、最近はあまりにも普通になんでもCTFEできてしまうので、かえって感動が薄くてつまらないです。

だって動的クロージャも例外もtry-catchもスコープガード(scope)もクラスも構造体もポインタ演算も動的配列も連想配列もtemplateも全部使えて、それで何かを実装できない方がむしろ恥ずかしいくらいですもんね。

終わり

ここまで読んでくれた人がいたらありがとうございました！

クリスマスの夜になにやってるんだろ俺、と思いつつ、このコンパイルタイムPEG構文解析器実装記事が風変わりなクリスマスプレゼントになれば幸いです。

15
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
15
13