第 5 回コンパイラコンパイラ

本日の内容

5-1. 拡張バッカスナウア記法
5-2. コンパイラコンパイラ
5-3. 数式処理

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

前回はバッカスナウア記法により文脈自由文法を記述し、さらに、その文法を処理するパーサをプログラムで作成する方法に関して議論しました。今回はまず、よく使われるバッカスナウア記法の拡張表記を説明します。その後、 Python で文脈自由文法を処理するコンパイラコンパイラである Lark を紹介します。

5-1. 拡張バッカスナウア記法

基本的なバッカスナウア記法では右辺に終端記号、非終端記号の連接の表現しかありませんでした。拡張バッカスナウア記法は、連接以外に正規文法の記法である、選択と繰り返しを指定できるようにしたものです。選択は |(縦棒) で右辺の表現を列挙します。一方、繰り返しに関しては多くの表現方法があります。本質的には次に示す一部が可能であれば、他の表現を実現できますが、よく使われる表現を紹介します。

(表現)*: 表現の 0 回以上の繰り返し
{表現}: 表現の 0 回以上の繰り返し
(表現)?: 表現を 0 回または 1 回
[表現]: 表現は記述しても省略してもよい(0 回または 1 回)
(表現)+: 表現の 1 回以上の繰り返し

なお、このような表記を使うため、今後、文法表記で終端記号をルールに含めるときは "" (ダブルクォーテーションマーク)で囲むことにします。

例5-1

足し算の文法 G₁ は以下の通りでした。

\begin{matrix} 和 \to 和 " + " 数 \\ 和 \to 数 \end{matrix}

これを拡張バッカスナウア記法で記述すると次のようになります。

和 \to 和 " + " 数 | 数

例5-2

G₁は左再帰性がありました。これを除去するには、繰り返し構造を見抜いて、繰り返し構文で記述します。

和 \to 数 (" + " 数) *

さらに、式の最後に =(イコール)記号をつけた文法を示します。これを G₃ とします。

和 \to 数 (" + " 数) * " = "

5-2. コンパイラコンパイラ

Lark

バッカス・ナウア記法を与えて、それを処理するプログラムを出力する処理系をコンパイラコンパイラと言います。 Python 用のコンパイラコンパイラに Larkというモジュールがあります。 Lark は構文解析も字句解析もできます。 Lark の基本的な利用法は、文脈自由文法を定義した文字列からパーサを生成します。そして、そのパーサに入力文字列を与えると、構文解析木を自動的に生成し返します。

Lark を使用する際は、パッケージをインポートして、Larkコンストラクタに、 Lark のパーサのソースを文字列で与え、また、開始ルールを指定することでパーサーが作られます。パーサのソースはPython のプログラム内に記述しても良いのですが、 Python とは別文法ですので、ここでは別ファイルで与えることにします。拡張子を .lark にすると、主要なエディタで Lark モードがサポートされていて、アシストを受けることができます。

Lark 自体はパーサに文字列を与えると、構文解析木を返すものです。その構文解析木を使用して実際に別の出力を得るために、 Visitor, Transformer, Interpreter の各クラスが用意されています。いずれもデザインパターンのビジターとして動作しますが、 Visitor では子ノードへのアクセスするのに対して、 Transformer は再帰的に処理をします。 Interpreter は逆に各子ノードは visit メソッドを明示的に呼び出すように作られているため、細かい処理を指定することができます。ここでは Transformer を使用した処理を示します。

例5-3

rei53.lark


start: token*
token: TOKEN
TOKEN: /\S/
%ignore /\s/

\sは空白文字（改行なども含む）、\Sは空白以外の文字を表します。

rei53.py


from lark import Lark,Transformer

class MyTransformer(Transformer):
    def token(self,args):
        print("Hello World")

with open("rei53.lark",encoding="utf-8") as grammar:
    parser = Lark(grammar.read(),start="start")

tree=parser.parse("1 2 34 567")
print(tree)
print(tree.pretty())
t=MyTransformer()
t.transform(tree)

このようにLark では文法をLarkコンストラクタに与えてパーサーを作り、 Visitorの継承クラスを作ることで、文字列を解釈して出力を得る仕組みを作ることができます。

次章以降では、以下の順に解説をします。

文法の与え方
構文解析木のコントロール
構文解析木の処理

Larkの文法

Lark のドキュメントは Documentation @readthedocs にまとまっています。ここでは、講義で使用するため、一部のみ紹介します。

終端記号

終端記号の名前は大文字で始めます。コロンで区切って右側には "(ダブルクォート) でくくった文字列か、/(スラッシュ)でくくった正規表現を書きます。


EQOP : "="    
NUM : /[1-9][0-9]*/

ルール(非終端記号)

ルール名は小文字で書きます。コロンで区切って右側には、ルール、終端記号、"(ダブルクォート)でくくった文字列を使った拡張バッカスナウア記法で記述します。 |(縦棒)で区切れば次の行にも定義を続けられます。なお、ε(空列)の使用は認められてないので、例えば、

A \to α | β | ε

を記述するときは、0回または 1回を意味する ?(クエスチョンマーク)を使い、 a: ( α | β)? と記述します。


sum : NUM sum2    
sum2 : ( "+" NUM sum2 )?

ディレクティブ

Lark には処理系に様々な指示をするディレクティブが用意されています。 %ignore は、処理を無視する文字を指定します。


%ignore "\n" | "\r" | " "

例5-4

rei54.lark


PLUSOP : "+"
EQOP : "="    
NUM : /[1-9][0-9]*/
start : sum EQOP
sum : NUM sum2    
sum2 : ( "+" NUM sum2 )?
%ignore "\n" | "\r" | " "

rei54.py


from lark import Lark

with open("rei54.lark",encoding="utf-8") as grammar:
    parser = Lark(grammar.read(),start="start")

tree=parser.parse("1+2+3=")
print(tree)
print(tree.pretty())

Lark の生成する構文木

Lark の生成する構文木は次のような構造になっています。

Tree(Token('RULE', 'start'), [Tree(Token('RULE', 'sum'), [Token('NUM', '1'), Tree(Token('RULE', 'sum2'), [Token('PLUSOP', '+'), Token('NUM', '2'), Tree(Token('RULE', 'sum2'), [Token('PLUSOP', '+'), Token('NUM', '3'), Tree(Token('RULE', 'sum2'), [])])])]), Token('EQOP', '=')])

また、この構文木は lark.Tree 型で、pretty() メソッドを持っていて、視覚的に木構造に見えるように整形した出力も可能です。

start
  sum
    1
    sum2
      +
      2
      sum2
        +
        3
        sum2
  =

後に、構文木のフォーマットをコントロールするために、次のようなルールの記法を用いることができます。

構文木に表示されるのは、ルール、終端記号、終端記号として解釈された文字列。逆にルール中の文字列は構文解釈木には表示されない
ルール名の前に?(クエスチョンマーク)を書くと、子ノードをそのまま親ノードに送るようなルールは省略されます
ルール定義行の最後に -> をつけてその後に名前をつけると、構文解釈木にはその名前が代わりに表示されます。

例5-5

rei55.lark


start : term*
?term : term1 | term3
term1: term2 -> term5
term2 : "a"
term3: TERM4 -> term6
TERM4: "b"
%ignore "\n" | "\r" | " "

rei55.py


from lark import Lark

with open("rei55.lark",encoding="utf-8") as grammar:
    parser = Lark(grammar.read(),start="start")

tree=parser.parse("ab")
print(tree)
print(tree.pretty())

出力例

Tree(Token('RULE', 'start'), [Tree('term5', [Tree(Token('RULE','term2'), [])])1,
Tree('term6', [Token('TERM4', 'b')])])
start
  term5
    term2
  term6 b

term2 の "a" はルール内に書かれた文字列なので、構文木には現れない。 term ルールは term1 または term3 に分岐しますが、子ノードを親ノードに送るだけなので、?が名前の前についているため、構文解析木に現れない。 term1 は term5, term3 は term6 として構文解析木に現れる。

Lark の構文木の処理

Lark に付属している Transformer を用いた構文木から出力を得ることを考えます。 Transformer クラスを継承したクラスを作成し、メソッドとして、self と values を引数とした、ルール名をそのまま名前としたメソッドを定義します。各メソッドでは、ルールの各要素の値がvalues の配列の要素として得られ、最後にそこから計算した値を return で返します。

例5-6

rei56.lark


PLUSOP : "+"
EQOP : "="    
NUM : /[1-9][0-9]*/
start : sum EQOP
sum : NUM sum2    
sum2 : ( PLUSOP NUM sum2 )?
%ignore "\n" | "\r" | " "

rei56.py


from lark import Lark, Transformer

class MyTransformer(Transformer):
    def start(self, values):
        return values[0]
    def sum(self, values):
        result = int(values[0])
        if len(values)==2:
            result += values[1]
        return result
    def sum2(self, values):
        if len(values)==0:
            return 0
        return  int(values[1])+values[2]

with open("rei56.lark",encoding="utf-8") as grammar:
    parser = Lark(grammar.read(),start="start")

tree=parser.parse("1+2+3+4=")
print(tree)
print(tree.pretty())
t =MyTransformer()
print(t.transform(tree))

5-3. 数式処理

本章では Lark による数式の処理を考えます。

足し算

足し算の文法として下記の G₃ を Lark に与えます。

和 \to 数 (" + " 数) * " = "

例5-7

rei57.lark


PLUSOP : "+"    
KAZU : /[1-9][0-9]*/
wa : KAZU ( PLUSOP KAZU)* "="
%ignore "\n" | "\r" | " "

rei57.py


from lark import Lark,Transformer

class Show(Transformer):
    def wa(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result = f"({result}{i}{j})"
        return result
class Rpn(Transformer):
    def wa(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result += f" {j} {i}"
        return result
class Eval(Transformer):
    def wa(self, values):
        result = int(values[0])
        for i,j in zip(values[1::2], values[2::2]):
           result += int(j)
        return result
        
with open("rei57.lark",encoding="utf-8") as grammar:
    parser = Lark(grammar.read(),start="wa")

tree=parser.parse("1+2+3=")
print(tree)
print(tree.pretty())
print(Show().transform(tree))
print(Rpn().transform(tree))
print(Eval().transform(tree))

Showクラスは中置記法による表示、Rpnクラスは逆ポーランド記法による表示、 Evalクラスは実際に式の値を計算するクラスです。それぞれに、ルール名のメソッドを持ちます。ルールが解釈されると、そのルールの文字列を除いた要素がvalues配列の要素に順に置かれます。Transformer クラスでは、その値はあらかじめその先のクラスで呼び出しが行われ、値に変換したものが得られます。繰り返しなどで処理をする場合に、複数個をループ内で同時に使用したい場合は、配列を個別に飛ばして組にするためzip関数を使用します。つまり、 zip(a[0::3],a[1::3],a[2::3]) で、(a[0],a[1],a[2]),(a[3],a[4],a[5]),... というデータ構造が作られます。

積和

次に足し算と掛け算の混ざった式を考えましょう。計算は積項の和をとることで行いますので、 G₃ を書き換えた次の文法を G₄ とします。

和 \to 積 (" + " 積) * " = "

積 \to 数 (" * " 数) *

なお、数について、単独のルールを設けるとVisitorでメソッド呼び出しができるようになります。すると、文字列のままとしても、データとしての数として取り扱うこともできるようになります。

例5-8

rei58.lark


PLUSOP : "+"
MULOP : "*"
KAZU : /[1-9][0-9]*/
wa : seki ( PLUSOP seki)* "="
seki : num ( MULOP num)*
num: KAZU
%ignore "\n" | "\r" | " "

rei58.py


from lark import Lark,Transformer

class Show(Transformer):
    def wa(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result = f"({result}{i}{j})"
        return result
    def seki(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result = f"({result}{i}{j})"
        return result
    def num(self, values):
        return values[0]
class Rpn(Transformer):
    def wa(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result += f" {j} {i}"
        return result
    def seki(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result += f" {j} {i}"
        return result
    def num(self, values):
        return values[0]
class Eval(Transformer):
    def wa(self, values):
        result = int(values[0])
        for i,j in zip(values[1::2], values[2::2]):
           result += int(j)
        return result
    def seki(self, values):
        result = int(values[0])
        for i,j in zip(values[1::2], values[2::2]):
           result *= int(j)
        return result
    def num(self, values):
        return int(values[0])


        
with open("rei58.lark",encoding="utf-8") as grammar:
    parser = Lark(grammar.read(),start="wa")

for test in ["2+3+4=","2*3*4=", "2+3*4=", "2*3+4="]:
    tree=parser.parse(test)
    print(tree)
    print(tree.pretty())
    print(Show().transform(tree))
    print(Rpn().transform(tree))
    print(Eval().transform(tree))

カッコ付きの式

さらに括弧の処理を考えます。括弧の中にはどんな式も入ります。一方括弧はその中の値を計算したら、計算の対象となる値として数と同じように扱われます。今まで「数」という終端記号を使ってきましたが、ここで「値」というルールを導入します。そして、値については、数かまたはカッコで括った式かを選ぶようにします。なお、丸かっこについてはVisitorで処理する必要が無いので、構文木に現れないように、ルールの中に文字列として埋め込みます。

値 \to 数 | " (" 和 ") "

また、かっこの中に和を入れるため、=記号を和から取り除いて、スタートルールに「和 =」とするようにします。このルールをG₅ とします。

始 \to 和 " = "

和 \to 積 (" + " 積) *

積 \to 値 (" * " 値) *

値 \to 数 | " (" 和 ") "

例5-9

rei59.lark


PLUSOP : "+"
MULOP : "*"
KAZU : /[1-9][0-9]*/
?start : wa "="
wa : seki ( PLUSOP seki)*
seki : atai ( MULOP atai)*
?atai: num | "(" wa ")"
num: KAZU
%ignore "\n" | "\r" | " "

rei59.py


from lark import Lark,Transformer

class Show(Transformer):
    def start(self,values):
        return values[0]
    def wa(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result = f"({result}{i}{j})"
        return result
    def seki(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result = f"({result}{i}{j})"
        return result
    def atai(self, values):
        return values[0]
    def num(self, values):
        return values[0]
class Rpn(Transformer):
    def start(self,values):
        return values[0]
    def wa(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result += f" {j} {i}"
        return result
    def seki(self, values):
        result = values[0]
        for i,j in zip(values[1::2], values[2::2]):
           result += f" {j} {i}"
        return result
    def atai(self, values):
        return values[0]
    def num(self, values):
        return values[0]
class Eval(Transformer):
    def start(self,values):
        return values[0]
    def wa(self, values):
        result = int(values[0])
        for i,j in zip(values[1::2], values[2::2]):
           result += int(j)
        return result
    def seki(self, values):
        result = int(values[0])
        for i,j in zip(values[1::2], values[2::2]):
           result *= int(j)
        return result
    def atai(self, values):
        return values[0]
    def num(self, values):
        return int(values[0])
        
with open("rei59.lark",encoding="utf-8") as grammar:
    parser = Lark(grammar.read(),start="start")

for test in ["2+3+4=","2*3*4=", "2+3*4=", "2*3+4=", "(2+3)*4=", "2+(3*4)="]:
    tree=parser.parse(test)
    print(tree)
    print(tree.pretty())
    print(Show().transform(tree))
    print(Rpn().transform(tree))
    print(Eval().transform(tree))

演習5-1

引き算、割り算を付加した文法を示しなさい。
引き算、割り算も処理し、構文解析木を出力するプログラムを作りなさい。

演習5-2

構文解析木を受け取り、計算を行うプログラムを作成しなさい。

演習5-3

入力に自然数だけでなく、整数を許す数式計算プログラムを実現しなさい。

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 5 回 コンパイラコンパイラ