構文解析器

参考:

構文解析器 – Wikipedia

概要

参考:

構文解析器 – Wikipedia

パーサジェネレータ – Wikipedia

構文解析 – Wikipedia

バッカス・ナウア記法 (BNF / EBNF)

参考:

バッカス・ナウア記法 – Wikipedia

EBNF – Wikipedia

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 個のトークンを先読みする。実用的に使われることはほとんどない。
  • 順位構文解析

参考:

ボトムアップ構文解析 – Wikipedia

トップダウン構文解析

  • LL 法
  • 再帰下降構文解析

参考:

トップダウン構文解析 – Wikipedia

再帰下降構文解析

参考:

JavaScript でゆるく学ぶ再帰下降構文解析 – Qiita

再帰下降構文解析 – Wikipedia

パーサーコンビネーター

参考:

JavaScript でパーサコンビネータのコンセプトを理解する | anatoo のブログ

パーサコンビネータで構文解析をより身近なものにする | mediba Creator × Engineer Blog

左再帰

参考:

左再帰 – Wikipedia

LR法 / LALR 法

参考:

LR(1) パーサジェネレータを自作して構文解析をする 第1回:かんたん構文解析入門 | わたしろぐ

構文解析メモ/LL, LR, LALR, yacc 関連 | Glamenv-Septzen.net

LALR 法 – Wikipedia

What is the difference between LALR and LR parsing? – Stack Overflow

What is the difference between LR, SLR, and LALR parsers? – Stack Overflow

LL 法

参考:

LL法 – Wikipedia

文脈自由文法

参考:

文脈自由文法 – Wikipedia

抽象構文木

参考:

抽象構文木 – Wikipedia

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

入手:

treetop | RubyGems.org

rsec

リポジトリ:

luikore/rsec: Parser / Regexp Combinator For Ruby – GitHub

入手:

rsec | RubyGems.org

kpeg

リポジトリ:

evanphx/kpeg: A simple PEG library for Ruby – GitHub

Racc

リポジトリ:

ruby/racc: Racc is an LALR(1) Parser Generator. It is written in Ruby itself, and generates ruby programs. – GitHub

ドキュメント:

class Racc::Parser | Ruby リファレンスマニュアル [公式]

参考:

Racc – Qiita

Racc の使い方 | LoveRuby.Net Projects

Racc を利用した Prolog ミニパーサ – Qiita

作ろう、ミニ言語 | DoRuby

Racc を使って言語処理系作ってた | platform-echo

strscan

ドキュメント:

library strscan | Ruby リファレンスマニュアル [公式]

参考:

class StringScanner | Ruby リファレンスマニュアル [公式]

Parslet

公式サイト:

Parslet [Official]

リポジトリ:

kschiess/parslet: A Small PEG Based Parser Library – GitHub

JavaScript Parser

Acorn

リポジトリ:

acornjs/acorn: A Small, Fast, JavaScript-Based JavaScript Parser – GitHub

参考:

JavaScript の構文解析をしてみる – Qiita

Esprima

公式サイト:

Esprima [Official]

リポジトリ:

jquery/esprima: ECMAScript Parsing Infrastructure for Multipurpose Analysis – GitHub

Chiffon

リポジトリ:

polygonplanet/Chiffon: A small ECMAScript parser, tokenizer and minifier written in JavaScript – GitHub

デモ:

Demo | Chiffon

参考:

ECMAScript の Parser/Tokenizer (字句解析) を JavaScript で書きました | 圧縮電子どうのこうの

記事をシェアする:

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

Protected by reCAPTCHA