演算子の優先順位解析器

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

parse_expression() はparse_expression_1(parse_primary(), 0)を返します。

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

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

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

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

式 2 + 3 * 4 + 5 == 19 の実行例は以下のとおりです。等式には 0、加算式には 1、乗算式には 2 の優先順位を与えます。

parse_expression_1 ( lhs = 2, min_precedence = 0)

• 先読みトークンは + で、優先順位は 1 です。外側の while ループに入ります。
• opは+（優先順位1）で、入力は進みます
• rhsは3です
• 先読みトークンは * で、優先順位は 2 です。内側の while ループに入ります。parse_expression_1 ( lhs = 3, min_precedence = 2)

• 先読みトークンは * で、優先順位は 2 です。外側の while ループに入ります。

• opは*（優先順位2）で、入力は進みます
• rhsは4です
• 次のトークンは + で、優先順位は 1 です。内部の while ループには入りません。
• lhsには3*4 = 12が割り当てられます
• 次のトークンは + で、優先順位は 1 です。外側の while ループが残ります。

• 12が返されます。

• 先読みトークンは + で、優先順位は 1 です。内側の while ループには入りません。
• lhsには2+12=14が割り当てられます
• 先読みトークンは + で、優先順位は 1 です。外側の while ループは終了しません。
• opは+（優先順位1）で、入力は進みます
• rhsは5です
• 次のトークンは == で、優先順位は 0 です。内部の while ループには入りません。
• lhsには14+5=19が割り当てられます
• 次のトークンは == で、優先順位は 0 です。外側の while ループは終了しません。
• opは==（優先順位0）で、入力が進みます
• rhsは19です
• 次のトークンは行末記号であり、演算子ではありません。そのため、内部のwhileループは実行されません。
• lhsには、19 == 19 の評価結果、例えば 1 (C 標準と同様) が代入されます。
• 次のトークンは行末文字であり、演算子ではありません。外側の while ループが終了します。

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 ( ")))+(((" ); continue ; case '-' : if ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "-" ); else printf ( ")))-(((" ); continue ; } } printf ( "%s" ,argv [ i ]); } printf ( ")))) \n " ); return0 ; }

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

gcc program.c -o program

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

パラメータを指定してプログラムを実行するコマンド。例：a * b + c ^ d / e

./program a '*' b + c '^' d / e

それは生み出す

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

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

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

- a^2

この出力を生成します

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

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