例
簡単な例
以下のコード例では、小型電卓に対して yacc を完全に適用する例を示します。この電卓は、a 〜 z の名前が付いた 26 個のレジスタを持っており、演算子 +、-、*、/、%、&、| と代入演算子で構成された算術式を使用できます。
最上位レベルの式が代入の場合は、その代入だけが行われます。それ以外の場合は、式が出力されます。C 言語の場合と同じように、0 で始まる整数は 8 進数とみなされます。それ以外は、10 進数とみなされます。
yacc 仕様の例として、この電卓プログラムでは、優先度とあいまいさの使い方を示し、簡単な回復処理も含まれています。大幅に簡略化されているのは字句アナライザの部分で、大部分のアプリケーションよりもかなり単純なものになっています。また出力は行ごとにすぐ生成されます。
構文規則によって 8 進 と 10 進の整数を読み取る方法に注目してください。このジョブは、字句アナライザで実行することもできます。
%{
# include <stdio.h>
# include <ctype.h>
int regs[26];
int base;
%}
%start list
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' %'
%left UMINUS /* 単項演算子 - の優先度を指定 */
%% /* 規則セクションの開始 */
list : /* 空 */
| list stat '¥n'
| list error '¥n'
{
yyerrok;
}
;
stat : expr
{
(void) printf( "%d¥n", $1 );
}
| LETTER '=' expr
{
regs[$1] = $3;
}
;
expr : '(' expr ')'
{
$$ = $2;
}
| expr '+' expr
{
$$ = $1 + $3;
}
| expr '-' expr
{
$$ = $1 - $3;
{
| expr '*' expr
{
$$ = $1 * $3;
}
| expr '/' expr
{
$$ = $1 / $3;
}
| exp '%' expr
{
$$ = $1 % $3;
}
| expr '&' expr
{
$$ = $1 & $3;
}
| expr '|' expr
{
$$ = $1 | $3;
}
| '-' expr %prec UMINUS
{
$$ = -$2;
}
| LETTER
{
$$ = reg[$1];
}
| number
;
number : DIGIT
{
$$ = $1; base = ($1= =0) ? 8 ; 10;
}
| number DIGIT
{
$$ = base * $1 + $2;
}
;
%% /* サブルーチンセクションの開始 */
int yylex( ) /* 字句解析ルーチン */
{ /* 小文字の場合は LETTER を返す */
/* yylval = 0 〜 25、DIGIT を返す */
/* 数字の場合、yylval = 0 〜 9 */
/* その他の文字はすぐに返される */
int c; /* 空白は読み飛ばす */
while ((c = getchar()) = = ' ')
;
/* c は空白以外の文字 */
if (islower(c)) {
yylval = c - 'a';
return (LETTER);
}
if (isdigit(c)) {
yylval = c - '0';
return (DIGIT);
}
return (c);
}
|
高度な例
この節では、高度な機能をいくつか使用した文法の例を示します。例 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));
}
|
- © 2010, Oracle Corporation and/or its affiliates