この節では、高度な機能をいくつか使用した文法の例を示します。例 1 の電卓を変更して、浮動小数点区間演算を実行できる電卓にしています。この電卓は、浮動小数点定数、算術演算子 +、-、*、/ 、および単項演算子 - を認識します。また、この電卓は、a 〜 z のレジスタを使用します。さらに、次のような X が Y より小さいまたは等しい区間演算も理解できます。
(X、Y)
A 〜 Z の 26 個の区間値変数を使用することもできます。使い方は例 1 の電卓と同様で、代入は値を返さず何も出力しませんが、式は (浮動小数点または区間) 値を出力します。
この例では、yacc と C の多数の機能を利用しています。区間は、double として保存されている左終点と右終点の値で構成される構造体で表されます。この構造体には、typedef
によって型名 INTERVAL が与えられます。
また、yacc の値スタックは、浮動小数点のスカラーと整数 (変数の値を格納する配列を指し示すために使用されます) を含むことができます。このプログラム全体の設計は、C 言語の構造体と共用体を割り当てることが可能ということに強く依存しているので注意してください。実際に、多くのアクションは構造体を返す関数を呼び出しています。
YYERROR を使用して、0 を含んだ区間による除算や、誤った順序で表された区間などのエラー状態を処理している点に注目してください。また、yacc のエラー回復メカニズムを使用して、残りの不正な行を無視しています。
値スタックでの型の混在に加え、この文法では、中間式の型 (スカラーや区間など) を監視する構文を使用することもできます。また、コンテキストで区間値が必要になった場合には、スカラー値を自動的に区間値に昇格できます。ただしその場合には、yacc によって文法が実行されたときに多数の衝突 (18 個の shift-reduce、26 個の reduce-reduce) が発生することになります。
この問題は、以下の 2 つの入力行で確認できます。
2.5 + (3.5 - 4.)
次に :
2.5 + (3.5, 4)
2 番目の例では区間値の式で 2.5 が使用されていますが、区間値であることはコンマを読み取るまでわからないということに注意してください。2.5 を読み取ったパーサーは、後戻りすることはできず、別の処理を行うことになります。一般的に、任意の数のトークンを先読みし、スカラーを区間に変換するかどうかを判断する必要があります。
この問題は、2 項区間値の演算子の規則を 2 つ用意することによって回避できます。1 つは、左側のオペランドがスカラーのときの規則、もう 1 つは、左側のオペランドが区間のときの規則です。後者の場合には、右側のオペランドを区間にする必要があります。それにより、変換は自動的に適用されます。
この問題回避を行なっても、変換するかどうかを判断しなければならないために、上記の衝突が発生する場合が多数あります。これらの問題は、スカラーを先に生成する規則を仕様ファイルに記述することによって解決されます。これにより、スカラー値の式は強制的に区間に変換されるまではスカラー値のまま維持されるため、衝突は解決されます。
複数の型を扱うこの方法は、参考になります。2 つだけでなくさまざまな型の式がある場合には、必要になる規則の数は大幅に増加し、衝突の数もさらに増加します。したがって、この例は確かに有益ですが、もっと普通のプログラミング言語環境における実践で、文法の一部ではなく値の一部として型の情報を扱うことをお勧めします。
最後に、字句解析に関する事項を説明します。このプログラムの唯一の特殊な機能は、浮動小数点定数の処理です。C 言語のライブラリルーチン atof() を使用して、文字列から倍精度の値への実際の変換を行なっています。字句アナライザは、エラーを検出すると、文法内の無効なトークンを返すことで応答します。これにより、パーサー内で構文エラーが発生し、エラー回復が行われます。yacc 仕様のコード例を以下に示します。
%{ #include <stdio.h> #include <ctype.h> typedef struct interval { double lo, hi; } INTERVAL; INTERVAL vmul(), vdiv(); double atof(); double dreg[26]; INTERVAL vreg[26]; %} %start lines %union { int ival; double dval; INTERVAL vval; } %token <ival> DREG VREG /* dreg と vreg 配列へのインデックス */ %token <dval> CONST /* 浮動小数点定数 */ %type <dval> dexp /* 式 */ %type <vval> vexp /* 区間式 */ /* 演算子に関する優先順位の情報 */ %left '+' '/-' %left '*' '/' %% /* 規則セクションの開始 */ lines : /* 空 */ | lines line ; line : dexp '¥n' { (void)printf("%15.8f¥n", $1); } | vexp '¥n' { (void)printf("(%15.8f, %15.8f)¥n", $1.lo, $1.hi); } | DREG '=' dexp '¥n' { dreg[$1] = $3; } | VREG '=' vexp '¥n' { vreg[$1] = $3; } | error '¥n' { yyerrok; } ; dexp : CONST | DREG { $$ = dreg[$1]; } | dexp '+' dexp { $$ = $1 + $3; } | dexp '-' dexp { $$ = $1 - $3; } | dexp '*' dexp { $$ = $1 * $3; } | dexp '/' dexp { $$ = $1 / $3; } | '-' dexp { $$ = -$2; } | '(' dexp ')' { $$ = $2; } ; vexp : dexp { $$.hi = $$.lo = $1; } | '(' dexp ',' dexp ')' { $$.lo = $2; $$.hi = $4; if($$.lo > $$.hi) { (void) printf("interval out of order¥n"); YYERROR; } } | VREG { $$ = vreg[$1]; } | vexp '+' vexp { $$.hi = $1.hi + $3.hi; $$.lo = $1.lo + $3.lo; } | dexp '+' vexp { $$.hi = $1 + $3.hi; $$.lo = $1 + $3.lo; } | vexp '-' vexp { $$.hi = $1.hi - $3.lo; $$.lo = $1.lo - $3.hi; } | dexp '-' vexp { $$.hi = $1 - $3.lo; $$.lo = $1 - $3.hi; } | vexp '*' vexp { $$ = vmul($1.lo, $1.hi, $3); } | dexp '*' vexp { $$ = vmul($1, $1, $3); } | vexp '/' vexp { if (dcheck($3)) YYERROR; $$ = vdiv($1.lo, $1.hi, $3); } | dexp '/' vexp { if (dcheck($3)) YYERROR; $$ = vdiv($1, $1, $3); } | '-' vexp { $$.hi = -$2.lo; $$.lo = -$2.hi; } | '(' vexp ')' { $$ = $2; } ; %% /* サブルーチンセクションの開始 */ # define BSZ 50 /* 浮動小数点数値のバッファーサイズ */ /* 字句解析 */ int yylex() { register int c; /* 空白文字は読み飛ばす */ while ((c=getchar()) = = ' ') ; if (isupper(c)) { yylval.ival = c - 'A'; return(VREG); } if (islower(c)) { yylval.ival = c - 'a'; return(DREG); } /* 数字、小数点、指数 */ if (isdigit(c) || c = = '.') { char buf[BSZ + 1], *cp = buf; int dot = 0, exp = 0; for (;(cp - buf) < BSZ; ++cp, c = getchar()) { *cp = c; if (isdigit(c)) continue; if (c = = '.') { if (dot++ || exp) return('.'); /* 構文エラーが発生する */ continue; } if (c = = 'e') { if (exp++) return('e'); /* 構文エラーが発生する */ continue; } /* 数字の終わり */ break; } *cp = '¥0'; if (cp - buf >= BSZ) (void)printf("constant too long -- truncated¥n"); else ungetc(c, stdin); /* 最後に読み取った char を元に戻す */ yylval.dval = atof(buf); return(CONST); } return(c); } INTERVAL hilo(a, b, c, d) double a, b, c, d; /* vmul と vdiv ルーチンで使用した a、b、c、d を含む最小区間を返す */ INTERVAL v; if (a > b) { v.hi = a; v.lo = b; } else { v.hi = b; v.lo = a; } if (c > d) { if (c > v.hi) v.hi = c; if (d < v.lo) v.lo = d; } else { if (d > v.hi) v.hi = d; if (c < v.lo) v.lo = c;: } return(v); } INTERVAL vmul(a, b, v) double a, b; INTERVAL v; { return(hilo(a * v.hi, a * v.lo, b * v.hi, b * v.lo)); } dcheck(v) INTERVAL v; { if (v.hi >= 0. && v.lo <= 0.) { (void) printf("divisor interval contains 0.¥n"); return(1); } return(0); } INTERVAL vdiv(a, b, v) double a, b; INTERVAL v; { return(hilo(a / v.hi, a / v.lo, b / v.hi, b / v.lo)); } |