目次
14 関係: 字句、幅優先探索、プログラミング言語、パーサジェネレータ、アーリー法、オンラインアルゴリズム、スタック、冨田勝、CYK法、自然言語、英語、LR法、文脈自由文法、曖昧な文法。
- 構文解析アルゴリズム
字句
字句（じく）とは、プログラミング言語などにおいてソースコードに出現する文字列の中で意味を持つ最小単位であり、トークン（token）とも言う。 詳細は言語によって異なるが、一般的には、以下のようなトークンがある。
見る GLR法と字句
幅優先探索
ドイツの都市間の接続を示した例 フランクフルトから幅優先検索を行った場合にできる木構造 幅優先探索（はばゆうせんたんさく、breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。 幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。
見る GLR法と幅優先探索
プログラミング言語
プログラミング言語（プログラミングげんご、）とは、プログラムを記述するための人工言語。コンピュータプログラムを書くために考案された、正確に定義された記号と規則のしくみ。以前は、しばしばプログラム言語と表記された。
パーサジェネレータ
パーサジェネレータ（parser generator）は、構文解析器(解釈)を作成するプログラムである。
アーリー法
アーリー法（Earley parser）は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。 アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。
見る GLR法とアーリー法
オンラインアルゴリズム
オンラインアルゴリズム（Online algorithm）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していけるアルゴリズムを指す。これに対して、オフラインアルゴリズム（Offline algorithm）は、問題を解くのに最初からデータ全体へのアクセスが必要なバッチ処理型アルゴリズムを指す。例えば、挿入ソートはオンラインアルゴリズムで、選択ソートはオフラインアルゴリズムである。 また、時系列データをリアルタイムに処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。
スタック
スタック（）は、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。 特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。
見る GLR法とスタック
冨田勝
冨田 勝（とみた まさる、1957年12月28日 - ）は、日本の生命科学者、計算機科学者。慶應義塾大学環境情報学部学部長、慶應義塾大学先端生命科学研究所所長を歴任して、慶應義塾大学名誉教授、（一社）鶴岡サイエンスパーク代表理事。ヒューマン・メタボローム・テクノロジーズ（株）創業者。Ph.D.（情報科学）、工学博士、医学博士、政策·メディア博士。父は作曲家の冨田勲。姉は妹尾理恵。 言語処理や人工知能を専門としていたが、後に生命科学に転じ、細胞シミュレーションソフトウェアE-Cellや、CE-MSによる新規のメタボローム測定法等を発表。システムバイオロジー研究・メタボローム解析の分野で第一人者となった。
見る GLR法と冨田勝
CYK法
CYK法（CYK algorithm）は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略（それぞれ、RISCの先駆と言われる801などでも知られるジョン・コック、Daniel Younger、嵩忠雄である）。文脈自由文法の構文解析手法と捉えることもできる。このアルゴリズムは一種の動的計画法である。 標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。
見る GLR法とCYK法
自然言語
自然言語（しぜんげんご、natural language）とは、言語学や論理学、計算機科学の専門用語で、「英語」・「中国語」・「日本語」といった「○○語」の総称。つまり普通の「言語」のこと。人間が意思疎通のために日常的に用いる言語であり、文化的背景を持っておのずから発展してきた言語。 対義語は「人工言語」「形式言語」、すなわちプログラミング言語や論理式など。
見る GLR法と自然言語
英語
英語（えいご、 、anglica）とは、インド・ヨーロッパ語族のゲルマン語派の西ゲルマン語群・アングロ・フリジア語群に属し、イギリス・イングランド地方を発祥とする言語である。
見る GLR法と英語
LR法
LR法またはLR構文解析器とは、文脈自由文法の構文解析手法/構文解析器である。LR法では、入力を左(Left)から右に読んでいき、右端導出(Rightmost derivation)を行う。このためLRと名づけられている。「LR(k)」といった場合、k は、消費をともなうことなく「先読み」が進められる入力記号の最大数を意味する。通常、k は 1 であり、その場合省略されることが多い。LR(k)の構文解析器が対応する文脈自由文法も LR(k) と呼ばれる。
見る GLR法とLR法
文脈自由文法
文脈自由文法（ぶんみゃくじゆうぶんぽう、、CFG）は、形式言語の理論（特に、生成文法）において全生成規則が以下のようである形式文法である。 ここで V は非終端記号であり、w は終端記号と非終端記号の（0個を含む）任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できる、という所から来ている（「文脈無用」という訳の提案もある）。文脈自由文法によって生成される形式言語を文脈自由言語という。
見る GLR法と文脈自由文法
曖昧な文法
曖昧な文法（あいまいなぶんぽう、ambiguous grammar〈直訳すると「多義的な文法」〉）とは、構文木が唯一にならないかもしれない文法のことである。ここでは、自然言語は文法自体が不確かであることが多いため、そうではない形式言語に議論を限定するが、自然言語にも同様なことを考えることは可能である。形式言語的な文法を持つ言語が「本質的に曖昧である」とは、その言語を生成できるような文法は曖昧な文法にならざるをえないということである。 以下では、議論を統語（syntax）の曖昧性（ambiguity）に限定し、さらに用語として「文法」ではなく「統語」を使うことができる文脈ではできるだけ「統語」を使う。
見る GLR法と曖昧な文法