Python Language
Python Lex-Yacc
サーチ…
前書き
PLYは、一般的なコンパイラ構築ツールlexとyaccの純粋なPython実装です。
備考
PLY入門
Python2 / 3のマシンにPLYをインストールするには、以下の手順に従ってください：
- ここからソースコードをダウンロードしてください 。
- ダウンロードしたzipファイルを解凍する
- 解凍した
ply-3.10フォルダに移動します。 - 端末で次のコマンドを実行します：
python setup.py install
上記のすべてを完了したら、PLYモジュールを使用できるようになります。 Pythonインタプリタを開き、 import ply.lexと入力してテストすることができます。
注：PLYをインストールするためにpipを使用しないでください。マシンに壊れたディストリビューションがインストールされます。
「こんにちは、世界！」のPLY - 簡単な電卓
簡単な例を挙げてPLYの力を実証しましょう。このプログラムは算術式を文字列入力として受け取り、それを解決しようとします。
好きなエディタを開き、次のコードをコピーしてください：
from ply import lex
import ply.yacc as yacc
tokens = (
'PLUS',
'MINUS',
'TIMES',
'DIV',
'LPAREN',
'RPAREN',
'NUMBER',
)
t_ignore = ' \t'
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIV = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
def t_NUMBER( t ) :
r'[0-9]+'
t.value = int( t.value )
return t
def t_newline( t ):
r'\n+'
t.lexer.lineno += len( t.value )
def t_error( t ):
print("Invalid Token:",t.value[0])
t.lexer.skip( 1 )
lexer = lex.lex()
precedence = (
( 'left', 'PLUS', 'MINUS' ),
( 'left', 'TIMES', 'DIV' ),
( 'nonassoc', 'UMINUS' )
)
def p_add( p ) :
'expr : expr PLUS expr'
p[0] = p[1] + p[3]
def p_sub( p ) :
'expr : expr MINUS expr'
p[0] = p[1] - p[3]
def p_expr2uminus( p ) :
'expr : MINUS expr %prec UMINUS'
p[0] = - p[2]
def p_mult_div( p ) :
'''expr : expr TIMES expr
| expr DIV expr'''
if p[2] == '*' :
p[0] = p[1] * p[3]
else :
if p[3] == 0 :
print("Can't divide by 0")
raise ZeroDivisionError('integer division by 0')
p[0] = p[1] / p[3]
def p_expr2NUM( p ) :
'expr : NUMBER'
p[0] = p[1]
def p_parens( p ) :
'expr : LPAREN expr RPAREN'
p[0] = p[2]
def p_error( p ):
print("Syntax error in input!")
parser = yacc.yacc()
res = parser.parse("-4*-(3-5)") # the input
print(res)
このファイルをcalc.pyとして保存して実行してください。
出力：
-8
-4 * - (3 - 5)正解はどちらですか？
パート1：Lexで入力をトークン化する
一つは、抽出されたトークンを分析し、結果を評価することを含むれ、それは演算式を構成するシンボルを探し、そして第二のステップは、 解析された入力手段と、 トークン化された：実施例1からのコードを行うことを2つのステップがあります。
この節では、ユーザー入力をトークン化して1行ずつ細かく分割する方法の簡単な例を示します。
import ply.lex as lex
# List of token names. This is always required
tokens = [
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
]
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
# Build the lexer
lexer = lex.lex()
# Give the lexer some input
lexer.input(data)
# Tokenize
while True:
tok = lexer.token()
if not tok:
break # No more input
print(tok)
このファイルをcalclex.pyとして保存します。 Yaccパーサーをビルドするときにこれを使用します。
壊す
import ply.lexを使用してモジュールをimport ply.lexすべてのレクサーは、レクサーが生成できるすべての可能なトークン名を定義
tokensと呼ばれるリストを提供する必要があります。このリストは常に必要です。tokens = [ 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN', ]
tokensは、（文字列ではなく）文字列のタプルでもあり、各文字列は前と同じようにトークンを表します。
各文字列の正規表現ルールは、文字列または関数として定義できます。いずれの場合も、変数名の前にt_が付いていなければなりません。
単純なトークンの場合、正規表現は文字列として指定できます：
t_PLUS = r'\+'何らかのアクションを実行する必要がある場合、トークンルールを関数として指定できます。
def t_NUMBER(t): r'\d+' t.value = int(t.value) return tルールは関数内のドキュメント文字列として指定されていることに注意してください。この関数は、
LexTokenインスタンスである1つの引数をLexToken、何らかのアクションを実行してから引数を返します。ドキュメント文字列を指定する代わりに、関数の正規表現ルールとして外部文字列を使用する場合は、次の例を検討してください。
@TOKEN(identifier) # identifier is a string holding the regex def t_ID(t): ... # actionsLexTokenオブジェクトのインスタンス（このオブジェクトをtと呼ぶ）には、次の属性があります。-
t.typeはトークンタイプ（文字列）です（例：'NUMBER'、'PLUS'など）。デフォルトでは、t.typeはt_接頭辞の後の名前に設定されます。 -
t.valueあるt.value（実際のテキストにマッチしたもの） - 現在の行番号である
t.lineno（これは自動的には更新されません。これは、レクサーが行番号を何も知らないためです）。t_newlineという関数を使ってlinenoを更新してt_newline。
def t_newline(t): r'\n+' t.lexer.lineno += len(t.value)-
t.lexposは、入力テキストの先頭を基準とするトークンの位置です。
-
regexルール関数から何も返されなければ、トークンは破棄されます。トークンを破棄したい場合は、t_ignore_接頭辞を同じルールの関数を定義するのではなく、正規表現のルール変数に追加することもできます。
def t_COMMENT(t): r'\#.*' pass # No return value. Token discarded...同じです：
t_ignore_COMMENT = r'\#.*'これは、あなたがコメントを見たときに何らかのアクションを実行している場合、もちろん無効です。その場合、正規表現ルールを定義する関数を使用します。
いくつかの文字に対してトークンを定義していないがそれでも無視したい場合は、
t_ignore = "<characters to ignore>"（これらの接頭辞は必要です）。t_ignore_COMMENT = r'\#.*' t_ignore = ' \t' # ignores spaces and tabsマスター正規表現を構築するとき、lexはファイルに指定された正規表現を次のように追加します：
- 関数で定義されたトークンは、ファイルに表示される順序と同じ順序で追加されます。
- 文字列で定義されたトークンは、そのトークンの正規表現を定義する文字列の文字列長の降順に追加されます。
==と=を同じファイルにマッチさせる場合は、これらの規則を利用してください。
リテラルはそのまま返されるトークンです。
t.typeとt.value両方が文字そのものに設定されます。リテラルのリストを次のように定義します。literals = [ '+', '-', '*', '/' ]または、
literals = "+-*/"リテラルが一致したときに追加アクションを実行するトークン関数を記述することは可能です。ただし、トークンの種類を適切に設定する必要があります。例えば：
literals = [ '{', '}' ] def t_lbrace(t): r'\{' t.type = '{' # Set token type to the expected literal (ABSOLUTE MUST if this is a literal) return t
t_error関数でエラーを処理します。
# Error handling rule def t_error(t): print("Illegal character '%s'" % t.value[0]) t.lexer.skip(1) # skip the illegal token (don't process it)一般に、
t.lexer.skip(n)は入力文字列内のn個の文字をスキップします。
最終的な準備：
lexer = lex.lex()を使用してレクサーを構築します。また、クラス内のすべてを配置し、クラスのインスタンスを使用してレクサーを定義することもできます。例えば：
import ply.lex as lex class MyLexer(object): ... # everything relating to token rules and error handling comes here as usual # Build the lexer def build(self, **kwargs): self.lexer = lex.lex(module=self, **kwargs) def test(self, data): self.lexer.input(data) for token in self.lexer.token(): print(token) # Build the lexer and try it out m = MyLexer() m.build() # Build the lexer m.test("3 + 4") #データが文字列である
lexer.input(data)を使用して入力を提供するトークンを取得するには、一致したトークンを返す
lexer.token()を使用します。次のようにループ内でレクサーを反復処理できます。for i in lexer: print(i)
パート2：トークン化された入力をYaccで解析する
このセクションでは、パート1のトークン化された入力がどのように処理されるかについて説明します。これは、コンテキストフリーグラマー（CFG）を使用して行われます。文法を指定しなければならず、トークンは文法に従って処理されます。フードの下では、パーサーはLALRパーサーを使用します。
# Yacc example
import ply.yacc as yacc
# Get the token map from the lexer. This is required.
from calclex import tokens
def p_expression_plus(p):
'expression : expression PLUS term'
p[0] = p[1] + p[3]
def p_expression_minus(p):
'expression : expression MINUS term'
p[0] = p[1] - p[3]
def p_expression_term(p):
'expression : term'
p[0] = p[1]
def p_term_times(p):
'term : term TIMES factor'
p[0] = p[1] * p[3]
def p_term_div(p):
'term : term DIVIDE factor'
p[0] = p[1] / p[3]
def p_term_factor(p):
'term : factor'
p[0] = p[1]
def p_factor_num(p):
'factor : NUMBER'
p[0] = p[1]
def p_factor_expr(p):
'factor : LPAREN expression RPAREN'
p[0] = p[2]
# Error rule for syntax errors
def p_error(p):
print("Syntax error in input!")
# Build the parser
parser = yacc.yacc()
while True:
try:
s = raw_input('calc > ')
except EOFError:
break
if not s: continue
result = parser.parse(s)
print(result)
壊す
各文法規則は、その関数に対するdocstringが適切な文脈自由文法仕様を含む関数によって定義される。関数本体を構成するステートメントは、ルールのセマンティックアクションを実装します。各関数は、対応するルール内の各文法記号の値を含むシーケンスである単一の引数pを受け取ります。
p[i]の値は、次のように文法シンボルにマッピングされます。def p_expression_plus(p): 'expression : expression PLUS term' # ^ ^ ^ ^ # p[0] p[1] p[2] p[3] p[0] = p[1] + p[3]
トークンの場合、対応する
p[i]の "値"は、レクサーモジュールで割り当てられたp.value属性と同じです。したがって、PLUSは値+を持ちます。非端末の場合、値は
p[0]配置されているものによって決まります。何も配置されていない場合、値はNoneです。また、p[-1]と同じではないp[3]ので、p単純なリスト（ないp[-1]埋め込まれたアクション（ここでは論じない）を指定することができます）。
この関数は、 p_が前に付いている限り、任意の名前を持つことができます。
p_error(p)ルールは構文エラーを捕捉するように定義されています（yacc / bisonのyyerrorと同じ）。複数の文法ルールを1つの関数にまとめることができます。これは、プロダクションの構造が類似していれば良い考えです。
def p_binary_operators(p): '''expression : expression PLUS term | expression MINUS term term : term TIMES factor | term DIVIDE factor''' if p[2] == '+': p[0] = p[1] + p[3] elif p[2] == '-': p[0] = p[1] - p[3] elif p[2] == '*': p[0] = p[1] * p[3] elif p[2] == '/': p[0] = p[1] / p[3]トークンの代わりに文字リテラルを使用できます。
def p_binary_operators(p): '''expression : expression '+' term | expression '-' term term : term '*' factor | term '/' factor''' if p[2] == '+': p[0] = p[1] + p[3] elif p[2] == '-': p[0] = p[1] - p[3] elif p[2] == '*': p[0] = p[1] * p[3] elif p[2] == '/': p[0] = p[1] / p[3]もちろん、リテラルはレクサーモジュールで指定する必要があります。
空のプロダクションは、
'''symbol : '''持ってい'''symbol : '''明示的に開始シンボルを設定するには、
start = 'foo'使用しますfooはstart = 'foo'記号です。precedenceとassociativityの設定は、precedence変数を使用して行うことができます。
precedence = ( ('nonassoc', 'LESSTHAN', 'GREATERTHAN'), # Nonassociative operators ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ('right', 'UMINUS'), # Unary minus operator )トークンの優先順位は、優先順位の低い順に並べられます。
nonassocは、それらのトークンが関連しないことを意味します。これは、a < b < cようなものは違法でありa < bは依然として合法であることを意味する。parser.outは、yaccプログラムが初めて実行されたときに作成されるデバッグファイルです。シフト/リダクションの競合が発生するたびに、パーサーは常にシフトします。