ブラウザよりも高速アクセス！
19 関係: チャートパーサ、チョムスキー標準形、ランダウの記号、ボトムアップ構文解析、パックラット構文解析、嵩忠雄、アルゴリズム、アーリー法、ジョン・コック、動的計画法、確率文脈自由文法、重み付き文脈自由文法、GLR法、IBM 801、構文解析、構文木、決定問題、文字列、文脈自由文法。
チャートパーサ
チャートパーサ（Chart parser）は、自然言語などの曖昧な文法に向いた構文解析器の一種である。動的計画法を用い、中間的かつ仮説的な結果をチャート（chart）と呼ばれるデータ構造に格納しておき、再利用する。これによりバックトラッキングを省き、同時に組合せ爆発を防ぐ。 チャートパーサは Martin Kay が開発した。.
新しい！!: CYK法とチャートパーサ · 続きを見る »
チョムスキー標準形
言語の理論（形式言語の理論）において、次のような生成規則のみからなる文法をチョムスキー標準形（チョムスキーひょうじゅんけい）という。 ここで、A 、 B および C は非終端記号、α は終端記号であり、Sは開始記号を表し、ε は空列を表すものとする。 また、チョムスキー標準形には次のような性質が挙げられる。.
新しい！!: CYK法とチョムスキー標準形 · 続きを見る »
ランダウの記号
ランダウの記号（ランダウのきごう、Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー（Order）から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.
新しい！!: CYK法とランダウの記号 · 続きを見る »
ボトムアップ構文解析
ボトムアップ構文解析（ボトムアップこうぶんかいせき、Bottom-up parsing）は、構文解析において、構文木を、木の葉に相当する終端記号の列から始めて、それを順次左辺の非終端記号へ書き換え、最終的に最上位の非終端記号（たとえば「文」）を得る、というような手順によって導出する構文解析の戦略である。逆はトップダウン構文解析。.
新しい！!: CYK法とボトムアップ構文解析 · 続きを見る »
パックラット構文解析
パックラット構文解析(英：Packrat Parsing)とは、PEGにより構文解析を行うアルゴリズムである。"packrat"はネズミの一種であり、そのネズミの習性に由来して「役に立たなそうなものでも習慣的に集めて持っておく人」という意味でも使われる。.
新しい！!: CYK法とパックラット構文解析 · 続きを見る »
嵩忠雄
嵩 忠雄（かさみ ただお、1930年4月12日 - 2007年3月18日）は日本の計算機科学者。符号理論、形式言語理論、計算理論などの分野に貢献した。.
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: CYK法とアルゴリズム · 続きを見る »
アーリー法
アーリー法（Earley parser）は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。 アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。.
新しい！!: CYK法とアーリー法 · 続きを見る »
ジョン・コック
ョン・コック（John Cocke, 1925年5月30日 - 2002年7月16日）は、アメリカの計算機科学者であり、特にコンピュータ・アーキテクチャとコンパイラの最適化設計への多大な貢献で知られている。「RISCアーキテクチャの父」とも呼ばれる。.
新しい！!: CYK法とジョン・コック · 続きを見る »
動的計画法
動的計画法（どうてきけいかくほう、Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。.
新しい！!: CYK法と動的計画法 · 続きを見る »
確率文脈自由文法
率文脈自由文法（Stochastic context-free grammar, SCFG, Probabilistic context-free grammar, PCFG）は、各生成規則に確率が対応している文脈自由文法である。導出（構文解析）の確率は、その導出で使われた生成規則群の確率の積で表される。従って、導出結果は他の文法よりも確率文法により近い。SCFGの文脈自由文法への拡張は、隠れマルコフモデルの正規文法への拡張と似ている。SCFGは主に自然言語処理とバイオインフォマティクスにおけるRNA分子の研究で利用されている。SCFGは加重文脈自由文法の特殊な形態と言うことができる。.
新しい！!: CYK法と確率文脈自由文法 · 続きを見る »
重み付き文脈自由文法
重み付き文脈自由文法（おもみつきぶんみゃくじゆうぶんぽう、英: Weighted context-free grammar、WCFG）とは、文脈自由文法の一種であり、各生成規則に数値的重み付けがなされているものである。WCFGにおける構文木の重さは、その木の親ノードの生成に使われた生成規則の重さに、その子となっている部分木の重さを加えたもので表される。WCFGは確率文脈自由文法における確率（の対数値）を、重みに一般化したものである。 確率的文脈自由文法と同様、CYK法の拡張版をつかって、与えられた文のうち最も重みが重い（軽い）ものを、最適な構文解釈とみなす使用法が一般的である。 Category:形式言語 Category:数学に関する記事.
新しい！!: CYK法と重み付き文脈自由文法 · 続きを見る »
GLR法
GLR法または一般化LR法（英: GLR parser）とは、非決定的で曖昧な文法を扱うようLR法を拡張したもの（"Generalized LR parser"）である。1986年、冨田勝が発表した。冨田法、並列構文解析法とも呼ばれる。 元々の形から進化し続けているが、その基本は変わっていない。冨田は自然言語を完全かつ効率的に構文解析することを目標としている。標準のLR法では自然言語の非決定的で曖昧な性質に対処できないが、GLR法では可能である。.
IBM 801
IBM 801は、1970年代にIBMが設計したRISCマイクロプロセッサアーキテクチャである。その成果は1980年代になってIBMの中で様々な役割を演じることとなった。 801は トーマス・J・ワトソン研究所の801ビルで ジョン・コックの統括の元に純粋な研究プロジェクトとして始められた。 彼らは、既存のIBMのマシンの性能を向上させる手段を探していた。そのためにシステム/370メインフレーム上でのプログラムの動作をトレースし、コンパイラコードを研究していた。 このプロジェクトから、非常に高速で非常に小さいプロセッサコアを作ることが可能だというアイデアが導き出された。 そして、いかなるマシンのマイクロコードもその上で実装できる。 プロジェクトはそれをCPUとして設計する方向に向かった。 その結果できたCPUは1977年に15MIPSという速さで動作した。 これは370メインフレーム用チャネル・コントローラを含むIBMの様々なデバイスで使用された。 そして9370メインフレームのCPUコアとしても使用されるに至った。 1980年代初頭、801の経験はアメリカプロジェクトに引き継がれ、そこからPOWERアーキテクチャが誕生したのである。 ジョン・コックは後に801に関する功績を認められ、チューリング賞（1987年）とアメリカ国家科学賞を獲得した。 801.
新しい！!: CYK法とIBM 801 · 続きを見る »
構文解析
構文解析（こうぶんかいせき、syntactic analysis あるいは parse）とは、文章、具体的にはマークアップなどの注記の入っていないベタの文字列を、自然言語であれば形態素に切分け、さらにその間の関連（修飾-被修飾など）といったような、統語論的（構文論的）な関係を図式化するなどして明確にする（解析する）手続きである。自然言語については自然言語処理における要点のひとつであり、プログラミング言語など形式言語の場合は、形式文法に従い構文木を得る。構文解析を行う機構を構文解析器（parser）と呼ぶ。.
構文木
構文木（こうぶんぎ）とは、構文解析の経過や結果（またはそれら両方）を木構造で表したもの。.
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.
文字列
文字列（もじれつ）は、単語や文章のような、文字の連なったもの。ストリング (string)、テキスト (text) という場合もある。コンピュータ、特にプログラミングの分野で用いることが多い。.
文脈自由文法
文脈自由文法（ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG）は、形式言語の理論（特に、生成文法）において全生成規則が以下のようである形式文法である。 ここで V は非終端記号であり、w は終端記号と非終端記号の（0個を含む）任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できる、という所から来ている（「文脈無用」という訳の提案もある）。文脈自由文法によって生成される形式言語を文脈自由言語という。.
新しい！!: CYK法と文脈自由文法 · 続きを見る »
