簡単な文法分析器

4月12日
基本的には完成していますが、文章はすでに発表されています.http://blog.csdn.net/lishuhuakai/article/details/70140914
4月10日
これは私が想像していたよりはるかに簡単です.正直に言うと、一ヶ月もかかりません.一週間で七七八八八八日になると思います.だから、人は、自分の想像力に驚かないでください.すべてはそんなに難しくありません.3月23日には、必ず一年かけて、簡単なyaccを叩いて、4月4日には、私はこのyaccを完成するのに1ヶ月で十分だと思います.今、4月10日、もう1週間来れば十分だと思います.だから、ほら、面白いですね.
ところで、これをやり終えたら、これから何をするつもりですか.少なくともこの小型のProjectを完成してから、仕事を探す前まで、私はもうしばらくの時間をかけて別の小型のプロジェクトをするのは難しいと思います.もちろん、定かではありません.1ヶ月以上前の頭が熱くなったように、yaccと正規式のコンボを作りたいと思っています.それから、何も考えずに1ヶ月以上もいたずらをしました.この味は、今思い出しても十分酸っぱいです.
次の时间の中で、もし头が热くなることができるならば、更に良くて、発达できないならば、大规模な复习を开くことができて、整理して、データの构造を読んで、一歩一歩自分の标准のライブラリを実现し始めて、アルゴリズムを読んで、ブラシleetcode、ブラシtemplate、事はいつもあって、いつもやりきれません.
全体的に、仕事を探す準備が必要です.
4月7日
時間は本当に流れる水のようで、今日少し良くなって、どのようにこの簡略化版のyaccを実現することに対して、私はほとんどすでに成竹が胸にあって、残りの、毎日少したたくことしかできなくて、毎日少したたくことができて、少しの時間と力を費やしてゆっくりとこのものを完成します.书くのは本当に大変です.细かい点がたくさんありますから、简単なほどいいです.とにかく3000~4000の性质のDemoです.
4月6日Projectの検索テーブルを構築するコードはすでに完成しており、次はテキストに読み込むルールを実現しようとしている.
4月5日LALR(1)とc++セットの検索を完了したアルゴリズムは、FIRSTテーブルの構築アルゴリズムを実現している.半分まで書くと、書きたくないので、一周旅行に出かけた.
2017年4月4日清明節の記録
まあ、この文章もあまり読んでいませんが、私はいっそ開発の状態、開発時にツッコミを入れたいものを全部ここに書きました.
前回正規表現エンジンを書き終わってからまたしばらく経って、3月23日から4月4日まで、この中で約12日ほど間隔を置いて、ここ数日、私は暇ではありません.いっそ前学期に落ちた`FOLLOWを読みましたが、実は全部読んでいません.LALR(1)という部分を読んで、個人的にはこの部分を読むのは本当に十分だと思います.これらの知識はすでに1つの核心版の< Parsing Technology -- A Practical Guide>を実現するのに十分なので、本を読む間、ついでに見た大部分のアルゴリズムはすべて1回実現して、LALR(1)、yacc、LL(1)、LR(0)、その他の各種のものがあります.今、どのように1つのLR(1)を実現するかについて、私は基本的に底があります.
くだらないことは言わないで、明日から、1ヶ月の时間で十分だと思います.私は比較的完璧な小型のyaccを書くことができます.最初のバージョンでは、文法定義のファイルを読んで、文法のメモリの中の表現を構築して、文法に基づいてyacc表を構築するつもりです.この中には必ず正規表現が使われます.しかし、私はしばらく自分が前に書いた正規表現を使うつもりはありません.LALR(1)が存在する可能性があるので、bug標準ライブラリに用意されている正規表現を使ってからにしましょう.
最初のバージョンはあまりカスタマイズされた構造を使用しませんが、後続の再構築されたバージョンでは、私は必ず自分が定義したいくつかの容器に参加しなければなりません.なぜなら、c++の容器は、本当に需要を満たすことができません.相応の機能を実現するために、私は大きなコードを書かなければなりません.非常に美しくありません.最初のバージョンはまず機能を実現してからにしよう.次に、自分が書いたこの正規表現エンジンを強化し、stlの正規表現を置き換えます.
結局、私の大学院生の間、コード量が最も大きく、持続時間が最も長いプロジェクトは、これです.
より簡潔なstl(2017年3月23日)
正規表現を文法ツリーにする方法は興味深い問題です.これまでのいくつかのバージョンではスタック計算機の原理を使っていましたが、正規表現の変換にも成功しましたが、汎用性が悪く、特殊な処理が必要な点が多く、デバッグに時間がかかりました.だからこの書き方はあまりお勧めではありません.
だから、私は1つの更に简単なparserを実现して、上から下へ、再帰的に分析して、このような方法はコンパイルの原理の中でいつも使って得て、核心の思想はあなたが事前に正则の表现の文法を书いて、难しいのはただ文法を书くだけで、プログラムは纯粋に文法によって书いて、とても简単で、通用性も良くて、その上正则の表现の文法もとても简単で、もちろん、私が書いたのはparserだけで、最も核心的なものはすでに実現して、もっと多くの細部は私も管理するのがおっくうです.
このようにしましょう、今年の下半期に仕事を探す前に、1つのdemoを完成することを望んで、このようにすれば、研二は悔いがありません.
バージョン3(2017年3月20日更新)
このバージョンの機能は基本的に実現されていますが、非常に小さなyaccが修理されています.今書いているものを見ていると、書くのが不快で、コードはきれいに書けるはずです.
本当のことを言うと、このバージョンの正規表現を書くのは確かに少し難しいですが、まあ、これを書くことで多くのことを学ぶことができて、全方位にコード能力を鍛えることができて、よし、何日かbugを修理して、それから載せましょう.
今はあまり書きたくありません.残りは角のあるものなので、難易度は高くありませんが、時間がかかるので、しばらく置いておきました.プロジェクトは元の住所にあります.https://github.com/lishuhuakai/Regular-Expression
バージョン2(2017年3月16日更新)
最初のバージョンは機能を実現したが、コードがきれいではないので、bugでもう一度実現しました.採用したアルゴリズムも元のアルゴリズムではありません.具体的にはcppの<>と<>の中のアルゴリズムを参考にしましたが、今は純粋な正規式のマッチングを実現しただけです.コードはここにあります.https://github.com/lishuhuakai/Regular-Expression
コードの可読性は非常に向上し、その2つの文章を参照すれば、コードを読むのはあまり難しくないと信じています.基本的にはすべて中のアルゴリズムを使っているからです.
拡張の正規マッチングについては、vczhの2つの文章を引き続き参考にして、実現を続けます.いいでしょう.実はアルゴリズムはもう読みました.実現はあまり難しくありませんが、今はしばらく時間がありません.しかし、2週間以内に、私は<>の中で提案した様々な機能を実現します.それはバージョンvczhと言えるでしょう.
バージョン1
コードは約1000行程度でC++を用いて記述されており、実現する機能は主に正規式を1本の二叉木に変換し、その後この二叉木の構造について再帰的にNFAを構築し、Thompsonの方法でこのNFAをDFAに変換することである.だから後のHopcroftアルゴリズムがDFAを最小化するのはあまり意味がないかもしれませんが、勝手に私はこのアルゴリズムを包みました.しかし、私もHopcroftアルゴリズムを完全に実現しました.
もちろん、正規サポートは不完全であり、*、|、()および接続操作のみをサポートします.しかし、一般的には、残りの正規式はこの3つのものの文法糖にすぎない.もちろん、ここには正則的なエラーチェックはありません.必ず正則的な正しさを保証してください.そうしないと、予想できないエラーが発生する可能性があります.
IDEはVS 2013を使っていますが、もちろん移植しやすく、C++標準ライブラリのいくつかの構造しか使いませんでした.ネット易雲教室の中のコンパイル原理課程を見ることをお勧めします.本はコンパイラの設計を使っています.
コードはここにあります.https://github.com/lishuhuakai/Compiler/tree/master/hw03!