「構文解析器」の版間の差分
削除された内容 追加された内容
Fryed-peach (会話 | 投稿記録) m編集の要約なし |
en:Parsing（2007年4月12日 16:00:40(UTC)）の部分訳をマージ |
||
6行目:
（プログラムの[[ソースコード]]が出力される）。
==構文解析器の種類==
構文解析器の役割は基本的に、開始記号に形式文法の規則を適用することで入力された文字列が得られるかどうかを判定することである。これは次の2種類の手法で行われる:
*[[トップダウン構文解析]] - 構文解析器は開始記号を始点として、それを変換していって入力された文字列を得ようとする。直観的に言えば、まず大きな要素から開始して徐々に細部に分解していく。例えば JavaCC はトップダウン構文解析手法を使っている。
*[[ボトムアップ構文解析]] - 構文解析器は入力された文字列を始点として、それを変換して開始記号に帰結させようとする。直観的に言えば、最も基本的な要素をまず特定し、それを含むより大きな要素、さらに大きな要素、と解析していく。例えば、Yacc はボトムアップ構文解析手法を使っている。
その他の重要な分類法として、構文解析器が「左端導出」なのか、「右端導出」なのかという分類もある（[[文脈自由文法]]参照）。LL法は左端導出であり、LR法は右端導出である（ほぼ正反対である）。
== 構文解析器の例 ==
=== トップダウン構文解析器 ===
[[トップダウン構文解析]]に従った構文解析器を以下に示す:
* [[再帰下降構文解析]]
* [[LL法]]
* [[解析表現文法]](PEG)
* [[末尾再帰構文解析]]
=== ボトムアップ構文解析器 ===
[[ボトムアップ構文解析]]に従った構文解析器を以下に示す:
* [[LR法]]
** [[SLR法]]
** [[LALR法]]
** [[正規LR法]]
** [[GLR法]]
* [[アーリー法]]
* [[CYK法]]
==パーサ開発ソフトウェア==
* [http://www.antlr.org/ ANTLR]
* [[Bison|Bison]]
* [http://www.ssw.uni-linz.ac.at/Research/Projects/Coco/ Coco/R]
* [http://www.devincook.com/goldparser/ GOLD]
* [https://javacc.dev.java.net/ JavaCC]
* [http://www.hwaci.com/sw/lemon/ Lemon Parser]
* [[Lex|Lex]]
* [http://parsetec.com/lrgen/ LRgen]
* [http://www.rebol.com/ Rebol]
* [http://www.sablecc.org/ SableCC]
* [http://spirit.sourceforge.net/ Spirit Parser Framework]
* [[Yacc|Yacc]]
{{comp-stub}}
[[Category:構文解析 (プログラミング)|*こうふんかいせきき]]
[[ca:Analitzador sintàctic]]
[[de:Parser]]
[[
[[
[[fi:Jäsennin]]
[[fr:Analyse syntaxique]]
[[it:Analisi sintattica]]
[[pl:Parser]]
[[pt:Parser]]
[[ru:Синтаксический анализ]]
[[sr:Парсер]]
[[sv:Parser]]
[[ta:இலக்கண பாகுபடுத்தி]]
| |||