パーサー調査
mikiパーサー・構文解析器 (Parser)
決まった文法に基づいて、データを解析して構文木を生成するプログラム
抽象構文木 (AST; Abstract Syntax Tree)
意味的な文法に基づいた構文木
具象構文木 (CST; Concrete Syntax Tree)
実際の文法に基づいた構文木
LL (LL; Left to right, Leftmost derivation)
左から右に読み込み、左から文法規則を適用する
一般化LL (GLL; Generalized LL)
LL法の構文解析をすべての文脈自由文法に拡張した
再帰下降 (Recursive descent)
関数の再帰呼び出しによって文法を再現する
パックラット (Packrat)
解析表現文法を使用する。バックトラッキングをしながら最初に成功した規則を適用する。文字列の位置について、構文解析の結果をキャッシュする
単純順位 (Simple precedence)
それぞれの記号同士で優先順位を決めて、より優先な記号を先に処理する
演算子順位 (Operator precedence)
演算子に優先順位を決めて、より優先な演算子を先に処理する
Pratt (Pratt)
演算子順位+再帰下降
LR (LR; Left to right, Rightmost derivation)
左から右に読み込み、右から文法規則を適用する
単純LR (SLR; Simple LR)
Follow集合を使って衝突を回避をする
LALR構文解析 (LALR; Look-Ahead LR)
マージされた先読み集合を使って衝突を回避する
正規LR構文解析 (CLR; Canonical LR)
先読み集合を使って衝突を回避する
一般化LR (GLR; Generalized LR)
衝突が起きた場合にすべての操作について、適用した場合のスタックを作成する
CYK (Cock-Younger-Kasami)
構文解析表 (Parse Table)
構文解析に必要な表
文脈自由文法 (CFG; Contest-Free Grammar)
解析表現文法 (PEG; Parsing Expression Grammar)
文脈自由文法に似ている
mikiWikipedia:ja
構文解析は、ある言語において、その形式文法に従って記号の文字列を分析する手続きである。
構文解析器とは、構文解析をおこなうプログラム。
形式文法は、形式的に与えられた文法である。
文脈自由文法は、形式言語の理論において全生成規則が以下のようである形式文法である。
V → w
正規文法は、形式文法における右正規文法と左正規文法の総称。
終端記号と非終端記号は、句構造規則の生成規則中にあらわれる記号類の分類である。
トップダウン構文解析は、構文解析において、構文木を、最上位の非終端記号から始めて、それを順次右辺の記号列へと書き換えていくような手順によって導出する構文解析の戦略である。
ボトムアップ構文解析は、構文解析において、構文木を、木の葉に相当する終端記号の列から始めて、それを順次左辺の非終端記号へ書き換え、最終的に最上位の非終端記号を得る、というような手順によって導出する構文解析の戦略である。
再帰下降構文解析は、相互再帰型の手続きで構成されるLL法のトップダウン構文解析であり、各プロシージャが文法の各生成規則を実装することが多い。
情報科学の分野において、 Prattパーサ は文法規則の代わりにトークンの意味ごとに関連付けを作るように改良された再帰下降構文解析のひとつ。
パックラット構文解析とは、PEGにより構文解析を行うアルゴリズムである。
LL法またはLL構文解析とは、文脈自由文法のサブセットのためのトップダウン構文解析法の一種である。入力文字列を左から構文解析していき、左端導出を行う。
LR法またはLR構文解析器とは、文脈自由文法の構文解析手法/構文解析器である。LR法では、入力を左から右に読んでいき、右端導出を行う。
単純LR法とは、文脈自由文法のための構文解析手法である。
LALR法は、構文解析手法の一種であり、Lookahead LR法の略である。
計算機科学において、正規LR法、LR(1)法、正規LR構文解析器、LR(1)構文解析器とは、k=1の場合におけるLR(k)、すなわち、終端記号1つを先読みする構文解析手法/構文解析器である。
GLR法または一般化LR法とは、非決定的で曖昧な文法を扱うようLR法を拡張したものである。
アーリー法は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。
CYK法は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。
mikiWikipedia:en
miki属性文法 佐々政孝
属性文法についての説明をしている
miki
題名 CoStar: A Verified ALL(*) Parser
書いた Sam Lasser、Kathleen Fisher、Chris Casinghino、Cody Roux
内容 ALL(*)法を使ったCoStarというパーサーの説明
miki字句解析機生成機のLexについての説明
miki再帰下降構文解析について説明
mikiPratt構文解析について説明
miki自然言語の学習の話？
mikiLeft-Corner Parsing(左端構文解析？)に関係する？
mikiLL/LRパーサーは曖昧な文法によるあいまいさで難しいことの説明
miki
Rubyで再帰下降構文解析を実装している
CFGではない(A*をwhileで解析している)
miki正規言語のやり方を使うみたい
mikiLR(k)を拡張したLR正規文法の話？
miki
LL(*)パーサー
LL(k)のkを固定せずにおく
miki正規言語とオートマトンについて
miki
名前 Right Nulled GLR Parsers
書いた ELIZABETH SCOTT and ADRIAN JOHNSTONE
右Nullの一般化LR構文解析
miki
名前 Generalized Bottom Up Parsers With Reduced Stack Activity
書いた Elizabeth Scott and Adrian Johnstone
一般化ボトムアップ構文解析器と縮小したスタックアクティビティ
miki
タイトル IELR(1): Practical LR(1) Parser Tables for Non-LR(1) Grammars with Conflict Resolution
書いた人 Joel E. Denny and Brian A. Malloy
IELR(1)法 (Inadequacy Elimination LR(1))について
LR(1)文法より広い範囲を解析できる
Bisonで使われている
miki文法からLALR(1)構文解析表を作るところを例を使って説明している
miki
LR(0)〜LALR(1)の作るところを日本語で書いてある
mikiLL(1)構文解析のやり方が日本語で書いてある
miki
LR(1) (CLR(1))構文解析器を作るところ
miki
LR(1)構文解析に関係する図がたくさん書いてある
mikiコンパイラの説明をしている
miki
タイトル On the Translation of Languages from Left to Right
書いた人 DONALD E. KNUTH
LR(k)の文法のこと
miki
タイトル On the definition of ELR(k) and ELL(k) grammars
書いた人 Stephan Heilbrunner
ELR(k)とELL(k)はLR(k)とLL(k)の右側に正規表現を加えて拡張した(Extended)もの
mikiBison
Yaccの上位互換ソフト
LR(1)の構文解析器を作れるパーサージェネレータ
miki
ANTLR
LL(*)の構文解析器を作れるパーサージェネレータ
miki言語(Language)
文法(Grammar)
構文(Syntax)
mikiS = A;
A = A + M
| M;
M = M * n
| n;
属性文法
- L属性文法
- S属性文法
- LR属性文法
- ECLR属性文法
合成属性と継承属性
mikiSDT Syntax directed translation 構文指示変換
miki合成属性と継承属性
合成属性(Synthesized attributes)は左辺にある非終端記号の属性
継承属性(Inherited attributes)は右辺の非終端記号の属性
miki属性文法の案内
属性文法の基本的な説明
miki佐々政孝
さっささん
mikiS属性文法
合成属性のみを持つ。
L属性文法
合成属性と左から右への継承属性を持つ。
mikiSDD Syntax Directed Definitions
構文指向定義
mikiBNF
文脈自由文法の定義に使われる記法
- 連結
A , BAの後にB - 選択
A | BAまたはB - 省略可能
[A]Aが0回または1回 - 繰り返し
A*Aが0回以上 - 必須繰り返し
A+Aが1回以上 - グループ
(A)A
digit = "0" | "1" ;
digits = "0" | "1" , digit* ;
digits with underscore = digits , ( "_" , digit+ )* ;
- 連結
A BAの後にB - 選択
A / BAまたはB - 省略可能
[A]Aが0回または1回 - 繰り返し
a*bAAがa回以上b回以下 - グループ
(A)A
zero = %x30 ; 0
one = %x31 ; 1
digit = zero / one
digits = zero / ( one *digit )
digits with underscore = digits *( "_" 1*digit )
文脈自由文法
Context-Free Grammar (CFG)
左辺は1個の非終端記号、右辺は0個以上の非終端記号と終端記号の並び
左辺に同じ非終端記号がある生成規則もある
miki曖昧な文法
複数の構文木が同じ文字列を表すことがある文法
mikiBNF → CFGの変換
- 選択
X = A | B ;
X → A
X → B
- 省略
X = [A] ;
X → A
X → ε
(ε(イプシロン)は空の文字列を表す)
- 繰り返し
X = A* ;
X → ε
X → A X
(X → X A も可能)
- グループ
X = (A B) ;
X → X2
X2 → A B
LL法
Left-to-right Leftmost Derivation
文字列を左から右へ読み、左の構文から解析していく
LLの実装
- LL解析表を作成する
- スタックを用意して、$(文字列の終わり記号)、S(開始記号)の順に追加する
- スタックのトップを見て
- 非終端記号なら
- 入力文字列から1つ先読みする
- スタックのトップを取り出す
- LL解析表からスタックのトップと先読みした文字に対応した生成規則を見つける
- 見つけた生成規則を出力し、右辺の記号列を逆順でスタックに追加する
- 見つからない場合、解析エラー
- 終端記号なら
- 入力文字列を1つ読み進める
- 読んだ文字とスタックのトップを比較して、等しいならスタックのトップを取り出す
- 等しくない場合、解析エラー
- $なら
- 文字列が終端の場合、解析を成功して終了
- 終端でない場合、解析エラー
- 非終端記号なら
- 3を停止するまで繰り返す
miki
LL(1)解析表の作成
- すべての生成規則のFirst集合
Fi(w_i) - すべての生成規則のFollow集合
Fo(A_i) - 解析表を作成する
以下の時、表の[A, a]はA→wを持つ- Fi(w) がaを含む
- Fi(w) がεを含み、 Fo(A) がaを含む