PLY (Python Lex-Yacc) で作る Algol 60 処理系

2008.9.26 - 2008.10.17 - 2008.12.8 - 2009.2.17 (鈴)

1. はじめに

D. M. Beasley 氏による PLY (Python Lex-Yacc) を使えば LALR による構文解析器を Python で簡単に作ることができます。 ここでは Algol 60 を例にとって実際に処理系を作ってみようと思います。

2. Algol 60 とは

Algol 60 とは 1960 年頃に設計された手続き型のプログラミング言語です。 プログラムを再帰的な入れ子構造で構成する最初期のプログラミング言語のひとつであり, 本格的に静的スコープ則を採用した最初のプログラミング言語のひとつでした。

たまたま記法を数学から借りただけの,いわば「なんちゃってラムダ」だった当時の Lisp にも影響を与え,近代的な Scheme および Common Lisp が生まれるきっかけになりました。

手続きへの引数渡しには call-by-value と call-by-name が選ぶことができました。 call-by-name による引数渡しは,今の目からみると,ある制限された形式のクロージャ渡しとみなせます。 呼出し時点での環境を伴った getter 関数と setter 関数のペアを渡すものとして実装できます。 クロージャをファーストクラスの値として扱わないため,変数の寿命を限定でき,スタックによる効率的なメモリ管理が可能です。 また,再帰呼出しや構造化制御文のほか,switch 宣言による Fortran ライクな計算型 goto もありました。

call-by-name の例は上記の E11.txt にあります。 Trapezion((1 - x) / (1 + x * x), x, 1e-6) の 実引数 (1 - x) / (1 + x * x) は,呼出し元の変数 x を含む環境を伴った無引数のラムダ式のように渡されます。 実引数 x は変数引数のように渡されます。

電子計算機が発明されてまだ間も無いころ,Algol に携わった人々は未来への力を無限に信じ, 技術的な限界を恐れずに野心的な設計に挑戦したのでしょう。 しかし,結局,今日一般に後継言語とみなされる Pascal は当時効率良い実装方法を暗中模索していた call-by-name を,ブロックその他の機能とともに切り捨てました。 BCPL から C は,ブロックは保持したものの,call-by-name と静的スコープによる入れ子の関数定義を事実上切り捨てました。

そして今,クロージャは,手続き型言語に採り入れるべき最新流行の機能となっています。 現代のプログラミング言語の進化とは,ある面では,かつてあきらめた夢を,格段に強力になった 計算機環境のもとで再び実現していく過程だといえるかもしれません。

しかし,だからといって Algol 60 は決して伝説的な上古の理想言語ではありません。 今の目からみると,大規模プログラムのためにプログラムを系統的にライブラリ化する機能は ありませんし,繰返しを表現する for 文の構文は複雑で洗練されていません。 文字列リテラルはありますが,引数としてしか使えません。 実際の文字列処理は,より低水準な言語で実装する必要があります。 コメントは構文上,特定の箇所にしか書けません。 そして,もっとも致命的な弱点として,データ構造は配列しかありません。 後続の Algol 68 や C の struct,Pascal の record にあたるものを欠いています。

これらの弱点をもって Algol 60 を「きれいな Fortran 66」と形容できるかもしれません。
また意外にも,言語の基本設計の観点からみると,Algol 60 の特徴を切り捨てることなく最もよく引き継いだ言語は,実は Scheme です。 Scheme は名目上は call-by-name を持ちませんが,クロージャを渡すことで同等の処理を記述できます。 Scheme の最大の拡張は,(メモリ管理の複雑さと引き換えに) クロージャを一般化し,格納したり,戻り値と することを可能にした点です。 Scheme の改訂報告書が Algol 60 の 改訂報告書 (1963) のパロディのようになっているのは,先人に対するリスペクトにほかならないのでしょう。
なお,Scheme が最近まで系統的なライブラリ化の機能を持たず,レコード ないし構造体を直接定義できなかったこともまた Algol 60 を見習ったこと…なのかどうかは不明です。

Algol 60 は言語の規模としては Scheme と同程度ないし一回り小さい一方,言語の構文としては, いわば保守本流にあたるため,今,構文解析を含む言語処理系づくりの題材として取り上げるには妥当なものといえます。 Algol は名前だけが広まって残り,手続き型言語の神秘的な祖語として半ば伝説化されているきらいがありますが, その是正にも有用でしょう。 Algol 60 のプログラム例を下記に示します。

  begin
    comment
      入力された整数に対して階乗を計算する。
      負数が入力されたら終了する;

    integer procedure Fac(k);
      value k; integer k;
      begin
        if k = 0 then Fac := 1
                 else Fac := k * Fac(k - 1)
      end Fac;

    integer n;
  LOOP:
    read(n);
    if n < 0 then goto EXIT;
    print(n, Fac(n));
    goto LOOP;
  EXIT:
  end

2.1 Algol 60 修正報告書

Algol 60 についての資料として Web 上の ALGOL 60 References (http://www.masswerk.at/algol60/), その中でもとりわけ Algol 60 修正報告書 (Modified Report on the Algorithmic Language Algol 60, 1976) を使うことにします。

報告書が定義する字句表現は印刷用の参照表現 (reference representation) であり, 具体的な実装ではこれとは別にハードウェア表現 (金物表現,hardware representation) を決める必要があります。 参照表現では,キーワードを下線で示したり,識別子の途中に自由に空白や改行を入れたり, ≠ や ≦ や ¬ などの記号を使ったりします。 古典的なハードウェア表現は Algol 60 - Sample Implementation and Examples にみることができますが, ここでは今風に Pascal や Ada に近い表現を採ることにします。 その要点は次のとおりです。

古典古代のラテン語に小文字がなく,U が V と分かれていなかったからといって, ラテン語の lingua (言語) を今さら当時に合わせて LINGVA とは書かないことと同じようなこと,といってよいかもしれません。

Algol 60 修正報告書 の 4.5.1 節 にはちょっとしたミスがあります。 そこでは条件 (付き) 文,つまり if 文の構文を次のように定義しています。

<if clause> ::= if <Boolean expression> then

<unconditional statement> ::= <basic statement> |
        <compound statement> | <block>

<if statement> ::= <if clause> <unconditional statement>

<conditional statement> ::= <if statement> |
        <if statement> else <statement> |
        <if clause> <for statement> |
        <block>: <conditional statement>

ここで最後の行にある <block>: <conditional statement> は,このとおりに受け取れば非常に奇妙な規則です。 これは,より古い Algol 60 改訂報告書の 該当箇所 にある <label>: <conditional statement> (条件付き文にラベルを付けるための構文規則) の転写ミスだと考えれば,意味がとおります。

3. PLY の導入

PLY は,字句解析器ジェネレータ lex に相当するモジュールと,構文解析器ジェネレータ yacc に相当するモジュールの二つから構成されています。 Python だけで書かれたパッケージですから導入は簡単です。

PLY の Web ページ から PLY-2.5 のソース ply-2.5.tar.gz をダウンロードします。 適当なディレクトリに展開して python setup.py install します。

$ gzcat ply-2.5.tar.gz | tar xf -
$ cd ply-2.5
$ python setup.py install

Python のライブラリ・ディレクトリの site-packagesply というディレクトリが作られ, __init__.pylex.pyyacc.py とそれぞれそのバイトコンパイルされた *.pyc ファイルが置かれます。

あるいはこのように「インストール」せずに,ply-2.5.tar.gz の展開結果である ply-2.5 の下にある ply ディレクトリを, 環境変数 PYTHONPATH が指す場所,またはカレントディレクトリに そっくりコピーして使うこともできます。

4. 字句解析

Lexer.py は Algol 60 用の字句解析器です。 そのクラス Lexer では一定の書式で字句解析ルールを記述します (次節参照)。 さらに,上位の構文解析器から利用される公のメソッドとして,入力ソースの文字列を指定する input(self, text) と,次のトークンを返す token(self) を定義します。 input(self, text) メソッドは,ply.lexlex 関数に自分自身のオブジェクト,つまり self を与えることによって内部的な字句解析器 self.lex を構成します。 両メソッドはこうして構成した self.lex に処理を委譲します。

import ply.lex
……
class Lexer:

    …… 字句解析ルールの記述 (次節参照) ……

    def token(self):
        return self.lex.token()

    def input(self, text):
        self.lex = ply.lex.lex(object=self)
        self.line_head_pos = 0
        self.lex.input(text)

    def test(self, text):
        try:
            self.input(text)
            while True:
                tok = self.token()
                if not tok:
                    break
                print tok
        except SyntaxError, ex:
            print ex

必ずしも不可欠ではありませんが,単体テストの便宜のため test(self, text) メソッドも用意します。 Algol 60 のソースを文字列で与えると,読み取ったトークンを次々と印字します。 下記のように,Lexer.py をモジュールではなく 単体のスクリプトとして実行したとき,簡単な単体テストが行われるようにします。

if __name__ == '__main__':
    lex = Lexer()
    lex.test("""
    foo(a, b) bar:(c); 
    value real integer Boolean boolean
    begin comment a b c && d & jjj;
    print(`this is' `a `string'');
    for a := 10e3, .567, 2.0
    = /= < > <= >= [] a*b**c
    end 1 end 2; 
    """)

このテストで与える文字列は Algol 60 の様々な字句を並べたもので,Algol プログラムとしては無意味です。 python 2.3.5 でも python 2.5.2 でも下記の実行結果になります。

$ python Lexer.py
LexToken(IDENTIFIER,'foo',2,5)
LexToken(LPAREN,'(',2,8)
LexToken(IDENTIFIER,'a',2,9)
LexToken(COMMA,',',2,10)
(中略)
LexToken(IDENTIFIER,'b',7,188)
LexToken(POWER,'**',7,189)
LexToken(IDENTIFIER,'c',7,191)
LexToken(END,'end',8,197)
LexToken(END,'end',8,203)
LexToken(SEMICOLON,';',8,208)
$

LexToken(IDENTIFIER,'foo',2,5)IDENTIFIER (識別子) であって,そのテキストが foo,2 行目,(文字列全体の先頭から) 5 文字目の字句トークン であることを意味します。

4.1 字句解析ルールの記述

クラス Lexer では,可能なトークンを表すリスト tokens と,t_ で始まる一連のメンバで字句解析ルールを記述します。

    tokens = [
        'POWER', 'COLONEQUAL', 'NOTEQUAL', 'NOTLESS', 'NOTGREATER',
        'EQUAL', 'LESS',  'GREATER', 
        'PLUS', 'MINUS', 'TIMES', 'DIVIDE',
        'COMMA', 'COLON', 'SEMICOLON',
        'LPAREN', 'RPAREN', 'LBRACKET', 'RBRACKET',
        'IDENTIFIER',
        'CLOSEDSTRING',
        'UNSIGNEDREAL',
        'UNSIGNEDINTEGER'
        ] + keywords.values()

keywords については後述します。 基本的には,tokens の各要素に対応する文字列値に t_ を接頭したメンバを定義します。 簡単なトークンは正規表現の文字列を値とするメンバ変数として定義します。

    t_POWER = r'\*\*'
    t_COLONEQUAL = ':='
    t_NOTEQUAL = '/='
    ……

トークンとして切り取ったテキストに対して処理を行う場合はメンバ関数,つまりメソッドとして定義します。 ドキュメンテーション文字列でトークンの正規表現を指定します。 読み取られたトークン (LexToken インスタンス) が引数として渡されます。

    def t_UNSIGNEDINTEGER(self, t):
        r'\d(_?\d)*'
        t.value = ''.join(t.value.split('_'))
        return t

このメソッドのドキュメンテーション文字列では符号無し整数に (読みやすくするため) 自由に下線をさしはさめるように正規表現を与えていますが,メソッド本体ではそのテキスト値 t.value から下線をすべて取り除いています。

   元の t.value == "1_234_567" ⇒ 加工後の t.value == "1234567"

tokens とは無関係な名前で t_ で始まるメソッドを定義することもできます。このときは,どのトークンかを表す t.type を陽に代入します。 この方法によれば,複雑な正規表現を無理に一つにせず,別々のメソッドで定義できます。

    def t_real1(self, t):
        r'(\d(_?\d)*)?\.\d(_?\d)*(e(\+|-)?\d(_?\d)*)?'
        t.type = 'UNSIGNEDREAL'
        t.value = ''.join(t.value.split('_'))
        return t

    def t_real2(self, t):
        r'\d(_?\d)*e(\+|-)?\d(_?\d)*'
        t.type = 'UNSIGNEDREAL'
        t.value = ''.join(t.value.split('_'))
        return t

また,これを逆に応用して,一般的な 正規表現で複数種類のトークンをまとめて切り出し,一つのメソッド本体の中で改めて分別することもできます。 識別子とキーワードの切り出しでは,この方法をとっています。

    keywords = {
        'begin': 'BEGIN',
        'end': 'END',
        'if': 'IF',
        'then': 'THEN',
        'else': 'ELSE',
        ……
        'equiv': 'EQUIV',
        'div': 'DIV'
        }
    ……
    def t_IDENTIFIER(self, t):
        r'[A-Za-z][0-9A-Za-z]*'
        t.type = self.keywords.get(t.value, 'IDENTIFIER')
        if t.type == 'END':
            t.lexer.push_state('end')
        elif t.type == 'COMMENT':
            t.lexer.push_state('com')
        return t

ここでは end キーワードと comment キーワードに対して特別な処理をしています。 Algol 60 には,end の後に何を書いても,別の end かセミコロンかそれとも else が現れるまですべて無視される, comment の後に何を書いてもセミコロンが現れるまですべて無視される,という特別な規則があるからです。

ですから,§2 のプログラム例にある end Fac;FacFac 関数の終わりを示すために構文で規定されているわけではなく, 人間の便宜のために書かれているにすぎません。

end キーワードに対しておこなっている処理 t.lexer.push_state('end') は,字句解析器を,これ以降,特別な 'end' 状態にします。 この状態では t_end_ で始まるメンバが使われます。

    # "end" <any sequence of zero or more characters not containing 
    # "end" or ";" or "else">
    t_end_ignore = t_ignore
    t_end_newline = t_newline
    def t_end_error(self, t): t.lexer.skip(1)

    def t_end_END(self, t):
        r'end'
        t.type = 'END'
        return t

    def t_end_ELSE(self, t):
        r'else'
        t.lexer.pop_state()
        t.type = 'ELSE'
        return t
        
    def t_end_SEMICOLON(self, t):
        r';'
        t.lexer.pop_state()
        t.type = 'SEMICOLON'
        return t

'end' 状態で end に出会ったときは (t_end_END により) トークンとしては end を返しますが,状態は継続させます。 セミコロンか else に出会ったときは (それぞれ t_end_SEMICOLONt_end_ELSE により) 対応するトークンを返すとともに t.lexer.pop_state() で状態から脱出します。

トークンとして認識できない文字に出会ったとき,通常状態ならばエラーにすべきですが,ここでは def t_end_error(self, t): t.lexer.skip(1) として単に読み飛ばします。 トークン間の区切りとして読み飛ばす文字を規定する t_end_ignore と,改行に対して行番号のカウントを増やす t_end_newline は,通常状態のものをそのまま流用します。

このように, 状態に対する接頭辞 (通常状態ならば t_'end' 状態ならば t_end_) に errorignore または newline を続けたメンバは特定の用途に使われます。 通常状態に対し,この3メンバを次のように定義します。 改行に対しては,行番号を増やすとともに,次の行の先頭が入力文字列全体で何文字目かを記録します (この情報はエラー表示に使います)。

    t_ignore = ' \t\r\f\v'
    ……
    def t_newline(self, t):
        r'\n'
        t.lexer.lineno += 1
        self.line_head_pos = t.lexpos + 1

    def t_error(self, t):
        s = t.value[0]
        raise SyntaxError("bad character", self, t.value[0])

ここで t_ignore の文字列は,正規表現ではなく,読み飛ばす文字の単純な羅列であることに注意してください。 t_ignore_ を接頭辞とするメンバを定義して,読み飛ばす文字の列を正規表現で追加指定できます。 次のように定義して # から行末までをコメント扱いにします。 これは Algol 60 の文法にはない非公式の独自仕様ですが,便宜として含めます。

    t_ignore_comment = r'\#.*'  # not official

Algol 本来のコメントは comment キーワードからセミコロンまでです。 前述の end と同じように特別な 'com' 状態の中で読み飛ばしを行います。 end の場合と微妙に異なり,'com' 状態で出現したセミコロンは, 1個のトークンとして扱わず,コメントの末尾を構成するものと見なします。 そのため,t_com_SEMICOLON では t を返しません (暗黙のうちに None を返します)。

    # "comment" <any sequence of zero or more characters not containing
    # ";"> ";"
    t_com_ignore = t_ignore
    t_com_newline = t_newline
    def t_com_error(self, t): t.lexer.skip(1)

    def t_com_SEMICOLON(self, t):
        r';'
        t.lexer.pop_state()
このように,トークンに対するメソッドで戻り値を返さないようにすれば,あってもなくても トークンとしては無視される (つまり,上位の構文解析から認識できなくなる) ようになります。

ただし,comment はどこにでも自由に出現できるわけではありません。 comment が出現できるのは begin かセミコロンの直後に限られています。 しかし,そのルールはここではなく,上位の構文解析で記述することにします。

` で始まり ' で終わる「閉じた文字列」 <closed string> も同様に特別な状態に入って処理します。 今どきの普通のプログラミング言語にない注意点は `' の入れ子が可能なことです。 入れ子レベル self.str_level を管理することで実装します。 状態突入時の入力文字列での位置を記録しておき, 状態脱出時に現在の位置までの部分文字列を取り出して,トークンの値 t.value にします。

    # <closed string> ::= "`" <open string> "'"
    def t_begin_str(self, t):
        r"`"
        self.str_start = t.lexer.lexpos
        self.str_level = 1
        t.lexer.push_state('str')

    t_str_ignore = t_ignore
    t_str_newline = t_newline
    def t_str_error(self, t): t.lexer.skip(1)
    
    def t_str_begin(self, t):
        r"`"
        self.str_level += 1

    def t_str_end(self, t):
        r"'"
        self.str_level -= 1
        if self.str_level == 0:
            t.lexer.pop_state()
            t.type = 'CLOSEDSTRING'
            t.value = t.lexer.lexdata[self.str_start: t.lexer.lexpos - 1]
            return t

ANSI/ISO C 言語の文字列リテラルと同様,隣り合った「閉じた文字列」はコンパイル時に一つの「文字列」 <string> にまとめられますが,そのルールはここではなく,上位の構文解析で記述することにします。

   `This is' ` a string' ⇒ `This is a string'
もちろん,設計された年を考えれば,まねをしたのは ANSI/ISO C です。 隣接する文字列リテラルの連結は K&R C にはなかった仕様です。 ANSI/ISO C で Algol の亡霊 :-) が一つ現代によみがえったわけです。
「閉じた文字列」を際限なく入れ子にできるということは,有限状態オートマトンないし正規表現だけでは Algol 60 の字句解析はできない,ということを意味します。 これはコメントの不自由さとともに,現代の言語のなかに復活すべきではない古風な複雑さであると 断言しても安全でしょう。

以上のように字句解析では,通常状態に加えて, 'end''com''str' の3状態を使いますが,これらは states で宣言しておく必要があります。 下記で 'exclusive' は通常状態の動作を引き継がないことを意味します。

    states = [
        ('com', 'exclusive'),
        ('end', 'exclusive'),
        ('str', 'exclusive')
        ]

結局,トークンに対するルールの大部分は,正規表現の文字列を値とする (t_ で始まる) メンバ変数 と,正規表現のドキュメンテーション文字列をもつ (t_ で始まる) メンバ関数で 表現するわけですが,字句解析時にそれらが適用される順序は次のとおりです。

  1. まず,メンバ関数が定義された順序で適用されます (したがって,整数に対する関数より先に,実数に対する関数を定義する必要があります)
  2. それから,メンバ変数の文字列が正規表現の長い順に適用されます (したがって,':='':' よりも優先されます)

5 構文解析

Parser.py は Algol 60 用の構文解析器です。 そのクラス Parser は一定の書式で構文解析ルールを記述します (次節参照)。 さらに,上位の言語処理系本体から利用される公のメソッドとして,入力ソースの文字列に対する構文木を 組み立てて返す parse(self, source_text) を定義します。 メソッド内部では, Lexer.pyLexer クラスのインスタンスを self.lexer として構築するとともに,ply.yaccyacc 関数に自分自身のオブジェクト,つまり self を与えることによって内部的な構文解析器 self.parser を構成します。そしてそれに処理をすべて委譲します。

import ply.yacc
from Lexer import Lexer, SyntaxError
……
class Parser:
    tokens = Lexer.tokens

    def __init__(self, **yacc_args):
        self.lexer = None
        self.yacc_args = yacc_args

    def parse(self, source_text):
        if self.lexer is None:
            self.lexer = Lexer()
            self.parser = ply.yacc.yacc(module=self, **self.yacc_args)
        return self.parser.parse(source_text, lexer=self.lexer)

    def p_error(self, t):
        raise SyntaxError("unexpected token", 
                          self.lexer, t.value, t.lineno, t.lexpos)

    …… 構文解析ルールの記述 (次節参照) ……

構文解析ルールで,どれがトークン つまり終端記号であるかを示すために Lexer.tokens の値を tokens という名前で定義しておきます。 定義しないと,ply.yacc.yacc 関数による内部的な構文解析器の構成に失敗します。 構文規則にあてはまらないトークンの出現に対する動作を p_error メソッドで指定します。 このメソッドには引数として前節で扱ったトークン・オブジェクトが渡されます。 ここではそれをもとに SyntaxError 例外を送出します。

Parser.py をモジュールではなく単体のスクリプトとして実行したときのために,簡単な単体テストを用意しておきます。

if __name__ == '__main__':
    import pprint
    source_text = """
  begin
    comment
      入力された整数に対して階乗を計算する。
      負数が入力されたら終了する;

    integer procedure Fac(k);
      value k; integer k;
      begin
        if k = 0 then Fac := 1
                 else Fac := k * Fac(k - 1)
      end Fac;

    integer n;
  LOOP:
    read(n);
    if n < 0 then goto EXIT;
    print(n, Fac(n));
    goto LOOP;
  EXIT:
  end
    """
    syntax_tree = Parser().parse(source_text)
    pprint.pprint(syntax_tree)

Parser.py は構文木をタプルとリストで組み立てます。 この単体テストでは,それを Python に備え付けの pprint.pprint でプリティ・プリントします。

$ pytho Parser.py
yacc: Generating LALR parsing table...
yacc: 8 shift/reduce conflicts
yacc: 92 reduce/reduce conflicts
['block',
 [],
 [['procedure_declaration',
   7,
   ('integer', 7),
   ('IDENTIFIER', 'Fac', 7),
   [('IDENTIFIER', 'k', 7)],
   [('IDENTIFIER', 'k', 8)],
   [[('integer', 8), [('IDENTIFIER', 'k', 8)]]],
   ['compound_statement',
    [],
    [['conditional_statement',
(中略)
   ['procedure_statement',
    ('IDENTIFIER', 'print', 18),
    [('IDENTIFIER', 'n', 18),
     ['function_designator',
      ('IDENTIFIER', 'Fac', 18),
      [('IDENTIFIER', 'n', 18)]]]]],
  ['basic_statement', [], ['goto_statement', 19, ('label', 'LOOP', 19)]],
  ['basic_statement', [('label', 'EXIT', 20)], ['dummy_statement']]]]
$

このとき,カレントディレクトリに構文解析ルールに関するデバッグ出力 parser.out と,生成された構文解析表 parsetab.py の2ファイルが ply.yacc によって作られます。 次回以降の Parser.py の実行では,この構文解析表が流用されますから,より高速に処理が終わります。

ply.yacc による構文解析表ファイルの作成やデバッグ出力を抑制するには, Parser コンストラクタを経由して ply.yacc.yacc 関数にキーワード引数 write_tables=False, debug=False を渡します。 テスト用の仮の主スクリプト Test.py にその例をみることができます。

# -*- coding: utf-8 -*-  H20.10/7 (鈴)
"""
構文解析テスト

コマンド行引数を Algol60 のソースファイルの名前として読み込み,
各ファイル名とその構文解析の結果としての構文木を印字する。
"""

from Parser import Parser
import pprint, sys

parser = Parser(write_tables=False, debug=False)
for file_name in sys.argv[1:]:
    print file_name
    rf = open(file_name)
    source_text = rf.read()
    rf.close()
    syntax_tree = parser.parse(source_text)
    pprint.pprint(syntax_tree)

5.1 構文解析ルールの記述

構文解析ルールは p_ で始めるメソッドで記述します。 特に指定がなければ (前節の p_error を除く) そのような最初のメソッドが 定義する非終端記号が開始記号になります。 Parser クラスでは下記が最初ですから,非終端記号 program が開始記号になります。

    # 4.1 Compound statements and blocks
    def p_program(self, p):
        '''program : block
                   | compound_statement'''
        p[0] = p[1]

構文のルール,つまり生成規則はドキュメンテーション文字列で記述します。 上記は Algol 60 修正報告書 4.1.1 節 の BNF

<program> ::= <block> | <compound statement>

を記述したものです。 メソッド名と非終端記号の名前は必ずしも一致させる必要はありません。 例えばメソッド名を p_program ではなく p_lets_start_here としても OK です。

引数の p は PLY の内部クラスのインスタンスです。 配列のように添え字付けしたり,len 関数で要素数を取得できるほか, トークンの行番号を取得するメソッド等が用意されています。 p[0] がルール左辺の非終端記号に対応します。 p[1]p[2],… がルール右辺の (終端・非終端) 記号に順に対応します。

生成規則に対する動作の記述であるメソッド本体は典型的には p[1]p[2],… から構築した値を p[0] に代入します。 上記のメソッド p_program では,非終端記号 block または compound_statement の構文木が p[1] に格納されています。 それを p[0] に代入することによって,非終端記号 program の値とします。 program は開始記号ですから,結局,この値が parse メソッドの戻り値になります。

今,p[1] にそれに対応する非終端記号 block または compound_statement の構文木が 格納されていると述べました。 これはひとりでにそうなるのではありません。 それぞれの非終端記号を定義するメソッドで,そのように記述する必要があります。 例えば block の BNF は次のように規定されています。

<block> ::= <unlabelled block> | <label>: <block>

この規定では,ルール右辺が1個の記号からなる場合と,(トークンであるコロン「:」を含めて) 3個の記号からなる場合があります。これを一つのメソッドにまとめて,len(p) で場合分けしてもよいのですが,今回はそうせずに二つのメソッドに分けて記述することにします。

    def p_block_1(self, p):
        'block : unlabelled_block'
        p[0] = [S_block, [], p[1][0], p[1][1]] # labels, head, tail

    def p_block_2(self, p):
        'block : label COLON block'
        p[3][1].append(p[1])
        p[0] =  p[3]

ここで代入されている p[0] がひるがえって p_program メソッドでの p[1] になります。 一見,謎めいた S_block は実は Parser.py の先頭で定義している文字列に過ぎません。

import ply.yacc
from Lexer import Lexer, SyntaxError

S_block = 'block'
S_compound_statement = 'compound_statement'
S_basic_statement = 'basic_statement'
S_UNSIGNEDINTEGER = 'UNSIGNEDINTEGER'
S_UNSIGNEDREAL = 'UNSIGNEDREAL'
S_string = 'string'
S_IDENTIFIER = 'IDENTIFIER'
……

p_block_1 の本体が込み入っていますが,これは unlabelled_block に対する下記のメソッド p_unlabelled_block で構築した ペアを分解して,4項組に再編成しているだけです (第1要素は S_block, 第2要素はブロックに付けられたラベルのリスト,そして第3,第4要素が下記で構築したペア)。

    def p_unlabelled_block(self, p):
        'unlabelled_block : block_head semicolon compound_tail'
        p[0] = (p[1], p[3])

ラベルのリストにラベルを追加する処理は p_block_2 で行います。 p[1] が label,p[2] が COLON トークン,p[3] が block に該当します。 これは再帰的な定義です。 非終端記号 block に対する再帰の底である p_block_1 で block の値を4項組のリストにしていますから,底から1段上がったところでは p[3] は4項組のリストになります。 その第2要素に label の値を append して,4項組のリストを p[0] に代入します。 したがって底から任意の n 段あがったところでも4項組のリストになります。

ここではリストへの append でいわば破壊的な代入をしているわけですが, そこに付けたラベルに対して再帰しているだけで,実体としてはある1個の block に1対1に対応し, なんら共有しませんから,問題はありません。 参考のため,block に複数のラベルをつけた (わざとらしい) 例を示します。

One: Two: Three: begin integer i; i := 4; foo(i) end

ちなみに非終端記号 block_head は次のように定義されます。生成規則としては begin とそれに続く1個の宣言 (declaration) を再帰の底とし,セミコロンではさんで宣言を追加します。 構文木としては,各宣言 (に対する構文木) を要素とするリストを組み立てます。

    def p_bock_head_1(self, p):
        'block_head : begin declaration'
        p[0] = [p[2]]

    def p_bock_head_2(self, p):
        'block_head : block_head semicolon declaration'
        p[0] = p[1] + [p[3]]

字句解析の節で述べたように comment が出現できるのは begin かセミコロンの直後に限られています。 そして,そのルールはここ,構文解析で記述することにしていました。 実際には下記の二つのメソッドで実現します。

    # 2.3 (Delimiters)
    def p_semicolon(self, p):
        '''semicolon : SEMICOLON
                     | semicolon COMMENT'''
        pass

    def p_begin(self, p):
        '''begin : BEGIN
                 | begin COMMENT'''
        pass

他の生成規則で終端記号 SEMICOLON,BEGIN を直接使うかわりに 一貫して非終端記号 semicolon,begin を使うことにすれば,comment のルールをかなえることができます。 ちなみに,どちらの記号も構文木の構成要素としてはどのルールからも使われませんから,メソッド本体は何もしません。 単に pass します。

同様に,隣り合った「閉じた文字列」はコンパイル時に一つの文字列にまとめられる,というルールも 字句解析ではなく構文解析で記述することにしていました。 これは下記の二つのメソッドで実現します。

    # 2.6 Strings
    def p_string_1(self, p):
        'string : CLOSEDSTRING'
        p[0] = (S_string, p[1], p.lineno(1))

    def p_string_2(self, p):
        'string : CLOSEDSTRING string'
        p[0] = (S_string, p[1] + p[2][1], p.lineno(1))

ここで終端記号,つまりトークンに対応する p[1] は,そのトークンの字句解析ルールで設定した t.value の値になります。 CLOSEDSTRING ではこれはソース上の文字列の最外の `' をそぎ落としたものです。 メソッド p_string_1 では, 他のデータではなく確かに「文字列」であることを示すために第1要素を S_string, 第2要素を p[1], そして第3要素を (デバッグの便宜のために) トークン p[1] に対応する行番号 p.lineno(1) にしたタプルを構成して p[0] に代入します。

メソッド p_string_2 では,文字列連結 p[1] + p[2][1] を行ってタプルを再構成します。

以下同様に,p[i] (i ≧ 1) が, 生成規則の i 番目の記号が終端記号 (トークン) ならばその字句解析ルールでの t.value 値, 非終端記号ならばそれを定義する p_ メソッドの p[0] 値になることを利用して, 構文解析ルールを記述します。

5.2 Algol 60 生成規則の修正

記述した生成規則がどのように適用されるかは,PLY が LALR 法に従って自動的に行いますから,ほとんど意識する必要はありません。 単純に言語仕様書の生成規則を書き写すだけで OK です。 ただし,例外が二つあります。

一つは修正報告書 5.1.1 節の 「型宣言」(type declaration) の規則です。

<local or own> ::= <empty> | own
<type declaration> ::= <local or own> <type> <type list>

ここで empty は「空」を表す記号です。PLY では一般に下記のようなメソッドで実装します。

    def p_empty(self, p):
        'empty :'
        pass

しかし,実際に

real a, b;

のような「型宣言」 を解析させると,「型」(type) に対して, 修正報告書 5.4.1 節の「手続き宣言」

<procedure declaration> ::= procedure <procedure heading> <procedure body> |
        <type> procedure <procedure heading> <procedure body>

の生成規則の二つ目の選択肢が適用されて失敗します。 この問題は empty を使わないようにして先読み能力の浪費を避ければ解決します。

<type declaration> ::= <type> <type list> |
                       own <type> <type list>

実際のメソッドでは次のようにします。

    def p_type_declation_1(self, p):
        'type_declaration : type type_list'
        p[0] = [S_type_declaration, S_local, p[1], p[2]]

    def p_type_declation_2(self, p):
        'type_declaration : OWN type type_list'
        p[0] = [S_type_declaration, S_own, p[1], p[2]]

もう一つは,いましがた議論した修正報告書5.4.1 節の「手続き宣言」の一部である「仮引数仕様部」 (specification part) です。

<specifier> ::= string | <type> | <array declarer> |
       label | switch | procedure | <type> procedure

<specification part> ::= <empty> | <specifier> <identifier list> ; |
        <specification part> <specifier> <identifier list>

これは仮引数の型と,仮引数名のカンマで区切った並びを,セミコロンで区切って 0 回以上繰り返す,という規則 ですが,実際にこのとおりに書くと 0 回また 1 回だけの繰り返しになります。 型と並びの出現に対して <specification part> の右辺の二つ目の選択肢が適用されますが, 2回以上の繰り返しに対しては,それ全体を三つ目の選択肢の先頭要素と読み直す必要があります。 PLY にこのようなバックトラックはできません。 しかし,規則を下記のように表現すれば,バックトラックが不要になりますから問題ありません。 2回以上の繰り返しも可能になります。

<specification part> ::= <empty> | 
                         <specifier> <identifier list> ; <specification part>

実際のメソッドでは次のようにします。

    def p_specification_part_1(self, p):
        'specs : empty'
        p[0] = []

    def p_specification_part_2(self, p):
        'specs : specifier identifier_list semicolon specs'
        p[0] = [[p[1], p[2]]] + p[4]
今,新しく設計する言語ならば,正当な理由なく,機械的に実現できない構文規則を採用することは賢明とはいえません。 しかし,そもそも Algol 60 は BNF を最初に採用した言語であり, DeRemer による LALR 法の発見はそれより後,1960 年代末期から 1970 年代初頭にかけてでした。 ですから,現在の見地から Algol 60 の文法表現に十分に正規化されていない点があることを非難することは不適切でしょう。
ちなみに Algol 60 の生成規則について悪名高い「ぶらさがり else」(dangling else) 問題は,実際には半世紀近く前に解決しています。 Algol 60 修正報告書の該当箇所の BNF から分かるように if 文の then の次に出現できるのは無条件文 (uncoditinal statement) に限られています。 したがって,if B then if C then S else T は構文的に許されません。 if B then begin if C then S end else T あるいは if B then begin if C then S else T end のように入れ子の if 文を陽に文括弧でくくって無条件文にする必要があります。 条件 (付き) 式 if B then E else F (いわゆる3項演算子ですが,Algol では文と同じキーワードを使います) についても同様であり,式 E の箇所で条件付き式を入れ子にするときは陽に括弧でくくる必要があります。 あいまいさは生じません。 1963 年の改訂報告書でもすでにこのようになっていますから,以来 45 年間,咎なく悪評が続いたことになります。

6. ここまでのまとめ

これまでみたように字句解析と構文解析は,いくつか注意すべき点はあるものの,基本的な処理は系統的に自動化されています。 再帰の概念に慣れていれば,その記述は単純作業と言ってもよいほどです。 PLY のようなパーサ・ジェネレータは,計算機科学の理論を実地に応用した古典的,模範的なフレームワークの実例と言えるでしょう。 今日,処理系作成の主要な興味は,その言語独特の意味論の効率的な実現にあります。 次回はいよいよその第一歩である名前の解決を行います。


目次へ 第2部へ


Copyright (c) 2008, 2009 OKI Software Co., Ltd.