構文解析器
参考：
概要
参考：
バッカス・ナウア記法 (BNF / EBNF)
参考：
PEG
参考：
Parsing Expression Grammar – Wikipedia
ボトムアップ構文解析
shift-reduce 構文解析とも呼ばれる。トークンをスタックに移す shift アクションあるいは生成規則を適用する reduce アクションのどちらかを選択しながら構文解析を実行する。
- LR 法
- LR(0)：トークンの先読みを行わない。
- SLR(1)：トークンを1つ先読みする。Follow-set を用いて構文解析表における衝突を解決する。
- LALR(1)：Lookahead-set を使って reduce アクションを構築する。
- LR(1)：理論的に全ての決定性文脈自由言語を扱うことができる。実装が複雑になりメモリを大量に必要とするため避けられてきた。
- LR(n)：n 個のトークンを先読みする。実用的に使われることはほとんどない。
- 順位構文解析
参考：
トップダウン構文解析
- LL 法
- 再帰下降構文解析
参考：
再帰下降構文解析
参考：
JavaScript でゆるく学ぶ再帰下降構文解析 – Qiita
パーサーコンビネーター
参考：
JavaScript でパーサコンビネータのコンセプトを理解する | anatoo のブログ
パーサコンビネータで構文解析をより身近なものにする | mediba Creator × Engineer Blog
左再帰
参考：
LR法 / LALR 法
参考：
LR(1) パーサジェネレータを自作して構文解析をする 第1回:かんたん構文解析入門 | わたしろぐ
構文解析メモ／LL, LR, LALR, yacc 関連 | Glamenv-Septzen.net
What is the difference between LALR and LR parsing? – Stack Overflow
What is the difference between LR, SLR, and LALR parsers? – Stack Overflow
LL 法
参考：
文脈自由文法
参考：
抽象構文木
参考：
Ruby
参考：
Which library to write a parser – Ruby-Forum
資料
文法と言語／文脈自由文法とLL構文解析 – SlidePlayer
何となく勉強した気分になれるパーサ入門 – SlideShare
Parsimmon
リポジトリ：
jneen/parsimmon: A monadic LL (infinity) parser combinator library for javascript – GitHub
Treetop
リポジトリ：
cjheath/treetop: A Ruby-based parsing DSL based on parsing expression grammars – GitHub
入手：
rsec
リポジトリ：
luikore/rsec: Parser / Regexp Combinator For Ruby – GitHub
入手：
kpeg
リポジトリ：
evanphx/kpeg: A simple PEG library for Ruby – GitHub
Racc
リポジトリ：
ドキュメント：
class Racc::Parser | Ruby リファレンスマニュアル [公式]
参考：
Racc の使い方 | LoveRuby.Net Projects
Racc を利用した Prolog ミニパーサ – Qiita
Racc を使って言語処理系作ってた | platform-echo
strscan
ドキュメント：
library strscan | Ruby リファレンスマニュアル [公式]
参考：
class StringScanner | Ruby リファレンスマニュアル [公式]
Parslet
公式サイト：
リポジトリ：
kschiess/parslet: A Small PEG Based Parser Library – GitHub
JavaScript Parser
Acorn
リポジトリ：
acornjs/acorn: A Small, Fast, JavaScript-Based JavaScript Parser – GitHub
参考：
Esprima
公式サイト：
リポジトリ：
jquery/esprima: ECMAScript Parsing Infrastructure for Multipurpose Analysis – GitHub
Chiffon
リポジトリ：
デモ：
参考：
ECMAScript の Parser/Tokenizer (字句解析) を JavaScript で書きました | 圧縮電子どうのこうの