前回ではLR(1)法による構文解析表の実装を済ませました。 今回はいよいよ、構文解析表をもとに実際に構文解析を行うことのできる構文解析器を実装し、実際に構文解析を行ってみます。

前回の記事ではLR(1)法の解説を行いました。 今回は前回解説した部分の実装を行います。

前回で構文解析器を生成する際に必要となる準備を済ませたため、LR(1)法ベースのパーサジェネレータを作る用意が整いました。 ですが相変わらず本題のパーサジェネレータ作成には入らず、まずはLR(1)法のおおまかな理論的概略の紹介を行います。

前回は字句解析器の作成を行ったので、次にLR(1)法による構文解析のためのパーサジェネレータの作成に入っていきます。 今回は、LR(1)構文解析器の構築のために必要な、終端記号と非終端記号の区別、Nulls集合、First集合の導出等を行えるようにしていきます。

前回は構文解析の概略を紹介したので、今回から実装に移っていきたいと思います。 まずは字句解析器を用意する必要があるため、今回は字句解析器の作成について紹介します。

なお今回から実際のプログラムを記述していきますが、使用言語はTypeScriptとします。

この記事はKobe University Advent Calendar 2016の21日の記事です。また遅刻か。 なお私は当該大学の学部2年(2016年12月現在)です。

構文解析ができるプログラマはちょっとかっこいいですよね。 「構文解析？ああ、できますよ」とか言って自分のスキルを自慢できそうな印象があります。

(ほぼ)フルスクラッチでTypeScriptによるLR(1)パーサジェネレータを実装した(ついでにLALR(1)パーサも作れる)ので、これを完成させるまでの流れを紹介していこうと思います。

今回は構文解析自体の入門編となります。