演算子優先順位パーサー

コンピュータサイエンスにおいて、演算子優先順位パーサーとは、演算子優先順位文法を解釈するボトムアップパーサーです。例えば、ほとんどの計算機は、演算順序に依存する人間が読める中置記法を、逆ポーランド記法（RPN）などの評価に最適化された形式に変換するために、演算子優先順位パーサーを使用しています。

Edsger Dijkstraの操車場アルゴリズムは、演算子優先順位パーサーの実装によく使用されます。

他のパーサーとの関係

演算子優先順位パーサは、 LR(1)文法のサブセットを解析できる単純なシフト還元パーサです。より正確には、演算子優先順位パーサは、連続する2つの非終端記号とイプシロンが規則の右側に出現しない すべてのLR(1)文法を解析できます。

演算子優先順位パーサーは実際にはあまり使用されませんが、大規模な設計において有用となる特性がいくつかあります。まず、演算子優先順位パーサーは手作業で記述できるほどシンプルです。これは、より洗練された右シフト還元パーサーでは一般的に当てはまりません。次に、実行時に演算子テーブルを参照するように記述できるため、解析中に演算子を追加または変更できる言語に適しています。(例えば、Haskellでは、ユーザー定義の挿入演算子に独自の結合性と優先順位を設定できます。そのため、参照されているすべてのモジュールを解析した後、プログラムに対して演算子優先順位パーサーを実行する必要があります。)

Rakuは、速度とダイナミズムのバランスをとるために、 2つの再帰下降パーサの間に演算子優先順位パーサを挟んでいます。GCCのCおよびC++パーサは、手作業でコーディングされた再帰下降パーサですが、算術式を高速に検査できる演算子優先順位パーサによって高速化されています。また、演算子優先順位パーサはコンパイラ生成のパーサにも組み込まれており、再帰下降アプローチによる式解析を大幅に高速化しています。[ 1 ]

優先順位上昇法

優先順位上昇法は、マーティン・リチャーズとコリン・ウィットビー・ストレベンスによって最初に説明された、式を解析するためのコンパクトで効率的かつ柔軟なアルゴリズムです。[ 2 ]

EBNF形式のインフィックス記法の式文法は、通常次のようになります。 

式:: =等式 等式:: =加法式( ( ' == ' | '! = ' )加法式) *加法式:: =乗法式( ( '+' | '-' )乗法式 ) *乗法式:: =プライマリ( ( ' * ' | ' / ' )プライマリ) *プライマリ:: = ' ( '式' ) ' | NUMBER | VARIABLE | ' - 'プライマリ

優先順位が多数ある場合、予測再帰下降パーサーでこの文法を実装すると非効率になる可能性があります。例えば、数値を解析する場合、文法内の非終端記号ごとに1つずつ、つまりprimaryに到達するまで5つの関数呼び出しが必要になることがあります。

演算子優先順位パーサーは、同じことをより効率的に行うことができます。[ 1 ] その考え方は、同じ優先順位の演算子が見つかる限り算術演算を左結合できるが、より高い優先順位の演算子を評価するために一時的な結果を保存する必要があるというものです。ここで提示するアルゴリズムは明示的なスタックを必要とせず、代わりに再帰呼び出しを使用してスタックを実装します。

このアルゴリズムは、ダイクストラ操車場アルゴリズムのような純粋な演算子優先順位パーサーではありません。再帰下降パーサーのように、主要な非終端記号は別のサブルーチンで解析されることを前提としています。

擬似コード

このアルゴリズムの擬似コードは次のとおりです。パーサーは関数parse_expressionから開始します。優先順位は0以上です。 

parse_expression() はparse_expression_1(parse_primary(), 0) を返します
parse_expression_1(lhs, min_precedence) lookahead  := 次のトークンを覗き見る 。lookaheadは優先順位が >= min_precedenceの二項演算子。op :  = lookahead 次のトークンに進む rhs  := parse_primary () lookahead  := 次のトークンを覗き見る lookaheadは二項演算子で あり、優先順位はopや右結合演算子 よりもその優先順位はop の優先 順位に等しいrhs  := parse_expression_1 ( rhs、opの優先順位 + (先読み優先順位の方が大きい 場合は 1 、そうでない場合は 0)) lookahead  := 次のトークンを覗く lhs :=オペランドlhsとrhsにop を適用した結果lhsを返す

次のような生成規則の場合（演算子は 1 回しか出現できない）に注意してください。 

等式:: =加法式( ' == ' | '! = ' )加法式

優先順位がmin_precedenceより大きい二項演算子のみを受け入れるようにアルゴリズムを変更する必要があります。

アルゴリズムの実行例

式 2 + 3 * 4 + 5 == 19 の実行例を以下に示します。等式には優先順位 0、加法式には優先順位 1、乗法式には優先順位 2 を割り当てます。

parse_expression_1 ( lhs = 2, min_precedence = 0)

  • 先読みトークンは + で、優先順位は 1 です。外側の while ループに入ります。
  • opは+（優先順位1）で、入力は進む
  • 右辺は3
  • 先読みトークンは*で、優先順位は2です。内側のwhileループに入ります。parse_expression_1 ( lhs = 3, min_precedence = 2)
  • 先読みトークンは * で、優先順位は 2 です。外側の while ループに入ります。
  • opは*（優先順位2）で、入力は進んでいる
  • 右辺は4
  • 次のトークンは + で、優先順位は 1 です。内部の while ループには入りません。
  • 左辺には3*4 = 12が割り当てられる
  • 次のトークンは + で、優先順位は 1 です。外側の while ループが終了します。
  • 12が返されます。
  • 先読みトークンは + で、優先順位は 1 です。内部の while ループには入りません。
  • 左辺は2+12=14となる
  • 先読みトークンは + で、優先順位は 1 です。外側の while ループは終了しません。
  • opは+（優先順位1）で、入力は進む
  • 右辺は5
  • 次のトークンは == で、優先順位は 0 です。内部の while ループには入りません。
  • 左辺は14+5=19に割り当てられる
  • 次のトークンは == で、優先順位は 0 です。外側の while ループは終了しません。
  • opは==（優先順位0）で、入力は進められる
  • 右辺は19
  • 次のトークンは行末ですが、これは演算子ではありません。内部の while ループには入りません。
  • lhs には、19 == 19 を評価した結果 (例: 1 (C 標準の場合)) が割り当てられます。
  • 次のトークンは行末ですが、これは演算子ではありません。外側の while ループが終了します。

1 が返されます。

プラット解析

プラット構文解析として知られるもう一つの優先順位解析器は、1973年の論文「Top Down Operator Precedence」[ 3 ]でヴォーン・プラットによって初めて記述されました。これは再帰降下法に基づいています。これは優先順位上昇法よりも古いものですが、優先順位上昇法の一般化と見なすことができます。[ 4 ]

プラットはもともとCGOLプログラミング言語を実装するためにパーサーを設計し、彼の指導の下で修士論文でさらに深く扱われました。[ 5 ]

チュートリアルと実装:

代替方法

演算子の優先順位規則を適用する方法は他にもあります。1つは、元の式のツリーを構築し、それにツリー書き換え規則を適用する方法です。

このようなツリーは、必ずしも従来のツリー構造を用いて実装する必要はありません。代わりに、どの要素をどの順序で処理するかを示す優先順位リストを同時に構築することで、トークンをテーブルなどのフラットな構造に格納できます。

完全な括弧

別のアプローチとしては、まず式全体を括弧で囲み、各演算子を複数の括弧で囲むことで、線形左から右への構文解析器で解析した場合でも正しい優先順位が得られるようにする方法がある。このアルゴリズムは初期のFORTRAN Iコンパイラで使用されていた。[ 7 ]

Fortran Iコンパイラは各演算子を括弧の列で展開します。アルゴリズムを簡略化すると、

  • +および を–それぞれ))+((およびに置き換えます))-((。
  • *および を/それぞれ)*(およびに置き換えます)/(。
  • ((各式の先頭と元の式の各左括弧の後に追加します。
  • ))式の最後と元の式の各右括弧の前に追加します。

明らかではないものの、アルゴリズムは正しく、クヌースの言葉を借りれば、「信じられないかもしれませんが、結果として得られる式は適切に括弧で囲まれています。」[ 8 ]

基本的な数学演算子( +、、、、、、および) の括弧-の処理*を実行/する単純な C アプリケーションの例コード: ^()

#include <stdio.h> #include <string.h>// コマンドライン引数の境界がレキサーです。int main ( int argc , char * argv [ ]) { int i ; printf ( "((((" ); for ( i = 1 ; i != argc ; i ++ ) { // strlen(argv[i]) == 2 if ( argv [ i ] && ! argv [ i ][ 1 ]) { switch ( * argv [ i ]) { case '(' : printf ( "((((" ); continue ; case ')' : printf ( "))))" ); continue ; case '^' : printf ( ")^(" ); continue ; case '*' : printf ( "))*((" ) ; continue ; case '/' : printf ( "))/((" ); continue ; case '+' : // 単項チェック: 最初または二次引数を期待する演算子があるif ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "+" ); else printf ( ")))+(((" );続行; case '-' : if ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "-" ); else printf ( ")))-(((" );続行; } } printf ( "%s" ,argv [ i ]); } printf ( ")))) \n " );戻り値0 ; }

まず、プログラムをコンパイルする必要があります。プログラムがC言語で記述されており、ソースコードがprogram.cというファイルにあると仮定すると、次のコマンドを使用します。 

gcc プログラム.c -o プログラム

上記のコマンドは、gcc に program.c をコンパイルし、program という名前の実行可能ファイルを作成するように指示します。

パラメータ付きでプログラムを実行するコマンド。例: a * b + c ^ d / e 

./プログラム a '*' b + c '^' d / e

それは生産する 

((((a))*((b)))+(((c)^(d))/((e))))

コンソールに出力されます。

この戦略の制限は、単項演算子はすべて中置演算子よりも高い優先順位を持つ必要があることです。上記のコードでは、「負」演算子は指数演算子よりも高い優先順位を持っています。この入力でプログラムを実行すると、 

- a ^ 2

この出力を生成する 

((((-a)^(2))))

それはおそらく意図されたものではないでしょう。

参考文献

  1. ^ a b Harwell, Sam (2008-08-29). 「演算子優先順位パーサー」 . ANTLR3 Wiki . 2017年10月25日閲覧。
  2. ^リチャーズ、マーティン、ウィットビー＝ストレベンス、コリン (1979). BCPL — 言語とそのコンパイラ. ケンブリッジ大学出版局. ISBN 9780521219655。
  3. ^ Pratt, Vaughan. 「トップダウン演算子の優先順位」第1回ACM SIGACT-SIGPLANプログラミング言語の原理に関するシンポジウム議事録（1973年）。
  4. ^ Norvell, Theodore. 「再帰降下法による表現の解析」 . www.engr.mun.ca.この記事の目的は、優先順位上昇から始め、コマンドパターンを使用するようにリファクタリングして、最終的にPrattパーサーに到達することです。[「優先順位上昇」という用語を作ったのはNorvellです。]
  5. ^ Van De Vanter, Michael L. 「 CGOL言語システムの形式化と正しさの証明」（修士論文）。MITコンピュータサイエンス研究所技術報告書MIT-LCS-TR-147（マサチューセッツ州ケンブリッジ）。1975年。
  6. ^ Crockford, D (2007-02-21). 「トップダウン演算子の優先順位」 .
  7. ^ Padua, David (2000). 「Fortran I コンパイラ」(PDF) . Computing in Science & Engineering . 2 (1): 70– 75. Bibcode : 2000CSE.....2a..70P . doi : 10.1109/5992.814661 . 2020年6月17日時点のオリジナル(PDF)からのアーカイブ。 2016年3月29日閲覧。
  8. ^ Knuth, Donald E. (1962). 「コンパイラ作成の歴史」 . Computers and Automation . 11 (12). Edmund C. Berkeley: 8–14 .
「 https://en.wikipedia.org/w/index.php?title=Operator-precedence_parser&oldid=1322027933」から取得