2020年3月20日投稿 / 2020年3月26日更新 / 投稿者 : うつりきまぐれ / タグ : 投稿プログラム ツール ライブラリ うつりきまぐれ 構文解析 パーサ パーサコンビネータ オブジェクト JSON
プチコン4上で文法を定義して構文解析するためのライブラリです。構文解析とはプログラムを先頭から読んで単語ごとに切り分け、それらを項や式、文、ブロックといったまとまりごとに構造的なデータ (構文木) に整理します。( 厳密には最初の単語ごとの分解処理は「字句解析」という構文解析の前の別のステップです。) 構文解析については説明が難しいのでまあググってもらえると助かります。
このライブラリが追加で使用するオブジェクトライブラリと JSON 解析・生成ライブラリ、および actorbug さんが製作した 正規表現ライブラリ の移植版がひとつのファイルになっています。
このライブラリでは文法を定義するのにパーサコンビネータというものを使います。詳しい説明はググれカス このライブラリを使おうと思っている皆さんは知っているだろうという前提で進めます。
サンプルプログラムとして四則演算と括弧が利用できる計算機を用意しています。また、ライブラリ内にもパーサコンビネータを実際に利用した JSON 解析ライブラリを内蔵しています ( 逆に生成もできます ) 。
構文解析ライブラリおよびオブジェクトライブラリの本体は PXII.LIB という名前です。以下のようにしてライブラリを読み込み、実行します。
- EXEC ”PXII.LIB”,1
別のプロジェクトから参照するときは EXEC がエラーになるので、代わりに LOAD でスロットに読み込んでから EXEC で実行してください。
- LOAD ”PXIILIB−0.3.0/PXII.LIB”,1
- EXEC 1
ライブラリの初期化のための DEF や GOSUB の呼び出しは特に必要ありません。
構文解析を行うより先に、次のように文法を定義してください。これは整数の四則演算の例です。符号はありません。……なお、実際に計算を行うには ACTP を使ってアクションというコールバック DEF も指定しなければならないため、これよりも少々複雑になります。
- PXDEFPC @_SPACE,REGEXP(”\s*”)
- PXDEFPC @EXPR,LISTP(@TERM,CHARP(”+−”))
- PXDEFPC @TERM,LISTP(@TERM,CHARP(”*/”))
- PXDEFPC @FACT,ORP(@REAL,SEQP(”(”,@EXPR,”)”))
- PXDEFPC @REAL,REGEXP(”[0−9]+”)
用意されているパーサを組み合わせて、新たなパーサを作成します。パーサは通常の変数に代入して利用できますが、これでは上記のような再帰文法が定義できません。( Undefined variable となる) そのため、別の手段として PXDEFPC を用いて @ からはじまる名前をつけます。この名前は上記の @EXPR のように再帰できます。( ただし自身の名前が含まれる再定義は現在のところできません ) またパーサコンビネータの実体はオブジェクトですが、代わりに名前を指定できるようになります。ただし @_SPACE という名前は、スキップパーサを示すために予約されており、ここに指定したものは PXPARSE が呼び出されるたびにパースされ無視されます。
また、@ から始まらない文字列を直接指定した場合は、自動的に TEXTP に変換されます。つまり、@ から始まらない文字列を読み取る場合は TEXTP を省略できます。
用意されているすべてのパーサコンビネータの詳細は パーサコンビネータのリファレンス を参照してください。
実際に構文解析を行うには次のようにします。
- DIM SOURCE=”11+(9−5)*7”
- DIM RES=PXPARSE(SOURCE,0,@EXPR)
第1引数に入力、第2引数に開始位置、第3引数にパーサコンビネータを指定します。結果はオブジェクトでまとめて返るため、情報を取得するには OBJGET などでキーから値を得る必要があります。オブジェクトの使い方については オブジェクトを扱う を参照してください。
次のようにして、パースが成功したかどうかと次回の開始位置 ( 終端位置 + 1 ) および読み取った文字列を取得できます。パースが失敗した場合は、その時点での位置になります。
- DIM SUCCESS=OBJGET(RES,”SUCCESS”)
- DIM EPOS=OBJGET(RES,”POS”)
- DIM BUFF=OBJGET(RES,”BUFF”)
また SEQP や REPP など一部のパーサコンビネータは別のパーサコンビネータを引数にとるため、これらの結果を参照できるように、”SUCCESS” と ”POS” および ”BUFF” のほかにも追加の情報が入っています。たとえば SEQP では、”SEQ0” に最初に指定したパーサコンビネータの結果が入ります。これもまたひとつの結果オブジェクトなので ”POS” などのキーを持っています。
PXDEFPC で定義した名前は再定義できるので、このライブラリを用いて言語処理系などを作ると、外部からパーサを変更することができます。たいていは後に出る例のように、そのパーサ自身を含むように拡張することになります。
しかし、その場合には問題があります。たとえば @FACT という名前のパーサがあったとします。先ほどの計算機で変数も利用できるように、次のように @FACT を使って @FACT を再定義すると、パース時に Stack overflow エラーになることがあります。( 以下の例で @VAR は既に定義されているものとします )
- PXDEFPC @FACT,ORP(@FACT,@VAR)
これを回避するには、再定義する対象のパーサを EXTP で包みます。
- PXDEFPC @FACT,ORP(EXTP(@FACT),@VAR)
バージョン v0.3.1 以上で利用できます。
この構文解析ライブラリでは、パーサコンビネータを保存したりパースの結果を返すのにオブジェクトが使われます。このオブジェクトは JavaScript のオブジェクトと同じようなものです。オブジェクトの実体は文字列配列ですが、値にキーという名前 ( 文字列の添え字のようなものです ) を付けて、あとからその名前で取得できるようになります。
オブジェクトには次の種類の値を格納することができます。
オブジェクトライブラリを使った例です。
- ’ オブジェクトを生成
- VAR A=OBJECT()
- ’ 数値や文字列を入れる
- OBJSET A,”SCORE”,80
- OBJSET B,”COMMENT”,”おめでとう”
- ’ 内容を表示
- ? ”あなたの点数は”;OBJGET(A,”SCORE”)
- ’ 別のオブジェクトを生成
- VAR B=OBJECT()
- ’ 同じように数値や文字列を入れる
- OBJSET B,”NAME”,”山田”
- OBJSET B,”AGE”,22
- ’ オブジェクトに別のオブジェクトを格納
- OBJSET B,”RESULT”,A
- ’ ピリオドで階層を指定
- ? OBJGET(B,”RESULT.COMMENT”);”!”
- ’ こうすることもできる (こちらの方は遅い)
- ? OBJGET(OBJGET(B,”RESULT”),”COMMENT”);”!”
- ’ OBJSET にもピリオドを使える
- OBJSET B,”RESULT.SCORE”,0
オブジェクトのキーを CHR$(&HFFFF) から始めることはできません。CHR$(&HFFFF) というキーはオブジェクトの終端を表すのに使用されています。
あらかじめ文字列配列内でのインデックスが予測できる場合は OBJGETH などを利用し、ヒントとしてインデックスを与えて高速化する方法もあります。
パーサコンビネータを定義したり実際に構文解析を行うための DEF です。
- DEF PXDEFPC PCDEF,PC
新しいパーサコンビネータを名前を付けて定義します。変数に格納することとの違いは、定義前に利用できるため再帰的な文法が定義できることです。
スキップパーサを指定するには @_SPACE という名前で定義します。スキップパーサはかならず成功する必要があります。
- DEF PXPARSE SOURCE,SPOS,PC OUT RES
構文解析を実行します。結果はオブジェクトで返ってきます。
- DEF PXPARSE PC OUT PCOBJ
PXDEFPC で定義したパーサの名前から、その実体を取得します。未定義の場合はエラーとなります。
PX.LIB に用意されているパーサコンビネータです。
- DEF BASEP()
何も読み取らないパーサを作成します。パースは常に成功します。
- DEF ACTP(SUBPC,ACALL)
別のあるパーサを引数にとり、その読み取りが成功したときにアクションというコールバック DEF を呼び出すパーサを返します。アクションには引数として結果オブジェクトが渡されます。このオブジェクトは改変することができるので、”BUFF” ( 読み取った文字列 ) を加工したり、追加の情報を設定することもできます。実際に同梱されている計算機のサンプル ( 簡易版のプログラムが こちら にあります ) では ”VALUE” という名前で計算結果を格納しています。
COMMON でない DEF を指定する際は 0: のように、スロットプレフィックスを加える必要があります。
- DEF EXTP(SUBPC)
別のあるパーサを引数にとり、そのパーサを展開したものを返します。その展開とは、名前で指定したパーサを取得することです。すでにパーサの実体である場合はそのまま返されます。やっていることは PXGETPCOBJ と完全に同じです。
これが有用なのはパーサを拡張するときです。こちら をご覧ください。
- DEF TEXTP(TEXT)
固定の文字列を読み取るパーサを作成します。文字列が @ から始まる場合を除いて、TEXTP は省略できます。つまり、パーサコンビネータに文字列を直接指定することができ、自動的に TEXTP に変換されます。
- DEF CHARP([CHARS])
現在位置の1文字が指定された文字列に含まれる場合、その1文字を読み取るパーサを作成します。空文字列にしたり、引数そのものを省略した場合は、どんな場合でも 1 文字読み取ります ( ただし既に EOF である場合は失敗します ) 。
- DEF REGEXP(REGEX[,FLAGS])
正規表現にマッチする文字列を読み取るパーサを作成します。第1引数には文字列で直接指定します。REGEX で生成した正規表現オブジェクトを指定するわけではありません。またオプションで大文字小文字を区別しないといったフラグを指定できます。
actorbug さんの 正規表現ライブラリ を移植して使用しています。
こちら よりそのまま引用しています。
メタ文字 | 説明 |
---|---|
\ | 直後のメタ文字を無効化して通常文字として扱う |
\n | LF、CHR$(10) |
\r | CR、CHR$(13) |
\t | Tab、CHR$(9) |
\xFF | 16進2桁で文字コード指定 |
\uFFFF | 16進4桁で文字コード指定 |
[] | 文字クラス、括弧内の文字のいずれかにマッチ、-で範囲指定可能 |
[^] | 否定文字クラス、括弧内の文字以外にマッチ、-で範囲指定可能 |
. | 任意の1文字(改行を除く)にマッチ、単一行モードなら改行もマッチ |
\d | 数字、[0-9]と同じ |
\D | 非数字、[^0-9]と同じ |
\w | 単語構成文字、[a-zA-Z0-9_]と同じ |
\W | 非単語文字、[^a-zA-Z0-9_]と同じ |
\s | 空白文字、[ \n\r\t]と同じ |
\S | 非空白文字、[^ \n\r\t]と同じ |
^ | 文字列の先頭、複数行モードなら改行の次にもマッチ |
$ | 文字列の末尾 or 最後が改行ならその前、複数行モードなら改行の前にもマッチ |
\A | 文字列の先頭 |
\Z | 文字列の末尾 or 最後が改行ならその前 |
\z | 文字列の末尾 |
\b | 単語境界 |
\B | 単語境界以外 |
\1~\9 | 後方参照 |
() | グループ化 & キャプチャ |
(?:) | グループ化(キャプチャなし) |
(?=) | 肯定の先読み |
(?!) | 否定の先読み |
(?<=) | 肯定の戻り読み(通常文字・文字クラス・一部アンカーのみ使用可) |
(?<!) | 否定の戻り読み(通常文字・文字クラス・一部アンカーのみ使用可) |
(?>) | アトミックなグループ |
(?修飾子) | モード修飾子(?i)(?-i)など |
(?修飾子:) | モード修飾子の範囲(?i:...)など |
| | 選択 |
* | 直前の式の0回以上の繰り返し、{0,}と同じ |
+ | 直前の式の1回以上の繰り返し、{1,}と同じ |
? | 直前の式が0回か1回現れる、{0,1}と同じ |
{n} | 直前の式のn回の繰り返し |
{m,} | 直前の式のm回以上の繰り返し |
{m,n} | 直前の式のm回以上n回以下の繰り返し |
*? | 直前の式の0回以上の繰り返し(最短マッチ) |
+? | 直前の式の1回以上の繰り返し(最短マッチ) |
?? | 直前の式が0回か1回現れる(最短マッチ) |
{m,}? | 直前の式のm回以上の繰り返し(最短マッチ) |
{m,n}? | 直前の式のm回以上n回以下の繰り返し(最短マッチ) |
*+ | 直前の式の0回以上の繰り返し(強欲) |
++ | 直前の式の1回以上の繰り返し(強欲) |
?+ | 直前の式が0回か1回現れる(強欲) |
{m,}+ | 直前の式のm回以上の繰り返し(強欲) |
{m,n}+ | 直前の式のm回以上n回以下の繰り返し(強欲) |
こちら よりそのまま引用しています。
オプションは数値で指定してください。複数指定する場合は足します。
オプション | 値 | 説明 |
---|---|---|
RXOPT_IC | 1 | 大文字小文字を区別しない |
RXOPT_SL | 2 | 単一行モード("."が改行にもマッチする) |
RXOPT_ML | 4 | 複数行モード("^","$"が改行前後にもマッチする) |
- DEF OPTP(SUBPC)
別のあるパーサを引数にとり、読み取りに失敗しても位置を戻して成功と扱うパーサを作成します。
失敗することがないので省略可能な部分を定義するのに利用します。
- DEF AHEADP(SUBPC)
別のあるパーサを引数にとり、読み取ったあとに位置を戻すパーサを作成します。読み取れなかった場合は失敗します。
- DEF NOTP(SUBPC)
別のあるパーサを引数にとり、読み取れた場合は逆に失敗し、読み取れなかった場合にその位置で成功するパーサを作成します。
特定の識別子を読み取り、直後にアルファベットや数字などの、識別子を構成する文字が続いていないかどうかを確認できます。
- DEF ORP(...)
別の複数のパーサを引数にとり、それらを順番にパースしていき、どれかが成功すればその結果をこのパーサの結果とするパーサを返します。
最初に成功したパーサの結果オブジェクトが、このパーサの結果オブジェクトとなります。どれかが成功した後は、それ以降のパーサは実行されません。
- DEF SEQP(...)
別の複数のパーサを引数にとり、それらを順番にパースしていき、最後まで成功した場合をこのパーサが成功したと扱うパーサを返します。
それぞれのパーサの結果オブジェクトが、このパーサの結果オブジェクトに格納されます。それらすべてを後から参照することが可能となります。
- DEF REPP(SUBPC,MINC,MAXC)
別のあるパーサを引数にとり、指定した回数の範囲、繰り返されるパーサを返します。ただし、正規表現が使える場合は、REGEXP の方が高速です。
それぞれの回の結果オブジェクトが、このパーサの結果オブジェクトに格納されます。それらすべてを後から参照することが可能となります。
- DEF LISTP(SUBPC,DELPC)
項目用のパーサとデリミタ ( 区切り ) 用のパーサを引数にとり、デリミタで区切られたリストを読み取るパーサを返します。
それぞれの項目の結果オブジェクトが、このパーサの結果オブジェクトに格納されます。
階層化可能なオブジェクトを実現するための DEF 。JSON を扱うこともできます。
- DEF OBJECT OUT OBJ
新しい空のオブジェクトを生成します。やっていることは ARRAY$(0) と同じです。
- DEF OBJGET OBJ,PATH OUT VALUE
オブジェクトから、キーを指定して値を取得します。
値は数値や文字列のようにプリミティブな型である場合も、オブジェクトである場合もあります。取得したオブジェクトからさらに値を取得したい場合、OBJGET で取得したオブジェクトに対してさらに OBJGET を使うより、ピリオドに続けて一気に指定した方が高速です。
- ’ 上よりも下のほうが速い
- OBJGET(OBJGET(OBJ,”FOO”),”BAR”)
- OBJGET(OBJ,”FOO.BAR”)
なおキーが存在しない場合はデフォルト値が返ってきます。TYPEOF で判定することができますが、存在を確認するだけならば OBJHAS という関数もあります。
- DEF OBJSET OBJ,PATH,VALUE
オブジェクトに、キーを指定して値を設定します。OBJGET と同じくピリオドを使って階層を指定できます。キーが存在しなければ追加され、存在すれば上書きされます。
- DEF OBJHAS OBJ,PATH OUT HAS
オブジェクトに、指定したキーがあるかどうかを確認します。存在すれば #TRUE しなければ #FALSE が返ります。
オブジェクトにあるキーの一覧を取得するには OBJPATHS を使います。
- DEF OBJDEL OBJ,PATH
オブジェクトから、キーを削除します。そのキーの値がオブジェクトだった場合はオブジェクトごと削除されます。キーが存在しない場合は何も起こりません。
- DEF OBJPATHS OBJ,SUB OUT PATHS
オブジェクトのキーの一覧を文字列配列で取得します。第2引数に #FALSE を指定したときは直下のキーのみを取得しますが、#TRUE を指定したときはキーの値がオブジェクトだった場合に再帰的にそのオブジェクトのキーの一覧も加えます。このキーの一覧はソートされています。
- DEF OBJGETH OBJ,INDEX,PATH OUT VALUE
オブジェクトから、キーを指定して値を取得します。
OBJGET と違うのは、インデックスという追加の引数を指定するという点です。インデックスとはオブジェクトの実体である文字列配列における添え字のことです。オブジェクトに入るキーが初めから決まっている、あるいはそうでなくてもキーのあるインデックスが固定値または計算で予測できる場合はヒントとしてそのインデックスを渡すことで、インデックスで指定した位置がまさにそのキーであった場合にはキーを検索せずそのままその位置を参照するため、高速になります。インデックスが異なった場合、つまり指定したインデックスにキーがなかった場合は OBJGET と同様にキーを検索します。
OBJGETH では数値と文字列のみを取得できます。子オブジェクトには対応していません。
- DEF OBJSETH OBJ,INDEX,PATH,VALUE
オブジェクトに、キーを指定して値を設定します。OBJGET と同じくピリオドを使って階層を指定できます。キーが存在しなければ追加され、存在すれば上書きされます。
OBJSET と違う点は OBJGETH にある説明と同じく、キーのある可能性が高い位置を同時に指定して、その位置が指定したキーだった場合にその位置を直接参照することです。
OBJSETH では数値と文字列のみを設定できます。子オブジェクトには対応していません。
- DEF ISOBJECT VALUE OUT ISOBJECT
渡された値がオブジェクトかどうかを調べます。やっていることは TYPEOF(VALUE)==#T_STRARRAY と同じです。
- DEF OBJFIND OBJ,PATH,SINDEX,EINDEX OUT INDEX
オブジェクトのキーのあるべき位置を取得します。キーがない場合はキーを追加 ( INSERT ) する場合の位置となります。キーの値がオブジェクトだった場合は先頭の位置を返します ( そのオブジェクトの先頭のキーはその次の位置にあります )。終端位置は同じキーで OBJFINDEND を使用します。
通常使用ではあまり推奨していません。
- DEF OBJFINDEND OBJ,PATH,SINDEX,EINDEX OUT INDEX
キーの値がオブジェクトの場合、終端位置を取得するのに使われます。OBJFIND(OBJ,PATH+”.”+CHR$(&HFFFF),SINDEX,EINDEX) と同じです。
通常使用ではあまり推奨していません。
- DEF JSON2OBJ JSON OUT VALUE
JSON をもとに新しいオブジェクトを生成します。SmileBASIC の文字列リテラルに直接 JSON を記述することも踏まえて文字列リテラルを ” ではなく ' で括ることもできるように拡張されています。エスケープシーケンスも有効です。
- DEF OBJ2JSON VALUE OUT JSON
オブジェクトまたは単独の数値、文字列から JSON を生成します。生成される JSON にはスペースやインデントは含まれません。
テキトーに作ったものです
- OPTION STRICT
- ACLS
- LOAD ”PXIILIB−0.3.0/PXII.LIB”,1
- EXEC 1
- INITPC
- LOOP
- LINPUT ”?”;EXPR
- PRINT ”=”;EVAL(EXPR)
- ENDLOOP
- DEF INITPC
- PXDEFPC @_SPACE,REGEXP(”[\x20]*”)
- PXDEFPC @EXPR,ACTP(LISTP(@TERM,CHARP(”+−”)),”0:ONCALCB”)
- PXDEFPC @TERM,ACTP(LISTP(@FACT,CHARP(”*/%”)),”0:ONCALCB”)
- PXDEFPC @FACT,ACTP(SEQP(REGEXP(”[−]*”),ORP(@REAL,SEQP(”(”,@EXPR,”)”))),”0:ONFACT”)
- PXDEFPC @REAL,REGEXP(”([0−9]+(\.[0−9]*)?|[0−9]*\.[0−9]+)”)
- END
- DEF EVAL(EXPR)
- DIM RES=PXPARSE(EXPR,0,@EXPR)
- IF OBJGET(RES,”SUCCESS”) THEN
- RETURN OBJGET(RES,”VALUE”)
- ELSE
- RETURN POW(2,1024)*0 ’nan
- ENDIF
- END
- DEF ONFACT RES
- DIM SIGN=1−(LEN(OBJGET(RES,”SEQ0.BUFF”)) MOD 2)*2
- DIM BUFF=OBJGET(RES,”SEQ1.BUFF”)
- IF LEFT$(BUFF,1)==”(” THEN
- OBJSET RES,”VALUE”,SIGN*OBJGET(RES,”SEQ1.SEQ1.VALUE”)
- ELSE
- OBJSET RES,”VALUE”,SIGN*VAL(BUFF)
- ENDIF
- END
- DEF ONCALCB RES
- DIM I,O,A,B
- A=OBJGET(RES,”LISTSUB0.VALUE”)
- FOR I=1 TO OBJGET(RES,”LIST#”)−1
- O=OBJGET(RES,”LISTDEL”+STR$(I−1)+”.BUFF”)
- B=OBJGET(RES,”LISTSUB”+STR$(I)+”.VALUE”)
- A=CALCB(O,A,B)
- NEXT
- OBJSET RES,”VALUE”,A
- END
- DEF CALCB(O,A,B)
- CASE O
- WHEN ”+”:RETURN A+B
- WHEN ”−”:RETURN A−B
- WHEN ”*”:RETURN A*B
- WHEN ”/”:RETURN A/B
- WHEN ”%”:RETURN A MOD B
- ENDCASE
- END
プチコン4用の公開キーです。
PXIILIB に関する感想や意見・要望ならなんでもどうぞ。バグ報告もこちらでお願いします。
表示モード : [ スマホ・3DS対応表示 | クラシック表示 ]
PukiWiki 1.4.7 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL. Based on "PukiWiki" 1.3 by yu-ji
ページの処理時間 : 0.276 秒 | このページの最終更新 : 2022/09/20 (火) 12:23:39 (565d) | ログイン
Copyright(C) 2011-2019 プチコンまとめWiki