50 行の Python コードで電卓を作成する

はじめに

この記事では、汎用の電卓のように四則演算式を解析して計算する方法を紹介します。完了すると、1+2*-(-3+2)/5.6+3 のような式を処理できる計算機が完成します。もちろん、拡張してさらに強力にすることもできます。

私の本来の目的は、文法解析と形式文法（編纂原理の内容）を解説する、簡単で面白い講座を提供することです。同時に、私が数年間断続的に改善してきた構文解析インターフェイスである PlyPlus を紹介したいと思います。このコースへのアドオンとして、最終的には eval() の安全な置き換えを行います。

この記事に記載されている例を自分のコンピューターで試してみたい場合は、まずコマンド pip install plyplus を使用して PlyPlus をインストールする必要があります。 (翻訳者注: pip は、Python で書かれたソフトウェア パッケージをインストールするために使用されるパッケージ管理システムです。具体的な使用方法は、Baidu または Google で見つけることができるので、詳細は説明しません。)

この記事では、Python の継承が必要です。理解するために使用します。

文法

解析と形式文法がどのように機能するかを理解していない人のために、ここで簡単に概要を説明します: 形式文法は、テキストを解析するために使用されるさまざまなレベルのルールのセットです。各ルールは、入力テキストの対応する部分がどのように構成されるかを記述します。展 ここに 1+2+3+4 を分析する方法を示す例があります:

ルール #1 - 加算は Add+Number

または Number

で作られます add: add'+'number

| number'+'number

;

パーサーは毎回 add+number または number+number を検索し、見つかった場合は add に変換されます。基本的に、すべてのパーサーの目標は、可能な限り最高レベルの式の抽象化を見つけることです。

パーサーの各ステップは次のとおりです:

数値 + 数値 + 数値 + 数値

最初の変換では、すべての数値が「数値」ルールに変換されます

[数値 + 数値] + 数値 + 数値

解析 プロセッサは、初めてのマッチングパターン！

[加算 + 数値] + 数値

パターンに変換した後、次の

[加算 + 数値]

加算

これらの順序付けされたシンボルは 1 つのレベルで 2 つの単純なシンボルになります ルール: 数値 + 数値そして加算+数値。この方法では、これら 2 つの問題を解決したかどうかをコンピューターに伝えるだけで、式全体を解析できます。実際、足し算のシーケンスがどんなに長くても、これが形式文法の力です。

演算子の優先順位

算術式は単なる記号の線形増加ではなく、演算子は暗黙の階層を作成します。これは正式な文法で表現するのに非常に適しています:

1 + 2 * 3 / 4 - 5 + 6

これは次と同等です:

1 + (2 * 3 / 4) - 5 + 6

この文法の構造は、ネストされたルールを通じて表現できます:

add: add+mul

| 'mul

;

mul: mul '*; 数値

| 数値'*'数値

;

数値の代わりに mul を演算するように add を設定すると、乗算優先ルールが得られます。

この魔法のパーサーを使用して 1+2*3*4 を分析するプロセスを頭の中でシミュレーションしてみましょう:

数値 + 数値 * 数値 * 数値

数値 + [数値 * 数値] * 数値

パーサーは、number+number の結果を知りません。そのため、これには別のオプションがあります (パーサー)

number + [mul * number]

number + mul

ここで、パーサーは少し困っています。 number+mul をどうすればいいのかわかりません。この状況を区別することはできますが、さらに探索を続けると、mul+number、add+number、add+add など、考慮されていないさまざまな可能性があることがわかります。

それで、私たちは何をすべきでしょうか？

幸いなことに、私たちはちょっとした「トリック」を行うことができます。数値自体を積として、また積自体を合計として考えることができます。

このアイデアは最初は少し奇妙に思えるかもしれませんが、意味はあります:

add: add'+'mul

| mul'+'mul

;

mul: mul' *'数値

| 数値'*'数値

| 数値

;

しかし、mul が add になり、number が mul になる可能性がある場合、一部の行の内容は冗長になります。それらを破棄すると、次のようになります:

add: add'+'mul

|

mul: mul'*'number

| number

;

1+ の実行をシミュレートしましょう文法を使用した 2*3*4:

数値 + 数値 * 数値 * 数値

数値 * 数値に対応するルールはありませんが、パーサーは「創造的」にすることができます

数値 + [数値] * 数値 * 数値

数値 + [mul * 数値] * 数値

数値 + [mul * 数値]

[数値] + mul

[mul] + mul

[add + mul]

add

成功しました! ！ ！

これが素晴らしいと思われる場合は、別の算術式でシミュレーションしてみて、その式が正しい方法で問題を段階的に解決できるかどうかを確認してください。または、待ってから次のセクションを読んで、コンピューターがどのように動作するかを段階的に確認してください。

パーサーを実行する

文法をどのように機能させるかについてかなり理解できたので、適用する実際の文法を書いてみましょう:

start: add;

add: add_symbol mul;

mul: mul mul_symbol number |number;

number:'[d.]+' // 10 進数の正規表現

mul_symbol:'*'|'/ ';// * または /

add_symbol: '+'|'-';// + または - に一致します

正規表現をブラッシュアップする必要があるかもしれませんが、いずれにしても、構文は非常に簡単です。式を使ってテストしてみましょう:

>>>fromplyplusimportGrammar

>>> g=Grammar("""...""")

>>>printg.parse('1+2* 3-5' ).pretty()

start

add

add_symbol

mul_sy mbol

5

素晴らしい仕事です!

ツリーをよく見て、パーサーがどのレベルを選択したかを確認してください。

このパーサーを自分で実行して独自の式を使用したい場合、必要なのは Python だけです。 Pip と PlyPlus をインストールした後、上記のコマンドを Python に貼り付けます ('...' を実際の構文に置き換えることを忘れないでください~)。

木の形を整える

Plyplus は自動的に木を作成しますが、必ずしも最適であるとは限りません。 mul に数値を入力し、mul に add を入力することは階層を作成するのに最適ですが、階層ができた今では負担になります。 Plyplus にプレフィックスを付けてルールを「展開」(つまり、削除) するように指示します。

@ はルールを展開することが多く、# はルールをフラット化し、子ノードがある場合は ? を使用してルールを展開します。この場合、必要なのは ? です。

start: add;

?add: add_symbol mul | mul; '[d.]+';

mul_symbol:'*'|'/';

add_symbol:'+'|'-';

新しい構文では、ツリーは次のようになります:

>>> g= Grammar("""...""")

>>>printg.parse('1+2*3-5')。 pretty()

start

add

add

number

1

add_symbol

数値

3

add_symbol

- -

数値

5

ああ、これはもっと簡単です。あえて言えば、とても良いです。

括弧処理とその他の機能

これまでのところ、括弧、単位演算子 (-(1+2))、式の途中での null 文字の許可など、必要な機能がまだ明らかに不足しています。実際、これらの機能は非常に簡単に実装できます。以下で試​​してみましょう。

最初に、原子という重要な概念を紹介する必要があります。アトム内で発生するすべての演算 (括弧内および単位演算) は、すべての加算または乗算演算 (ビット単位の演算を含む) より優先されます。アトムは単なる優先コンストラクターであり、文法的な意味を持たないため、コンパイル中に展開できるように「@」記号を追加してください。

式にスペースを使用できるようにする最も簡単な方法は、次の説明を使用することです。 ただし、この説明では冗長になり、読みにくくなります。したがって、Plyplus が常にスペースを無視するようにする必要があります。

上記の機能を含む完全な構文は次のとおりです:

start: add;

?add: (add add_symbol)? mul;

?mul: (mul mul_symbol)? | 数値 |'('add')';

neg:'-'atom;

number:'[d.]+';

mul_symbol:'*'|'/';

add_symbol:' + '|'-';

WHITESPACE:'[ t]+'(%ignore);

次のステップである計算に進む前に、この構文を必ず理解してください。

操作

これで、最終結果を得るためにツリーのブランチをブランチごとにスキャンするだけで済みます。

これからコードを書き始めます。その前に、このツリーについて 2 つのことを説明する必要があります:

1. 各ブランチは、次の 2 つの属性を含むインスタンスです:

ヘッド: ルール名 (add や番号); 末尾: 一致するすべてのサブルールのリストが含まれます。

2.Plyplusはデフォルトで不要なタグを削除します。この例では、「( 」、「)」および「-」が削除されます。ただし、add と mul には独自のルールがあり、Plyplus はそれらが必要であることを認識し、削除しません。これらのタグを保持する必要がある場合は、この機能を手動でオフにすることができますが、私の経験から、より良い結果を得るには、これを行わずに、関連する構文を手動で変更することをお勧めします。

本題に戻り、コードを書き始めます。非常に単純なコンバータを使用してこのツリーをスキャンします。最も外側のブランチからルート ノードに到達するまでスキャンを開始します。私たちの仕事は、スキャン方法を伝えることです。すべてがうまくいけば、常に最外層からスキャンが開始されます。どのように機能するかを見てみましょう。

>>>importoperator as op

>>>fromplyplusimportSTransformer

classCalc(STransformer):

def_bin_operator(self, exp):

arg1,operator_symbol,しっぽ

F Operator_func = {'+': OP.ADD,

'-': OP.Sub,

'*': OP.mul,

'/': OP.DIV} [Operator_symbol]

O Returnoperator_func (ARG1, ARG2)

数値 = lambdaseld, exp: float (exp.tail [0])

neg = lambdaseld, exp: -exp.tail [0] __Default _ Lambdas ELF, EXP: exp .tail[0]

add=_bin_operator

mul=_bin_operator

各メソッドはルールに対応します。メソッドが存在しない場合は、__default__ メソッドが呼び出されます。 start、add_symbol、mul_symbol は独自のブランチのみを返すため、省略しました。

数値の解析には float() を使用しました。これは遅延メソッドですが、パーサーを使用して実行することもできます。

ステートメントをわかりやすくするために、演算子モジュールを使用しました。たとえば、add は基本的に「lambda x,y: x+y」などです。

OK、このコードを実行して結果を確認しましょう。

>>> Calc().transform( g.parse('1 + 2 * -(-3+2) / 5.6 + 30'))

31.357142857142858

eval() はどうですか? 7

>>>eval('1 + 2 * -(-3+2) / 5.6 + 30')

31.357142857142858

成功:)

最後のステップ: REPL

美しさのためにこれを素敵な電卓にラップします REPL:

defmain():

calc=Calc()

whileTrue:

try:

s=raw_input('> ')

ExceptEOFError :

Break

ifs=='':

break

tree=calc_grammar.parse(s)

printcalc.transform(tree)

完全なコードはここから入手できます:

https://github.com/erezsh/plyplus/ blob/master/examples/calc.py