TXR：再帰的パターンマッチディレクティブを書き込む

Question

TXRで再帰的パターンマッチング関数を書く方法を理解できません。以下では、ファイルパスを認識するための再帰的なディレクティブを定義しようとします。私はこの場合、正規表現([a-z]+\/)+[a-z]+でこの文法を表すことができますが、実際のコードではより複雑なルールが念頭に置かれています。スラッシュがあるときにこのディレクティブが失敗する原因は何ですか？

@(define location)@\ 
@ (cases)@\ 
@/[a-z]+/@\ 
@ (or)@\ 
@/[a-z]+//@(location)@\ 
@ (end)@\ 
@(end) 
@(repeat) 
@(cases) 
@{location (location)} 
@ (output) 
@location is a valid location. 
@ (end) 
@(or) 
@location 
@ (output) 
@location is not a valid location. 
@ (end) 
@(end) 
@(end) 

例有効な入力：。/[a-z]+(\/[a-z]+)*/私はと仮定しています：

this/is/valid 
this/is/also/valid 
this 
a/b/c 

Answer 1

（もちろん、あなたはほぼ確実locationは、我々は正規表現を持つだけのmungeすることができ、通常の言語に一致していることを認識しておりますこれはちょうど複雑な何かのためのウォークアップ "再帰の世界"ウォームアップです）

約casesについては、上から下、短絡評価を使用しています。 2番目のケースは、最初のケースが接頭辞と一致するため一致しません。これは部分正規表現の順序が重要でない正規表現の分岐演算子のようなものではありません。

私は単純に2つのケースを交換すると、サンプルが私のために働く。

casesはsomeに変更されています。 some指示は、最初の試合で停止しません。時々、あなたが（例えば、いくつかの条件がヒットした左再帰を避けるため）、または縮退を回避するために、再帰を終了させる場合を中心に短絡する必要があるため、someを使用して

は万能cases注文この種の問題のためではありませんパフォーマンス（指数関数的時間）。私は大学の教授の冗談を思い出しています："分裂と征服について聞いたことがあります;これは倍増し、降伏します"。

someには、後の節が以前の正常に一致する節からのバインディングを「参照」するというプロパティもあります。それは、それがcasesの順序問題の解決策であることを妨げる可能性があります。つまり、後の節は、可変の衝突のために一致しない可能性があります。 フィーチャーsomeはその状況で役立つかもしれないし、そうでないかもしれない。