C++ 構文解析入門 - プログラミングの教科書を置いておくところ
はじめに 近年、組み込み環境でもスクリプト言語への関心が高まっていますが、そういった言語処理系を書く際に必要となってくるのが字句解析、構文解析です ここでは簡単な再帰下降型のパーサを例に、実際に実装してみながら構文解析について学んでゆきましょう 再帰下降型の構文解析器は単純に実装するとスタックの消費が激しいことやスタック領域の枯渇の予測が難しいことなどであまり実用的なものにはならないのですが、構造が簡単なので構文解析の仕組みを理解するのには向いています （「再帰降下」でも「再帰下降」でもどっちでもいいです。「recursive descent」の訳かな） BNF 式の構造の定義としてＢＮＦ的な表記を用いていますが、別にＢＮＦを知らなくても問題ありません 空文字列（ε）は省略してあります 一部には正規表現的な表記も用いています * は 0回以上の繰り返し、+ は 1回以上の繰り返しを表してい
単項演算子も使えるようにする - プログラミングの教科書を置いておくところ
これまでは負の数を指定する方法がありませんでした 単項演算子をサポートすることで負の数も使えるようにしてみましょう 仕組み 単項演算子も使えるようにしたパーサが処理すべき式は必ず次のような形式になっています 完結式 ::= 部分式_comma 部分式_comma ::= 部分式_add_sub 部分式_comma_ 部分式_comma_ ::= 演算子_comma 部分式_add_sub 部分式_comma_ 演算子_comma ::= ， 部分式_add_sub ::= 部分式_mul_div_mod 部分式_add_sub_ 部分式_add_sub_ ::= 演算子_add_sub 部分式_mul_div_mod 部分式_add_sub 演算子_add_sub ::= ＋ あるいは − 部分式_mul_div_mod ::= 部分式_unary 部分式_mul_div_mod_ 部分式
カンマ演算子も使えるようにする - プログラミングの教科書を置いておくところ
実はカンマ（，）も演算子です このカンマ演算子を使えるようにしてみましょう 仕組み カンマ演算子も使えるようにしたパーサが処理すべき式は必ず次のような形式になっています 完結式 ::= 部分式_comma 部分式_comma ::= 部分式_add_sub 部分式_comma_ 部分式_comma_ ::= 演算子_comma 部分式_add_sub 部分式_comma_ 演算子_comma ::= ， 部分式_add_sub ::= 部分式_mul_div_mod 部分式_add_sub_ 部分式_add_sub_ ::= 演算子_add_sub 部分式_mul_div_mod 部分式_add_sub 演算子_add_sub ::= ＋ あるいは − 部分式_mul_div_mod ::= 定数式 部分式_mul_div_mod_ 部分式_mul_div_mod_ ::= 演算子_mul
足し算、引き算ができるようにする - プログラミングの教科書を置いておくところ
まずは単純に数値の足し算、引き算ができるようにしてみましょう 仕組み パーサが処理すべき式はたぶん次のような形式になっているでしょう 完結式 ::= 部分式 部分式 ::= 数値 演算子 部分式 演算子 ::= ＋ あるいは − 数値 ::= 16進数 あるいは 8進数 あるいは 10進数 16進数 ::= 0x[0-9a-fA-F]+ 8進数 ::= 0[0-7]* 10進数 ::= [1-9][0-9]*「部分式」のところに注目してください 「部分式」の定義に「部分式」自身が含まれていますね つまり定義が再帰的になっているわけです そしてこの定義を上から下へと順番に降りながら解析するので、この手法を「再帰下降型」と呼んでいます このように定義が固まれば後は特に何も考えずにこれをそのまま C++ のコードとして実装すればいいだけです まずパーサに指定されるのは「完結式」の文字列ですから
括弧も使えるようにする - プログラミングの教科書を置いておくところ
演算子の優先順位というものを理解したところで、今度は括弧が使えるようにしてみましょう 仕組み 括弧も使えるようにしたパーサが処理すべき式は必ず次のような形式になっています 完結式 ::= 部分式_add_sub 部分式_add_sub ::= 部分式_mul_div_mod 部分式_add_sub_ 部分式_add_sub_ ::= 演算子_add_sub 部分式_mul_div_mod 部分式_add_sub_ 演算子_add_sub_ ::= ＋ あるいは − 部分式_mul_div_mod ::= 定数式 部分式_mul_div_mod_ 部分式_mul_div_mod_ ::= 演算子_mul_div_mod 定数式 部分式_mul_div_mod_ 演算子_mul_div_mod ::= ＊ あるいは ／ あるいは ％ 定数式 ::= 数値 あるいは ( 部分式_add_sub
コメントも書けるようにする - プログラミングの教科書を置いておくところ
ここまでの入力文字列中に改行を使うことはできましたが、コメントを書くことはできませんでした そこで入力文字列中に C/C++ 風のコメントがあったときはその部分を無視することができるようにしてみましょう 仕組み コメントは式の評価には関係ないので構文解析器の立場からすると空白と同じです 空白を読み飛ばす関数は skipspace ですから、これをコメント対応に改造してみましょう それだけで全体がコメント対応になります 簡単ですね では実装してみましょう 実装 bool string_calc::skipspace(){ char comment = 0; while( !eof()){ char c1 = at( 0, SEEK_CUR ); char c2 = at( 1, SEEK_CUR ); char c = 0; if( comment == '/' ){ c = getch()
構文木を使う - プログラミングの教科書を置いておくところ
ここまでは解析と評価を一度に行ってきましたが、普通は解析処理と評価／実行の処理を分けるようにします 解析処理は入力文字列が文法に合っているかどうかをチェックしながら出現した演算子や数値などの文法要素を評価の順番に並べたリストを作ることを仕事にします この文法要素を繋げたリストは自然にツリー構造となることから、これを構文木と言います 解析処理は文字列を入力とし、構文木を出力とします 評価／実行処理は構文木を入力とします 評価／実行処理の仕事は構文木を辿って結果を得ることです 構文木はその構造自体によって、演算子の優先順位や演算子の右結合性・左結合性といった問題は自明に解決されているので、単純に先頭から順番に辿って行くだけで結果を得られるような仕組みになっています 仕組み 構文木はツリー構造です ツリー構造の各ノードは枝と葉に分かれます 葉のノードでは「値」が必要です 枝のノードでは「演算子」
エラーメッセージに行番号を加える - プログラミングの教科書を置いておくところ
これまでのエラーメッセージでは起きたエラーが何かということは判りましたが、それがどこで起きたのかということは判りませんでした そこでエラーメッセージに行番号を加えてどこで発生したエラーなのかも判るようにしてみましょう 仕組み 解析器で改行を数えます 改行文字は必ず空白なので skipspace に手を加えます ノードのメンバには行番号を追加しましょう ノードの実装 class node { size_t m_lineno; . . . public: size_t get_lineno() const { return m_lineno; } . . . void clear(){ m_lineno = ( size_t )-1; m_operator.clear(); m_operands.clear(); m_value.clear(); } void assign( size_t l
実数も使えるようにする - プログラミングの教科書を置いておくところ
これまでは使える数値は整数だけで実数を指定する方法がありませんでした 実数も使えるようにしてみましょう 仕組み 実数も使えるようにしたパーサが処理すべき式は必ず次のような形式になっています 完結式 ::= 部分式_comma 部分式_comma ::= 部分式_add_sub 部分式_comma_ 部分式_comma_ ::= 演算子_comma 部分式_add_sub 部分式_comma_ 演算子_comma ::= ， 部分式_add_sub ::= 部分式_mul_div_mod 部分式_add_sub_ 部分式_add_sub_ ::= 演算子_add_sub 部分式_mul_div_mod 部分式_add_sub 演算子_add_sub ::= ＋ あるいは − 部分式_mul_div_mod ::= 部分式_unary 部分式_mul_div_mod_ 部分式_mul_div_
プログラミングの教科書を置いておくところ
はじめに C++20 の前の基礎知識として、以前 C++ の名前解決 でも紹介した ADL (Argument-dependent name lookup) に関連した話題を少し紹介してみます ■蛇足 ここで「名前を探す」などと言っているのはすべてコンパイル時の話です コンパイラ内部の話です 実行時に関数を探すようなコードが生成されるわけではありません ADL と関数テンプレート 標準に次のような記述があり、通常の関数テンプレート呼び出しには ADL は適用されるが、テンプレート引数を明示的に指定した場合は他の候補の名前が見えていないと ADL は適用されない（呼び出そうとしている Unqualified name がテンプレート関数だと認識されない）。と言っています N1905 14 Templates 14.8 Function template specializations 14.
解析器と構文木と評価器を分ける - プログラミングの教科書を置いておくところ
前回 0 除算の実行時エラーの処理がノードのクラスにありました ノードのクラスなのに実行時のエラー処理まで持っているのは美しくないですね これはノードのクラスに評価器の機能まで持たせてしまっているのが原因でした 構文木と評価器とは分けてしまいましょう そしてついでなので解析器も分けてしまいましょう 仕組み 解析器は、中身自体は今までの string_calc クラスと同じなのですが、エラー処理を分離するためにコールバック用のインターフェイスを持つようにします そしてエラー時にメンバ関数を呼び出していたところをこのインターフェイスのメソッドを呼び出すように置き換えます 評価器は、評価の仕組み自体は同じなので、ノードにあった評価に関連した機能をそのまま評価器に移してしまえばいいだけです ノードの実装 class node { std::string m_operator; std::list<
Lex - Wikipedia
字句解析はテキスト中の文字列の変換、カウント、抽出などさまざまな目的に使われ、その応用領域は、コンパイラやコンバータの作成を筆頭に、自然言語処理や簡単な整形まで幅広い。 このうち、コンパイラにおけるレキシカルアナライザの位置づけを、以下に説明する。 プログラムを中間言語あるいは機械語に変換するコンパイラは、一般的にソースを入力し構文木を出力する構文解析部(1)と、その構文木を入力し中間言語コードまたは機械語を出力するコード生成部(2)からなる。 コンパイラ ├構文解析部(1) │ ├字句解析器(1.1) ←〔ソース〕 │ │呼出し↑↓ │ │ ↑〔トークン列〕 │ │ ↑↓ │ └構文解析器(1.2) │ ↓ │ 〔構文木〕 │ ↓ └コード生成部(2) →〔中間言語コードまたは機械語〕 このうち(1)の前半は、ソースを入力しトークン（語彙素）列を出力する字句
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Good night, Posterous
記事一覧 - プログラミングの教科書を置いておくところ