(57)【要約】  複数のＸＭＬ文字列を解析するためのシステムおよび方法である。前記方法に従って、入力文字列は、複数の連結リストノード構造に変形される。前記入力文字列の前記シンタックスは、検証される。複数の属性を備える前記複数の連結リストノード構造を用いて、複数の連結リスト属性構造が生成される。前記複数の連結リストノード構造の前記複数の予約ポインタを用いて、前記入力文字列内の複数のデータセグメントが得られる。前記複数の連結リストノード構造および属性構造は解放される。前記複数の連結リストノード構造および複数の属性構造を解放することは、前記複数の連結リストノードおよび属性構造内で定義される、前記入力文字列に含まれる複数の要素のそれぞれの内にデータおよび複数の属性を定義する前記入力文字列への複数のポインタを維持しながら前記複数の連結リストノードおよび属性構造を削除する。
2007514239.tif 000002
【特許請求の範囲】
【請求項１】
複数のマークアップ言語記述を分けるための方法であって、
入力文字列を複数の連結リストノード構造に変形する段階と、
前記入力文字列のシンタックスを検証する段階と、
複数の属性を有する前記複数の連結リストノード構造から、連結リスト属性構造を作成する段階と、
データを有する前記複数の連結リストノード構造からデータセグメントを得る段階と、
前記複数の連結リストノード構造および複数の属性構造を解放する段階と
を備える方法。
【請求項２】
前記複数の連結リストノード構造および複数の属性構造を解放する段階は、前記入力文字列に含まれる複数の要素のそれぞれの内にデータおよび複数の属性を定義する前記入力文字列への前記複数の連結リストノードおよび属性構造の中で定義される複数のポインタを維持しながら前記複数の連結リストノードおよび属性構造を削除する請求項１に記載の方法。
【請求項３】
前記複数の連結リストノード構造の中の前記複数のポインタは、タグ名称、名称空間、予約位置、次タグ、親タグ、ピア要素、および終了タグへの１つ以上のポインタを備える請求項２に記載の方法。
【請求項４】
前記複数の連結リスト属性構造の中の複数のポインタは、属性名称、属性値、接頭辞名称、および次属性への１つ以上のポインタを備える請求項２に記載の方法。
【請求項５】
前記予約位置への前記ポインタは、開始タグのために次の閉括弧へのポインタおよび終了タグのために開括弧へのポインタを備える請求項３に記載の方法。
【請求項６】
入力文字列を複数の連結リストノード構造に変形する段階は、
前記入力文字列および区切り文字として開括弧文字を受け取る段階と、
前記開括弧の区切り文字を用いて、前記入力文字列を解析する段階と、
複数のトークンの連結リストを返す段階と
を備え、
前記連結リストのそれぞれのトークンは、１つの連結リストノード構造を提供するために解析される請求項１に記載の方法。
【請求項７】
１つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析する段階は、
前記トークンがスラッシュ（"／"）で始まるかどうかを判断する段階と、
前記トークンが前記スラッシュで始まらない場合、前記連結リストノード構造の中の開始タグ領域をセットし、および前記トークンが前記スラッシュで始まる場合、前記開始タグ領域を消去する段階と、
スペース文字が前記トークンの中で見つかる場合、前記トークンを一番目の部分および二番目の部分に分けるために、前記区切り文字として前記スペース文字を用いて前記トークンを解析する段階と
を備え、
前記スペース文字が前記トークンの中で見つかる場合、
名称空間のために前記連結リストノード構造の中の名称空間ポインタを前記トークンの前記一番目の部分の中の一番目の文字にセットする段階であって、前記名称空間の前記長さは、前記トークンの前記一番目の部分の中の一番目の文字から前記トークンの前記一番目の部分の中のコロンに先立つ文字にわたる段階と、
タグ名称のために前記連結リストノード構造の中のタグ名称ポインタを前記トークンの前記一番目の部分の中の前記コロンの右の文字にセットする段階であって、前記タグ名称の前記長さは、前記コロンの前記右の前記文字から前記トークンの前記一番目の部分の最後の文字にわたる段階と
を備え、
前記スペース文字が前記トークンの中で見つからない場合、
前記連結リストノード構造の中の前記タグ名称ポインタを前記トークンの中の前記複数の文字にセットする段階であって、前記タグ名称の前記長さは、前記トークンの前記長さである段階と、
前記連結リストノード構造の中の前記名称空間ポインタをｎｕｌｌポインタとしてセットする段階であって、前記名称空間の前記長さは、ゼロである段階と
を備え、
１つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析する段階は、
前記連結リストノード構造の中の次領域ポインタが前記次のトークンの先頭を指し示すようにセットする段階を備える請求項６に記載の方法。
【請求項８】
前記トークンが開始タグの場合、前記連結リストノード構造の中の予約ポインタが前記トークンの前記最後の閉括弧を指し示すようにセットし、および前記トークンが終了タグの場合、前記予約ポインタが前記トークンの前記先頭の開括弧を指し示すようにセットする段階をさらに備える請求項７に記載の方法。
【請求項９】
前記トークンの前記二番目の部分の一番目の文字が前記スラッシュで始まるかどうかを判断する段階と、
前記トークンの前記二番目の部分が前記スラッシュで始まる場合、前記連結リストノード構造の中の空タグ領域をセットする段階と、
前記トークンの前記二番目の部分が前記スラッシュで始まらない場合、前記連結リストノード構造の中の空タグ領域を消去する段階と
をさらに備える請求項７に記載の方法。
【請求項１０】
前記入力文字列のシンタックスを検証する段階は、
スタックを初期化する段階と、
入力文字列のための連結リストノード構造を受け取る段階と、
前記連結リストノード構造が開始タグおよび終了タグの１つを表すかどうかを判断する段階と
を備え、
前記連結リストノード構造が現在の開始タグを表す場合、
前記連結リストノード構造の中の親領域を前記スタックの上部の前記開始タグへのポインタで満たす段階と、
前記現在の開始タグを前記スタックに置く段階と
を備え、
前記連結リストノード構造が現在の終了タグを表す場合、
前記スタックの前記上部の前記開始タグをポップオフする段階と、
前記連結リストノード構造の中のピア領域を前記現在の終了タグの次領域ポインタへのポインタで満たす段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合するかどうかを判断する段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合しない場合、前記入力文字列を無効であると示す段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合する場合、前記入力文字列を有効であると示し、前記連結リストノード構造の終了タグを前記現在の終了タグで満たす段階と
を備え、
前記入力文字列が有効であり、かつ、前記連結リストノード構造が前記入力文字列のための前記最後の連結リストノード構造でない場合、前記スタックの前記初期化を除いて、前記入力文字列からの前記次の連結リストノード構造を用いて、上記プロセスを繰り返す段階を備える請求項７に記載の方法。
【請求項１１】
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成する段階は、
開始タグのための連結リストノード構造を受け取る段階と、
前記連結リストノード構造の中の予約ポインタを用いる段階であって、開括弧文字が前記入力文字列の中で見つかるまで、前記予約ポインタの位置を減らし、前記開括弧文字と前記予約ポインタとの間の全ての文字は、属性文字列を表す段階と、
前記属性文字列の一番目の部分および前記属性文字列の二番目の部分を提供するために、区切り文字としてスペース文字を用いて、前記属性文字列を解析する段階と、
前記属性文字列の前記一番目の部分を廃棄する段階と、
前記区切り文字として等号を用いて、前記属性文字列の前記二番目の部分を解析する段階と、
前記連結リスト属性構造の中の属性値ポインタを前記属性文字列の前記二番目の部分の前記等号の後の前記一番目の文字へセットする段階であって、属性値長は、前記属性文字列の前記二番目の部分の前記一番目の文字から前記属性文字列の前記二番目の部分の最後にわたる段階と、
前記区切り文字としてコロンを用いて、前記属性文字列の前記一番目の部分を解析する段階と
を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つかる場合、
前記連結リスト属性構造の中の接頭辞名称ポインタを前記属性文字列の前記一番目の部分の中の前記一番目の文字へセットする段階であって、接頭辞名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記一番目の文字から前記属性文字列の前記一番目の部分の中の前記コロンに先立つ文字にわたる段階と、
前記連結リスト属性構造の中の属性名称ポインタを前記属性文字列の前記一番目の部分の中の前記コロンの後の一番目の文字へセットする段階であって、属性名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記コロンの後の前記一番目の文字から前記属性文字列の前記一番目の部分の前記最後の文字にわたる段階と
を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つからない場合、
前記連結リスト属性構造の中の前記接頭辞名称ポインタをｎｕｌｌポインタとしてセットする段階であって、前記接頭辞名称の前記長さは、ゼロである段階と、
前記連結リスト属性構造の中の前記属性名称ポインタを前記属性文字列の前記一番目の部分の前記一番目の文字としてセットする段階であって、前記属性名称の前記長さは、前記属性文字列の前記一番目の部分の前記長さである段階と
を備え、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成する段階は、
前記連結リスト属性構造の中の次属性領域が前記入力文字列の中の前記次の属性を指し示すようにセットする段階を備える請求項１に記載の方法。
【請求項１２】
データを有する前記複数の連結リストノード構造からデータセグメントを得る段階は、
対応する開始タグおよび終了タグのための前記複数の連結リストノード構造を受け取る段階と、
前記開始および終了タグの前記複数の連結リストノード構造が前記データセグメントを決定するために、複数の予約ポインタを使用する段階であって、前記データセグメントは、前記開始タグの前記予約ポインタおよび前記終了タグの前記予約ポインタの間の前記データを有する段階と
を備える請求項１に記載の方法。
【請求項１３】
前記入力文字列は、ＸＭＬ（拡張可能マークアップ言語）入力文字列を備える請求項１に記載の方法。
【請求項１４】
複数の機械アクセス可能命令を有する記憶媒体を備え、前記複数の命令がプロセッサにより実行された場合、前記複数の命令は、
入力文字列を複数の連結リストノード構造に変形すること、
前記入力文字列のシンタックスを検証すること、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成すること、
データを有する前記複数の連結リストノード構造からデータセグメントを得ること、および
前記複数の連結リストノード構造および属性構造を解放すること
を提供する製品。
【請求項１５】
前記複数の連結リストノード構造および複数の属性構造を解放することは、前記複数の連結リストノードおよび属性構造の中で定義される、前記入力文字列に含まれる複数の要素のそれぞれの内にデータおよび複数の属性を定義する前記入力文字列への複数のポインタを維持しながら前記複数の連結リストノードおよび属性構造を削除する請求項１４に記載の製品。
【請求項１６】
前記複数の連結リストノード構造の中の前記複数のポインタは、タグ名称、名称空間、予約位置、次タグ、親タグ、ピア要素、および終了タグへの１つ以上のポインタを備える請求項１５に記載の製品。
【請求項１７】
前記複数の連結リスト属性構造の中の複数のポインタは、属性名称、属性値、接頭辞名称、および次属性への１つ以上のポインタを備える請求項１５に記載の製品。
【請求項１８】
前記予約位置への前記ポインタは、開始タグのために次の閉括弧へのポインタおよび終了タグのために開括弧へのポインタを備える請求項１６に記載の製品。
【請求項１９】
入力文字列を複数の連結リストノード構造に変形することのための複数の命令は、
前記入力文字列および区切り文字として開括弧文字を受け取ることと、
前記開括弧の区切り文字を用いて、前記入力文字列を解析することと、
複数のトークンの連結リストを返すことと
のための複数の命令を備え、
前記連結リストのそれぞれのトークンは、１つの連結リストノード構造を提供するために解析される請求項１４に記載の製品。
【請求項２０】
１つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析することのための複数の命令は、
前記トークンがスラッシュ（"／"）で始まるかどうかを判断することと、
前記トークンが前記スラッシュで始まらない場合、前記連結リストノード構造の中の開始タグ領域をセットし、および前記トークンが前記スラッシュで始まる場合、前記開始タグ領域を消去することと、
スペース文字が前記トークンの中で見つかる場合、前記トークンを一番目の部分および二番目の部分に分けるために、前記区切り文字として前記スペース文字を用いて前記トークンを解析することと
のための複数の命令を備え、
前記スペース文字が前記トークンの中で見つかる場合、
名称空間のために前記連結リストノード構造の中の名称空間ポインタを前記トークンの前記一番目の部分の中の一番目の文字にセットすることであって、前記名称空間の長さは、前記トークンの前記一番目の部分の中の一番目の文字から前記トークンの前記一番目の部分の中のコロンに先立つ文字にわたることと、
タグ名称のために前記連結リストノード構造の中のタグ名称ポインタを前記トークンの前記一番目の部分の中の前記コロンの右の文字にセットすることであって、前記タグ名称の前記長さは、前記コロンの右の前記文字から前記トークンの前記一番目の部分の最後の文字にわたることと
のための複数の命令を備え、
前記スペース文字が前記トークンの中で見つからない場合、
前記連結リストノード構造の中の前記タグ名称ポインタを前記トークンの中の前記複数の文字にセットすることであって、前記タグ名称の前記長さは、前記トークンの前記長さであることと、
前記連結リストノード構造の中の前記名称空間ポインタをｎｕｌｌポインタとしてセットすることであって、前記名称空間の前記長さは、ゼロであることと
のための複数の命令を備え、
１つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析することのための複数の命令は、
前記連結リストノード構造の中の次領域ポインタが前記次のトークンの先頭を指し示すようにセットすることのための複数の命令を備える請求項１９に記載の製品。
【請求項２１】
前記トークンが開始タグの場合、前記連結リストノード構造の中の予約ポインタが前記トークンの前記最後の閉括弧を指し示すようにセットし、および前記トークンが終了タグの場合、前記予約ポインタが前記トークンの前記先頭の開括弧を指し示すようにセットすることのための複数の命令をさらに備える請求項２０に記載の製品。
【請求項２２】
前記トークンの前記二番目の部分の一番目の文字が前記スラッシュで始まるかどうかを判断することと、
前記トークンの前記二番目の部分が前記スラッシュで始まる場合、前記連結リストノード構造の中の空タグ領域をセットすることと、
前記トークンの前記二番目の部分が前記スラッシュで始まらない場合、前記連結リストノード構造の中の空タグ領域を消去することと
のための複数の命令をさらに備える請求項２０に記載の製品。
【請求項２３】
前記入力文字列のシンタックスを検証することのための複数の命令は、
スタックを初期化することと、
入力文字列のための連結リストノード構造を受け取ることと、
前記連結リストノード構造が開始タグおよび終了タグの１つを表すかどうかを判断することと
のための複数の命令を備え、
前記連結リストノード構造が現在の開始タグを表す場合、
前記連結リストノード構造の中の親領域を前記スタックの上部の前記開始タグへのポインタで満たすことと、
前記現在の開始タグを前記スタックに置くことと
のための複数の命令を備え、
前記連結リストノード構造が現在の終了タグを表す場合、
前記スタックの前記上部の前記開始タグをポップオフすることと、
前記連結リストノード構造の中のピア領域を前記現在の終了タグの次領域ポインタへのポインタで満たすことと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合するかどうかを判断することと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合しない場合、前記入力文字列を無効であると示すことと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合する場合、前記入力文字列を有効であると示し、前記連結リストノード構造の終了タグを前記現在の終了タグで満たすことと
のための複数の命令を備え、
前記入力文字列が有効であり、かつ、前記連結リストノード構造が前記入力文字列のための最後の連結リストノード構造でない場合、前記スタックの前記初期化を除いて、前記入力文字列からの前記次の連結リストノード構造を用いて、上記プロセスを繰り返すことのための複数の命令を備える請求項１４に記載の製品。
【請求項２４】
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成することのための複数の命令は、
開始タグのための連結リストノード構造を受け取ることと、
前記連結リストノード構造の中の予約ポインタを用いて、開括弧文字が前記入力文字列の中で見つかるまで、前記予約ポインタの位置を減らすことであって、前記開括弧文字と前記予約ポインタとの間の全ての文字は、属性文字列を表すことと、
前記属性文字列の一番目の部分および前記属性文字列の二番目の部分を提供するために、区切り文字としてスペース文字を用いて、前記属性文字列を解析することと、
前記属性文字列の前記一番目の部分を廃棄することと、
前記区切り文字として等号を用いて、前記属性文字列の前記二番目の部分を解析することと、
前記連結リスト属性構造の中の属性値ポインタを前記属性文字列の前記二番目の部分の前記等号の後の前記一番目の文字へセットすることであって、属性値長は、前記属性文字列の前記二番目の部分の前記一番目の文字から前記属性文字列の前記二番目の部分の最後にわたることと、
前記区切り文字としてコロンを用いて、前記属性文字列の前記一番目の部分を解析することと
のための複数の命令を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つかる場合、
前記連結リスト属性構造の中の接頭辞名称ポインタを前記属性文字列の前記一番目の部分の中の前記一番目の文字へセットすることであって、接頭辞名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記一番目の文字から前記属性文字列の前記一番目の部分の中の前記コロンに先立つ文字にわたることと、
前記連結リスト属性構造の中の属性名称ポインタを前記属性文字列の前記一番目の部分の中の前記コロンの後の一番目の文字へセットすることであって、属性名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記コロンの後の前記一番目の文字から前記属性文字列の前記一番目の部分の前記最後の文字にわたることと
のための複数の命令を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つからない場合、
前記連結リスト属性構造の中の前記接頭辞名称ポインタをｎｕｌｌポインタとしてセットすることであって、前記接頭辞名称の前記長さは、ゼロであることと、
前記連結リスト属性構造の中の前記属性名称ポインタを前記属性文字列の前記一番目の部分の前記一番目の文字としてセットすることであって、前記属性名称の前記長さは、前記属性文字列の前記一番目の部分の前記長さであることと
のための複数の命令を備え、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成することのための複数の命令は、
前記連結リスト属性構造の中の次属性領域が前記入力文字列の中の前記次の属性を指し示すようにセットすることのための複数の命令を備える請求項１４に記載の製品。
【請求項２５】
データを有する前記複数の連結リストノード構造からデータセグメントを得ることのための複数の命令は、
対応する開始タグおよび終了タグのための前記複数の連結リストノード構造を受け取ることと、
前記開始および終了タグの前記複数の連結リストノード構造が前記データセグメントを決定するために、複数の予約ポインタを使用することであって、前記データセグメントは、前記開始タグの前記予約ポインタおよび前記終了タグの前記予約ポインタの間の前記データを有することと
のための複数の命令を備える請求項１４に記載の製品。
【請求項２６】
前記入力文字列は、ＸＭＬ（拡張可能マークアップ言語）入力文字列を備える請求項１４に記載の製品。
【請求項２７】
複数のマークアップ言語記述を分けるためのシステムであって、
ゼロコピー文字列パーサ、および
前記ゼロコピー文字列パーサに結合されるロジックパーサを備え、
前記ゼロコピー文字列パーサおよび前記ロジックパーサは、入力文字列をメモリにコピーすることなくアプリケーションからの前記入力文字列を解析するために、対話するシステム。
【請求項２８】
前記ゼロコピー文字列パーサは、シングルパスパーサを備える請求項２７に記載のシステム。
【請求項２９】
前記ロジックパーサは、ＸＭＬ（拡張可能マークアップ言語）文字列を解析するために要求されるロジックを備える請求項２７に記載のシステム。
【請求項３０】
前記入力文字列は、前記入力文字列に関連する長さを有し、および前記ロジックパーサは、前記ゼロコピー文字列パーサが前記入力文字列を１つ以上の連結リストノード構造に解析することを可能にするために、区切り文字を前記ゼロコピー文字列パーサに提供する請求項２７に記載のシステム。
【請求項３１】
前記１つ以上の連結リストノード構造は、前記ゼロコピー文字列パーサがさらに複数の連結リスト属性構造を作成するために前記複数のポインタを用いて前記入力文字列を解析することを可能にするために、前記入力文字列への複数のポインタを有し、
前記複数の連結リスト属性構造は、前記入力文字列の中で見つかる１つ以上の属性への付加的な複数のポインタを含む請求項３０に記載のシステム。
【請求項３２】
前記１つ以上の連結リストノード構造は、前記ゼロコピー文字列パーサが前記入力文字列に含まれる要素の中に見つかるデータを得るために前記入力文字列をさらに解析することを可能にするために、前記入力文字列への複数の予約ポインタを備える請求項３０に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広くインターネット技術に関する。より具体的には、本発明は、ＸＭＬ（拡張可能マークアップ言語）パーシングのためのシステムおよび方法に関する。
【発明の開示】
【０００２】
拡張ワイヤレスＰＣ（パーソナルコンピュータ）、ディジタルホーム、およびディジタルオフィスの複数の先駆けは、全てＸＭＬ（拡張可能マークアップ言語）を活用する複数の標準プロトコルに基づく。複数の伝統的なＸＭＬパーサは、複雑であり、複数の組み込み型デバイスにそれほど適していない。多くのデバイスベンダは、ＸＭＬパーシングの複雑さおよびオーバーヘッドのため、これら複数の標準プロトコルを彼らの複数のデバイスの中に実装することの困難さを有している。例えば、現在のパーサは、ＤＯＭ（ドキュメントオブジェクトモデル）およびＳＡＸ（Ｓｉｍｐｌｅ  ＡＰＩ（アプリケーションプログラミングインターフェース）  ｆｏｒ  ＸＭＬ）の２つのカテゴリに分類される。
【０００３】
複数のＤＯＭパーサは、ＸＭＬ文字列を解析し、複数のＸＭＬ要素のまとまりを返すことで動作する。それぞれの要素は、ＸＭＬドキュメントの中の特定の要素に関する情報を有する。これを可能にするには、情報の全ては、返される構造にコピーされなければならない。これは、多くのメモリオーバーヘッドをもたらす。
【０００４】
複数のＳＡＸパーサは、設計において、とてもよりシンプルである。それらは、複数のステートレスフォワードパーサである。つまり、パーサを用いるアプリケーションは、状態を維持するために、ロジックを有さなければならず、アプリケーションに渡される任意のデータは、アプリケーションのメモリバッファにコピーされなければならない。ＳＡＸパーサは、ＤＯＭパーサよりもとてもシンプルな設計であるが、ＳＡＸパーサは、それでも多くのメモリオーバーヘッドを要求する。
【０００５】
したがって、必要とされることは、多くのメモリオーバーヘッドを要求しないＸＭＬを解析するためのシステムおよび方法である。同様に必要とされることは、設計においてシンプルであり、その上、省スペースを要求するＸＭＬを解析するためのシステムおよび方法である。さらに必要とされることは、設計においてシンプルであり、少しのオーバーヘッド要求し、それにより複数のデバイスベンダがＸＭＬパーシングを彼らの複数のデバイスに組み込むことを可能にするＸＭＬを解析するためのシステムおよび方法である。
【図面の簡単な説明】
【０００６】
ここに盛り込まれ、明細書の部分を構成する添付の複数の図面は、本発明の複数の実施形態を説明し、その説明と共に、さらに本発明の複数の原理を説明し、ならびに当業者が本発明を生産するおよび使用することを可能にすることに役立つ。複数の図面で、同様の複数の参照番号は、同一の、機能上同様な、および／または構造上同様な複数の要素を広く示す。要素が最初に現れる図面は、対応する参照番号内の左端の（複数の）桁により示される。
【０００７】
【図１】本発明の一実施形態に従って複数のＸＭＬ文字列を解析するための一例のシステムを説明するブロック図である。
【０００８】
【図２Ａ】本発明の一実施形態に従って複数のＸＭＬ文字列を解析するための一例の方法を説明するフロー図である。
【０００９】
【図２Ｂ】本発明の一実施形態に係る一例の連結リストノード構造を説明する。
【００１０】
【図２Ｃ】本発明の一実施形態に係る一例の連結リスト属性構造を説明する。
【００１１】
【図３Ａ】一例のＸＭＬ文字列を説明する。
【００１２】
【図３Ｂ】本発明の一実施形態に従ってソースＸＭＬをトークン化するための方法を説明する一例のフロー図である。
【００１３】
【図３Ｃ】本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図である。
【図３Ｄ】本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図である。
【００１４】
【図３Ｅ】本発明の一実施形態に係る図３Ａに図示される一例のＸＭＬ文字列のための一例の連結リストノード構造を説明する。
【００１５】
【図４】本発明の一実施形態に従ってＸＭＬ文字列が有効かどうかを判断する一例の方法を説明するフロー図である。
【００１６】
【図５Ａ】本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成する一例の方法を説明するフロー図である。
【図５Ｂ】本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成する一例の方法を説明するフロー図である。
【００１７】
【図５Ｃ】図３Ａの一例のＸＭＬ文字列のための本発明の一実施形態に係る一例の連結リスト属性構造を説明する。
【００１８】
【図６Ａ】本発明の一実施形態に従って開始および終了連結リストノード構造からデータを得るための一例の方法を説明するフロー図である。
【００１９】
【図６Ｂ】本発明の一実施形態に従って図３Ａの一例のＸＭＬ文字列から抽出されるデータを説明する。
【発明の詳細な説明】
【００２０】
本発明は、ここで特定の複数のアプリケーションのための説明に役立つ複数の実施形態への参照を伴い説明されるが、本発明がそれに制限されないことは、理解されるべきである。ここで提供される複数の内容が入手可能な当業者は、その範囲内の付加的な複数の修正、複数の応用、および複数の実施形態および本発明の複数の実施形態が非常に役立つ付加的な複数の領域を認識するだろう。
【００２１】
本発明の明細書中の"１つの実施形態"、"一実施形態"または"他の実施形態"への参照は、実施形態に関連して説明される特定の特徴、構造または特性は、本発明の少なくとも１つの実施形態に含まれることを意味する。したがって、明細書を通してさまざまな場所に現れる複数のフレーズの複数の出現"１つの実施形態において"または"一実施形態において"は、必ずしも同じ実施形態を参照している全てではない。
【００２２】
本発明の複数の実施形態は、大量のメモリオーバーヘッドを要求しないＸＭＬを解析するためのシステムおよび方法に向けられる。本発明は、複数のゼロメモリコピーをを用いることでこれを果たし、これにより、省スペースでとても効果的なパーサを生み出す。本発明の複数の実施形態は、ＸＭＬに関して説明されるが、複数のマークアップ言語の他の複数のタイプも同様に応用可能である。
【００２３】
図１は、ＸＭＬを解析するためのシステム１００を説明する一例のブロック図である。システム１００は、ゼロコピー文字列パーサモジュール１０２およびパーサロジックモジュール１０４を備える。ゼロコピー文字列パーサモジュール１０２は、パーサロジックモジュール１０４に結合される。
【００２４】
ゼロコピー文字列パーサモジュール１０２は、任意のデータをコピーすることなく複数のＸＭＬ文字列を解析することに対して責任がある。ゼロコピー文字列パーサモジュール１０２は、シングルパスパーサであり、したがって、アプリケーションから受信される入力文字列は一度だけ読み込まれる。
【００２５】
図１に示されるように、パーサロジックモジュール１０４は、ゼロコピー文字列パーサモジュール１０２の上部に構築される。パーサロジックモジュール１０４は、ＸＭＬ実体を解析するために要求されるロジックを備える。したがって、パーサロジックモジュール１０４は、ＸＭＬ文字列をメモリにコピーせざる得ないことなく、複数のＸＭＬ文字列を解析するために、ゼロコピー文字列パーサモジュール１０２と対話する。
【００２６】
ゼロコピー文字列パーサモジュール１０２は、解析すべき入力文字列および入力文字列の長さをアプリケーションから受信する。パーシングロジックモジュール１０４は、ゼロコピー文字列パーサモジュール１０２に、解析するための区切り文字を提供し、それにより、ゼロコピー文字列パーサモジュール１０２が文字列をトークン化することを可能にする。それぞれのトークンは、ソースＸＭＬ文字列（すなわち入力文字列）へのインデックスを有し、その値、および値の長さを表す特性を表す。文字列が一旦トークン化されると、複数の連結リストノード構造は、複数のトークンを用いて構築され、複数の連結リスト属性構造は、複数の連結リストノード構造を用いて構築される。複数のノードおよび属性構造は、ソースＸＭＬ文字列への複数のポインタを有する。複数の連結リストノードおよび属性構造は、ソースＸＭＬ文字列に関連する複数のポインタを維持する間、メモリから解放される。複数の構造を削除しながら複数のポインタを維持することは、ＸＭＬ文字列がコピーされなくてはならないことを防ぎ、これにより、メモリオーバーヘッドを最小にする。
【００２７】
文字列のトークン化の後、ゼロコピー文字列パーサモジュール１０２は、それぞれのトークンをパーシングロジックモジュール１０４へ複数の連結リストノード構造を作成するために送る。パーシングロジックモジュール１０４は、複数のトークンを受信すると、トークンの長さおよび区切り文字と共に、ゼロコピー文字列パーサモジュール１０２へ、１回に１つのトークンを返す。ゼロコピー文字列パーサモジュール１０２は、その後、連結リストノード構造のための複数のポインタを得るために、その区切り文字を用いてトークンを解析するこのプロセスは、全てのトークンが適切に解析されるまで続く。複数の連結リストノード構造が一旦作成されると、複数の連結リストノード構造は、ＸＭＬ文字列に含まれる複数の属性への複数のポインタを提供するための複数の連結リスト属性構造を作成するために使用される。同様に、ＸＭＬ文字列内のデータは、複数のポインタを用いて、複数の連結リストノード構造から抽出される。
【００２８】
ＸＭＬ文字列を解析するために、少なくとも５つの区切り文字が使用される。複数の区切り文字は、開括弧"＜"、スペース"  "、コロン"："、等号"＝"、および閉括弧"＞"を含むが、これに制限されない。ロジックパーサモジュール１０４は、複数のトークンを解析し、それぞれのトークンを解析するために、ゼロコピー文字列パーサモジュール１０２へ適切な区切り文字を提供する。複数のＸＭＬ文字列を解析するプロセスは、これから図２Ａを参照して説明される。
【００２９】
図２Ａは、本発明の一実施形態に従って複数のＸＭＬ文字列を解析するための一例の方法を説明するフロー図２００である。本発明は、フロー図２００に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック２０２で始まり、直ちにブロック２０４へ進む。
【００３０】
ブロック２０４では、アプリケーションからゼロコピー文字列パーサモジュール１０２への入力であるＸＭＬ文字列が、複数の連結リストノード構造に変形される。ＸＭＬ文字列内のそれぞれの要素は、開始タグのための１つのノード構造およびエンドタグのための１つのノード構造の２つのノード構造に変形される。
【００３１】
図２Ｂは、本発明の一実施形態に係る一例のノード構造２２０を説明する。ノード構造２２０は、名称領域２２２、名称長領域２２４，名称空間領域２２６、名称空間長領域２２８、開始タグ領域２３０、空タグ領域２３２、予約領域２３４、次領域２３６、親領域２３８、ピア領域２４０、および終了タグ領域２４２を備える。
【００３２】
名称領域２２２は、要素タグの名称を表す。名称長領域２２４は、要素タグの名称の長さを表す。名称空間領域２２６は、要素タグに関連する任意の接頭辞の名称を表す。名称空間長領域２２８は、要素タグに関連する任意の接頭辞の長さを表す。
【００３３】
開始タグ領域２３０は、セットされた場合、要素タグが開始タグであることを示すフラグを表す。開始タグ領域２３０が消去された場合、タグは終了タグである。空タグ領域２３２は、セットされた場合、要素タグが空タグであることを示すフラグを表す。空タグは、それ自身のそばにあるタグである。言い換えれば、空タグは、どの内容をも囲まない。空タグは、閉括弧（すなわち、"＞"）の代わりに、スラッシュおよび閉括弧（すなわち、"／＞"）で終わる。
【００３４】
予約領域２３４は、タグが開始タグの場合、次の閉括弧（すなわち、"＞"）の位置を表す。予約領域２３４は、タグが終了タグの場合、最初の開括弧（すなわち、"＜"）の位置を表す。次領域２３６は、次のノード構造へのポインタを表す。
【００３５】
親領域２３８は、親要素の開要素へのポインタを表す。親要素は、ネスト化された要素を囲む要素である。ピア領域２４０は、ピア要素の開要素へのポインタを表す。ピア要素は、別の要素と同一の場所に配置される要素である。言い換えれば、複数のピア要素は、同じレベルである。例えば、同じ親要素を有する複数の子要素は複数のピア要素である。終了タグ領域２４２は、要素タグの閉要素へのポインタを表す。
【００３６】
図２のブロック２０４に戻って、ノード構造２２０内の特定の複数の領域は、最初に満たされる。これら複数の領域は、名称領域２２２、名称長領域２２４、名称空間領域２２６、名称空間長領域２２８、開始タグ領域２３０、空タグ領域２３２、予約領域２３４、および次領域２３６を含む。名称、名称空間、予約、および次は、ソースＸＭＬ文字列への複数のポインタである。ＸＭＬ文字列から連結リストノード構造を決定する方法は、図３Ｂ−図３Ｄを参照して以下においてさらに説明される。
【００３７】
ブロック２０６において、ＸＭＬ入力文字列のシンタックスは、入力文字列が有効かどうかを判断するために検証される。これは、それぞれの要素が正しく開けられるおよび閉じられるかどうかを検証することで果たされる。複数のＸＭＬドキュメントのための制約は、それらが適格であることである。特定の複数のルールは、ＸＭＬドキュメントが適格かどうかを判断する。１つのこのようなルールは、全ての開始タグは終了タグを有し、終了タグは、開始タグと同じ名称、同じ名称空間等を含まなければならないことである。例えば、＜Ａ：ＥｌｅｍｅｎｔＴａｇ＞と名付けられた開始タグは、＜／Ａ：ＥｌｅｍｅｎｔＴａｇ＞と名付けられた終了タグで終わらなければならない。同様に、全てのタグは完全にネスト化されなければならない。例えば、１つは、＜ＥｌｅｍｅｎｔＴａｇ＞  …  ＜ＩｎｎｅｒＴａｇ＞  …  ＜／ＩｎｎｅｒＴａｇ＞  …  ＜／ＥｌｅｍｅｎｔＴａｇ＞を有し、＜ＥｌｅｍｅｎｔＴａｇ＞  …  ＜ＩｎｎｅｒＴａｇ＞  …  ＜／ＥｌｅｍｅｎｔＴａｇ＞  …  ＜／ＩｎｎｅｒＴａｇ＞ではない。
【００３８】
ＸＭＬ文字列が検証されている間、連結リストノード構造の残りの複数の領域が満たされる。これら複数の領域は、親領域２３８、ピア領域２４０および終了タグ領域２４２を含む。ＸＭＬ文字列のシンタックスを検証するための方法は、図４を参照して以下で説明される。
【００３９】
ブロック２０８において、複数の属性構造の連結リストは、連結リストノード構造から作成される。一例の連結リスト属性構造２５０は、図２Ｃで説明される。連結リスト属性構造２５０は、属性名称領域２５２、属性名称長領域２５４、属性値領域２６０、接頭辞名称領域２５６、接頭辞名称長領域２５８、属性値長領域２６２、および次属性領域２６４を備える。
【００４０】
属性名称領域２５２は、属性の名称を表す。属性名称長領域２５４は、属性名称の長さを表す。接頭辞名称領域２５６は、接頭辞の名称を表す。接頭辞名称長領域２５８は、接頭辞名称の長さを表す。属性値領域２６０は、属性の値を表す。属性値長領域２６２は、属性値の長さを表す。次属性領域２６４は、幾つか存在する場合、次の属性へのポインタを表す。連結リスト属性構造を作成するための方法は、図５Ａおよび図５Ｂを参照して、以下で説明される。
【００４１】
図２Ａに戻って、ブロック２１０において、与えられるノード構造からのデータセグメントが得られる。１つの実施形態では、与えられる要素のデータは、単純な文字列である。１つの実施形態では、与えられる要素のデータは、ＸＭＬサブツリーである。データセグメントの決定は、図６Ａを参照して、以下に説明される。
【００４２】
ブロック２１２において、複数のノード構造連結リストおよび複数の属性構造連結リストは、消去または解放され、元のＸＭＬ文字列への複数のポインタのみを残す。
【００４３】
連結リストノード構造および連結リスト属性構造を作成するための複数の方法を説明するに先立って、これら複数の方法を説明する時に参照される一例のＸＭＬ文字列が説明される。図３Ａは、一例のＸＭＬ文字列３０２を説明する。ＸＭＬ文字列３０２は、"ｕ：ＥｌｅｍｅｎｔＴａｇ"と名付けられた開始タグ３０４、"ｉｄ"と名付けられた属性３０６、"ＴｅｓｔＶａｌｕｅ"と名付けられた属性値３０８、"ＩｎｎｅｒＴａｇ"と名付けられた開始タグ３１０、"ＳａｍｐｌｅＶａｌｕｅ"と名付けられたテキストデータ３１２、"ＩｎｎｅｒＴａｇ"と名付けられた終了タグ３１４、および"ｕ：ＥｌｅｍｅｎｔＴａｇ"と名付けられた終了タグ３１６を備える。それぞれの開始タグ３０４および３１０は、適合している終了タグ３１６および３１４をそれぞれ有する。したがって、それぞれの開始タグは、開括弧"＜"により識別され、各終了タグは、スラッシュが続く開括弧"＜／"により識別される。
【００４４】
図３Ｂは、本発明の一実施形態に従ってソースＸＭＬをトークン化するための方法を説明する一例のフロー図３２０である。本発明は、フロー図３２０に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック３２２で始まり、プロセスは、直ちに、ブロック３２４へ進む。
【００４５】
ブロック３２４において、アプリケーションからのＸＭＬ文字列およびパーシングロジック１０４からの開括弧（"＜"）区切り文字は、ゼロコピー文字列パーサモジュール１０２への入力である。ゼロコピー文字列パーサモジュール１０２は、複数のトークンのリストを得るために、開括弧区切り文字を用いてＸＭＬ文字列を解析する（ブロック３２６）。複数のトークンのリストは、ＸＭＬ入力文字列内のそれぞれのタグの開始を表す。図３Ａからの一例のＸＭＬ文字列３０２を用いて、以下の複数のトークンのリストが返される。（１）ｕ：ＥｌｅｍｅｎｔＴａｇ；（２）ＩｎｎｅｒＴａｇ；（３）／ＩｎｎｅｒＴａｇ；および（４）／ｕ：ＥｌｅｍｅｎｔＴａｇそれぞれのトークンは、ソースＸＭＬ文字列へのインデックスを代表し、その値、および値の長さを表す特性を表す。
【００４６】
ブロック３２８において、複数のトークンのリストは、パーサロジックモジュール１０４へ返される。複数のトークンのリストからのそれぞれのトークンは、別個の連結リストノード構造を作成するために使用され、それは、図３Ｃおよび図３Ｄを参照してさらに説明される。
【００４７】
図３Ｃおよび図３Ｄは、本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図２０４である。本発明は、フロー図２０４に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、図３Ｃのブロック３３０で始まり、プロセスは、直ちにブロック３３２へ進む。
【００４８】
ブロック３３２において、トークンおよびスペース区切り文字（すなわち、"  "）は、パーサロジックモジュール１０４からゼロコピー文字列パーサモジュール１０２への入力である。
【００４９】
ブロック３３４において、トークンは、構造のためのタグ名称を識別するために、スペース（すなわち、"  "）区切り文字を用いて解析される。例えば、トークンｕ：ＥｌｅｍｅｎｔＴａｇ  ｉｄ＝"ＴｅｓｔＶａｌｕｅ"を用いて、ゼロコピー文字列パーサモジュール１０２は、スペース区切り文字を用いて解析し、トークンの２つの部分をパーサロジックモジュール１０４に返す。すなわち、一番目の部分は、ｕ：ＥｌｅｍｅｎｔＴａｇであり、二番目の部分は、ｉｄ＝"ＴｅｓｔＶａｌｕｅ"である。トークンの一番目の部分、ｕ：ＥｌｅｍｅｎｔＴａｇは、常にタグ名称を備える。トークンの二番目の部分、ｉｄ＝"ＴｅｓｔＶａｌｕｅ"は、（複数の）属性を備える。スペースを含まない複数のトークンに対して、ゼロコピー文字列パーサモジュール１０２は、トークンをそのままで返す。この場合、返されるトークンは、一番目のトークンなので、それは、タグ名称を備える。
【００５０】
ブロック３３６において、パーサロジックモジュール１０４は、タグ名称を備える一番目の部分をコロン文字（すなわち、"："）区切り文字と共にゼロコピー文字列パーサ１０２へ送る。コロン区切り文字は、タグのローカル名称から名称空間を抽出するために使用される。
【００５１】
判断ブロック３３８において、タグ名称を備えるトークンの一番目の文字が"／"で始まるかが判断される。タグ名称を備えるトークンの一番目の文字が"／"で始まる場合、タグは、終了タグである。この場合、開始タグは、消去され（ブロック３４０）、一番目の開括弧（"＜"）は、予約ポインタとしてセットされる（３４２）。プロセスは、その後ブロック３４８へ進む。
【００５２】
判断ブロック３３８に戻り、タグ名称を備えるトークンの一番目の文字が"／"で始まらない場合、タグは、開始タグである。この場合、開始タグは、セットされ（ブロック３４４）、次の閉括弧（"＞"）の位置は、予約ポインタとしてセットされる（ブロック３４６）。プロセスは、その後ブロック３４８へ進む。
【００５３】
ブロック３４８において、タグ名称を備えるトークンは、コロン区切り文字を用いて解析される。
【００５４】
図３Ｄの判断ブロック３５０において、タグ名称を備えるトークン内でコロン区切り文字が見つかるかが判断される。トークン内にコロン区切り文字が見つかる場合、コロンの左の全ての文字は、名称空間としてセットされ、コロンの右の全ての文字は、要素のローカル名称またはタグ名称としてセットされる（ブロック３５２）。例えば、解析された場合、開始タグｕ：ＥｌｅｍｅｎｔＴａｇは、"ｕ"を名称空間接頭辞としておよび"ＥｌｅｍｅｎｔＴａｇ"をローカルタグ名称として示す。トークン内にコロン区切り文字が見つからない場合、トークン内の全ての文字は、タグ名称を表す（ブロック３５４）。
【００５５】
ブロック３５６において、タグ名称の長さおよび、存在する場合、名称空間の長さが決定される。
【００５６】
ブロック３５８において、タグ名称および名称空間は、存在する場合、パーサロジックモジュール１０４に返される。ブロック３６０において、トークンの二番目の部分は、ゼロコピー文字列パーサ１０２へ渡される。
【００５７】
判断ブロック３６２において、トークンの二番目の部分の一番目の文字が"／"かどうかが判断される。一番目のトークンの二番目の部分の一番目の文字が"／"であると判断される場合、タグは、空タグであり、プロセスは、ブロック３６４へ進む。
【００５８】
ブロック３６４において、空タグ領域２３２は、セットされる。プロセスは、その後ブロック３６８へ進む。
【００５９】
判断ブロック３６２へ戻って、一番目のトークンの二番目の部分の一番目の文字が"／"でないと判断される場合、プロセスは、ブロック３６６へ進む。
【００６０】
ブロック３６６において、空タグ領域２３２は、消去され、プロセスは、ブロック３６８へ進む。
【００６１】
ブロック３６８において、次領域２３６は、次のタグの開始へのポインタとしてセットされる。例えば、一例のＸＭＬ文字列３０２において、開始タグｕ：ＥｌｅｍｅｎｔＴａｇのための次領域２３６は、ＩｎｎｅｒＴａｇへのポインタである。
【００６２】
図３Ｅは、図３Ａに示される一例のＸＭＬ文字列３０２のための本発明の一実施形態に係る複数の一例の連結リストノード構造を説明する。ＸＭＬ文字列３０２内のそれぞれの開始タグおよび終了タグのための連結リストノード構造が示される。複数の連結リストノード構造の複数の領域からの複数の矢印は、実際のＸＭＬ文字列への複数のポインタを示す。
【００６３】
一番目の連結リストノード構造３７０は、開始タグｕ：ＥｌｅｍｅｎｔＴａｇを代表する。タグ名称は、ＥｌｅｍｅｎｔＴａｇである。ＥｌｅｍｅｎｔＴａｇは、名称長領域２２４に示されるように、長さにおいて１０文字である。名称空間接頭辞は、ｕであり、名称空間長領域２２８に示されるように、長さにおいて１文字である。開始タグは、セットされる。空タグは消去される。予約領域２３４は、開始タグｕ：ＥｌｅｍｅｎｔＴａｇの閉括弧を指し示す。次領域２３６は、ＩｎｎｅｒＴａｇである次のタグを指し示す。終了タグ領域２４２は、／ｕ：ＥｌｅｍｅｎｔＴａｇであるｕ：ＥｌｅｍｅｎｔＴａｇの終了タグを指し示す。
【００６４】
二番目の連結リストノード構造３７２は、開始タグＩｎｎｅｒＴａｇを代表する。タグ名称は、ＩｎｎｅｒＴａｇである。ＩｎｎｅｒＴａｇは、領域２２４に示されるように、長さにおいて８文字である。ＩｎｎｅｒＴａｇは、名称空間を有さない（それは、ＩｎｎｅｒＴａｇ内のコロン文字の欠如によりしめされる）。したがって、名称空間長は、領域２２８に示されるようにゼロ（０）である。開始タグは、セットされる。空タグは、消去される。予約領域２３４は、開始タグＩｎｎｅｒＴａｇの閉括弧を指し示す。次領域２３６は、／ＩｎｎｅｒＴａｇである次のタグを指し示す。ＩｎｎｅｒＴａｇの親は、ｕ：ＥｌｅｍｅｎｔＴａｇである。終了タグ領域２４２は、／ＩｎｎｅｒＴａｇであるＩｎｎｅｒＴａｇの終了タグを指し示す。
【００６５】
三番目の連結リストノード構造３７４は、終了タグ／ＩｎｎｅｒＴａｇを代表する。タグ名称は、ＩｎｎｅｒＴａｇであり、長さは８文字である。前に示したように、ＩｎｎｅｒＴａｇは、名称空間を有さず、したがって、名称空間長はゼロである。開始タグは、消去される。空タグは、消去される。予約領域２３４は、終了タグ／ＩｎｎｅｒＴａｇの開括弧を指し示す。次領域２３６は、／ｕ：ＥｌｅｍｅｎｔＴａｇである次のタグを指し示す。ノード構造３７４は、終了タグを表すので、残りの複数の領域２３８、２４０、および２４２は、空である。
【００６６】
四番目の連結リストノード構造３７６は、終了タグ／ｕ：ＥｌｅｍｅｎｔＴａｇを代表する。タグ名称は、ＥｌｅｍｅｎｔＴａｇであり、長さは１０文字である。名称空間は、ｕであり、長さは１文字である。開始タグは、消去される。空タグは、消去される。予約領域２３４は、終了タグｕ：ＥｌｅｍｅｎｔＴａｇの開括弧を指し示す。ノード構造３７６は、終了タグを表し、ＸＭＬ文字列３０２内の最後のタグなので、次領域２３６、親領域２３８、ピア領域２４０および終了タグ領域２４２は、空である。
【００６７】
図４は、本発明の一実施形態に従ってＸＭＬ文字列が有効かどうかを判断するための方法を説明する一例のフロー図２０６である。本発明は、フロー図２０６に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック４０２で始まり、プロセスは、直ちにブロック４０４へ進む。
【００６８】
ブロック４０４において、スタックは、初期化される。これは、スタックを消去することで果たされる。
【００６９】
ブロック４０６において、連結リストノード構造は、受け取られる。判断ブロック４０８において、連結リストノード構造が開始タグを表すかどうかが判断される。連結リストノード構造が開始タグを表すと判断される場合、プロセスは、判断ブロック４１０へ進む。
【００７０】
判断ブロック４１０において、開始タグがすでにスタック内に存在するかどうかが判断される。開始タグがスタック内にすでに存在する場合、親領域２３８は、スタックの上部の現在のアイテムへのポインタで満たされる（ブロック４１２）。例えば、図３Ａ内のＸＭＬ文字列３０２を用いて、ＥｌｅｍｅｎｔＴａｇは、ＩｎｎｅｒＴａｇの親である。これは、図３Ｅの連結リストノード構造３７２においても同様に示される。プロセスは、その後ブロック４１４へ進む。
【００７１】
ブロック４１０へ戻り、開始タグはスタック内に存在しないと判断される場合（すなわち、スタックは、空である）、プロセスは、ブロック４１４へ進む。
【００７２】
ブロック４１４において、現在の連結リストノード構造の開始タグは、スタック上に置かれる。プロセスは、次の連結リンクノード構造を受信するために、ブロック４０６へ戻る。
【００７３】
ブロック４０８へ戻り、連結リストノード構造が終了タグであると判断される場合、プロセスは、ブロック４１６へ進む。ブロック４１６において、スタックの上部の開始タグは、スタックからポップオフされる。
【００７４】
ブロック４１８において、ポップされた開始タグのピア領域２４０は、現在の終了タグの次領域ポインタ２３６で満たされる。次のＸＭＬ構造は、ピアを説明する。
＜ｕ：ＥｌｅｍｅｎｔＴａｇ  ｉｄ＝""ＴｅｓｔＶａｌｕｅ"＞
＜ＩｎｎｅｒＴａｇ＞ＳａｍｐｌｅＶａｌｕｅ＜／ＩｎｎｅｒＴａｇ＞
＜ＡｎｏｔｈｅｒＴａｇ＞ＡｎｏｔｈｅｒＶａｌｕｅ＜／ＡｎｏｔｈｅｒＴａｇ＞
＜／ｕ：ＥｌｅｍｅｎｔＴａｇ＞
上の例において、ＩｎｎｅｒＴａｇおよびＡｎｏｔｈｅｒＴａｇは複数のピアである。ＩｎｎｅｒＴａｇおよびＡｎｏｔｈｅｒＴａｇは、同様に両方とも、ｕ：ＥｌｅｍｅｎｔＴａｇの子供たちである。プロセスは、判断ブロック４２０へ進む。
【００７５】
判断ブロック４２０において、ポップオフされた開始タグが現在の終了タグに適合するかどうかが判断される。ポップオフされた開始タグが現在の終了タグと適合する場合、ＸＭＬ文字列は、有効な文字列であるとみなされる（ブロック４２２）。言い換えれば、ＸＭＬ文字列のシンタックスは、この時点では、正しい。終了タグ領域２４２は、現在の終了タグで満たされる（ブロック４２４）。
【００７６】
判断ブロック４２６において、現在の連結リストノード構造が現在のＸＭＬ文字列のための最後の構造かどうかが判断される。現在の連結リストノード構造が現在のＸＭＬ文字列のための最後の構造ではないと判断される場合、プロセスは、次の連結リストノード構造を受信するためにブロック４０６へ戻る。
【００７７】
判断ブロック４２６へ戻り、現在の連結リストノード構造が現在のＸＭＬ文字列のための最後の構造であると判断される場合、プロセスはブロック４３０へ進み、プロセスは終了する。
【００７８】
判断ブロック４２０へ戻り、ポップオフされた開始タグが現在の終了タグに適合しないと判断される場合、ＸＭＬ文字列は無効な文字列とみなされる（ブロック４２８）。プロセスは、ブロック４３０へ進み、プロセスは、直ちに終了する。
【００７９】
アプリケーションが与えられる要素内に含まれる複数の属性へのアクセスを望む場合、アプリケーションは、ゼロコピー文字列パーサ１０２に連結リストノード構造を与えてよい。ゼロコピー文字列パーサ１０２は、複数の属性を解析するために、要素の複数の予約ポインタを使用する。ゼロコピー文字列パーサ１０２は、複数の属性構造の連結リストを返し、複数の値の長さを表す複数の特性と同様に属性名および属性値を表すために、これは、元の文字列への複数のポインタを有する。属性解析がアプリケーションにより要求されないので、複数の属性を解析するためにこの方法を使用することは、大多数のケースにとって、より少ないオーバーヘッドをもたらす。同様に、複数の属性が解析される場合、メモリコピーが無く、これは、旧来の複数の解析方法と比べて、より高い性能およびより少ないリソースの使用をもたらす。
【００８０】
図５Ａおよび図５Ｂは、本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成するための一例の方法を説明するフロー図２０８である。本発明は、フロー図２０８に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、図５Ａのブロック５０２で始まり、プロセスは、直ちにブロック５０４へ進む。
【００８１】
ブロック５０４において、開始タグのための連結リストノードは、ゼロコピー文字列パーサ１０２への入力である。
【００８２】
ブロック５０６において、連結リストノード構造からの予約ポインタの位置を用いて、予約ポインタは、ＸＭＬ文字列内に開括弧が見つかるまで、減らされる。開括弧文字から予約ポインタの間の情報は、属性文字列を定義する。
【００８３】
ブロック５０８において、属性文字列は、スペース文字を用いて複数のトークンへ解析される。前に示されたように、一番目のトークンは、タグ名称である。残りのトークンまたは複数のトークンは、幾らかでもあれば、実際の複数の属性である。ブロック５１０において、一番目のトークンは、属性ではないので廃棄される。
【００８４】
ブロック５１２において、残りのトークンまたは複数のトークンは、属性名称を属性値から分離させるために、等号文字を用いて解析される。属性名称は、等号の左の複数の文字の全てに等しく、また、属性値は、等号の右の複数の文字の全てに等しい（ブロック５１４）。
【００８５】
ブロック５１６において、属性名称は、存在するならば接頭辞を得るために、コロン記号（すなわち、"："）を用いて解析される。図５Ｂの判断ブロック５１８において、属性名称内にコロン文字が見つかるかどうかが判断される。コロン文字が見つかる場合、コロンの左の全ては、接頭辞名称としてセットされ、コロンの右の全ては、属性名称としてセットされる（ブロック５２０）。属性名称内にコロン文字が存在しないと判断される場合、ブロック５２２において、全体のトークンが属性名称としてセットされる。
【００８６】
ブロック５２４において、属性名称、属性値、および接頭辞名称の長さが決定される。接頭辞名称が存在しない場合、接頭辞名称の長さは、ゼロにセットされる。
【００８７】
ブロック５２６において、ＸＭＬ文字列内に別の属性が存在する場合、次属性領域２６４は、次の属性へのポインタとしてセットされる。
【００８８】
図５Ｃは、図３Ａの一例のＸＭＬ文字列３０２のための本発明の一実施形態に係る一例の連結リスト属性構造５３０を説明する。図５Ｃに示されるように、唯一の属性、すなわち、ｉｄ＝"ＴｅｓｔＶａｌｕｅ"は、ＸＭＬ文字列３０２に含まれる。連結リスト属性構造５３０内の複数のポインタは、ＸＭＬ文字列３０２内の位置を指し示す複数の矢印を用いて示される。残りの複数の領域２５４，２５８，および２６２は、それぞれ、属性名称、接頭辞名称、および属性値の長さを示す。ＸＭＬ文字列３０２は、１つの属性のみを有するので、次属性領域２６４は、ＸＭＬ文字列３０２内の位置へのポインタを含まない。
【００８９】
アプリケーションが要素内に含まれるデータへのアクセスを望む場合、一つの実施形態では、アプリケーションは、開始連結リストノード構造をゼロコピー文字列パーサモジュール１０２へ与える。開始連結リストノード構造内の複数のポインタを用いて、ゼロコピー文字列パーサモジュール１０２は、終了タグを配置する。他の実施形態では、アプリケーションは、開始および終了連結リストノード構造をゼロコピー文字列パーサモジュール１０２へ与える。ゼロコピー文字列パーサモジュール１０２は、データセグメントを決定するために、パーサ１０２に渡される複数の構造のための開始および終了タグの複数の予約ポインタを使用し、データセグメントをアプリケーションへ返す。
【００９０】
図６Ａは、本発明の一実施形態に従って開始および終了連結リストノード構造からデータセグメントを得るための一例の方法を説明するフロー図２１０である。本発明は、フロー図２１０に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック６０２で始まり、プロセスは、直ちにブロック６０４へ進む。
【００９１】
ブロック６０４において、対応する開始および終了タグのための両方の連結リストノード構造が受け取られる。
【００９２】
ブロック６０６において、開始および終了タグの複数の予約ポインタを用いて、データセグメントは、決定される。開始タグのための予約ポインタは、閉括弧を指し示し、終了タグのための予約ポインタは、開括弧を指し示す。したがって、データセグメントは、これら２つの予約ポインタの間の全てである。図６Ｂは、本発明の一実施形態に従って図３Ａの一例のＸＭＬ文字列から抽出されるデータを説明する。ＩｎｎｅｒＴａｇの開始タグのための予約ポインタ６１０は、ＩｎｎｅｒＴａｇの閉括弧を指し示しており、さらに、／ＩｎｎｅｒＴａｇの終了タグのための予約ポインタ６１２は、／ＩｎｎｅｒＴａｇの開または開始括弧を指し示している。したがって、ＳａｍｐｌｅＶａｌｕｅ６１４は、複数の予約ポインタ６１０および６１２それぞれの間に位置するので、データセグメントである。
【００９３】
ブロック６０８において、データセグメントは、アプリケーションへ返される。
【００９４】
本発明の複数の実施形態の特定の複数の側面は、ハードウェア、ソフトウェア、またはその組み合わせを用いて実装され、１つ以上のコンピュータシステムまたは他の複数のプロセッシングシステム内に実装される。実際、１つの実施形態において、複数の方法は、複数の携帯できるまたは固定されたコンピュータ、複数のパーソナルディジタルアシスタント（ＰＤＡ）、複数のセットトップボックス、複数の携帯電話および複数のページャ、ならびにそれぞれがプロセッサ、プロセッサにより読み込み可能な記憶媒体（揮発性および不揮発性メモリおよび／または複数の記憶要素を含む）、少なくとも１つの入力デバイス、および１つ以上の出力デバイスを備える他の複数の電子デバイスなどの複数のプログラム可能マシン上で実行している複数のプログラムで実装される説明された複数の機能を実行するためにおよび出力情報を生成するために、プログラムコードは、入力デバイスを用いて入力されるデータに適用される。出力情報は、１つ以上の出力デバイスに適用される。当業者であれば、本発明の複数の実施形態は、複数のマルチプロセッサシステム、複数のミニコンピュータ、複数のメインフレームコンピュータ、および同様なものを含むさまざまなコンピュータシステム構成で実行されることを理解するだろう。本発明の複数の実施形態は、同様に、複数の分散コンピューティング環境で実行され、複数のタスクは、コミュニケーションネットワークを介してリンクされる複数のリモートプロセッシングデバイスにより実行される。
【００９５】
それぞれのプログラムは、プロセッシングシステムと通信するために、高水準手続き型またはオブジェクト指向プログラミング言語で実装される。しかしながら、所望されれば、複数のプログラムは、アセンブリまたは機械言語で実装される。どんな場合でも、言語は、コンパイルまたは解釈される。
【００９６】
複数のプログラム命令は、複数の命令でプログラムされる汎用または特定用途プロセッシングシステムにここで説明された複数の方法を実行させるために使用される。あるいは、複数の方法は、複数の方法を実行するためのハードウェアロジックを備える特定の複数のハードウェアコンポーネントにより、または複数のプログラムされたコンピュータコンポーネントおよび複数のカスタムハードウェアコンポーネントの任意の組み合わせにより実行される。ここで説明される複数の方法は、プロセッサシステムまたは他の電子デバイスが本複数の方法を実行するようにプログラムするために使用される複数の命令がそこに記憶される機械可読媒体を含むコンピュータプログラム製品として提供される。ここで用いられる用語"機械可読媒体"または"機械アクセス可能媒体"は、機械による実行のために複数の命令の列を記憶またはエンコードでき、機械にここで説明される複数の方法の任意の一つを実行させる任意の媒体を含む。複数の用語"機械可読媒体"および"機械アクセス可能媒体"は、それ故に、複数の半導体メモリ、複数の光学および磁気ディスク、およびデータ信号をエンコードする搬送波を含むが、制限はされない。その上、どのような形（例えば、プログラム、プロシージャ、プロセス、アプリケーション、モジュール、ロジック等）にせよ、動作を起こすまたは結果をもたらすように技術的にソフトウェアについて言及することは、一般的である。このような複数の表現は、単に、プロセッサに行為を遂行させるまたは結果を生成させるプロセッシングシステムによるソフトウェアの実行を述べる簡単な方法である。
【００９７】
上記において、本発明のさまざまな実施形態が説明されたが、それらは、ほんの例として示され、制限ではないことは、理解されるべきである。添付の複数の請求項に定義される本発明の精神および範囲から逸脱することなく、形式および詳細のさまざまな変更がそこになされることは、当業者には理解されるだろう。したがって、本発明の広さおよび範囲は、上記において説明された例の複数の実施形態のいずれかにより制限されるべきではなく、複数の請求項およびそれらの複数の均等物に従って定義されるべきである。
【図１】
2007514239.tif 000003
【図２Ａ】
2007514239.tif 000004
【図２Ｂ】
2007514239.tif 000005
【図２Ｃ】
2007514239.tif 000006
【図３Ａ】
2007514239.tif 000007
【図３Ｂ】
2007514239.tif 000008
【図３Ｃ】
2007514239.tif 000009
【図３Ｄ】
2007514239.tif 000010
【図３Ｅ】
2007514239.tif 000011
【図４】
2007514239.tif 000012
【図５Ａ】
2007514239.tif 000013
【図５Ｂ】
2007514239.tif 000014
【図５Ｃ】
2007514239.tif 000015
【図６Ａ】
2007514239.tif 000016
【図６Ｂ】
2007514239.tif 000017
【国際調査報告】
2007514239.tif 000018
2007514239.tif 000019
2007514239.tif 000020