「構文解析ハンズオン」を開催しました（2017/07/01） - kmizuの日記
今まで、あまり見たことがない（一般エンジニア向け）勉強会で、かつ、これを学ぶことは実用上とても意味があるテーマの一つに「構文解析」があります*1。 たとえば、Webアプリケーションにおいて、ユーザの入力に大して何らかの構文的制約をつけてバリデーションをする機会は多いですが、正規表現による簡単なチェック（あるいは、滅茶苦茶複雑な正規表現を作って色々な入力のバリエーションに対応する）や、よくわからない緩いバリデーションで済まされることは多いように感じます（自分の開発経験というより、Webアプリケーションのフォームのバリデーションの仕方などを見ての感想です）。 正規表現によるバリデーションで十分なことも多いので、それをむやみに否定するものではありませんが、入力が（原理的に）正規表現でバリデーションできない場合や、可能だが正規表現が爆発するケースだと、正規表現が不適当なこともしばしばです。 個人的
Big Sky :: Ruby の a = a + 1 はなぜ undefined method '+' for nil:NilClass なのか
以前からずっと疑問に思っていた事があった。 ruby の後置 if/unless で条件が偽になった場合でも代入構文が実行されるのはどうしてだろう 例えば以下のコードを irb や pry で実行してみて欲しい。 a = 1 if false 続けて a をタイプする。すると nil が表示される。 僕のこれまでの理解だと後置if/unlessは、ステートメントに作用するのでそのステートメント自体が無効になる、つまり代入自体されなかった事になるという理解だった。ruby のパーサのソースコードを見ても後置ifはステートメントに作用している様だった。 | stmt modifier_if expr_value { /*%%%*/ $$ = new_if($3, remove_begin($1), 0); fixpos($$, $3); /*% $$ = dispatch2(if_mod, $
ビジュアル構文解析
プログラミング言語のコンパイラで用いられる構文解析の手法を図解で解説。 演算子順位法・LR法・再帰下降構文解析・Backtrack parsing・Packrat parsing・左再帰を許すPackrat parsingを扱っています。 非常に長いですがパラパラ漫画的な感覚で読んでみてください。Read less
構文解析にまつわる小話たち | κeenのHappy Hacκing Blog
# 構文解析にまつわる小話たち ---------------------- [#peg_study](https://twitter.com/search?q=%23peg_study&src=typd&vertical=default&f=tweets) === # About Me ---------  + κeen + [@blackenedgold](https://twitter.com/blackenedgold) + Github: [KeenS](https://github.com/KeenS) + サイバエージェントの新卒エンジニア + Lisp, ML, Shell Scriptあたりを書きます === # ウォームアップ === # 構文解析はバッドノウハウ -----------------------
Spaghetti Source - 再帰下降型構文解析 ( LL(1) )
説明 再帰下降型構文解析は BNF で与えられた文法を解析する手法である．与えられた BNF を直接書き下すことでパーシングを行うことができる．ここでは LL(1) パーザの例として四則演算パーザを題材に，作成法を示す． 1. BNF を書く 再帰下降型のパーザを書くためには，まず BNF を書かなければならない．BNF でかける文法は二型文法(文脈自由文法)とよばれるクラスになる．これは実用上最も有用なクラスなので，多くの用途にはこれで足りる． 四則演算の BNF は次のようになる．どうせ自分でパーザを書くので BNF のきちんとしたルールに従っていなくても書ける気がすれば適当なルールを追加してよい． equation := equation + factor | factor factor := factor * term | term term := (equation) | Num
LL法 - Wikipedia
$ という特殊な終端記号に関する行があることに注意されたい。$ は入力の終わりを示す。 構文解析手続き[編集] 最初に、構文解析器は入力バッファから '(' を読み込み、スタックから 'S' を読み込む。表を参照すると、規則2を適用すべきであることがわかる。規則2はスタック上の 'S' を '( S + F )' に書き換え、規則番号を出力する。スタックの内容は次のようになる。 [ (, S, +, F, ), $ ] 次に、入力バッファとスタック双方から '(' を取り除く。 [ S, +, F, ), $ ] 次に、入力バッファには '1' があり、スタックのトップが 'S' であることから規則1が適用されて、スタックのトップが 'F' に書き換えられ、さらに規則3が適用される（適用した規則の番号として 1 と 3 が出力される）。スタックは次のようになる。 [ F, +, F, ),
構文解析 Howto
こうぶん、かいせきー 構文解析なんてやるだけゲーです。99%やるだけゲーです。問題はそれがどれぐらい大 きいのかとか、それと複合してほかの問題を解かなければいけない(しかも方程式を解 いたりするものがおおい)とかそんなのばっかです。一問だけ難しい構文解析ゲーがあ りますが、AOJで未だに一人しかACしてないです。そんなの解けなくてもいいです。 ただ、構文解析には人によって、書き方みたいなのがいくつかあるらしくて、基本的な 方針は同じなのに、複雑になっていたりします。このHowtoは複雑なのをできるだけ避 ける書き方をしてみたいと思います。 方針 構文解析というと、字句解析をして、構文木をつくってみたいなガチなのが思いだされ ますが、ICPCで出る構文解析は99%そんなことしなくてもいいはずなので、省きます。 直接文字列をパースして、結果を直接作ります。 例題として普通の四則演算をやりましょ
Racc の使い方
Racc は文法規則から Ruby で書かれたパーサを生成するパーサジェネレータです。 パーサ生成アルゴリズムには yacc などと同じ LALR(1) を使用しています。 yacc を知っている人は記述法の違いだけわかれば使えると思います。 yacc を知らない人は 拙著『Ruby を 256 倍使うための本 無道編』(青木峰郎著、ASCII) などを一読していただくのがよいかと思います。 他の UNIX コマンドなどとは異なり、 いきなり使うだけで Racc を理解するのはかなり困難です。 Racc とはなにか Racc は文法を処理するツールです。 文字列はただの文字の列で、コンピュータにとっては意味を持ちません。 しかし人間はその文字の列の中になにか意味を見出すことができます。 コンピュータにもそのようなことを、部分的にでも、させられたら便利でしょう。 Racc はその手伝いをして
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Introduction to PEG