タグ

関連タグで絞り込む (1)

タグの絞り込みを解除

pegとalgorithmに関するTKashiwagiのブックマーク (1)

  • Parsing Expression Grammar - Wikipedia

    Parsing Expression Grammar(PEG)は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文(文法)の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「|」(縦棒、バーティカルバー)で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」(「/」であらわす)という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析

    TKashiwagi
    TKashiwagi 2009/03/07
    PEG はそのまま再帰下降構文解析器に変換可能である[要出典]。先読みが無制限に可能であるため、最悪の場合指数関数時間かかる。 解析の途中結果をメモ化し、各構文解析関数が同じ入力位置について高々1回までしか呼ば
  • 1