META in Squeak

仕事

昨日思いつくまでSqueak版METAはParsing Expression Grammar(PEG)をちゃんとサポートしているとは思っていなかったのだが、PEGが要求するとされていた(Wikipediaによればhttp://en.wikipedia.org/wiki/Parsing_expression_grammar)"And-predicate"は、「Not-predicateを使ってnotのnot」として書けば自分で書けるということに気がついた。

というわけで、Squeak版METAで書いた
$a^{n} b^{n} c^{n} : n > 0$
の例はこんな感じ。

MTokenizer subclass: #MABC
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Meta-Examples'!

!MABC methodsFor: 'productions' stamp: 'yo 5/4/2007 11:15'!
a ::= $a <a> $b | `true`! !

!MABC methodsFor: 'productions' stamp: 'yo 5/4/2007 11:23'!
aa ::= <a>:a ?`a ~= true`! !

!MABC methodsFor: 'productions' stamp: 'yo 5/4/2007 11:24'!
b ::= $b <b> $c | `true`! !

!MABC methodsFor: 'productions' stamp: 'yo 5/4/2007 11:26'!
bb ::= <b>:b ?`b ~= true`! !

!MABC methodsFor: 'productions' stamp: 'yo 5/4/2007 11:28'!
s ::= ~(~(<aa> ~$b)) $a+ <bb> ~$c! !

これをfile inしたあと、

MABC match: 'aaabbbccc' with: #s

とすると、任意長先読みの文脈依存の構文解析ができるわけでした。

Wikipediaにも、Bryan Fordの発表資料にも、and-predicateはPEGの一部であるかのように書かれていますが、元論文ではand-predicateは含まれていませんでした(?も含まれていなかった)。というわけで、最小限の定義以上のものがどこかで入ってきてしまっていたようです。