「ほっ」と。キャンペーン

カテゴリ:JavaScript( 127 )

SVG の画像をセンタリングする。

SVGで図表を作成しても、HTML文書の中でレイアウトできなければ使い勝手が悪い。しかし、SVG 要素 を DIV要素
の子要素にして、DIV 要素のスタイルを text-align: center にすると画像のセンタリングができるようだ。

<div style="text-align: center">
<svg widhth="200" height="200">
<circle cx="100" cy="100" r="80" fill="red">
</svg>
</div>

SVG 要素の中に図表を作成して DIV 要素でくるんでやれば、HTML文書内でのレイアウトがしやすくなる。

[PR]
by tnomura9 | 2016-07-07 15:48 | JavaScript | Comments(0)

SVG入門

新しく作り始めたホームページに SVG で図表を作成しようとして挫折した。そこで、Googleで『SVG入門』で検索して次のサイトを見つけた。

SVG | MSDN

ここの記事を参考にちょっとしたダイアグラムを作成するところまでやってみようと思う。練習には以前に紹介した HTML edit E を使うことにした。

最初に、HTML 文書の中に要素として SVG を埋め込むのは意外と簡単だった。

<svg wdith="320" height="320">
<circle cx="100" cy="100" r="80" fill="yellow" stroke="red">
</svg>

ダイアグラムの部品としては、あとは文字列と矩形と多角形と直線と折れ線があれば十分だが、疲れたので今日はこれまで。

[PR]
by tnomura9 | 2016-07-04 18:36 | JavaScript | Comments(0)

「正規表現」は誤訳?

正規表現は regular expression の訳だ。Wikipedia には、
正規表現とは文字列の集合を一つの文字で表現する方法のひとつである。... まれに正規式と表現されることもある。
とある。たとえば、/a*b/ という正規表現は b, ab, aab, aaab, ... という0回以上の a の繰り返しのあとに b がつくすべての文字列を表している。/a*b/ は特定の文字列ではなく、文字列の集合を表している。/a/ の場合もこれがあらわすのは {a} という文字列1個だけの集合なのだ。/ab/ のように ab と文字を並べている場合もこれは集合 {a} の要素と集合 {b} の要素のすべての連結からなる集合 {ab} を表している。この正規表現に対応する文字列の集合が正規言語だ。

これはまた、/ab/ の ab は {a} . {b} という正規言語どうしが連接演算 . で結合されたものと見ることができる。つまり、正規表現 /ab/ は正規言語 /a/ と正規言語 /b/ の連接演算の式であるとみることができる。この式 /ab/ があらわすものもやはり正規言語 {ab} だから、正規言語の集合は連接演算について閉じている。

正規表現に現れる正規言語の演算はこの連接演算以外に、選択演算 | と クリーネ閉包を作る(クリーネ)スター演算子 * がある。クリーネ閉包とは、ある演算の繰り返しが生成する文字列の集合である。例えば文字列の集合 {"ab", "c"} のクリーネ閉包は次のようになる。

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

これらの連接、選択、クリーネ閉包の演算はすべて正規言語の集合について閉じているので、これは正規言語の集合の代数を構成する。

いずれにせよ、/[+-][0-9][0-9]*/ という正規表現は、こういう書き方をしてよければ、{+, -} . {0, 1, 2, .., 9} . {0, 1, 2, .., 9}* という正規言語の演算の「式」になっている。この意味では regular expression の訳としては「正規表現」よりもまれにしか使われない「正規式」のほうが適切であることが分かる。expression は「表現」ではなくて「式」の意味で使われている。

regular expression の「正規表現」という訳は、「正規式」という訳に比べて正規表現の意味を的確に表していないような気がする。しかし、文字列のパターンを表すという意味での「正規式」の使い方が普及したので「正規表現」の訳語のほうが圧倒的に使われているのだろう。

[PR]
by tnomura9 | 2016-03-01 18:15 | JavaScript | Comments(0)

生成文法と分析文法

誰でも一度は自分で考えた小さなプログラム言語を作ってみたいと考えるものだ。しかし、パーサをプログラムするソースコードを読んでまず挫折してしまう。BNF で記述された文法がどうやってパーサ(構文解析器)になるのかが理解できないからだ。再帰下降型の構文解析のプログラムを見ても、BNFと似ているような気はするが、どうしてその記述になるのか全く分からない。

それは、BNF で記述される文法と、構文解析プログラムで活躍する文法とは方向性が全く異なっているのに気が付いていないからだ。BNF をはじめとする生成文法は、文法にマッチする文字列を生成するための文法である。たとえば、次の正規文法がどのような文字列を生成するかを考えてみる。

1. S -> aS
2. S -> b

この文法では非終端記号 S は矢印の右の記号で置き換えることができることを示している。ある正規言語は非終端記号の S であらわすことができるが、この S は上の文法の矢印の右の記号で置き換えることができる。上の文法の S にルール 1 を適用すると S を aS に置き換えることができる、この aS の S をさらにルール 2 を使って b に置き換えると文字列 ab ができる。ab はすべて終端記号でできておりこれ以上置き換えることができないから ab は上の正規文法によって定められる正規言語(集合)の要素の一つである。

正規言語の要素は ab だけではない、上のルールの組み合わせでたくさんの文字列を作ることができる。ルール 1 を2回、ルール 2 を 1 回適用すると aab が生成される。同様に aaab, aaaab, aaaaaab, のようにこの文法の正規言語の要素は無限に生成される。

BNF 記法であらわされる文法もこのような生成文法だ。それは非終端記号を置き換えることで様々な記号列を生成することができるが、記号の生成法は単に記号の置き換えを繰り返すだけなので、なにも不可解なところはない。

しかし、パーサの構文解析に使われる文法はこのような生成文法ではなく、与えられた文字列が文法の規定を満たしていって、最終的に非終端記号 S に置き換えられるかどうかを調べる、分析文法なのだ。

正規言語の場合は、このような分析文法は有限オートマトンで表現される。有限オートマトンとは文字列を入力し、入力によってプログラムの変数の状態が変化するプログラム機械だ。ここに q0 と q1 という二つの状態を持った有限オートマトンがあったとする。この状態はオートマトンの入力に対応して q0 から q1 にかわったり、q1 から q0 に変わったりする。

さて、このオートマトンに "aaabacad" のような文字列を入力することを考える。このオートマトンはこのうち a と b しか受け付けないものとする。c を入力するとたちまちエラーを吐き出して止まってしまう。また、このオートマトンの最初の状態は q0 であるとする。これに a や b を入力するとオートマトンの状態が q0 や q1 に変化するが、その変化にはルールがある。状態が q0 の時は a が入力されるたびに状態は q0 になるが、b が入力されると状態が q0 から q1 に変化して機械が停止する。文字列は先頭部分から順にオートマトンに入力されていくが、ab や aab や aaab が入力されると文字列を読み終わると同時に機械も停止する。この時機械の状態が q1 あれば、その文字列が正規文法を満たす正規言語の要素であることが分かる。abaa のような場合は機械は途中まで読み終わってしまった時点で止まってしまうので排除される。

このようなやり方でオートマトンは上の正規文法による正規言語の要素の文字列だけを取り出すことができる。

分析文法は何もオートマトンでなければならないわけではなく、単に a を複数回読み込んだ後最後に b が来るような文字列に対しては、マッチを通知し、それ以外はエラーを通知するようなプログラムを普通に書いてもいい。いずれにせよ、分析文法は、生成文法とは随分形の変わったものになる。

このように同じ正規言語を記述するにも生成文法と分析文法では性質が異なっている。したがって、分析文法として働くパーサをつくるためには、生成文法をいったんコンパイルして、分析文法に変換しなくてはならない。これば yacc のような構文解析プログラムを生成文法から作り出すコンパイラ・コンパイラが必要とされる所以だ。

構文解析プログラムのソースの意味が解らなかったのは、生成文法だけを眺めて構文解析器を作ることを考えていたためだ。

追記

上の正規文法は正規表現では /a*b/ と表すことができる。これは a が複数回現れた後、b が現れることを意味している。これも文字列を選別するので文法の一つだ。しかし、これは再帰的定義の正規文法とは形が異なっている。また、正規表現からは、正規文法よりもマッチする文字列を選び出すプログラムを作りやすい。

このように、正規文法と正規表現は同じ正規言語(文字列の集合)を作り出すが表現が異なっている。したがって、正規表現は、一種の分析文法と言えるのかもしれない。

最近プログラム言語を記述する文法として PEG (parsing expression grammer) が提唱されているが、これは BNF 記法と異なり構文解析の曖昧性がない。また、文法の再帰的な定義ができるが、文法の表現法としては、正規表現に似ている。このためか、PEG は生成文法ではなく、分析文法の範疇に入れられているようだ。

PEG の BNF との最大の違いは、BNF の選択が PEG では優先順位つき選択であることだ。複数の選択肢がある時は、最初に記述された選択肢が採択された場合、後の選択肢はスキップされる。このため BNF で記述された時のような構文の曖昧さが排除される。また、PEG では左再帰を排除した記述ができるため、構文解析プログラムをトップダウンに記述しても、無限再帰が回避できる。

このような特徴のため、PEG は自然言語の分析には向かないが、プログラム言語の文法の記述については、パーサプログラムを作りやすい。

[PR]
by tnomura9 | 2016-02-29 18:35 | JavaScript | Comments(0)

変数つき1行電卓

パーサの記事も大分続いたので、テキストフィールドに入力した数式を計算する電卓のプログラムを紹介して最後にする。HTML edit E (http://www.mnet.ne.jp/~tnomura/javascript/edite.html) にコピペしてアンダースコア_ を消去すれば動作確認できる。perse.js は http://www.mnet.ne.jp/~tnomura/javascript/parse.js に置いた。テキストフィールドに数式を入力してリターンキーを入力すると結果が表示される。変数が使えるので、次のような計算もできる。

a = 1
b = 2
(a + b) * (a + b)

<!doctype html>
<html lang="ja">
<head>
<meta charset="utf-8">
<script src="parse.js"></script>
<script>

// Lexical Analysis

var spacing = P.pat( P.lex(/^\s*/), P.pop )
var num = function() {return P.lex(/^\d+/)() && spacing() }
var m = function() {return P.lex(/^[*/]/)() && spacing() }
var p = function() {return P.lex(/^[+-]/)() && spacing() }
var lpar = function() {return P.lex(/^[(]/)() && spacing() }
var rpar = function() {return P.lex(/^[)]/)() && spacing() }

// Syntactic Analysis

var mFact = P.pat( function() {return m() && fact() }, function() {
    var b = parseInt(P.pop()); op = P.pop(); a = parseInt(P.pop())
    if (op == "*") {
        P.push( "" + (a*b) )
    } else {
        P.push( "" + (a/b) )
    }
})
var term = function() {return fact() && P.many( mFact )() }
var pTerm = P.pat( function() {return p() && term()}, function() {
    var b = parseInt(P.pop()); op = P.pop(); var a = parseInt(P.pop())
    if (op == "+") {
        P.push( "" + (a+b) )
    } else {
        P.push( "" + (a-b) )
    }
})
var expr = function() {return term() && P.many( pTerm )() }
var paren = P.pat( function() {return lpar() && expr() && rpar() }, function() {
    P.pop(); var val = P.pop(); P.pop()
    P.push( val )
})
var fact = function() {return num() || evalvar() || paren() }

// Subscription

var variables = {}

var ident = function() {return P.lex(/^\w+/)() && spacing() }
var equal = function() {return P.lex(/^=/)() && spacing() }
var notequal = P.notPred( P.lex(/^=/) )
var subscribe = P.pat( function() {return ident() && equal() && expr() }, function() {
    var value = P.pop(); P.pop(); var identifier = P.pop()
    variables[identifier] = value
    P.push(value)
})
var evalvar = P.pat( function() {return ident() && notequal()}, function() {
    var id = P.pop()
    P.push( variables[id] )
})

var program = function() {return subscribe() || expr() }

function calculate() {
    var line = d_ocument.getElementById("line")
    P.setLine( line.value )
    program()
    line.value = P.pop()
}

</script>
</head>
<body>
<input type="text" id="line" o_nchange="calculate()">
</body>
</html>
[PR]
by tnomura9 | 2016-02-27 22:10 | JavaScript | Comments(0)

形式文法とは何か

プログラム言語の文法は形式文法で記述される。したがって、形式文法とは何かというイメージを持っていないと、yacc などの記述が何をやっているのかが理解できない。

形式文法とは、単に記号の置き換えの規則だ。例えば次の文法は、正規文法で書かれているが、これは単に左の記号を、右の記号で置き換えことができるということを示しているだけだ。

1. S -> aS
2. S -> b

この文法では記号 S は aS かまたは b に置き換えることができるということを示している。S は S 以外の記号で置き換えることができるので非終端記号と呼ばれる。また、a や b は実際の文字であるので、置き換えはできない。これは終端記号と呼ばれる。ややこしいが、S は数式の変数と考え、a や b は数式の定数と考えると良い。数式でも例えば n の階乗の定義は次のようにする。

fact n = n * fact (n-1)
fact 0 = 1

上の n が変数で、0 や 1 が定数だ。言い方を変えると n が非終端記号で 0 と 1 は終端記号だ。

話を形式文法に戻すが、これがどうして文法になるのかというと、このルールで文字列を生成できるからだ。S という記号はルール 1 によって、aS と置き換えることができる。そこでさらに aS の S をルール 2 によって b に置き換えると、ab が得られる。これは、ab という文字列が上の文法を満たしているということを示している。

それでは、ルールの使い方を少し変えて、ルール1を2回適用し、ルール2を1回適用したらどうなるだろうか。この場合 aab が得られることになる。同様に aaab, aaaab, ... と無限にこの文法が適用できる文字列を作っていくことができる。これらの有限の文字列全てを要素とする(無限)集合が、上の正規文法の言語だ。

普通、文法について考えるときは、文が先にあって、その文の構造はどうなっているのかという分析の仕方をするが、上の生成文法では、文法が先にあって、それから無限にそれに適合する文字列を生成することができる。方向性が逆なのだ。

それではなぜこのような文法で、プログラム言語の構文解析ができるのだろうか。そこで、aab という文字列に上の文法を適用してみる。S -> aab となるかどうかは、まず 先頭の a に適合する文法のルールがあるかどうかを調べる。ルール 1 では S -> aS なので、

S -> aS

と置き換えることができる。先頭の部分はマッチすることが分かったのでさらに S -> aS という置き換えができるかどうかを見てみる。これも、ルール 1 を適用することで S -> aS と置き換えることができる。つまり、

S -> aS -> a(aS)

だ。aab の aa の部分は文法に適合することが分かったので S -> b の置き換えができれば、aab が文法に受容されることがわかる。ルール 2 は S -> b なので結局、

S -> aS -> a(aS) -> a(a(b)) -> aab

の置き換えができることがわかり、aab は上の文法にかなう(受容される)ことが分かった。このように文法の定義は、元々がその文法にかなう文字列を生成する定義であり、文字列が文法に適合するかという問題については、その逆の処理を行うことになる。

したがって、構文解析のプログラムは、文字列を生成する規則である文法から、文字列がその規則に合致しているかどうかを判別するプログラムを作らないといけない。これが、yacc を始めとする多くの構文解析のプログラムがコンパイラ・コンパイラになっている理由だ。

このように、プログラム言語の文法を作成することと、その文法からパーサを作成することとは方向性が逆の作業であることに注意が必要だ。


[PR]
by tnomura9 | 2016-02-26 06:01 | JavaScript | Comments(0)

正規表現とは何か

正規表現について調べていたら正規言語、正規演算、正規表現、正規文法、有限オートマトン、文脈自由文法などの概念が出てきて混乱した。それで、分かったと思う分だけをまとめてみる。

まず有限オートマトンだが、これは、メモリの極端に少ないコンピュータのことだ。このコンピュータに文字列を入力すると、入力し終わった時にコンピュータは「受容」か「拒否」かの値を返す。正規言語とは、この有限オートマトンで受容の値が帰る文字列全ての集まりのことだ。一個の有限オートマトンで、複数の(無限の)文字列の集まりを定めることができる。このあつまりが、そのオートマトンによって定められる言語だ。

この正規言語を二つを合わせたものはやはり正規言語になる。もちろんこの正規言語に対する有限オートマトンは、二つの正規言語に対応する有限オートマトンとは異なるが、それらから合成することができる。

また、二つの正規言語の中からそれぞれ文字列を取り、その二つの文字列を連結させる。このような連結された文字列の全ての集まりもまた正規言語になる。

さらに正規言語の文字列を複数回連結した文字列を作ることができるが、これも正規言語になる。このように正規言語の和集合、連結、複数回の連結の繰り返しも正規言語を作る。このような正規言語に対する演算を正規演算という。

正規表現とは、要素的な文字列から選択、連結、繰り返しという3つの演算を使って作り出された文字列を定義する演算規則のことである。正規言語と、正規表現は発想が違うが、同じ文字列の集まりを表すことができる。

また、正規言語は正規文法を使って作ることができる。正規文法は形式文法の一つで、左側に非終端記号 S があり、右側には終端記号か、一つの非終端記号と一つの終端記号しか許されない文法だ。

形式文法は、非終端記号を別の非終端記号や終端記号に置き換えるためのルールを示した式だ。例えば、次の文法は正規文法だ。

1. S -> aS
2. S -> bA
3. A -> ε
4. A -> cA

ルール 1 から aaS が導出され、これにルール 2 を適用することで、aabA が導出される。これにルール 4 を2回適用すると aabccA が導出される。最後に、ルール 3 を適用して aabcc という文字列を導出できる。これは正規表現の a*bc* に相当する。

文脈自由文法とは上のような置き換えの規則で、左側に終端記号が1つだけ置くことが許されているものだ。次の文法は文脈自由文法の例だ。

1. S -> aSb
2. S -> ab

プログラミング言語は大半が文脈自由文法で記述できるので、プログラム言語を作る時の重要な作業は、そのプログラミング言語を記述できる文脈自由文法をプログラムすることだ。

文脈自由文法は正規文法を包含しており、文脈自由言語は、正規言語を含んでいる。また、正規言語を正規表現で記述するときには、選択、連結、繰り返しの3つしか使わない。プログラム言語の正規表現の多くの表現は、この三つの演算の組み合わせのシンタックスシュガーだ。

正規言語は、有限オートマトンで定義できる。また、文脈自由言語は、有限オートマトンにプッシュダウンスタックを追加した、プッシュダウン・オートマトンで定義できる。

文脈自由文法は、正規表現にスタックを加えたものと考えることができる。また、文脈自由文法は、正規文法に再帰的定義を追加したものと考えられる。

また、これらの言語の数学的議論では、文字列の先読みは出てこない。したがって、構文解析器の文法の設計に現れる「文字列の先読み」は、言語としての定義としてよりは、構文解析の効率を上げるための付加的な工夫のように思われる。

数学的な発想から生まれた正規表現がケン・トンプソンによってコンピュータのプログラミングに導入された後、その本来の意味は忘れられ、便利なパターンマッチ機械としての利用法のみが前面に出てきているのだろう。しかし、構文解析プログラムの文法をプログラムするときは、形式文法の本来の意味も考えておかなければならない。

例えば電卓のプログラムだが、文法規則だけを抜き出すと次のようになる。

expression -> term (+ term)*
term -> factor (* factor)*
factor -> number / ’(’ expression ’)’

expression の定義の term (+ term)* は正規表現の連接と繰り返しが適用されているのでこれは正規表現だ。文脈自由文法は正規表現を含むので、これは文脈自由文法にもかなっている。factor の定義の右項は number という終端記号と、expression という非終端記号の重みつき選択になっている。正規表現では右項には終端記号または非終端記号と終端記号の連接しか認められていないので、この定義は正規表現では表現できない。この部分が括弧の中の再帰的文法を定義している。したがって、再帰的な構造についての文法の適用は正規表現ではできないのがわかる。このような言語を導出するためには、文脈自由文法が必要なのだ。

上の文法で定義した再帰下降パーサでは expression 関数が呼ばれると、その関数から term 関数が呼ばれ、term 関数から factor 関数が呼ばれ、factor 関数で number 正規表現のマッチングが行われる。これは、形式文法の非終端記号の文法による置き換えを忠実に反映している。したがって、再帰下降パーサはトップダウンの生成文法の実装になっている。これは、パーサコンビネータの場合も一緒で。expression 関数が呼ばれるとその中から term 関数が呼ばれ、term 関数から factor 関数が呼ばれという再帰下降パーサと同じような非終端記号の置き換えが起こる。つまり、再帰下降型で記述したパーサと、パーサコンビネータで記述したパーサは同じものであるのが分かる。

パターンマッチャー P モジュールは、選択、連接、繰り返しのコンビネータしかないが、理論的にはこれだけで、文脈自由文法の言語は導出可能だ。他のパーサに習って、肯定先読みや、否定先読みのパーサも記述したが、これば、文法の問題というよりは、パーサの効率に関係するものだ。

P モジュールはマッチしたパターンの消費や、トラックバックの処理のオーバーヘッドがひどいのでプログラム言語のパーサの記述には向かないが、少なくとも、原理的にはそのような言語の記述も可能だと思われる。

ただ、ここで強調したいのは、データ型に関数型を持ち、正規表現の装備されたプログラム言語なら、本当に小さいライプラリで、パーサコンビネータ型の文脈自由文法を書くことができるということだ。動作の効率に関しても、正規表現を文字列のキャラクタポインタの位置から始めることができれば、問題ないはずだ。JavaScript の正規表現では g オプションを使った時に RegExp.prototype.exec() メソッドでそういうことができるが、これが String.prototype.match() メソッドでも行えるようになれば、十分実用的なパーサが書けるようになるはずだ。

手軽に文脈自由文法のパーサをかけるようになれば、自作のプログラムの関数に渡す引数などをもっと自由にコントロールできるようになるのではないだろうか。電卓のパーサくらいなら、単に慣れの問題だけで難しいところはないと感じられるようになる。正規表現とデータ型としての関数型の普及で、構文解析プログラムはプログラムの言語の開発者だけでなく、一般のプログラマも気軽に利用できるような環境になってきている気がする。

[PR]
by tnomura9 | 2016-02-24 23:53 | JavaScript | Comments(0)

正規表現で構文解析

このブログで紹介したパターンマッチャー P モジュールの構文解析は、幾つかの機能のコンポーネントに分けることができる。それは、モジュールが、要素的なパーサの連接、優先順位付き選択、繰り返しを定義できるということだ。

ところが、このパターンの連接、選択、繰り返しの定義は正規表現でもできる。それでは、正規表現で、ソースの生の文字列ではなく、字句解析を行った後のトークンの種別を対象に解析すれば、構文解析ができるのではないかと思い立った。そこで、次のようなソースを書いてみた。

<script>
var number = 'number'
var star = '[*]'
var plus = '[+]'

var term = number + '(' + star + number + ')*'
var expression = term + '(' + plus + term + ')*'

parser = new RegExp( expression )
d_ocument.write(parser.toString()+'<br>')
function parse(string) {
result = string.search(parser)
if (result != -1) {
return true
} else {
return false
}
}

string = "number*number*number+number*number"
d_ocument.write( parse( string ))
d_ocument.close()
</script>

これなら、正規表現を利用して、電卓の構文解析をほぼ文法の通りに記述できる。このプログラムはこのブログで以前に紹介した Code Mirror HTML Editor にコピペして実験してみることができる。このプログラムを実行すると次のようになって文法のチェックだけだが、四則演算の構文解析ができる。

/number([*]number)*([+]number([*]number)*)*/
true

しかし、文法定義を次のように括弧の処理を含む再帰的定義にしたら正規表現では動作しなかった。

var term = primary + '(' + star + primary + ')*'
var expression = term + '(' + plus + term + ')*'
var primary = number + '|' + '(' + expression + ')'

つまり、正規表現で再帰的定義ができれば、構文解析も可能であるということだ。これは、Pモジュールでは、正規表現と違って処理対象が文字列ではなく要素的なパーサ関数の列であるが、連接、選択、繰り返しという処理については正規表現と同じようなイメージでプログラムできることを意味している。ただ、P モジュールの場合は、正規表現と違って、再帰的定義が行えるところが本質的に異なっている。

要するに、構文解析のパーサは再帰的定義もできる正規表現なのだというイメージをつかむことができれば、その働きがわかりやすくなる。プログラム言語の構文解析は、言語の文法をどうやって、要素的なパーサの連接、選択、繰り返しで表現できるかを考えればいいだけだからだ。

また、P モジュールの意味も、要素的なパーサの列の連接、選択、繰り返しのパターンを記述するためのものだと理解することで、利用法のイメージがスッキリする。文字列に対して正規表現が行っていることを、P モジュールの利用では、対象を文字列からパーサ関数の列に置き換えればいいだけだからだからだ。

P モジュールでやっているのは、パーサの連接を function() {return parser1() && parser2() && .. } で表現し、パーサの選択を funnction() {return parser1() || parser2() || ... } で表現し、パーサの0回以上の繰り返しを many( parser ) で表現しているだけだからだ。また、このような複合パーサは要素的なパーサと同列に扱うことができるから、正規表現ではできなかった再帰的定義も利用することができる(ただし、再帰的な展開を止める base case を意識していないと無限再帰を引き起こしてしまうが... )。さらに、パーサがマッチした時のアクションを P.pat() 関数でペアリングできるので、パターンのマッチだけではなく、直接処理や構文木の構築もできる。

P. モジュールの記述があまりにも単純なので、これで大丈夫なのだろうかと少々不安だったが、先読みつきLLパーサの構文解析はそれほど複雑なことをやっているわけではないのかもしれない。

P モジュールでは先読みをした時のバックトラックの処理や、パーサがマッチした時の文字列の消費の処理で文字列のコピーを行ってしまうので、オーバーヘッドが大きく、プログラム言語のパーサを作るのは難しいだろうが、正規表現では表現できない再帰的定義を含んだパターンの解析を手軽に行うという用途には便利ではないかと思う。

ただし、JavaScript の正規表現の適用が、文字列へのキャラクターポインターから開始できるようになれば、ソースの文字列をコピーしなくても良くなるので、結構実用的なパーサも作れるのではないかと思っている。

もっと良いのは先読みつきLLパーサを JavaScript の仕様に取り込んでくれることだ。これについては、正規表現を拡張して再帰的定義も含む変数の使用ができるようにして、さらに正規表現のマッチが起きた時のアクションをペアリングすることができるようにすれば、正規表現だけでシームレスに字句解析からパーサまで書けるようになるので便利だろう。

[PR]
by tnomura9 | 2016-02-21 09:38 | JavaScript | Comments(0)

変数つき1行電卓

電卓パーサを改良して、a = 10 のように変数に代入したり、a + b のように変数を含んだ計算をしたりできる電卓のパーサを作りました。P.setLine で行を取り込み、program() でパースできますが、パースできるのは1行だけで、複文はパースできません。P モジュールに先読み andPred (and-predicate) パーサと否定先読み notPred (not-predicate) パーサを追加しました。

<script>
// Simple Pattern Matcher Module
// written by tnomura, Feb. 11, 2016
// This is a public domain software

P = (function() {

var line = ""
stack = []

function setline( ln ) { line = ln }
function getline() { return line }
function push( dat ) { stack.push( dat ) }
function pop() { return stack.pop() }
function getstack() { return stack }

function lex( re ) {
return function() {
var match = line.match( re )
if ( match ) {
line = line.replace( re, "" )
stack.push( match[0] )
return true
} else {
return false
}
}
}

function pat( pattern, action ) {
return function () {
var trackback = line
var stacklength = stack.length
if (pattern()) {
action()
return true
} else {
line = trackback
stack = stack.slice(0, stacklength)
return false
}
}
}

function andpred ( pattern ) {
return function () {
var trackback = line
var stacklength = stack.length
if (pattern()) {
line = trackback
stack = stack.slice(0, stacklength)
return true
} else {
line = trackback
stack = stack.slice(0, stacklength)
return false
}
}
}

function notpred( pattern ) {
return function () {
var trackback = line
var stacklength = stack.length
if (pattern()) {
line = trackback
stack = stack.slice(0, stacklength)
return false
} else {
line = trackback
stack = stack.slice(0, stacklength)
return true
}
}
}

function many( pattern ) {
return function() {
while( pattern() ) {}
return true
}
}


return {
setLine: setline,
getLine: getline,
push: push,
pop: pop,
getStack: getstack,
lex: lex,
pat: pat,
andPred: andpred,
notPred: notpred,
many: many,
}

})()

// Definition of The Grammar

var spacing = P.pat( P.lex(/^\s*/), P.pop )
var number = function() {return P.lex(/^[0-9]+/)() && spacing() }
var star = function() {return P.lex(/^[*/]/)() && spacing() }
var plus = function() {return P.lex(/^[+-]/)() && spacing() }
var lparen = function() {return P.lex(/^[(]/)() && spacing() }
var rparen = function() {return P.lex(/^[)]/)() && spacing() }

var stnum = P.pat( function() {return star() && primary()}, function() {
var a = parseFloat(P.pop()); var op = P.pop(); var b = parseFloat(P.pop())
if (op == "*") {
P.push("" + (a*b))
} else {
P.push("" + (b/a))
}
})

var term = function() {return primary() && P.many( stnum )() }

var adterm = P.pat( function() {return plus() && term()}, function() {
var a = parseFloat(P.pop()); var op = P.pop(); var b = parseFloat(P.pop())
if (op == "+") {
P.push("" + (a+b))
} else {
P.push("" + (b-a))
}
})

var expr = function() {return term() && P.many( adterm )() }

var paren = P.pat( function() {return lparen() && expr() && rparen() }, function() {
P.pop(); var a = P.pop(); P.pop()
P.push( a )
})

var primary = function() {return number() || evalvar() || paren() }

var variables = {}

var ident = function() {return P.lex(/^\w+/)() && spacing() }
var equal = function() {return P.lex(/^=/)() && spacing() }
var notequal = P.notPred( P.lex(/^=/) )
var subscribe = P.pat( function() {return ident() && equal() && expr() }, function() {
var value = P.pop(); P.pop(); var identifier = P.pop()
variables[identifier] = value
})
var evalvar = P.pat( function() {return ident() && notequal()}, function() {
var id = P.pop()
P.push( variables[id] )
})

var program = function() {return subscribe() || expr() }

// Main Program

P.setLine("a = 1 + 2*3")
program()
P.setLine("b = a+3")
program()
P.setLine("a + b")
program()
a_lert(P.getStack())
</script>

[PR]
by tnomura9 | 2016-02-20 05:51 | JavaScript | Comments(0)

パーサコンビネータ seq()

パターンマッチャーの可読性をもう少し良くしたくなったので、パーサコンピネータの試作品を作ってみた。seq() コンビネータ (sequence) はパーサを順次実行し、パーサの戻り値が false になったところで処理を中断して false を返す。同じ形のプログラムで パーサの戻り値が true になった時点で処理を中断する pc (prioritized choice) も作れるはずだ。下のコードが試作品だ。

<script>
function number() { a_lert('number'); return true }
function lparen() { a_lert('('); return true }
function rparen() { a_lert(')'); return true }
function seq() {
n = arguments.length
for (i = 0; i < n; i++) {
result = arguments[i]()
if (result == false) {
return false
}
}
return true
}
a_lert( seq(lparen, number, rparen) )
</script>

追記

いろいろやってみたが、結局うまくいかなかった。複雑なパターンを組むと無限ループになってしまう。理想は次のように文法を PEG で記述すると、expression() でパースしてくれることだが、無理だった。

expression = term (’+’ term)*
term = primary (’*’ primary)*
primary = number || ’(’ expression ’)’

しかし、パターンマッチャーを書いてみてわかったのは、上の文法が expression という関数が呼ばれるとその関数が term という関数を呼び、さらに term は primary を呼ぶというような関数呼び出しの連鎖でパースが行われているということだ。手書きで再帰下降型パーサを書くときも、このような関数呼び出しになるので、パーサコンビネータと再帰下降型のプログラムは類縁のものだ。P モジュールを利用したパーサの記述は、割と簡潔にこの辺の関係を表現してくれる。P モジュールで遊びながら、構文解析の教科書を読むと、yacc などもよくわかるようになるのかもしれない。

DSLを作るなどというのは大それた望みかもしれないが、構文解析に関しては、どのプログラム言語もワンパターンで理解できるのではないだろうか。しかしながら、独学では教科書を読んでも、動くプログラムがないと理解し辛い気がする。P モジュールなら字句解析のパーサの段階から動作確認できるので。構文解析プログラムに対する垣根が低くなるのではないだろうか。

[PR]
by tnomura9 | 2016-02-19 04:50 | JavaScript | Comments(0)