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

Category: dev

Tag: parsing parser generator parser lexer

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

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

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

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

自作したパーサジェネレータは https://github.com/Tatamo/parsergenerator にあります。
今のところパーサジェネレータ部分は完成、基本的な構文解析なら問題なくこなせるので構文規則や字句規則を外部から読み取って構文解析してパーサジェネレータに渡すような処理や、全体の見通しを良くするための設計の見直しやリファクタリング等を行っている段階です。 ドキュメント作ってなくてすみません。

構文解析をしたい

構文解析、時々見かけるフレーズです。 プログラマなら覚えておいて損はない技術……かどうかはわかりませんが、そういう類のスキルに(傍からは)見えます。
ぜひやりましょう。

ひとまず、何をやりたいのかを明確にする必要があります。
この記事では、「入力として与えられるLR(1)文法に属する文法に従ったトークン列をパース(構文解析)することで、その構造を構文木として出力する」ことを目標とします。 何を言っているのかさっぱりわかりませんね、わからなくていいです。

順を追って説明する必要がありますが、詳細は適宜省略します。 そのため、まずは今回主に参照した資料を列挙しておきます。

参考資料一覧

より詳しく知りたい方は、下記に挙げる資料やそこで紹介されている参考文献などを参照されるのが良いと思われます。

構文解析とは？(ざっくり)

9 + 11 * (2 + 1) という数式を考えてみます。 構文解析をすることによる最終的な目的は、この数式を(たとえば)文字列として与えると、結果としてこの数式の答えが42であることを導く、といったことです。

そのためには、以下のものが必要になります：

  • 数式を表現する構文規則
  • 上記構文規則を解析するように作られた構文解析器(Parser)
  • 解析された構文を処理するプログラム

さらに、これらの構文解析に入る前の下準備のために以下が必要です：

  • 文字列をトークンとして分割して表現するための字句規則
  • 上記字句規則をもとに、文字列を読み取ってトークンを返す字句解析器(Lexical Analyzer、略してLexer)

ちなみに、今回の記事の目標は、それらに加えて以下のものを実装することです：

  • 構文規則および字句規則を入力として与えることで、構文解析器そのものを自動生成するパーサジェネレータ

実際の構文解析を行う手順とはずれてしまいますが、紹介した順番に沿って構文解析器→字句解析器の順に解説していきます。

構文解析器(パーサ)

9 + 11 * (2 + 1) という数式を解析するためには、まずこの数式がどのようなルールで記述されているのかを(再)定義する必要があります。 そのルールをを表すのが構文規則です。 構文規則を書き表すルールは、たとえばBNFなど様々な種類がありますが、基本的な発想としては

S -> X Y Z

のように左辺の記号を右辺の記号の並びによって定義することで行います。

具体的に見てみましょう。

式 -> 式 "+" 項
式 -> 項
項 -> 項 "*" 因子
項 -> 因子
因子 -> 数
因子 -> "(" 式 ")"

妥当ですね。 式 -> 式 + 項 と 式 -> 項の２つの規則が、再帰的な繰り返しを表現していることに注意してください。 たとえば、項は当然式ですし、項 + 項も式(->項) + 項 より式となります。 さらに、項 + 項 + 項は最初の項 + 項が式なので、式(->項 + 項) + 項 より式です。 よって、式は項を"+"によって任意の回数だけ繋げたものであり、同様に項は因子を"*"で繋げたものとなります。 最後に、因子は単なる数かもしれませんし、または"("と")"で囲まれた式かもしれません。 これは括弧で囲まれた部分の式が他の部分よりも高い優先順位となることを表現しています。

たとえば9 + 11 * (2 + 1)は、

式{ [9] [+] [11 * (2 + 1)] }
式{ 項{ [9] } "+" 項{ [11] [*] [(2 + 1)] } }
式{ 項{ 因子{9} } "+" 項{ 因子{11} "*" 因子{ [(] [2 + 1] [)] } } }
式{ 項{ 因子{9} } "+" 項{ 因子{11} "*" 因子{ "(" 式{ [2] [+] [1] } ")" } } }
式{ 項{ 因子{9} } "+" 項{ 因子{11} "*" 因子{ "(" 式{ 項{ [2] } "+" 項{ [1] } } ")" } } }
式{ 項{ 因子{9} } "+" 項{ 因子{11} "*" 因子{ "(" 式{ 項{ 因子{2} } "+" 項{ 因子{1} } } ")" } } }

のように展開されます(こうして得られた構造をどう解析するかについては省略します)。この、解析対象→構文木の変換を自動で行うのがパーサです。

ちなみにですが、この構文規則は解析したい対象ごとにあなたが一から書き上げる必要があります。

字句解析器(レキシカルアナライザ)

上記構文規則では、+や*のような演算子、数についての規定はありません。 これらの「左辺に現れない記号」を、「終端記号」と呼びます。左辺に現れる記号は非終端記号と呼ばれます。

通常、9 + 11 * (2 + 1) のような入力は文字列で与えられますが、記号と記号の間には複数もしくは0個の空白が挿入されている可能性もあります。 しかし以下のような構文規則を定義するのは本質的ではありません：

空白 -> " "
空白 -> " " 空白
数字 -> "0" | "1" | "2" | ... | "9"
数字 -> ("0" | "1" | "2" | ... | "9") 数字
数 -> ("1" | "2" | "3" ... | "9") 数字
ただし、|は「または」を表す

そこで、通常は「入力として与えられた文字列」を「終端記号として分類されたトークンの列」に変換する処理をはさみ、これによって得られたトークンを構文解析器に与えます。 トークンとは終端記号と、必要ならばそれに紐付いた元々の情報を保持しておいたものです。たとえば、9 + 11 * (2 + 1)は、

数字: 9
プラス: +
数字: 11
アステリスク: *
左括弧: (
数字: 2
プラス: +
数字: 1
右括弧: )

というような9つのトークンの列に分けることができます。 構文解析器はそのトークンがどのような終端記号に対応しているかは見ますが、たとえば個々の数字が何であるかを判断することはしません。 これによって、構文解析器は本質的な文法の解析のみに注力することができます。

この処理をするのが字句解析器で、どのような文字や文字列が与えられた場合に何という終端記号かを判別するための規則が字句規則です。

字句規則は、例えば以下のような書き方になるでしょう：

数字: /[1-9][0-9]*/
プラス: "+"
アステリスク: "*"
左括弧: "("
右括弧: ")"
(読み捨て): /\s/
(不正): /./

ここでは字句規則の表現のために、文字列および正規表現を使用しています。 通常(?)字句規則は上から順に文字列の先頭部分を当てはめていき、マッチするものがあればその終端記号に対応付けます。 そのため、(不正)の部分は入力された文字全てにマッチする正規表現/./が使用されていますが、これは上の規則のいずれにも当てはまらなかった場合にのみマッチします。

与えられた文字列を前から順番に見ていくだけなので、字句解析器の実装はパーサやパーサジェネレータの実装と比べると単純です。

パーサジェネレータ

ここまで構文解析器(パーサ)と字句解析器(レキシカルアナライザ)について見てきました。 基本的にはこの2つによって構文解析を行うことができ、基本的な流れとしては

  1. 入力となるような解析したい言語を用意する
  2. 字句規則を用意して、それをもとにしたレキシカルアナライザを用意する
  3. レキシカルアナライザに入力を与え、トークンの列を取得する
  4. 構文規則を用意して、それをもとにしたパーサを用意する
  5. パーサにトークンの列を与え、解析結果を得る

となります。 パーサジェネレータとは何かというと、この 4. の部分を自動化するものです。 (LR法の)構文解析器は、内部的には入力を受け取ってスタックに積みながら状態遷移を繰り返すオートマトンにすぎません。 そのため、どの入力が与えられればどのような状態に遷移するかを示す「構文解析表」を得ることができれば、その構文を解析するパーサを作成することができます。 パーサジェネレータは、構文規則を読み取ることでこの構文解析表をつくり上げるという処理を主に行います。

字句解析器程度ならわざわざジェネレータを作らなくても、字句規則そのものを字句解析器に渡せば良い感じに字句解析してくれるようにできますが、パーサジェネレータも「構文解析表の構築後、それをもとにして構文解析を行う」ような機能がついていればそれはパーサであるとも言えます。 わざわざパーサとパーサジェネレータが分けられているのは、一つには計算資源の乏しかった昔はパーサジェネレータがオンメモリで展開した構文解析表をもとにそのままパーサとして振る舞うというようなことが少なく、構文解析表を与えることで「パーサのソースコード」を出力するようなものが一般的だったからではないかと思われます(適当な思いつきを言っています)。 もっとも、パーサジェネレータがパーサを生成する際の処理にかかる時間を省略したい場合、予めパーサをコンパイルしておけるようにするのは妥当といえるでしょう。 字句解析器のための「字句解析器ジェネレータ」も実際に存在していますが、ここでは簡単のために字句解析器はコンストラクタに字句規則を与えれば勝手に良い感じの字句解析を行ってくれるようになるものと思ってもらえればよいです。

文脈自由言語について

構文解析器が解析対象とする「言語」がどのようなものであるかについてはいろいろな定義がなされています。

これについては、参考資料でも紹介したうさぎさん(@ki6o4)の

が詳しいため、こちらを参照していただくことをおすすめします。 ここでは、厳密な話はあまりせずにごくごく簡単に触れていこうと思います。

構文解析の対象とするのは、基本的に文脈自由言語となります。 構文解析の手法にも様々なものがありますが、それらの手法の中には文脈自由言語すべてを解析できるわけではないものも多く、たとえばLR(1)法ならLR(1)文法やLR(1)言語というように、ある手法で解析できる文法や、解析できる言語全体をその手法の名前で表される言語として表現することがあります。

解析手法と言語のクラス

いくつかの手法を主観を交えて乱暴に紹介していきます。

先読み

**この項は下のLR法などの項を「先読み」してから戻ってきて読むことをおすすめします**

たとえばLR(1)法のように、数字を括弧でくくって(k)と表現している手法がいくつかあります。このkは何文字先読みするかを示していて、たとえば(1)ならば1文字先読みするという意味です。 先読み数については、たとえばLR法については以下のようなことが言われています。

  1. LR(k)で表せる文法のクラス ⊆ LR(k+1)先読みで表せるクラス である
  2. LR(k)文法によって受理可能な言語のクラスは、LR(1)のそれと等しい

2.より、基本的には(1)について考えることが多いようです。

LL(1)法

「再帰を使って構文解析する」という発想としては単純なもの。 LL(1)文法のクラスはLR(1)よりも大幅に小さいものの、それでもLALR(1)文法を外れた文法を解析できたりします。

S -> S + E

というような、右辺の一番左の場所に左辺の記号が登場するような「左再帰則」を読むことができません。ナンセンス。

LR(0)法

先読み数が0なのでよわい。

SLR法

SLRのSはSimpleの意味です。LR(0)から単純な先読みを加えることでLR(0)よりも解析可能な文法が増えますが、それでもLALR(1)には及びません。

LR(1)法

LR(0)に対し、1文字だけ先読みして次にどのような入力が期待されるかを判断。 LR(1)文法がそれなりに広いという点で優秀な一方、LR(0)に比べて構文解析表の大きさが爆発しやすいという欠点がある、と言われています。 しかし今の時代はそんなものは大した欠点になり得ない気がします。

LALR(1)法

プログラミング言語を解析するコンパイラなどによく使われている手法です。 基本的に先読み数1で行うので、(1)を略してLALR法と呼ばれることも多くあります。 LALR(1)のLAはLook-Aheadの略で、LR(1)法の構文解析表のうち、文法部分が同じで先読み記号だけが違うような状態をマージした構文解析表を使うという特徴があります。 表を併合してしまうためにLR(1)法よりも解析可能な文法のクラスが小さくなるものの、実用上はほとんど問題にならず、LR(1)法の構文解析表が大きくなりすぎるという欠点を補える手法です。

状態数が多くなるLR(1)法の構文解析表を一度作らずとも、直接LALR構文解析表を作ることのできるアルゴリズムも存在しています。

また、LALR法のLAはLook-Aheadの略だと言いましたが、注意しなければならないのはLook-Ahead(先読み)を行うのはLALR法固有の手法ではないということです。 先読み自体はLR(1)法でもやりますし、LALR(1)はあくまでLR(1)の先読み部分をマージしたものにすぎません。 私はLALR法の名前の付け方はあまり良くないと思っていて、MLR法(Merged Look-Ahead LR法)とかなんとか、そういう感じの名前に変えたほうが良いと思います。

GLR法

「あいまいな」解釈が可能な文法があった場合、考えられうるすべての可能性を探索してしまうことによって解決する手法。

「お魚くわえた猫を追いかけるサザエさん」で魚をくわえているのが猫とサザエさんの両方に解釈できるように、一つの入力に対して複数の結果が得られることがあります。 どちらかというと自然言語処理向きかもしれません。

CYK法

強力なアルゴリズムにより、文脈自由言語すべてを比較的高速に解析可能。 ただし、

S -> NP VP
VP -> v

のように、チョムスキー標準形といわれるような、「右辺が非終端記号ちょうど2つか終端記号1つでなければならない」、つまり結果として得られる構造が二分木になっていなければならないというナンセンスにも程がある制約を課されます(アルゴリズムの改良や規則の変換、得られた木構造の後処理などによって回避は可能ですが)。

このCYK法の計算量オーダーはO(n^3)程度で、曖昧性のない文法であればO(n^2)で解析できると言われています。 これは文脈自由言語全てを解析可能なアルゴリズムの中では高速ですが、この記事で紹介されている他のアルゴリズムよりは低速となります。 たとえばLR(1)法は文脈自由言語全体を解析出来ないかわりにO(n)で解析が可能です。

プログラミング言語の解析では、言語の開発者が文法自体をある程度自由に定義することができるため、文脈自由言語の一部だけでなく全体を解析したいという需要はあまり発生しません。

LR(1)パーサジェネレータをつくろう

構文解析の大まかな流れはわかりました。 とりあえず字句規則と構文規則を用意して、あとはどうにかしてこの構文を読んでくれるようなパーサを用意すれば構文解析ができそうです(字句解析器なんてのは適当にやってもすぐ用意できます)。

先ほど紹介したような手法によって構文ごとに一からパーサをプログラミングするようなことはやりたくないので、パーサジェネレータを用いてパーサを自動的に生成してもらえば事は済みそうですね。

ここにBisonという有名なパーサジェネレータがあります。 今の時代にわざわざCやC++で構文解析なんてしたくないのでしたら、PythonでPLYとか、JavaScriptのjisonというものなど、いくらでも選択肢があります。 これらのうち一つを選んで、チュートリアルを読んでパーサを作っていくのがいいでしょう。

というわけで、前段を書いていると結構分量が膨らんでしまったため、今回はここで区切ります。

では次回からは、構文解析を行えるようになるため、LR(1)法を用いたパーサジェネレータを実際に作っていく流れを紹介していきたいと思います。

えっちょっとまって、今パーサジェネレータは既存のものを使えばいいって言ったよね、ねえ

次回:字句解析器の実装