Python用の字句解析器と構文解析器の生成用ライブラリである、SLYのドキュメントを和訳しました。
原文はこちらです：https://sly.readthedocs.io/en/latest/sly.html
訳語の選択に、サイエンス社のコンパイラ 原理・技法・ツール I & II(初版)とbison、flexの日本語訳を参考にしました。
ありがとうございます。
SLY (Sly Lex Yacc)
本ドキュメントはSLYによる字句解析処理と構文解析処理の概要を紹介する。構文解析処理は本質的に複雑なため、SLYで大規模開発に当たる前に、本ドキュメント全体を（さわりだけでも）読むことを強く推奨する。
SLYはPython 3.6以上を必要とする。より古いバージョンを使っている場合、運が悪いと諦めること。すまんね。
前置き
SLYは構文解析器やコンパイラを記述するためのライブラリである。伝統あるコンパイラ生成ツールであるlexとyaccを手本とし、それらが用いるのと同様にLALR(1)構文解析アルゴリズムを実装している。lexとyaccで使える機能の大部分はSLYにも備わっている。SLYは付加機能（たとえば抽象構文木の自動生成機能や深さ優先巡回）を十分に提供していないことに注意せよ。また、これを構文解析フレームワークと捉えるべきでない。その代わり、Pythonによる構文解析器を記述用ライブラリとして十分な骨組みであることが分るだろう。
本ドキュメントの残りの部分は、読者が構文解析器の定石、構文主導翻訳、他言語向けのlexやyacc風コンパイラ生成ツールの用法に十分慣れ親しんでいることを想定している。これらの題目に不慣れなら、たとえばAho、 Sethi、Ullmanらによる"Compilers: Principles, Techniques, and Tools（コンパイラ―原理・技法・ツール）"などの入門書に当たるべきだろう。O'Reillyから出ているJohn Levineの"Lex and Yacc"も手頃だろう。実際、SLYの参考に実質的に同じ概念のものを扱うO'Reilly本が使用できる。
SLYの概要
SLYは2つの独立したクラスLexerとParserを提供する。Lexerクラスは入力テキストを正規表現規則によって特定されるトークン列への分割処理に使用される。Parserクラスは文脈自由文法の形式で記述される言語構文の認識処理に使用される。構文解析器の作成には、通常、この2つのクラスが併用される。もちろん、これはそうした制限ではなく、柔軟に変更する余地がある。基本的な事項を次の2つのパートで説明する。
字句解析器の記述
あるプログラミング言語の記述に際し、以下の文字列を構文解析したいと仮定しよう。
x = 3 + 42 * (s - t)
構文解析の第一歩は、テキストをトークンに分割する処理である。トークンはそれぞれ型と値を持つ。上記のテキストは、以下のトークンタプルのリストとして記述することができる。
[ ('ID','x'), ('EQUALS','='), ('NUMBER','3'),
('PLUS','+'), ('NUMBER','42'), ('TIMES','*'),
('LPAREN','('), ('ID','s'), ('MINUS','-'),
('ID','t'), ('RPAREN',')') ]
SLYのLexerクラスが、これを実行する。上記のテキストをトークン分割する、単純な字句解析器のサンプルがこちら。
# calclex.py
from sly import Lexer
class CalcLexer(Lexer):
# Set of token names. This is always required
tokens = { ID, NUMBER, PLUS, MINUS, TIMES,
DIVIDE, ASSIGN, LPAREN, RPAREN }
# String containing ignored characters between tokens
ignore = ' \t'
# Regular expression rules for tokens
ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
NUMBER = r'\d+'
PLUS = r'\+'
MINUS = r'-'
TIMES = r'\*'
DIVIDE = r'/'
ASSIGN = r'='
LPAREN = r'\('
RPAREN = r'\)'
if __name__ == '__main__':
data = 'x = 3 + 42 * (s - t)'
lexer = CalcLexer()
for tok in lexer.tokenize(data):
print('type=%r, value=%r' % (tok.type, tok.value))
これを実行すると、以下の出力が生成される。
type='ID', value='x'
type='ASSIGN', value='='
type='NUMBER', value='3'
type='PLUS', value='+'
type='NUMBER', value='42'
type='TIMES', value='*'
type='LPAREN', value='('
type='ID', value='s'
type='MINUS', value='-'
type='ID', value='t'
type='RPAREN', value=')'
字句解析器は公開メソッドtokenize()を一つだけ備えている。これは、Tokenインスタンスのストリームを生成するジェネレータ函数となっている。Tokenのtype属性とvalue属性は、それぞれトークン型名と値を保持している。
tokensのセット
字句解析器は、自身によって生成される可能性のあるあらゆるトークン型名をtokensセットで規定しておく必要がある。これは常に必須で、様々な検証処理で使用される。
トークン名を規定するコードの例。
class CalcLexer(Lexer):
...
# Set of token names. This is always required
tokens = { ID, NUMBER, PLUS, MINUS, TIMES,
DIVIDE, ASSIGN, LPAREN, RPAREN }
...
トークン名はすべて大文字で指定することが推奨される。
トークン照合パターンの仕様
トークンの指定は、reモジュールと互換性のある正規表現規則の記述で行なう。規則の名称は、tokensセットで示したトークン名のいずれか一つに対応させる必要がある。例）
PLUS = r'\+'
MINUS = r'-'
可読性を向上させるため、正規表現パターンは re.VERBOSEフラグをつけてコンパイルされる。このモードでは、エスケープされていない空白文字は無視され、コメントの記述も許可される。パターンに空白文字を含める場合、\sを使用する。#文字の照合には、 [#]か \#を使う。
Lexerクラスにリストされたパターンの順序が、トークンの照合順序となる。長めのトークンは、短めのトークンより常に先に指定しておかれなければならない。たとえば、=と==のトークンを区別したい場合、==を先に指定する必要がある。例）
class MyLexer(Lexer):
tokens = { ASSIGN, EQ, ...}
...
EQ = r'==' # MUST APPEAR FIRST! (LONGER)
ASSIGN = r'='
破棄テキスト
入力ストリーム中で無視すべき単一文字の集まりを指定するために、ignore特殊指定が用意されている。通常、これは、空白文字やその他不要な文字の読み飛ばし処理で使用される。ignoreに文字が指定されていても、正規表現パターンの一部として含まれているその文字は無視されない。たとえば、引用符で括られたテキストの規則があるとき、そのパターンにignore指定された文字が含まれていてもおかしくない。ignoreは主として、構文解析処理の対象となるトークンの隙間にある空白文字やその他のパディングを無視するために使われる。
また、名称に接頭子ignore_付けた正規表現ルールを記述することで、それ以外のテキストパターンを破棄することができる。例えば、次の構文解析器はコメントと改行を無視する規則を備えている。
# calclex.py
from sly import Lexer
class CalcLexer(Lexer):
...
# String containing ignored characters (between tokens)
ignore = ' \t'
# Other ignored patterns
ignore_comment = r'\#.*'
ignore_newline = r'\n+'
...
if __name__ == '__main__':
data = '''x = 3 + 42
* (s # This is a comment
- t)'''
lexer = CalcLexer()
for tok in lexer.tokenize(data):
print('type=%r, value=%r' % (tok.type, tok.value))
照合動作の追加
特定トークンの照合時に、照合に加えて何らかの追加動作を実行したい場合がある。例えば、数値の変換処理や言語の予約語の検索処理などがある。これを実施する一つの手法として、その動作をメソッドとして記述し、それを紐付ける正規表現を@_() デコレータで付与する。
@_(r'\d+')
def NUMBER(self, t):
t.value = int(t.value) # Convert to a numeric value
return t
このメソッドは単一引数を持ち、Token型のインスタンスを受け取る。規定動作では、t.typeにトークンの名称（'NUMBER'など）が格納されている。必要に応じ、函数内でトークン型やトークン値を変更して良い。最後に、戻り値として処理後のトークンが返される必要がある。函数が戻り値を返さない場合、そのトークンは破棄され、次のトークンが読み込まれる。
@_()デコレータはLexerクラス内に自動的に定義される。このため、importなどは不要である。正規表現規則を複数持たせても良い。例：
@_(r'0x[0-9a-fA-F]+',
r'\d+')
def NUMBER(self, t):
if t.value.startswith('0x'):
t.value = int(t.value[2:], 16)
else:
t.value = int(t.value)
return t
@_()デコレータを使用する代わりに、文字列で指定したトークンと同名のメソッドを直後に記述してもよい。例：
NUMBER = r'\d+'
...
def NUMBER(self, t):
t.value = int(t.value)
return t
この手法は字句解析器のデバッグで役立つ可能性がある。メソッドをトークンに一時的に紐付け、トークン出現時にそれを実行させることができる。用が済んだらそのメソッドを取り除き、字句解析器の挙動を元に戻すことができる。
トークンの再割り当て
特定条件の下でトークンの再割り当てが必要になる場合がある。"abc"、"python"、"guido"などの識別子を照合する場合を考えてみよう。"if"、"else"、"while"など特定の識別子は、特殊キーワードとして扱われるべきである。字句解析器の記述にトークン再割り当て規則を含めることで、これを実現できる。
# calclex.py
from sly import Lexer
class CalcLexer(Lexer):
tokens = { ID, IF, ELSE, WHILE }
# String containing ignored characters (between tokens)
ignore = ' \t'
# Base ID rule
ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
# Special cases
ID['if'] = IF
ID['else'] = ELSE
ID['while'] = WHILE
識別子の解析時に、この特例が特定トークンの照合値を新しいトークン型で置き換える。上の例では、識別子の値が"if"の場合にIFトークンが生成される。
行番号と位置の追跡
規定動作では、字句解析器は行番号について何も関知しない。字句解析器に入力の"行"に関する定義（たとえば改行文字や、そもそも入力がテキストデータかどうかなど)が与えられていない、というのがその理由である。そうした情報を与えるために、改行に関する特例指定を追加してもい。ignore_newline特例でこれを実施してみよう。
# Define a rule so we can track line numbers
@_(r'\n+')
def ignore_newline(self, t):
self.lineno += len(t.value)
特例により、字句解析器のlineno属性が更新されるようになった。行番号が更新された後、何も返していないためそのトークンは破棄される。
字句解析器は桁位置追跡に類することを自動で行なわない。その代わり、トークンのindex属性に個々のトークンの位置情報を記録する。これを使用することで。桁位置を算出できる可能性がある。たとえば、直前の改行が見つかるまで後方検索を行なっても良い。
# Compute column.
# input is the input text string
# token is a token instance
def find_column(text, token):
last_cr = text.rfind('\n', 0, token.index)
if last_cr < 0:
last_cr = 0
column = (token.index - last_cr) + 1
return column
桁位置情報はエラー処理の文脈でのみ必要とされる。このため桁位置の計算処理は各トークンに対してではなく、必要に応じて実施できるようになっている。
文字定数
文字定数をクラスのliteralsセットで定義することができる。例）
class MyLexer(Lexer):
...
literals = { '+','-','*','/' }
...
文字定数は、字句解析器から遭遇した"まま"の状態で返される、単なる_単一文字_である。文字定数は、定義済み正規表現規則すべての後に確認される。そのため、文字定数のいずれか一文字を先頭に持つルールは、文字定数より優先される。
文字定数は、その返却時にtype属性とvalue属性にその文字自身が格納される。 例）'+'
定数が照合された時に実行される追加動作として、トークンメソッドを記述することができる。ただし、そのトークンメソッドは適切なトークン型を設定するように実装されなければならない。例：
class MyLexer(Lexer):
literals = { '{', '}' }
def __init__(self):
self.nesting_level = 0
@_(r'\{')
def lbrace(self, t):
t.type = '{' # Set token type to the expected literal
self.nesting_level += 1
return t
@_(r'\}')
def rbrace(t):
t.type = '}' # Set token type to the expected literal
self.nesting_level -=1
return t
エラー処理
字句解析中に不正な文字が検出されると、字句解析処理は停止する。これに対し、字句解析エラーを処理するerror()メソッドを追加することができる。エラー処理メソッドはTokenを一つ受け取る。このトークンのvalue属性には、トークン化される前のテキスト全体が格納されている。典型的なハンドラーは、このテキストを見て、何らかの方法で読み飛ばし処理を行なう。例：
class MyLexer(Lexer):
...
# Error handling rule
def error(self, t):
print("Illegal character '%s'" % t.value[0])
self.index += 1
このケースでは、そこで問題となっている文字を印字し、字句解析の位置情報を更新することで1文字の読み飛ばし処理を実施する。解析器のエラー処理は、多くの場合、難しい問題を引き起こす。エラー処理では、セミコロン、空行や、それに類する記号といった、論理的に判断できる同期箇所までの読み飛ばし処理が必要になるだろう。
error()メソッドが未処理のトークンを返すと、ストリームにERRORトークンが出現する。これは、構文解析器がエラートークンを確認したい場合、たとえば、エラーメッセージの改良やその他エラー処理を行なうのに役立つ。
より完全な例
参考用に、これらの多くの概念を実践するより完全な例を示す。
# calclex.py
from sly import Lexer
class CalcLexer(Lexer):
# Set of token names. This is always required
tokens = { NUMBER, ID, WHILE, IF, ELSE, PRINT,
PLUS, MINUS, TIMES, DIVIDE, ASSIGN,
EQ, LT, LE, GT, GE, NE }
literals = { '(', ')', '{', '}', ';' }
# String containing ignored characters
ignore = ' \t'
# Regular expression rules for tokens
PLUS = r'\+'
MINUS = r'-'
TIMES = r'\*'
DIVIDE = r'/'
EQ = r'=='
ASSIGN = r'='
LE = r'<='
LT = r'<'
GE = r'>='
GT = r'>'
NE = r'!='
@_(r'\d+')
def NUMBER(self, t):
t.value = int(t.value)
return t
# Identifiers and keywords
ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
ID['if'] = IF
ID['else'] = ELSE
ID['while'] = WHILE
ID['print'] = PRINT
ignore_comment = r'\#.*'
# Line number tracking
@_(r'\n+')
def ignore_newline(self, t):
self.lineno += t.value.count('\n')
def error(self, t):
print('Line %d: Bad character %r' % (self.lineno, t.value[0]))
self.index += 1
if __name__ == '__main__':
data = '''
# Counting
x = 0;
while (x < 10) {
print x:
x = x + 1;
}
'''
lexer = CalcLexer()
for tok in lexer.tokenize(data):
print(tok)
このコードを実行すると、次のような出力が得られる。
Token(type='ID', value='x', lineno=3, index=20)
Token(type='ASSIGN', value='=', lineno=3, index=22)
Token(type='NUMBER', value=0, lineno=3, index=24)
Token(type=';', value=';', lineno=3, index=25)
Token(type='WHILE', value='while', lineno=4, index=31)
Token(type='(', value='(', lineno=4, index=37)
Token(type='ID', value='x', lineno=4, index=38)
Token(type='LT', value='<', lineno=4, index=40)
Token(type='NUMBER', value=10, lineno=4, index=42)
Token(type=')', value=')', lineno=4, index=44)
Token(type='{', value='{', lineno=4, index=46)
Token(type='PRINT', value='print', lineno=5, index=56)
Token(type='ID', value='x', lineno=5, index=62)
Line 5: Bad character ':'
Token(type='ID', value='x', lineno=6, index=73)
Token(type='ASSIGN', value='=', lineno=6, index=75)
Token(type='ID', value='x', lineno=6, index=77)
Token(type='PLUS', value='+', lineno=6, index=79)
Token(type='NUMBER', value=1, lineno=6, index=81)
Token(type=';', value=';', lineno=6, index=82)
Token(type='}', value='}', lineno=7, index=88)
この例をもう少し掘り下げてみよう。解釈に時間がかかるかもしれないが、字句解析器の記述の要点が、すべてここに示されている。トークンは正規表現ルールで指定されなければならない。一定のパターンが検出された場合に実行される動作を付随させることができる。文字定数などのいくつかの機能により、正規表現ルールを個別に作成する手間を省ける。また、エラー処理を追加することもできる。
構文解析器の記述
Parserクラスは言語構文の構文解析に使用される。例を示す前に、押さえておくべき背景知識がいくつか存在する。
構文解析の背景知識
構文解析器の記述を行う際、通常、_構文_はBNF記法で定義される。たとえば単純な数式を構文解析する場合、最初に、曖昧さを排除した次のような文法仕様を記述する。
expr : expr + term
| expr - term
| term
term : term * factor
| term / factor
| factor
factor : NUMBER
| ( expr )
文法の中にあるNUMBER、+、-、*、/などの記号は_終端記号_と呼ばれ、生の入力トークンに対応している。term、factorなどの識別子は、終端記号の集合とその他規則で構成される文法規則を参照する。これらの識別子は _非終端記号_として知られている。文法を複数の階層（expr、termなど）に分割することで、扱いが異なる演算子の優先順位規則を組み込むことができる。この例では、乗算と除算の方が加算と減算よりも優先される。
構文解析の中で生じる意味（semantics）は、多くの場合、構文主導翻訳として知られる手法で定義される。構文主導翻訳において、文法の中にある記号は一つの対象物として扱われる。各種文法規則が認識されると、値が記号に割り当てられ、それらの値に対する操作が実行される。先に取り上げた数式の文法が与えられたとき、以下のようにして、単純な計算機の計算処理を以下のように記述できる。
Grammar Action
------------------------ --------------------------------
expr0 : expr1 + term expr0.val = expr1.val + term.val
| expr1 - term expr0.val = expr1.val - term.val
| term expr0.val = term.val
term0 : term1 * factor term0.val = term1.val * factor.val
| term1 / factor term0.val = term1.val / factor.val
| factor term0.val = factor.val
factor : NUMBER factor.val = int(NUMBER.val)
| ( expr ) factor.val = expr.val
この文法において、新しい値はNUMBERトークンを通して導入される。これらの値は上で示した動作によって伝搬される。例えば、factor.val = int(NUMBER.val)がNUMBERの値をfactorへ伝搬する。term0.val = factor.valがfactorの値をtermに伝搬する。expr0.val = expr1.val + term1.valのような規則が値の結合を実施し、更にその先へと値を伝搬する。数式2 + 3 * 4のなかで値がどのように伝搬されていくかを以下に示す。
NUMBER.val=2 + NUMBER.val=3 * NUMBER.val=4 # NUMBER -> factor
factor.val=2 + NUMBER.val=3 * NUMBER.val=4 # factor -> term
term.val=2 + NUMBER.val=3 * NUMBER.val=4 # term -> expr
expr.val=2 + NUMBER.val=3 * NUMBER.val=4 # NUMBER -> factor
expr.val=2 + factor.val=3 * NUMBER.val=4 # factor -> term
expr.val=2 + term.val=3 * NUMBER.val=4 # NUMBER -> factor
expr.val=2 + term.val=3 * factor.val=4 # term * factor -> term
expr.val=2 + term.val=12 # expr + term -> expr
expr.val=14
SLYは、LR構文解析、または、移動還元構文解析（shift-reduce parsing）として知られる構文解析技法を使用する。LR構文解析法は、様々な文法規則の右辺の認識を試行する、ボトムアップ手法である。入力されたものの中に(文法定義の)右辺に適合するものが見つかると、それに沿った動作メソッドが実行され、右辺に相当する文法記号群が左辺の文法記号で置換される。
LR構文解析は、一般的に、文法記号をスタックに移動（shift）する処理と、スタックと次の入力が文法規則の型にはまるかどうかを試行する処理で実装されている。アルゴリズムの詳細はコンパイラの教科書を見れば分るだろう。次の例は数式3 + 5 * (10 - 20)を上で定義した文法で構文解析する過程を示す。この例のなかで、特殊記号$は入力の終端を示す。
---- --------------------- --------------------- -------------------------------
1 3 + 5 * ( 10 - 20 )$ Shift 3
2 3 + 5 * ( 10 - 20 )$ Reduce factor : NUMBER
3 factor + 5 * ( 10 - 20 )$ Reduce term : factor
4 term + 5 * ( 10 - 20 )$ Reduce expr : term
5 expr + 5 * ( 10 - 20 )$ Shift +
6 expr + 5 * ( 10 - 20 )$ Shift 5
7 expr + 5 * ( 10 - 20 )$ Reduce factor : NUMBER
8 expr + factor * ( 10 - 20 )$ Reduce term : factor
9 expr + term * ( 10 - 20 )$ Shift *
10 expr + term * ( 10 - 20 )$ Shift (
11 expr + term * ( 10 - 20 )$ Shift 10
12 expr + term * ( 10 - 20 )$ Reduce factor : NUMBER
13 expr + term * ( factor - 20 )$ Reduce term : factor
14 expr + term * ( term - 20 )$ Reduce expr : term
15 expr + term * ( expr - 20 )$ Shift -
16 expr + term * ( expr - 20 )$ Shift 20
17 expr + term * ( expr - 20 )$ Reduce factor : NUMBER
18 expr + term * ( expr - factor )$ Reduce term : factor
19 expr + term * ( expr - term )$ Reduce expr : expr - term
20 expr + term * ( expr )$ Shift )
21 expr + term * ( expr ) $ Reduce factor : (expr)
22 expr + term * factor $ Reduce term : term * factor
23 expr + term $ Reduce expr : expr + term
24 expr $ Reduce expr
25 $ Success!
数式の構文解析を行なう時、背後にある状態機械と手元の入力トークンによって次の動作が決定される。次のトークンが（スタック上の要素と併せて）有効な文法規則の一部として見なされると、そのトークンはスタック上に移動される（積まれる）。スタックの先頭部分が文法ルールの右辺に適合すると、それが"還元（reduce）"され、それらの記号群が左辺のシンボルに置き換えられる。この還元が発生したときに、それに対応する動作が（あれば）実行される。入力トークンが移動されず、スタックの先頭がいずれの文法規則にも適合しない場合、構文エラーが発生し、構文解析器は復旧手順をとるか救済処置を行なう必要がある。構文解析スタックが空でかつ入力トークンがなくなったとき、唯一、構文解析が成功したものとみなされる。
裏側にある巨大な有限状態機械が、巨大な表の集まりで実装されていることに留意しなければならない。これらの表の構成法は単純ではなく、説明の範囲を超えている。この上の例9段階目で構文解析器がexpr : expr + termを還元する代わりにトークンをスタックに移動するその理由は、手順の詳細を見ることで解き明かされる。
構文解析の例
先に紹介したような単純な算術計算式を評価する構文解析器を作成したいと仮定する。SLYでそれを実現するにはこのようにする。
from sly import Parser
from calclex import CalcLexer
class CalcParser(Parser):
# Get the token list from the lexer (required)
tokens = CalcLexer.tokens
# Grammar rules and actions
@_('expr PLUS term')
def expr(self, p):
return p.expr + p.term
@_('expr MINUS term')
def expr(self, p):
return p.expr - p.term
@_('term')
def expr(self, p):
return p.term
@_('term TIMES factor')
def term(self, p):
return p.term * p.factor
@_('term DIVIDE factor')
def term(self, p):
return p.term / p.factor
@_('factor')
def term(self, p):
return p.factor
@_('NUMBER')
def factor(self, p):
return p.NUMBER
@_('LPAREN expr RPAREN')
def factor(self, p):
return p.expr
if __name__ == '__main__':
lexer = CalcLexer()
parser = CalcParser()
while True:
try:
text = input('calc > ')
result = parser.parse(lexer.tokenize(text))
print(result)
except EOFError:
break
この例では、各文法規則は@_(rule)によってデコレートされたメソッドとして記述されている。一番最初の文法規則（BNF記法の中で最初の規則）は、構文解析の最上位を定義する。各メソッドの名称は、構文解析対象となる文法ルールの名称と一致している必要がある。@_()デコレータの引数には、文法の右辺を記述する文字列文字列となっている。以下のような文法規則は、
expr : expr PLUS term
このようなメソッドになる。
@_('expr PLUS term')
def expr(self, p):
...
入力の中で文法規則が認識されると、そのメソッドが起動される。メソッドは文法記号値のシーケンスを引数pで受け取る。これらのシンボルを参照する方法が二つある。一つ目は、以下のようにシンボル名を使用する。
@_('expr PLUS term')
def expr(self, p):
return p.expr + p.term
他にも、配列と同じようにpのインデックスを扱える。
@_('expr PLUS term')
def expr(self, p):
return p[0] + p[2]
トークンのp.symbolやp[i]には、構文解析器がトークンに割り当てるp.value属性と_同じ_値が割り当てられている。非終端記号では、規則の中でメソッドに返された値になっている。
文法規則に同じ記号名が複数含まれている場合、記号名を明確に区別するために数字を末尾に追加する必要がある。例：
@_('expr PLUS expr')
def expr(self, p):
return p.expr0 + p.expr1
最後に、各規則内で値を返却し、文法記号に対応させる必要がある。このようにして、文法内で値が伝搬される。
文法の中で、これとは違う種類の動作をしても良い。たとえば、文法定義で構文木の一部を生成しても良い。
@_('expr PLUS term')
def expr(self, p):
return ('+', p.expr, p.term)
また、抽象構文木に関連したインスタンスを作成しても良い。
class BinOp(object):
def __init__(self, op, left, right):
self.op = op
self.left = left
self.right = right
@_('expr PLUS term')
def expr(self, p):
return BinOp('+', p.expr, p.term)
記号（ここでは"expr"）に関連付けする値をメソッドが返すことが大切である。これは前節で示した値の伝搬である。
文法規則函数の組み合わせ
文法規則が似ている場合、単一のメソッドに統合しても良い。たとえば、1つの構文木を生成する規則が2つ存在するとしよう。
@_('expr PLUS term')
def expr(self, p):
return ('+', p.expr, p.term)
@_('expr MINUS term')
def expr(self, p):
return ('-', p.expr, p.term)
2つの函数の代わりに、単一の函数を以下のように記述しても良い。
@_('expr PLUS term',
'expr MINUS term')
def expr(self, p):
return (p[1], p.expr, p.term)
この例では、演算子はPLUSかMINUSのどちらかになる。シンボル名を値として使用することはできないので、代わりにp[1]のように配列操作を行なうとよい。
一般的に、 あるメソッドの@_()デコレータに複数の文法規則を与えることが許される。単一函数に複数の文法ルールを組み込む場合、すべての規則が同じ構造をとっている（例えば、項とシンボル名の数が一致している）必要がある。さもないと、それを対処するアクションコードが必要以上に複雑になる可能性がある。
文字リテラル
必要に応じ、文法に単一文字からなるトークンを含めることができる。例：
@_('expr "+" term')
def expr(self, p):
return p.expr + p.term
@_('expr "-" term')
def expr(self, p):
return p.expr - p.term
文字リテラルは、必ず"+"のように引用服で括る必要がある。加えて、対応する字句解析器クラスのliteralsでそれらを宣言しておく必要がある。
class CalcLexer(Lexer):
...
literals = { '+','-','*','/' }
...
文字定数は、単一文字に限られる。つまり、<=、==のような定数の指定は合法ではない。こうした定数は、通常の字句解析規則に従う必要がある（たとえば、LE = r'<='のような規則を定義する）。
空の生成規則
何も生成したくない場合、以下のような規則を定義する。
@_('')
def empty(self, p):
pass
空の生成規則を使用する場合、"empty" という名前をシンボルとして使用するとよい。省略可能な要素を規則に組み込む必要がある場合、以下のようにする。
spam : optitem grok
optitem : item
| empty
SLYでは以下のように組み込む。
@_('optitem grok')
def spam(self, p):
...
@_('item')
def optitem(self, p):
...
@_('empty')
def optitem(self, p):
...
注：空の文字列を指定することで、どこにでも空のルールを記述できる。一方、"empty"規則を記述し、それが何も生成しない"空"であることを明記することで、可読性が上がり、意図がより明確に示される。
曖昧な文法の対処法
先に示した数式の文法は、曖昧さを排除するため特別な書式で記述されている。しかし、多くの場合、この書式で文法を記述するのはとても困難かつ厄介なものになる。より自然な文法の記法は、以下のようなコンパクトな記法である。
expr : expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIVIDE expr
| LPAREN expr RPAREN
| NUMBER
残念なことに、この文法仕様には曖昧さがある。例えば、文字列"3 * 4 + 5"を構文解析するとき、演算子がどのようにグループ化されるかを判断する方法がない。この式は"(3 * 4) + 5"だろうか、さもなくば"3 * (4+5)"だろうか?
曖昧な文法が与えられると、"shift/reduce conflicts"や"reduce/reduce conflicts"といったメッセージが表示される。shift/reduce conflict（シフト/還元衝突）は、構文解析器生成器が規則を還元するか、解析スタック上のシンボルをシフトするかを判断できない場合に発生する。例えば、文字列"3 * 4 + 5"の構文解析の内部スタックを考えてみよう。
Step Symbol Stack Input Tokens Action
---- ------------- ---------------- -------------------------------
1 $ 3 * 4 + 5$ Shift 3
2 $ 3 * 4 + 5$ Reduce : expr : NUMBER
3 $ expr * 4 + 5$ Shift *
4 $ expr * 4 + 5$ Shift 4
5 $ expr * 4 + 5$ Reduce: expr : NUMBER
6 $ expr * expr + 5$ SHIFT/REDUCE CONFLICT ????
この例の構文解析器は、6番目の段階に到達したとき、2つの選択肢がある。一つは、規則expr : expr * exprをスタック上で還元することである。もう一つの選択肢は、トークン+をスタックに移動することである。両選択肢とも、文脈自由文法の規則上完全に合法である。
通常、すべての移動/還元衝突は移動の選択によって解決される。それ故に、上記の例の構文解析器は、+を還元せずに移動する。この戦略は多くの場合上手く働く（たとえば"if-then"と"if-then-else"）が、算術計算式ではそうならない。実際、上記の例において、+の移動は完全に誤りである。乗算は加算より算術の優先順位が高く、expr * exprの還元を選択するべきである。
特に計算式の文法において、曖昧さを解決するために、SLYはトークンに対し優先順位と結合規則の割り当てを許している。これを実現するには、構文解析器クラスに変数precedenceを追加すれば良い。
class CalcParser(Parser):
...
precedence = (
('left', PLUS, MINUS),
('left', TIMES, DIVIDE),
)
# Rules where precedence is applied
@_('expr PLUS expr')
def expr(self, p):
return p.expr0 + p.expr1
@_('expr MINUS expr')
def expr(self, p):
return p.expr0 - p.expr1
@_('expr TIMES expr')
def expr(self, p):
return p.expr0 * p.expr1
@_('expr DIVIDE expr')
def expr(self, p):
return p.expr0 / p.expr1
...
このprecedence指定はPLUS/MINUSが同じ優先順位で左結合、TIMES/DIVIDEが同じ優先順位で左結合であることを指定している。precedence指定の中で、トークンは底優先度から高い優先度の順に並べられる。従って、この指定は、優先度指定の後部にあるTIMES/DIVIDEがPLUS/MINUSより高い優先度を持つことを指定している。
優先順位指定は、優先順位レベル値や結合方向をトークンに関連付けることによって機能する。たとえば、上記の例では以下が得られる。
PLUS : level = 1, assoc = 'left'
MINUS : level = 1, assoc = 'left'
TIMES : level = 2, assoc = 'left'
DIVIDE : level = 2, assoc = 'left'
次に、これらの数値は、優先順位レベル値や結合方向を個々の分布規則に付与するために使用される。_常にこれらは右端の終端記号の値によって決定される。例：
expr : expr PLUS expr # level = 1, left
| expr MINUS expr # level = 1, left
| expr TIMES expr # level = 2, left
| expr DIVIDE expr # level = 2, left
| LPAREN expr RPAREN # level = None (not specified)
| NUMBER # level = None (not specified)
移動/還元衝突が発生すると、構文解析器生成器は優先順位規則や結合の指定を用いて衝突の解決を行なう。
- 現在のトークンがスタック上の規則より高い優先順位を持つ場合、それは移動される。
- スタック上の文法規則が高い優先順位を持つ場合、それは還元される。
- 現在のトークンと文法規則が同じ優先順位を持つ場合、左結合であれば規則が還元され、右結合であればトークンは移動される。
- 優先順位についての情報が存在しない場合、移動/還元衝突は規定動作の移動によって解決される。
たとえば、expr PLUS exprが構文解析された次のトークンとしてTIMESが来たとする。TIMESの優先順位レベルはPLUSより高いため、移動が行なわれる。逆に、expr TIMES exprが構文解析され次のトークンとしてPLUSが来たとする。PLUSの優先順位はTIMESより低いため、還元が行なわれる。
優先順位規則があっても三番目の手法で移動/還元衝突が解決されたときSLYはエラーや衝突を報告しない。
優先順位指定の手法には一つ問題がある。特定の文脈で優先順位を変えたくなる場合がある。たとえば、3 + 4 * -5にある単項マイナス演算子を考えよう。数学的には、単項マイナスは通常非常に高く、優先順位–乗算の前に評価される。しかしながら、我々の優先順位指定では、MINUSはTIMESより低い優先順位を持っている。これに対処するため、"架空のトークン"と呼ばれる優先順位規則を与えることができる。
class CalcParser(Parser):
...
precedence = (
('left', PLUS, MINUS),
('left', TIMES, DIVIDE),
('right', UMINUS), # Unary minus operator
)
ここで、文法ファイルに単項マイナスの規則を記述する。
@_('MINUS expr %prec UMINUS')
def expr(p):
return -p.expr
この例では、%prec UMINUSが規定規則による優先順位設定を、UMINUSの優先順位で上書きする。
初見だと、この例にあるUMINUSの用法が、非常に紛らわしく見えるかもしれない。UMINUSは入力トークンでも文法規則でもない。これは、優先順位表の中の特殊マーカーに付けた名称と考えると良い。 %prec修飾子を使用するとき、SLYに対し、その式の優先順位を通常の優先順位ではなく、特殊マーカーの優先順位と同様とするよう伝えていることになる。
また、優先順位表の中で、結合なしを指定することもできる。このやり方は、演算子同士を連続して_使いたくない_ときに使われる。たとえば、<と>の比較演算子をサポートしたいが、a < b < cのような組み合わせは求めていないと仮定する。このために、優先順位を以下のように指定する。
...
precedence = (
('nonassoc', LESSTHAN, GREATERTHAN), # Nonassociative operators
('left', PLUS, MINUS),
('left', TIMES, DIVIDE),
('right', UMINUS), # Unary minus operator
)
こうすることで、a < b < cのような入力テキストに対し、構文エラーが生成される。もちろん、a < bのような単純な式に対してはうまくいく。
還元/還元衝突は、与えられた記号のセットに対し、複数の文法規則が適用可能なときに引き起こされる。この類いの衝突はほぼ必ず間違いである。この衝突は文法ファイルの中で最初に現れた規則によって解決される。異なる文法規則の集合が､何らかの形で同じ記号のセットを生成しようとする場合に、還元/還元衝突が発生する。例：
assignment : ID EQUALS NUMBER
| ID EQUALS expr
expr : expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIVIDE expr
| LPAREN expr RPAREN
| NUMBER
この例では、2つの規則の間で還元/還元衝突が存在する。
assignment : ID EQUALS NUMBER
expr : NUMBER
たとえば、a = 5を構文解析しているとき、構文解析器はassignment : ID EQUALS NUMBERを還元するべきか、または5をexpressionとして還元してさらにassignment : ID EQUALS expr規則を還元するべきかを特定できない。
文法から還元/還元衝突を見つけ出すのが難しい、ということは周知の事実である。還元/還元衝突が発生すると、SLYは以下のような警告文を出して、助けを求める。
WARNING: 1 reduce/reduce conflict
WARNING: reduce/reduce conflict in state 15 resolved using rule (assignment -> ID EQUALS NUMBER)
WARNING: rejected rule (expression -> NUMBER)
このメッセージは、衝突状態にある規則が2つ存在することを特定している。しかし、なぜ構文解析器がそのような結論を出したかについて、このメッセージはなにも伝えてくれない。これを特定するためには、適度に高濃度なカフェイン添加を以て、文法と、構文解析器のデバッグファイルの内容を調べる必要があるだろう。
構文解析器のデバッグ
LR構文解析アルゴリズムの使用の中でも、移動/還元衝突と還元/還元衝突の掘り下げは歓喜の一言に尽きる。デバッグ処理を支援するため、SLYの構文解析表の作成時にデバッグファイルを出力させることができる。これには、クラスにdebugfile属性を追加する。
class CalcParser(Parser):
debugfile = 'parser.out'
...
このようにすると、指定したファイルに文法全体と、構文解析の状態が出力される。構文解析器の状態は以下のような形式で出力される。
state 2
(7) factor -> LPAREN . expr RPAREN
(1) expr -> . term
(2) expr -> . expr MINUS term
(3) expr -> . expr PLUS term
(4) term -> . factor
(5) term -> . term DIVIDE factor
(6) term -> . term TIMES factor
(7) factor -> . LPAREN expr RPAREN
(8) factor -> . NUMBER
LPAREN shift and go to state 2
NUMBER shift and go to state 3
factor shift and go to state 1
term shift and go to state 4
expr shift and go to state 6
状態は、その時点で照合過程の一部となり得る文法規則の追跡をする。各規則の中で、その規則の構文解析における現在位置が文字"."で示される。他にも、有効な入力トークンに対応する動作が一覧化されている。（若干の練習が必要だが、）これら規則を調査することで、構文解析における衝突を追跡することができるようになる。すべての移動/還元衝突が間違いとは限らないことを、強調しておこう。それらが正しく解決されることを確認する方法は、デバッグファイルの調査しかない。
構文エラー処理
業務用途の構文解析器を作成する場合、構文エラー処理を疎かにしてはならない。誰も、問題の兆候が出ただけでお手上げ状態になるような構文解析器を求めていない。そうす代わりに、入力に含まれる複数のエラーが利用者にまとめて報告される方が望ましい。そのためには、エラーを報告し、可能なら回復し、構文解析処理を継続させる必要がある。これは、C、C++、Javaなどの言語のコンパイラで見られる、ありふれた振る舞いである。
SLYでは、構文解析中に構文エラーが発生すると、そのエラーは即座に検出される（つまり、構文解析器はエラーの原因となる箇所を超えてトークンを読み取ることをしない）。その時点で構文解析器が復旧モードに入るため、そこで構文解析を継続するための試みが可能である。一般的に、LR構文解析器内でのエラー回復処理は古代の技術と黒魔術を含む繊細なトピックである。SLYによって提供される復旧の仕組みはUnix yaccに匹敵しており、その詳細はO'Reillyの"Lex and Yacc"を参照すると良い。
構文エラーが発生すると、SLYは以下の手順を実施する。
- エラーが発生したとき、最初に
error()メソッドが問題のトークンを引数にとって呼び出される。end-of-fileの到達による構文エラーでは、代わりにNoneが渡される。そして構文解析器は"エラー回復"モードに入り、少なくとも3つのトークンが構文解析スタック上で移動に成功するまでerror()メソッドの呼び出しは行なわれなくなる。 -
error()で回復動作が行なわれない場合、問題となっている先読トークンは特殊なerrorトークンに置き換えられる。 - 問題のある先読みトークンが既に
errorトークンに設定されると、構文解析スタックの先頭要素が削除される。 - 構文解析スタックが巻き戻されると、構文解析器は再起動状態に入り、初期状態からの構文解析の開始を試みる。
- 文法規則が
errorをトークンとして受容する場合、構文解析スタックにそれが移動される。 - 構文解析スタックの先頭が
errorとなった場合、構文解析器によって新しい記号が移動されるかerrorに巻き込まれた規則が還元されるまで、先読みトークンが破棄されていく。
エラー規則による回復処理と再同期
格調高い構文エラー処理を試みるには、文法規則内にerrorトークンを組み込むことである。print文の文法規則を持つとある言語を考えてみよう。
@_('PRINT expr SEMI')
def statement(self, p):
...
記述に問題がある可能性を考慮し、以下のような文法規則を追加しても良い。
@_('PRINT error SEMI')
def statement(self, p):
print("Syntax error in print statement. Bad expression")
この例のerrorトークンは、セミコロンが出現するまでの何らかのトークン列を照合する。セミコロンに到達するとその規則が呼び出され、errorトークンは消失する。
この種の回復処理は、構文解析の再同期処理と呼ばれることもある。errorトークンは不正な入力テキストに対するワイルドカードとして機能し、errorトークンの直後にあるトークンが同期トークンとして動作する。
通常、エラー規則の最右端errorトークンを置くことはない。例：
@_('PRINT error')
def statement(self, p):
print("Syntax error in print statement. Bad expression")
こうした規則で不正なトークンの先頭部分を還元できたとしても、さらにその直後に不正なトークンが継続していると、回復が困難になる。ここはやはり、セミコロン、閉じ括弧、その他同期点として使用できる境界の区切りをいくつか用意しておくとよい。
パニックモ－ド回復処理
別のエラー回復策として、それなりの手段で構文解析器が回復できる箇所までトークンを破棄する、パニックモード回復処理がある。
パニックモード回復処理は、そのすべてがerror()函数として実装される。たとえば、次の函数は閉じ括弧'}'に達するまでトークンを捨てる。その後、構文解析器は初期状態から再開する。
def error(self, p):
print("Whoa. You are seriously hosed.")
if not p:
print("End of File!")
return
# Read ahead looking for a closing '}'
while True:
tok = next(self.tokens, None)
if not tok or tok.type == 'RBRACE':
break
self.restart()
この函数は不正なトークンを破棄し、構文解析器にエラーから回復したことを伝える。
def error(self, p):
if p:
print("Syntax error at token", p.type)
# Just discard the token and tell the parser it's okay.
self.errok()
else:
print("Syntax error at EOF")
使用されている属性とメソッドについての詳細を示す。
-
self.errok()これは構文解析器をリセットし、すでにエラー回復モードではないことを示す。これによりerrorトークン生成の抑止と内部カウンターリセットを実施し、別の構文エラーが見つかったときに再度error()を呼び出せるようにする。 -
self.tokensこれは構文解析対象の列挙可能なシーケンスとなっている。next(self.tokens)を呼ぶことで、一つ先のトークンへと進ませる。 -
self.restart()構文解析スタックをすべて破棄し、構文解析器を初期状態へリセットする。
error()はトークンを一つ返すことにより、構文解析器に次の先読みトークンを渡すことができる。これは、特定文字での同期を試みる際に役立つ。例：
def error(self, tok):
# Read ahead looking for a terminating ";"
while True:
tok = next(self.tokens, None) # Get the next token
if not tok or tok.type == 'SEMI':
break
self.errok()
# Return SEMI to the parser as the next lookahead token
return tok
構文エラーの報告タイミング
入力中に不正なトークンが見つかると、多くの場合、SLYは即座にエラーを処理する。このとき、SLYがエラー処理を、一つ以上の文法規則が還元されるまでの間、遅延させようとすることに注意せよ。"既定の状態"として知られる背後の構文解析表上の特殊な状態によって、この動作が予期しない結果を引き起こす可能性がある。既定の状態とは、次の入力にかかわらず同じ文法規則が還元される構文解析器の状態である。そのような状態下のSLYは、_次の入力トークンを読まずに_先に進むことを選択し、文法規則を還元する。継続するトークンが不正であれば、SLYはそれを読み込もうとし、構文エラーを報告する。こうした文法エラーに先立って文法規則が実行される動作仕様は、変わったものに見えるかもしれない。
エラー処理についての一般論
通常の言語において、エラー規則と再同期文字によるエラーからの復旧は、最も信頼性の高い手法である。文法でエラーを拾えるようになり、比較的容易に復旧し、構文解析処理を継続できる。パニックモード回復処理は、入力テキストからごっそり内容をそぎ落とし、再開のための道を歩ませたい、といったある種特別なアプリケーションでのみ役立つ。
行番号と位置情報の追跡
位置情報の追跡は、コンパイラーの作成時にしばしば厄介な問題となる。規定動作では、SLYはどのあらゆるトークンの行番号や位置情報を追跡する。生成規則内で、以下の属性が役に立つ。
-
p.lineno生成規則中の左端にある終端記号の行番号。 -
p.index生成規則の左端にある終端記号の字句解析インデックス。
例）
@_('expr PLUS expr')
def expr(self, p):
line = p.lineno # line number of the PLUS token
index = p.index # Index of the PLUS token in input text
SLYは、非終端記号に対して行番号を伝搬しない。これを行なう必要がある場合、自身で行番号を格納し、ASTノード内で他のデータ構造にそれを伝搬させる必要がある。
AST（抽象構文木）の生成
SLYは抽象構文木の生成に関する特殊函数を提供しない。とはいえ、そうした構築処理は自前で簡単に実施できる。
木構造生成の簡易手法として、個々の文法規則函数でタプルやリストを生成し、伝搬させる方法がある。様々な実現方法があるが、そのうちの一つを示す。
@_('expr PLUS expr',
'expr MINUS expr',
'expr TIMES expr',
'expr DIVIDE expr')
def expr(self, p):
return ('binary-expression', p[1], p.expr0, p.expr1)
@_('LPAREN expr RPAREN')
def expr(self, p):
return ('group-expression',p.expr])
@_('NUMBER')
def expr(self, p):
return ('number-expression', p.NUMBER)
他にも、抽象構文木ノードの種類に応じたデータ構造を作り、規則の中で対応するノード型を生成する方法がある。
class Expr:
pass
class BinOp(Expr):
def __init__(self, op, left, right)
self.op = op
self.left = left
self.right = right
class Number(Expr):
def __init__(self, value):
self.value = value
@_('expr PLUS expr',
'expr MINUS expr',
'expr TIMES expr',
'expr DIVIDE expr')
def expr(self, p):
return BinOp(p[1], p.expr0, p.expr1)
@_('LPAREN expr RPAREN')
def expr(self, p):
return p.expr
@_('NUMBER')
def expr(self, p):
return Number(p.NUMBER)
この手法の利点は、より複雑な意味情報や型チェック、コード生成機能、ノードクラスのためのその他機能を付与できることにある。
開始記号の変更
通常、構文解析クラスに最初に現れる規則が、文法規則の開始規則（最上位規則）となる。これを変更するには、クラスにstart指定を追加する。例：
class CalcParser(Parser):
start = 'foo'
@_('A B')
def bar(self, p):
...
@_('bar X')
def foo(self, p): # Parsing starts here (start symbol above)
...
start指定は、巨大な文法の一部分のデバッグ処理で役に立つ。
埋め込み動作
SLYが使用する構文解析手法は、動作は規則の終了時に実行される。以下のような規則があると仮定する。
@_('A B C D')
def foo(self, p):
print("Parsed a foo", p.A, p.B, p.C, p.D)
この例では、提供された動作コードは、記号A、B、C、Dのすべてが構文解析がされた後に実行される。ときおり、ではあるが、構文解析の最中にで小さなコードの断片を実行させることが有効な場合がある。たとえば、Aが構文解析された直後に、いくつかの動作を実行させたい場合があるとする。このためには、空規則を作成する。
@_('A seen_A B C D')
def foo(self, p):
print("Parsed a foo", p.A, p.B, p.C, p.D)
print("seen_A returned", p.seen_A])
@_('')
def seen_A(self, p):
print("Saw an A = ", p[-1]) # Access grammar symbol to the left
return 'some_value' # Assign value to seen_A
この例ではAが構文解析スタックに移動された直後に空のseen_A規則が実行される。この規則の中でp[-1]は、スタック上にあるseen_A記号のすぐ左隣の記号を参照する。 上記のfoo規則では、Aの値となる。他の規則と同様に、埋め込み動作が値を返すことで、値が返却される。
埋め込み動作の使用は、希に余計な移動/還元衝突を引き起こす。たとえば、衝突を起こさない文法があるとする。
@_('abcd',
'abcx')
def foo(self, p):
pass
@_('A B C D')
def abcd(self, p):
pass
@_('A B C X')
def abcx(self, p):
pass
ここで、規則の一つに埋め込み動作を挿入したとする。
@_('abcd',
'abcx')
def foo(self, p):
pass
@_('A B C D')
def abcd(self, p):
pass
@_('A B seen_AB C X')
def abcx(self, p):
pass
@_('')
def seen_AB(self, p):
pass
これにより余計な移動/還元衝突が差し込まれる。この衝突は、abcd規則とabcx規則の双方で同じ記号Cが隣に出現する、という事実によって引き起こされる。構文解析器は記号の移動（abcd規則）と、規則seen_AB(abcx規則)の還元のどちらを実行しても良い。
埋め込み規則の一般的な使用法は、ローカル変数のスコープなど、構文解析の別の側面から制御を行なうことである。たとえばCのコードの構文解析をするなら、以下のようなコードを記述する。
@_('LBRACE new_scope statements RBRACE')
def statements(self, p):
# Action code
...
pop_scope() # Return to previous scope
@_('')
def new_scope(self, p):
# Create a new scope for local variables
create_scope()
...
この例のnew_scopeはLBRACE（{）記号が構文解析された直後に実行される。これが、内部の記号表と構文解析器とは別の側面の挙動を修正する。規則statementsが完了すると、コードが埋め込み動作で行なわれた操作（pop_scope()など）を元に戻す。