Skip to content

Instantly share code, notes, and snippets.

@qnighy
Created February 23, 2018 08:14
Show Gist options
  • Save qnighy/951d1ee5a7ee7c8f95bb323e881eaf8a to your computer and use it in GitHub Desktop.
Save qnighy/951d1ee5a7ee7c8f95bb323e881eaf8a to your computer and use it in GitHub Desktop.

SATySFi構文メモ (2018/02/23)

SATySFiの字句解析器には主要なモードが4つある:

  • プログラムモード
  • 垂直モード
  • 水平モード
  • 数式モード

またサブモードとして

  • ヘッダモード
  • アクティブモード
  • リテラルモード
  • コメントモード

がある。

プログラムモード

プログラムモードの字句は以下の通り(\s[ \t\n\r]):

  • /\s+/ 空白(無視)
  • /%.*$/ コメント
  • /@\w+:.*$/ ヘッダ指令
  • /\(\)/ ユニット
  • /\(/ .. /\)/ 括弧
  • /\(\|/ .. /\|\)/ レコード
  • /\[/ .. /\]/ リスト
  • /;/ リスト区切り
  • /\{/ .. /\}/ 水平モード
  • /'</ .. />/ 垂直モード
  • /\$\{/ .. /\}/ 数式モード
  • /<\[/ .. /\]>/ パスのための括弧
  • /\.\./ パス曲線オペレータ
  • /--/ パス直線オペレータ
  • /`+/ リテラル (同じ数の /`/ で閉じる)
  • /\\[a-zA-Z][-a-zA-Z0-9]*/ 水平コマンド名
  • /\+[a-zA-Z][-a-zA-Z0-9]*/ 垂直コマンド名
  • /\#/ メンバオペレータ
  • /->/ 矢印
  • /<-/ セルの書き換えオペレータ
  • /\|/ パターンの区切り
  • /_/ ワイルドカード
  • /\./ モジュール名の区切り
  • /:/ 型の指定
  • /,/ 各種区切り
  • /::/ コンス
  • /-/ 減算、負の符号
  • /=/ 定義、比較
  • /\*/ 乗算
  • /[-+*/^&|=<>][-+*/^&|=<>!:~'.?]*/ オペレータ (/-/, /\*/, /=/, /&/, /\|/ は除く)
  • /\?/ 矢印型におけるオプション引数
  • /\?:/ オプション引数
  • /\?\*/ 引数の省略
  • /!/ 参照外し
  • /'[a-z][-a-zA-Z0-9]*/ 型変数
  • /([A-Z][-a-zA-Z0-9]*\.)*[a-z][-a-zA-Z0-9]/ 識別子。ただし以下は予約語
    • not (否定)
    • mod (剰余)
    • if then else (if式)
    • let let-rec let-mutable let-inline let-block let-math (let式)
    • and (同時定義)
    • in (let-in式)
    • fun (ラムダ抽象)
    • true false (真理値定数)
    • before (逐次処理; OCamlの ";")
    • while do (while式)
    • match with when (match式)
    • as (asマッチ)
    • type of (バリアント定義)
    • module struct sig val end direct (モジュール定義)
    • constraint (多相バリアント制約)
    • controls cycle (パス記述)
    • inline-cmd block-cmd math-cmd (組込みのコマンド型)
    • command 水平コマンドの中身
  • /[A-Z][-a-zA-Z0-9]*/ コンストラクタ名
  • /0|[1-9][0-9]*/ 整数
  • /0[xX][0-9a-fA-F]+/ 整数
  • /[0-9]+\.[0-9]*|\.[0-9]+/ 浮動小数点数
  • /(0|[1-9][0-9]*[0-9]+\.[0-9]*|\.[0-9]+)[a-z][-a-zA-Z0-9]*/ 長さ

プログラムモードの文法は以下の通り。

// 開始
main ::= list(headerelem) nxtoplevel
       | list(headerelem) vxblock EOI
       | list(headerelem) nxwhl EOI

// ヘッダ要素
headerelem ::= "@require: .."
             | "@import: .."

// トップレベル
nxtoplevel ::= "let-rec" nxrecdec nxtopsubseq
             | "let" nxnonrecdec nxtopsubseq
             | "let-mutable" "x" "<-" nxlet nxtopsubseq
             | "let-inline" nxhorzdec nxtopsubseq
             | "let-block" nxvertdec nxtopsubseq
             | "let-math" nxmathdec nxtopsubseq
             | "type" nxvariantdec nxtopsubseq
             | "module" "X" nxsigopt "=" "struct" nxstruct nxtopsubseq

// トップレベル後続 ("in" が来たら直前のletはlet-inに降格)
nxtopsubseq ::= nxtoplevel
              | EOI
              | "in" nxlet EOI

// モジュールシグネチャ宣言
nxsigopt ::= ()
           | ":" "sig" list(nxsigelem) "end"

// モジュールシグネチャの要素
nxsigelem ::= "type" list("'x") "x" list(constrnt)
            | "val" "x" ":" txfunc list(constrnt)
            | "val" "\\x" ":" txfunc list(constrnt)
            | "val" "+x" ":" txfunc list(constrnt)
            | "direct" "\\x" ":" txfunc list(constrnt)
            | "direct" "+x" ":" txfunc list(constrnt)

// モジュールシグネチャの制約
constrnt ::= "constraint" "'x" "::" kxtop

// struct後続
nxstruct ::= "end"
           | "let-rec" nxrecdec nxstruct
           | "let" nxnonrecdec nxstruct
           | "let-mutable" "x" "<-" nxstruct
           | "let-inline" nxhorzdec nxstruct
           | "let-block" nxvertdec nxstruct
           | "let-math" nxmathdec nxstruct
           | "type" nxvariantdec nxstruct
           | "module" "X" nxsigopt "=" "struct" nxstruct nxstruct

// 水平コマンド定義 ("x" はコンテキスト変数)
nxhorzdec ::= "x" "\\x" list(arg) "=" nxlet
            | "\\x" argpats "=" nxlet

// 垂直コマンド定義 ("x" はコンテキスト変数)
nxvertdec ::= "x" "+x" list(arg) "=" nxlet
            | "+x" argpats "=" nxlet

// 数式コマンド定義
nxmathdec ::= "\\x" argpats "=" nxlet

// "let" の引数パート
nonrecdecargpart ::= ":" txfunc
                   | ":" txfunc "|" nonempty_list(arg)
                   | "|" nonempty_list(arg)
                   | list(arg)

// "let-rec" の引数パート
recdecargpart ::= ":" txfunc
                | ":" txfunc "|" nonempty_list(arg)
                | nonempty_list(patbot)
                | argpats

// 引数
arg ::= patbot
      | "?:" defedvar

// 変数名
defedvar ::= "x"
           | "(" binop ")"

// "let-rec" 後続
nxrecdecsub ::= "and" nxrecdec
              | ()

// "let-rec" の中身
nxrecdec ::= defedvar recdecargpart "=" nxlet nxrecdecsub
           | defedvar recdecargpart "=" nxlet "|" nxrecdecpar nxrecdecsub

// "let-rec" 直下でのパターンマッチの分岐
nxrecdecpar ::= argpats "=" nxlet "|" nxrecdecpar
              | argpats "=" nxlet

// "let" の中身
nxnondecrec ::= patbot nonrecdecargpart "=" nxlet

// "type" の中身
nxvariantdec ::= list("'x") "x" "=" variants constrnts "and" nxvariantdec
               | list("'x") "x" "=" variants constrnts
               | list("'x") "x" "=" "|" variants constrnts "and" nxvariantdec
               | list("'x") "x" "=" "|" variants constrnts
               | list("'x") "x" "=" txfunc constrnts "and" nxvariantdec
               | list("'x") "x" "=" txfunc constrnts

// モジュールシグネチャの制約の本体
kxtop ::= "(|" txrecord "|)"

// 式
nxlet ::= "match" nxlet "with" option("|") pats
        | nxletsub

// "match"以外の式
nxletsub ::= "let-rec" nxrecdec "in" nxlet
           | "let" nxnonrecdec "in" nxlet
           | "let-mutable" "x" "<-" nxlet "in" nxlet
           | "let-math" nxmathdec "in" nxlet
           | nxwhl

// "match" と "let*" 以外の式
nxwhl ::= "while" nxlet "do" nxwhl
        | nxif

// "match" と "let*" と "while" 以外の式
nxif ::= "if" nxlet "then" nxlet "else" nxlet
       | nxbfr

// "match" と "let*" と "while" と "if" 以外の式
nxbfr ::= nxlambda "before" nxbfr
        | nxlambda

// "match" と "let*" と "while" と "if" と "before" 以外の式
nxlambda ::= "x" "<-" nxlor
           | "fun" argpats "->" nxlor
           | nxlor

// 引数リスト
argpats ::= list(patbot)

// "match" と "let*" と "while" と "if" と "before" と "<-" と "fun" 以外の式
// "||" は "|" で始まる演算子全般 ("|" を除く)
nxlor ::= nxlor "||" nxland
        | nxland

// "match" と (中略) "|" 以外の式
// "&&" は "&" で始まる演算子全般 ("&" を除く)
nxland ::= nxland "&&" nxcomp
         | nxcomp

// "match" と (中略) "&" 以外の式
// "==", "<", ">" は "=", "<", ">" で始まる演算子全般 ("=" を除く)
nxcomp ::= nxconcat "==" nxcomp
         | nxconcat "<" nxcomp
         | nxconcat ">" nxcomp
         | nxcomp

// "match" と (中略) "==", "<", ">" 以外の式
// "^" は "^" で始まる演算子全般
nxconcat ::= nxlplus "^" nxconcat
           | nxlplus "::" nxconcat
           | nxlplus

// "match" と (中略) "^", "::" 以外の式
// "+" は "+" で始まる演算子全般
nxlplus ::= nxlminus "+" nxrplus
          | nxlminus

// "match" と (中略) "^", "::", "+" 以外の式
// "--" は "-" で始まる演算子全般 ("-" を除く)
nxlminus ::= nxlplus "--" nxrtimes
           | nxlplus "-" nxrtimes
           | nxltimes

// "match" と (中略) "^", "::" および単項演算子 ("-", "not", コンストラクタ) 以外の式
// "+" は "+" で始まる演算子全般
nxrplus ::= nxrminus "+" nxrplus
          | nxrminus

// "match" と (中略) "^", "::", "+" および単項演算子 ("-", "not", コンストラクタ) 以外の式
// "--" は "-" で始まる演算子全般 ("-" を除く)
nxrminus ::= nxrplus "--" nxrtimes
           | nxrplus "-" nxrtimes
           | nxrtimes

// "match" と (中略) "^", "::", "+", "-" 以外の式
// "**" は "*" で始まる演算子全般 ("*" を除く)
// "/" は "/" で始まる演算子全般
nxltimes ::= nxun "**" nxrtimes
           | nxun "*" nxrtimes
           | nxun "/" nxrtimes
           | nxun "mod" nxrtimes
           | nxun

// "match" と (中略) "^", "::", "+", "-" および単項演算子 ("-", "not", コンストラクタ) 以外の式
// "**" は "*" で始まる演算子全般 ("*" を除く)
// "/" は "/" で始まる演算子全般
nxltimes ::= nxapp "**" nxrtimes
           | nxapp "*" nxrtimes
           | nxapp "/" nxrtimes
           | nxapp "mod" nxrtimes
           | nxapp

// "match" と (中略) "^", "::", "+", "-", "*", "/", "mod" 以外の式
nxun ::= "-" nxapp
       | "not" nxapp
       | "X" nxbot
       | "X"
       | nxapp

// "match" と (中略) "^", "::", "+", "-", "*", "/", "mod" および単項演算子 ("-", "not", コンストラクタ) 以外の式
nxapp ::= nxapp nxbot
        | nxapp "X"
        | "!" nxbot
        | "command" hcmd
        | nxapp "?:" nxbot
        | nxapp "?*"
        | nxbot

// "match" と (中略) 関数適用、 "!", "command" 以外の式
nxbot ::= nxbot "#" "x"
        | "x"
        | "X.x"
        | "42"
        | "42.0"
        | "42.0cm"
        | "true"
        | "false"
        | "()"
        | "(" nxlet ")"
        | "(" nxlet "," tuple ")"
        | "'<" vxblock ">"
        | "`str`"
        | "[" "]"
        | "[" nxlist "]"
        | "(" binop ")"
        | "(|" "|)"
        | "(|" nxrecord "|)"
        | "<[" path "]>"
        | "${" mathblock "}"

// パス記述
path ::= nxbot pathsub
pathsub ::= pathcomp pathsub
          | option(pathcompcycle)
pathcomp ::= "--" nxbot
           | ".." "controls" nxbot "and" nxbot ".." nxbot
pathcompcycle ::= "--" "cycle"
                | ".." "controls" nxbot "and" nxbot ".." "cycle"

// レコードコンストラクタの本体
nxrecord ::= "x" "=" nxlet
           | "x" "=" nxlet ";"
           | "x" "=" nxlet ";" nxrecord

// リストコンストラクタの本体
nxlist ::= nxlet ";" nxlist
         | nxlet ";"
         | nxlet

// バリアント定義の本体
variants ::= "X" "of" txfunc "|" variants
           | "X" "of" txfunc
           | "X" "|" variants
           | "X"

// 型
txfunc ::= txprod "->" txfunc
         | txprod "?" "->" txfunc
         | txprod

// "->" 以外の型
txprod ::= txapppre "*" txprodsub
         | txapppre
txprodsub ::= txapppre "*" txprodsub
            | txapppre

// "->", "*" 以外の型
txapppre ::= txapp
           | "[" txlist "]" "inline-cmd"
           | "[" txlist "]" "block-cmd"
           | "[" txlist "]" "math-cmd"
           | "(" txfunc ")"
           | "(|" txrecord "|)"
           | "'x"

// "->", "*", "*-cmd", "(| |)", "'x" 以外の型
txapp ::= txbot txapp
        | "(" txfunc ")" txapp
        | "'x" txapp
        | txbot

// "->", "*", "*-cmd", "(| |)", "'x", 型関数適用 以外の型
txbot ::= "x"
        | "X" "." "x"

// 型のリスト
txlist ::= txfunc ";" txlist
         | txfunc
         | txapppre "?" ";" txlist
         | txapppre "?"
         | ()

// レコード型の本体
txrecord ::= "x" ":" txfunc ";" txrecord
           | "x" ":" txfunc ";"
           | "x" ":" txfunc

// タプル式の後続
tuple ::= nxlet
        | nxlet "," tuple

// パターンマッチの腕
pats ::= patas "->" nxletsub
       | patas "->" nxletsub "|" pats
       | patas "when" nxletsub "->" nxletsub
       | patas "when" nxletsub "->" nxletsub "|" pats

// パターン
patas ::= pattr "as" "x"
        | pattr

// "as" 以外のパターン
pattr ::= patbot "::" pattr
        | "X" patbot
        | "X"
        | patbot

// "as", "::", コンストラクタ 以外のパターン
patbot ::= "42"
         | "true"
         | "false"
         | "()"
         | "_"
         | defedvar
         | "(" patas ")"
         | "(" patas "," pattuple ")"
         | "[" "]"
         | "`str`"

// タプルパターンの後続
pattuple ::= patas
           | patas "," pattuple

// 二項演算子名
binop ::= "**"
        | "/"
        | "^"
        | "=="
        | ">"
        | "<"
        | "&&"
        | "||"
        | "+"
        | "--"
        | "-"
        | "mod"
        | "before"
        | "not"

アクティブモード

アクティブモードは垂直モード・水平モードでコマンドを読んだときに一部のプログラムモードの字句を受理するモードである。アクティブモードの字句は以下の通り:

  • /\s+/ 空白(無視)
  • /%.*$/ コメント
  • /\(/ .. /\)/ プログラムモード
  • /\(\|/ .. /\|\)/ レコード (プログラムモード)
  • /\[/ .. /\]/ リスト (プログラムモード)
  • /\{/ .. /\}/ 水平モード (アクティブモードを終了し垂直/水平モードに復帰)
  • /</ .. />/ 垂直モード (アクティブモードを終了し垂直/水平モードに復帰)
  • /;/ 引数の強制的な終わり (アクティブモードを終了し垂直/水平モードに復帰)

最後の3種類の字句のいずれかを読んだ時点でアクティブモードを終了し垂直/水平モードに復帰する。

垂直モード

垂直モードの字句は以下の通り:

  • /\s+/ 空白(無視)
  • /%.*$/ コメント
  • /#([A-Z][-a-zA-Z0-9]*\.)*[A-Za-z][-a-zA-Z0-9]*/ 変数名
  • /+([A-Z][-a-zA-Z0-9]*\.)*[A-Za-z][-a-zA-Z0-9]*/ 垂直コマンド (アクティブモードに遷移)
  • /</ .. />/ 括弧
  • /\{/ .. /\}/ 水平モード

垂直モードの文法は以下の通り。

// 垂直モード
vxblock ::= list(vxbot)

// 垂直モード命令
vxbot ::= ("+X.x" | "+x") nargs sargs
        | ("#X.x" | "#x") ";"

// 引数部1
nargs ::= list(narg)
narg ::= "(" nxlet ")"
         | "(" ")"
         | "(|" "|)"
         | "[" "]"
         | "?:" "(" nxlet ")"
         | "?:" "(" ")"
         | "?:" "(" ")"
         | "?:" "(|" "|)"
         | "?:" "[" "]"
         | "?*"

// 引数部2
sargs ::= ";"
        | nonempty_list(sarg)
sarg ::= "<" vxblock ">"
       | "{" sxsep "}"

水平モード

水平モードの字句は以下の通り(空白は必ずしも無視されない):

  • /\s*\{\s*/ .. /\}/ 括弧
  • /\s*<\s*/ .. />/ 垂直モード
  • /\s*\|/ リスト区切り
  • /\s*\*+/ アイテム用バレット
  • /%.*$\s*/ コメント
  • /#([A-Z][-a-zA-Z0-9]*\.)*[A-Za-z][-a-zA-Z0-9]*/ 変数名 (アクティブモードに遷移)
  • /\\([A-Z][-a-zA-Z0-9]*\.)*[A-Za-z][-a-zA-Z0-9]*/ 水平コマンド (アクティブモードに遷移)
  • /\\[ -@[-`{-~]/ 記号のエスケープ
  • /`+/ リテラル (同じ数の /`/ で閉じる)
  • /$\{/ .. /\}/ 数式モード
  • /\s/ スペース・改行
  • /[^ \t\n\r@`\\{}%|*$#;]+/ 平文

水平モードの文法は以下の通り。

// 水平モード (リストまたは単一ブロックまたはアイテムリスト)
sxsep ::= "|" sxlist
        | sxblock
        | nonempty_list(sxitem)

// リストの後続
sxlist ::= sxblock "|" sxlist
         | ()

// アイテム ("*" は "*" の1個以上の並び)
sxitem ::= "*" sxblock

// 水平ブロック (ihtextとihcmdの並びでihtextは連続しない)
sxblock ::= ih
ih ::= ihtext
     | ihtext ihcmd ih
     | ihcmd ih
     | ()

// 水平ブロック中のコマンド呼び出し
ihcmd ::= ("\\X.x" | "\\x") nargs sargs
        | "${" mathblock "}"
        | ("#X.x" | "#x") ";"

// 水平ブロック中の平文 ("c" は通常の文字、 "\\@" は記号のエスケープ)
ihtext ::= nonempty_list(ihchar)
ihchar ::= "c"
         | "\\@"
         | " " | "\t" | "\r" | "\n"

数式モード

数式モードの字句は以下の通り:

  • /\s+/ 空白(無視)
  • /%.*$/ コメント
  • /!\{/ .. /\}/ 水平モード
  • /!</ .. />/ 垂直モード
  • /!\(/ .. /\)/ プログラムモード
  • /!\[/ .. /\]/ リスト(プログラムモード)
  • /\{/ .. /\}/ 括弧
  • /\^/ 上付き文字命令
  • /_/ 下付き文字命令
  • /[-+*/:=<>~'.,?`]+/ 数学記号
  • /[a-zA-Z0-9]/ 文字
  • /\#([A-Z][-a-zA-Z0-9]*\.)*[a-zA-Z][-a-zA-Z0-9]*/ 変数
  • /\\([A-Z][-a-zA-Z0-9]*\.)*[a-zA-Z][-a-zA-Z0-9]*/ 数式コマンド
  • /\\[ -@[-`{-~]/ 記号のエスケープ

数式モードの文法は以下の通り。

// 数式モード
mathblock ::= mathlist
mathlist ::= list(mathsuper)

// 連接以外の数式
mathsuper ::= mathsub "^" mathgroup
            | mathsub

// 連接、"^" 以外の数式
mathsub ::= mathbot "_" mathgroup
          | mathbot

// 下付き・上付き部分
mathgroup ::= "{" mathlist "}"
            | mathbot

// 連接、"^", "_" 以外の数式 ("a" は小文字、 "A" は大文字、 "0" は数字、 "\\@" は記号のエスケープ、 "+" は数学記号全般)
mathbot ::= "a" | "A" | "0"
          | "\\@"
          | "+"
          | ("\\X.x" | "\\x") list(matharg)
          | ("#X.x" | "#x")

// 数式コマンドの引数
matharg ::= "{" mathblock "}"
          | "!{" sxsep "}"
          | "!<" vxblock "}"
          | math_narg

// narg と同じだが数式モードではこうなる
math_narg ::= "!(" nxlet ")"
         | "!(" ")"
         | "!(|" "|)"
         | "![" "]"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment