$BBh(B9$B>O(B $BB.=,(Byacc

$B35MW(B

$B%Q!<%5$H%9%-%c%J(B

$B%W%m%0%i%`8@8l$N%Q!<%5$N=q$-$+$?$O@N$+$i$7$D$3$/8&5f$5$l$F$-$F$*$j!"(B $B$+$J$j$7$C$+$j$7$?Dj@P$,$"$k!#$h$[$IJQ$J!J$^$?$O[#Kf$J!KJ8K!$G$J$$(B $B8B$j!"Dj@P$K$N$C$F$$$1$P2r7h$G$-$k$b$N$@!#(B

$B$^$::GDlJU$K$OJ8;zNs$rC18l!J%H!<%/%s$H$b8@$&!K$NNs$K@Z$j=P$9It(B $BJ,$,$"$k!#$3$l$r%9%-%c%J!J(Bscanner$B!K$H$+%l%/%5!J(Blexer$B!K$H8@(B $B$&!#F|K\8l$G8@$&$H;z6g2r@O4o$@$,!"8@$$$K$/$$$N$G%9%-%c%J$H8F$\$&!#(B

$B%9%-%c%J$H$$$&$b$N$,=P$F$/$k:,Dl$K$O$=$b$=$b!VC18l$N6h@Z$j$K$O6uGr$"$k(B $B$G$7$g!W$H$$$&>o<1$,$"$k!#$=$7$F

$BNc$($P8E$$(BFortran$B$G$O6uGr$,0UL#$r;}$?$J$+$C$?!#$D$^$j6uGr$rF~$l$F$b(B $BC18l6h@Z$j$H$O8B$i$J$$$7!"JQ?t$NESCf$G2?$NA0?($l$b$J$/6uGr$rA^F~$7$?$j(B $B$9$k$3$H$b$G$-$?!#$H$3$m$,2r@O$,62$m$7$/LLE]$J$b$N$G%3%s%Q%$%i%Y%s%@$,(B $B

$B$A$J$_$K(BFortran 77$B$,$J$<6uGr$K0UL#$r;}$?$;$J$+$C$?$+$H8@$&$H!"%W%m%0%i(B $B%`$r%Q%s%A%+!<%I$KBG$D$H$-$K6uGr$N?t$r4V0c$$$d$9$+$C$?$+$i!"$i$7$$!#(B

$B5-9fNs(B

$B%9%-%c%J$OC18l!J%H!<%/%s!K$NNs$rEG$-$@$9$H8@$C$?$,!"@53N$K8@$&$HC18l$G(B $B$O$J$$!#%9%-%c%J$,@8@.$9$k$N$O!V5-9f!W$NNs$G$"$k!#(B

$B5-9f$H$O$J$s$@$m$&$+!#Nc$($P?tCM$N$3$H$r9M$($F$_$h$&!#%W%m%0%i%`8@8l(B $B$J$i(B1$B$b(B2$B$b(B3$B$b(B99$B$bF1$8!V?t!W$@!#$I$l$bJ8K!E*$K$OA4$/F1$807$$$r$5$l$k!#(B 1$B$H=q$1$k>l=j$J$i(B2$B$b(B3$B$b=q$1$k!#$@$+$i%Q!<%5$H$7$F$_$l$PI,$:$7$b$3$l$i$r(B $BA4It6hJL$7$F07$&I,MW$O$J$$!#?tCM$J$i!V?tCM!W$G==J,$@!#(B

$B$=$N!V?tCM!W$H$+!V<1JL;R!W$N$h$&$J$b$N$r$^$H$a$F!V5-9f!J(Bsymbol$B!K!W(B $B$H8F$V!#(B $BF|K\8l$K$J$C$F$7$^$&$H0UL#$,$o$+$j$E$i$$$,!"$3$N>l9g$N5-9f$H$O!V0UL#!W(B $B$H$+!V>]D'!W$N$h$&$J0UL#$G;H$o$l$F$$$k!#$b$&$A$g$C$H$$$$8F$S$+$?$O$J$$(B $B$b$N$+$H9M$($?$N$@$,!"%7%s%\%k$H8@$&$H(BSymbol$B%/%i%9$N%$%s%9%?%s%9$HJ6$i(B $B$o$7$$!#(Bsymbol$B$H=q$/$HJQ?tL>$HJ6$i$o$7$$!#;EJ}$,$J$$$N$G$"$-$i$a$F!V5-(B $B9f!W$H8F$s$G$*$/$3$H$K$9$k!#(B

$B%9%-%c%J$O$^$:J8;zNs$rC18l$K6h@Z$j!"$=$7$F$=$N5-9f$r3d$j=P$9!#(B $BNc$($P?tCM$J$i(BNUMBER$B$d(BDIGIT$B!"(B $B!V(Bname$B!W$N$h$&$JL>A0!J<1JL;R!K$J$i(BIDENTIFIER$B!"(B $BM=Ls8l$N(Bif$B$J$i(BIF$B!"$H$$$&$h$&$K!#(B $B$=$7$F$=$N5-9f$r

$B%Q!<%5%8%'%M%l!<%?(B

$B$5$F%9%-%c%J$,EG$-$@$7$?C18l$H5-9f$NNs$r:#EY$O%D%j!<>u$KAH$_N)$F$F$$$/!#(B $B$3$N%D%j!<$r9=J8LZ!J(Bsyntax tree$B!K$H8@$&!#(B

$BC1$K%Q!<%5$H$$$&8@MU$r;H$&$H9=J8LZ$r:n$k$H$3$m$+$i%9%-%c%J$^$GA4It4^$a(B $B$k$3$H$b$"$k$N$G!"$3$N9=J8LZ$r:n$kAuCV$r8BDjE*$K695A$N%Q!<%5$H8F$\$&!#(B $B$=$N695A$N%Q!<%5$O$I$&$d$C$F$?$@$N5-9fNs$r%D%j!<$K$9$k$N$@$m$&$+!#(B $B8@$$49$($k$H!"2?$KCmL\$9$l$P%D%j!<$rH/8+$G$-$k$@$m$&$+!#(B

$B0l$D$O!"$=$NC18l$N;}$D0UL#$KCmL\$9$k$H$$$&var$B$H$$$&(B $BC18l$rH/8+$7$?$H$7$h$&!#$3$N$H$-$^$G$K%m!<%+%kJQ?t(Bvar$B$NDj5A$,H/8+$5$l(B $B$F$$$l$P!"$3$l$O%m!<%+%kJQ?t$N;2>H$@$J!"$H$o$+$k$O$:$G$"$k!#(B

$B$b$&0l$D$O$R$?$9$i8+$?$a$KCmL\$9$kJ}K!$G$"$k!#Nc$($P<1JL;R$N=$B$,Mh(B $B$?$i!"$3$l$OBeF~$@$J!"$H$o$+$k!#M=Ls8l$N(Bif$B$,EP>l$7$?$i!"$3$3$+$i$O(B if$BJ8$@$J!"$H$o$+$k!#(B

$B8e$C$F%D!<%k$G<+F02=$G$-$k$+$i$G$"$k!#(B $B$=$N<+F02=%D!<%k$r%Q!<%5%8%'%M%l!<%?!J(Bparser generator$B!K$H8@$&!#(B

$B$=$7$F(BUNIX$B$G0lHV;H$o$l$F$$$k%Q!<%5%8%'%M%l!<%?$,(Byacc$B$@!#(Bruby$B$N(B $B%Q!<%5$b8fB?J,$KO3$l$:$3$N(Byacc$B$r;H$C$F=q$+$l$F$$$k!#(Bparse.y$B$,$=$N(B $BF~NO$@!#$D$^$j(Bruby$B$N%Q!<%5$rFI$`$?$a$K$O(Byacc$B$N$3$H$r$"$kDxEYCN$C$F(B $B$*$+$J$1$l$P$J$i$J$$!#(B

$B$=$3$GK\>O$O(Bparse.y$B2r@O$NA0=`Hw$H$7$F(Byacc$B$N4JC1$J2r@b$r9T$&$,!"$"$/$^(B $B$GFI$`$N$KI,MW$J:G>.8B$N@bL@$K$H$I$a$k!#$b$C$H>\$7$/%Q!<%5$H%Q!<%5%8%'(B $B%M%l!<%?$K$D$$$FCN$j$?$$FI

$B$=$l$G$b$d$C$Q$jJL$N?M$N$,$$$$!"$H$$$&$3$H$J$i(B $B%*%i%$%j!<$N!X(Blex&yacc$B%W%m%0%i%_%s%0!Y(B \footnote{$B!X(Blex&yacc$B%W%m%0%i%_%s%0!Y(BJohn R. Levine, Tony Mason, Doug Brown$BCx!"B<>eNsLu!"%"%9%-!<=PHG6I!"(B1994} $B$r$*4+$a$9$k!#(B $B$=$l$G$b$^$@K~B-$G$-$J$1$l$P$"$H$O(BAho$B$N(B $B!X%3%s%Q%$%i!Y(B \footnote{$B!X%3%s%Q%$%i!Y(BAlfred V.Aho, Ravi Sethi, Jeffrey D.Ullman$B6&Cx!"86ED8-0lLu!"%5%$%(%s%9

$BJ8K!(B

$BJ8K!%U%!%$%k(B

yacc$B$X$NF~NO$OJ8K!%U%!%$%k$H8@$&!#J8K!$r=q$$$?%U%!%$%k$@$+$iJ8K!%U%!%$(B $B%k$@!#J8K!%U%!%$%k$O(B*.y$B$H$$$&%U%!%$%kL>$K$9$k$N$,47Nc$G$"$k!#(B $B$3$l$r(Byacc$B$K$+$1$k$H(BC$B$N%=!<%9%3!<%I$,$G$-$k$N$G!"(B $B$"$H$OIaCJDL$j$=$l$r%3%s%Q%$%k$9$l$P$h$$!JA4BN?^$O?^(B1$B!K!#(B

(build)
$B?^(B1: $B%U%!%$%k4X78?^(B

$B$J$*!"=PNO%U%!%$%kL>$O>o$K(By.tab.c$B$G!"JQ99$G$-$J$$!#(B $B?7$7$$(Byacc$B$@$H$?$$$F$$%3%^%s%I%i%$%s%*%W%7%g%s$GJQ99$G$-$k$,!"(B $B8_49@-$r9M$($k$H(By.tab.c$B$K$7$F$*$$$?$[$&$,L5Fq$G$"$k!#(B $B$A$J$_$K(By.tab.c$B$N(Btab$B$O(Btable$B$N(Btab$B$i$7$$!#5pBg$J%F!<%V%k$,$?$/$5$s(B $BDj5A$5$l$F$$$k$+$i$@!#0lEY%U%!%$%k$rGA$$$F$_$k$H$$$$!#(B

$B$5$F!"J8K!%U%!%$%k$NCf?H$O

$B"'J8K!%U%!%$%k357A(B

%{
$B%X%C%@(B
%}
%union ....
%token ....
%type ....

%%
$B5,B'It(B
%%
$B%f!<%6Dj5AIt(B

yacc$B$NF~NO$O$^$:(B%%$B$GBg$-$/;0$D$K6hJ,$5$l$k!#:G=i$N0l$D(B $B$ODj5AIt$H8@$$!"$$$m$$$m$JDj5A$r$7$?$jA0=`Hw$r=q$/!#FC$K(B%{$B$+$i(B %}$B$^$G$O(BC$B8@8l$G9%$-$J$3$H$,=q$1$k>l=j$G$"$k!#$3$3$K$ONc$($PI,MW$J%^(B $B%/%m$r=q$$$?$j$9$k!#$=$N30$G$O(B%$B$r;H$C$?(Byacc$BFCM-$NL?Na$,B3$/!#$3$3$G;H(B $B$&L?Na$K$D$$$F$O$=$NETEY@bL@$7$h$&!#(B

$B??$sCf$O5,B'It$H8@$&!#(Byacc$B$N0lHV4N?4$J$H$3$m$G!"$3$3$K!V$3$&$$$&J8K!$r(B $B%Q!<%9$7$?$$$s$@!W$H=q$$$F$*$/$H%Q!<%5$,$G$-$k!#>\$7$/$O

$B:G8e$N0l$D!"%f!<%6Dj5AIt$O%f!<%6$,<+M3$K;H$C$F$h$$!#(Byacc$B$O$3$3$NFbMF$K(B $B$OA4$/4XCN$;$:!"0l;z0l6g$=$N$^$^=PNO%U%!%$%k$K%3%T!<$7$F$/$l$k!#(B $BNc$($P%Q!<%9$N$H$-$KI,MW$K$J$kJd=u%k!<%A%s$r=q$$$?$j$9$k$N$K;H$&!#(B

yacc$B$N$9$k$3$H(B

yacc$B$,LLE]$r8+$F$/$l$k$N$Oyacc$B$,$=$l$r(Byyparse()$B$H$$$&4X?t$KJQ49$7$F$/$l$k!#(B $B$3$l$,$D$^$j695A$N%Q!<%5$G$"$k!#(B

$B695A$N!"$J$N$G!"$=$NB>$K%9%-%c%J$,I,MW$G$"$k!#$7$+$7(Byacc$B$O%9%-%c%J$^$G(B $B$OLLE]$r8+$F$/$l$J$$$N$G%f!<%6$,MQ0U$7$J$1$l$P$J$i$J$$!#(B $B%9%-%c%J$O(Byylex()$B$H$$$&4X?t$G$"$k!#(B

$B$=$l$+$i!"(Byyparse()$B$K$7$F$b(Byacc$B$,@8@.$7$F$/$l$k$N$O$=$NCf$N$5$i$K4N?4(B $B$JItJ,$@$1$G!"8e=R$9$k!V%"%/%7%g%s!W$H$$$&$H$3$m$O$[$H$s$I(Byacc$B$NHO0O30(B $B$K$J$k!#$=$l$G$O(Byacc$B$N3hLv$9$kItJ,$,>/$J$9$.$J$$$+!"$H;W$&$+$b$7$l$J$$(B $B$,!"$5$K$"$i$:!#$=$N!V4N?4$JItJ,!W$H$$$&$N$,$"$^$j$K$b(B $B4N?4$9$.$k$+$i$3$=!"$J$s$@$+$s$@$HJ86g$r8@$o$l$D$D$b(Byacc$B$,$$(B $B$^$@$K@8$-;D$C$F$$$k$N$G$"$k!#$G$O$=$N4N?4$JItJ,$H$O$$$C$?$$2?$J$N$+!"(B $B$H$$$&OC$K$J$k$o$1$@!#(B

BNF

C$B$G%Q!<%5$r=q$/$H$9$k$H!"$=$N%3!<%I$O!VJ8;zNs$N$3$3$r$3$&@Z$C$F!"$3$l(B $B$r(Bif$BJ8$K$7$F!D!D!W$H$J$k!#%Q!<%5%8%'%M%l!<%?$r;H$&>l9g$O$=$N5U$G!"!V$3(B $B$&$$$&J8K!$r%Q!<%9$7$?$$$s$@!W$H8@$($P$$$$!#$=$&$9$k$H$=$NJ8K!$r07$&%Q!<(B $B%5$r@8@.$7$F$/$l$k!#$D$^$j;EMM$rEA$($k$Hyacc$B$NJXMx$J$H$3$m$G$"$k!#(B

$B$G$O$I$&$d$C$F;EMM$rEA$($k$N$@$m$&$+!#(B yacc$B$N>l9g$O(BBNF$B!J(BBackus-Naur Form$B!K(B $B$H$$$&5-=RJ}K!$r;H$&!#$4$/$4$/4JC1$JNc$r8+$F$_$h$&!#(B 

if_stmt: IF expr THEN stmt END

$B!V(B:$B!W$N:81&$GJ,$1$F8+$k!#:8B&$N$b$N!"$D$^$j(Bif_stmt$B$O!"1&B&$NJB$S$KEy$7(B $B$$!D!D$H$$$&$N$,!"$3$3$G8@$C$F$$$k$3$H$@!#$D$^$j(B

if_stmt$B$O(BIF expr THEN stmt END$B$H$$$&JB$S$HEy$7$$(B

$B$H8@$C$F$$$k$N$@!#$3$3$G(Bif_stmt$B$d(BIF$B$d(Bexpr$B$d!D!D$OA4$F!V5-9f!W$G$"$k!#(B expr$B$O(Bexpression$B!J<0!K!"(Bstmt$B$O(Bstatement$B!JJ8!K$NN,$N$D$b$j$@!#$3$l$O(B $B$-$C$H(Bif$BJ8$NDj5A$J$s$@$m$&!#(B

$B$3$NDj5A0l$D$N$3$H$r5,B'$H8@$&!#$=$7$F!V(B:$B!W$N:8B&$r!V:8JU!W!"(B $B1&B&$r!V1&JU!W$H8F$V!#

$B$5$F$7$+$7!"$3$l$@$1$G$O$A$g$C$H$b$N$?$j$J$$!#(Bif$BJ8$J$i(Belse$B$bIU$1$i$l$J(B $B$$$H7y$@!#$=$l$b!"$$$D$b(Belse$B$r=q$/$N$OLLE]$J$N$G(Belse$B$,I,MW$J$$$H$-$O(B $B>JN,$G$-$k$h$&$K$7$?$$!#$=$&$$$&$H$-$O 

if_stmt: IF expr THEN stmt END
       | IF expr THEN stmt ELSE stmt END

$B!V(B|$B!W$O!V(Bor$B!J$^$?$O!K!W$N0UL#$G$"$k!#(B

if_stmt$B$O!"!V(BIF expr THEN stmt END$B!W$H$$$&JB$S$+(B $B$^$?$O!V(BIF expr THEN stmt ELSE stmt END$B!W$H$$$&JB$S$G$"$k!#(B

$B$H$$$&$3$H$@!#(B

$B$3$3$GCm0U$7$F$[$7$$$N$O!"(B|$B$G6h@Z$k$H$=$l$@$1$G5,B'$O0l$DA}$($F$$(B $B$k$H$$$&$3$H$@!#|$B$G6h@Z$k$H$$$&$N$O:8JU$N5-=R$r>JN,$7$F$$$k$@$1$G(B $B$"$j!"O@M}E*$K$O@hDx$NNc$O 

if_stmt: IF expr THEN stmt END
if_stmt: IF expr THEN stmt ELSE stmt END

$B$D$^$j@hDx$NNc$GDj5A$7$?5,B'$OFs$D$G$"$k!#(B

$B$3$l$@$1$G(Bif$BJ8$NDj5A$,407k$7$?$o$1$G$O$J$$!#(Bexpr$B$d(Bstmt$B$J$s$F5-9f(B $B$O%9%-%c%J$+$iAw$i$l$F$/$k$O$:$,$J$$$+$i!"$=$l$,$I$&$$$&JB$S$J$N$+$r$A$c(B $B$s$HDj5A$7$J$$$H$$$1$J$$!#(BRuby$B$K6aIU$1$k$Y$/!"BgC@$K5,B'$rB-$7$F$_$h$&!#(B 

stmt   : if_stmt
       | IDENTIFIER '=' expr   /* $BBeF~(B */
       | expr

if_stmt: IF expr THEN stmt END
       | IF expr THEN stmt ELSE stmt END

expr   : IDENTIFIER       /* $BJQ?t;2>H(B */
       | NUMBER           /* $B@0?tDj?t(B */
       | funcall          /* $B4X?t8F$S=P$7!J(BFUNction CALL$B!K(B */

funcall: IDENTIFIER '(' args ')'

args   : expr             /* $B$H$j$"$($:0z?t$O0l$D$@$1(B */

$B?7$7$$MWAG$rFs$D;H$C$?!#$^$:(BC$B8@8l$HF1$87A<0$N%3%a%s%H!"$=$l$+$i(B'='$B$N$h(B $B$&$JJ8;z$NI=8=$@!#$3$N(B'='$B$b$d$O$j5-9f$G$"$k!#(B $B!V(B=$B!W$N$h$&$J5-9f$O?t$J$I$H0c$C$F$?$@0l'='$B$G$$$$$N$@!#$HMh$l$PM=Ls8l$J$I$K$bJ8;zNs$r(B $B$=$N$^$^;H$$$?$/$J$k$,!"(BC$B8@8l$N@)Ls$N$?$a$=$l$O$G$-$J$$!#(B

$B$3$&$$$&$U$&$K5,B'$rA}$d$7$F$$$C$F!"=>$&$Y$-5,B'A4BN$,=q$1$l$PJ8K!$N$G(B $B$-$"$,$j$@!#(Byacc$B$G$O0lHV>e$K=q$$$?5,B'$N:8JU$,!VI=8=$7$?$$J8K!A4BN!W$r(B $BI=$9$3$H$K$J$C$F$$$k$N$G!"$3$NNc$J$i(Bstmt$B$,%W%m%0%i%`A4BN$rI=$9$3$H$K$J(B $B$k!#(B

$B$A$g$C$HCj>]E*$K$9$.$?!#$b$&>/$76qBNE*$K@bL@$7$h$&!#!V(Bstmt$B$,%W%m%0%i%`(B $BA4BN$rI=$9!W$H$$$&$N$O!"(Bstmt$B$H5,B'>e!VEy$7$$!W5-9f$NJB$SA4$F$,J8K!$H$7(B $B$FG'$a$i$l$k!"$H$$$&$3$H$G$"$k!#Nc$($P$^$:!"(Bstmt$B$O(Bstmt$B$HEy$7$$!#$"$?$j(B $B$^$($@!#expr$B$O(Bstmt$B$HEy$7$$!#$3$l$O5,B'$=$N$^$^$@!#$=$7$FNUMBER$B$O(Bstmt$B$HEy$7$$!#$J$<$J$i(BNUMBER$B$O(Bexpr$B$G(Bexpr$B$O(Bstmt$B$@$+$i$@!#(B

$B$b$A$m$s$b$C$HJ#;($J$b$N$bEy$7$$$H8@$($k!#(B 

              stmt
               $B"-(B
             if_stmt
               $B"-(B
      IF expr THEN stmt END
          $B"-(B        $B"-(B
IF IDENTIFIER THEN expr END
                    $B"-(B
IF IDENTIFIER THEN NUMBER END

$B$3$3$^$GE83+$7$?$H$3$m$GA4It%9%-%c%J$+$iAw$i$l$F$/$k5-9f$K$J$C$?$h$&$@!#(B $B$D$^$j$3$&$$$&5-9f$NJB$S$O%W%m%0%i%`$H$7$F@5$7$$$H$$$&$3$H$G$"$k!#5U$K(B $B8@$($P!"$3$&$$$&5-9f$NJB$S$,%9%-%c%J$+$iAw$i$l$F$/$k$H%Q!<%5$OE83+$N5U(B $B$N=g=x$GF~NO$rM}2r$7$F$$$1$k!#(B 

IF IDENTIFIER THEN NUMBER END
                    $B"-(B
IF IDENTIFIER THEN expr END
          $B"-(B        $B"-(B
      IF expr THEN stmt END
               $B"-(B
             if_stmt
               $B"-(B
              stmt

$B$=$7$F(Bstmt$B$O%W%m%0%i%`A4BN$rI=$95-9f$@!#$@$+$i$3$N5-9fNs$O%W%m%0%i%`$H(B $B$7$F@5$7$$!#$H!"%Q!<%5$O;W$&$3$H$@$m$&!#$=$&$J$k$H%Q!<%9%k!<%A%s(B yyparse()mail protected]$7$?$H$$$&0u$K(B0$B$rJV$7$F=*N;$9$k!#(B

$B$A$J$_$K@lLgMQ8l$@$H%Q!<%[email protected]$N$3$H$r

$B=*C<5-9f$HHs=*C<5-9f(B

$B$5$F!"$I$5$/$5$KJ6$l$F!V%9%-%c%J$+$iMh$k5-9f!W$J$s$F8@MU$r@bL@$J$7$GF~(B $B$l$F$_$?$o$1$@$,!"2~$a$F@bL@$7$h$&!#

$B0l$D$O%9%-%c%J$+$iAw$i$l$F$/$k5-9f!"Nc$($P(BIF$B!"(BTHEN$B!"(BEND$B!"(B'='$B$J$I(B $B$G$"$k!#$3$l$r=*C<5-9f!J(Bterminal symbol$B!K$H8@$&!#@hDx$N$h$&$K$I$s$I$s(B $BE83+$7$?$H$-$K0lHVC<$C$3$KJB$V$+$i$@!#K\>O$G$O=*C<5-9f$O>o$KA4$FBgJ8;z(B $B$G5-=R$9$k!#$?$@$7(B'='$B$N$h$&$K%/%*!<%H$G$/$/$C$F$"$k$b$N$OFCJL$@!#$3$N(B $BN`$N5-9f$ONc30$J$/=*C<5-9f$G$"$k!#(B

$B$b$&0l$D$O%9%-%c%J$+$i$O@dBP$KMh$J$$5-9f!"Nc$($P(Bif_stmt$B!"(Bexpr$B!"(B stmt$B$G$"$k!#$3$&$$$&5-9f$rHs=*C<5-9f!J(Bnonterminal symbol$B!K$H(B $B8@$&!#Hs=*C<5-9f$O%9%-%c%J$+$iMh$J$$$o$1$@$+$i!"%Q!<%5$NCf$@$1$NB8:_$@!#(B $B$=$7$FHs=*C<5-9f$O$$$D$+I,$:5,B'$N:8JU$K8=$l$k!#K\>O$G$OHs=*C<5-9f$OA4(B $B$F>.J8;z$G5-=R$9$k!#(B

$B%F%9%H$NJ}K!(B

$B$3$3$i$GJ8K!%U%!%$%k$r(Byacc$B$G 

%token A B C D E
%%
list: A B C
    | de

de  : D E

$B$^$:;H$C$F$$$k=*C<5-9f$r(B%token$B$N$"$H$KA4$FJB$Y$k!#(B $B$?$@$7%/%*!<%H$r;H$C$?5-9f!J(B'='$B$J$I!K$O=q$+$J$/$F$h$$!#(B $B$=$7$F(B%%$B$G6h@Z$C$FJ8K!$r=q$/!#$3$l$@$1$@!#(B

$B$G$O=hM}$7$F$_$h$&!#(B 

% yacc first.y
% ls
first.y  y.tab.c
%

UNIX$B%D!<%k$N>o$H$7$F!VD@L[[email protected]$N0U!W$G$"$k!#(B

$B$=$l$+$i!"5,B'!J72!K$N:G8e$K%;%_%3%m%s$,I,MW$J(Byacc$B$bB8:_$9$k!#(B $B$=$N$H$-$O 

%token A B C D E
%%
list: A B C
    | de
    ;

de  : D E
    ;

$BI.o$K>JN,$9$k!#(B

$B6u5,B'(B

$B$G$O$b$&>/$7(Byacc$B$NJ8K!5-=R$NDj@P$r$$$/$D$+8+$F$*$/$3$H$K$9$k!#(B $B$^$:$O6u5,B'$+$i>R2p$7$h$&!#(B 

void:

$B1&JU$K2?$b$J$$!#$H$$$&$3$H$O!"5-9f(Bvoid$B$O!VL5!W$HEy$7$$$H$$$&$3$H$G$"(B $B$k!#Nc$($Ptarget$B$OA4$/F1$80UL#$K$J$k!#(B 

target: A B C

target: A void B void C
void  :

$B$3$s$J$b$N$,2?$NLr$KN)$D$N$@$m$&$+!#$=$l$,$H$F$bLr$KN)$D$N$@!#(B $BNc$($P 

if_stmt : IF expr THEN stmts opt_else END

opt_else:
        | ELSE stmts

$B6u5,B'$r;H$&$3$H$G!V(Belse$B@a$O>JN,$5$l$k!JL5!K$+$b$7$l$J$$!W$3$H$r(B $B$&$^$/I=8=$G$-$?!#@hDx$N$h$&$KF1$8$h$&$J5,B'$rFs$DJB$Y$F=q$/$h$j$b(B $B$3$A$i$N$[$&$,4J7i$@$7!"@UG$$,J,;6$7$J$/$F$h$$!#(B

$B:F5"Dj5A(B

$B/$7$o$+$j$K$/$$!#(B 

list: ITEM         /*  $B5,B'(B1  */
    | list ITEM    /*  $B5,B'(B2  */

$B$3$l$O0l8D0J>e$N(BITEM$B$rJB$Y$?%j%9%H$rI=8=$7$F$$$k!#(B $B$D$^$j0J2<$N5-9fNs$N$$$:$l$+$r<($9!#(B 

ITEM
ITEM ITEM
ITEM ITEM ITEM
ITEM ITEM ITEM ITEM
      $B!'(B

$B$I$&$7$F$+$o$+$k$@$m$&$+!#$^$:5,B'(B1$B$K$h$j(B list$B$O(BITEM$B$HFI$_49$($k$3$H$,$G$-$k!#(B $B$9$k$H:#EY$O5,B'(B2$B$+$i(Blist$B$O(BITEM ITEM$B$@$H8@$($k$h$&$K$J$k!#(B 

list: list ITEM
    = ITEM ITEM

$B$3$l$G(BITEM ITEM$B$H$$$&5-9fNs$b(Blist$B$HEy$7$$$H$o$+$k!#(B $B$3$l$r$^$?$5$i$K5,B'(B2$B$N(Blist$B$K$"$F$O$a$l$P(BITEM$B;0$D$b(Blist$B$KEy$7$$$H8@$(!D!D(B $B$3$l$r$I$s$I$sB3$1$l$P(BITEM$B$r$$$/$i$G$bA}$d$7$F$$$1$k!#(B $B?t3XE*5"G

$BITEM$B$r%<%m8D0J>eJB$Y$?%j%9%H$rI=$9!#(B 

list:
    | list ITEM

$B$^$:0l9TL\$O!V(Blist$B$O!JL5!K$HEy$7$$!W$H$$$&0UL#$G$"$k!#(B $BL5$H$OB($A(BITEM$B%<%m8D$N%j%9%H$G$"$k!#(B $Blist ITEM$B!W$O(BITEM$B0l8D$HEy$7$$$H8@$($k!#(B $B$J$<$J$i(Blist$B$OL5$HEy$7$$$+$i$@!#(B 

list: list ITEM
    =$B!JL5!K(BITEM
    =      ITEM

$B@hDx$HF1$8$h$&$K$3$NCV$-49$(:n6H$r2?EY$bB3$1$l$P!"(Blist$B$O%<%m8D0J>e(B $B$N(BITEM$B$N%j%9%H$NI=8=$G$"$k$H$o$+$k!#(B

$B$3$NCN<1$r1~MQ$9$l$P!V(BITEM$B$,Fs8D0J>e$N%j%9%H!W$H$+!V(BITEM$B$,;08D0J>e$N%j%9%H!W(B $B$O4JC1$@$7!"!V(BITEM$B$,6v?t8D$N%j%9%H!W$J$s$F$b$N$b:n$l$k!#(B 

list:
    | list ITEM ITEM

$BCM$N9=C[(B

$BCj>]E*$JOC$,B3$$$?$N$G$3$N@a$O;W$$$-$jJ*M}E*$KOC$r?J$a$?$$$H;W$&!#(B

$B%7%U%H$H4T85(B

$B$3$3$^$G$G$OJ8K!$N=q$-$+$?$r$$$m$$$m@bL@$7$F$-$?$,!"2f!9$,$d$j$?$$$N$O(B $B$"$/$^$G9=J8LZ$r:n$k$3$H$@!#$7$+$7;DG0$J$,$i5,B'$rEA$($k$@$1$G9=J8LZ$^(B $B$G:n$C$F$/$l$k$o$1$G$O!"$5$9$,$K$J$$!#$=$3$G:#EY$O5,B'$K%W%i%9%"%k%U%!(B $B$7$F9=J8LZ$r:n$kJ}K!$r65$($h$&!#(B

$B$^$:%Q!<%5$,8= 

%token A B C
%%
program: A B C

$B%Q!<%5$NCf$K$O%;%^%s%F%#%C%/%9%?%C%/!J(Bsemantic stack$B!K$H8F$P$l$k%9%?%C(B $B%/$,0l$D$"$k!#$=$7$F$3$l$K%9%-%c%J$+$iMh$k5-9f$r$I$s$I$s%W%C%7%e$7$F$$(B $B$/!#$3$NF0:n$N$3$H$r;X$7$F!V5-9f$r%7%U%H!J(Bshift$B!K$9$k!W$H8@$&!#(B 

[ A B ] $B"+(B C   $B%7%U%H(B

$B$=$7$FJ8K!$N$$$:$l$+$N1&JU$K$"$kJB$S$,%9%?%C%/$N@hC<$KB7$&$H!"(B $B$3$l$r!VM}2r!W$9$k!#!VM}2r!W$9$k$H1&JU$NJB$S$,:8JU$N5-9f$KJQ$o$k!#(B 

[ A B C ]
    $B"-(B         $B4T85(B
[ program ]

$B$3$NF0:n$r!V(BA B C$B$r(Bprogram$B$K4T85!J(Breduce$B!K$9$k!W$H8@$&!#(B $B8@MU$O0N$=$&$@$,$h$&$9$k$KGrb$Cf$,B7$&$HBg;085$K$J$k$h$&$J$b$N$@!#(B $B!D!D$=$l$O0c$&$+!#(B

$B$=$7$F(Bprogram$B$O%W%m%0%i%`A4BN$rI=$9$+$i!"%9%?%C%/$K(Bprogram$B$@$1$,$"$k$H(B $B$$$&$3$H$O%W%m%0%i%`A4BN$r8+IU$1$?$N$+$b$7$l$J$$!#$@$+$i$3$3$G$A$g$&$I(B $BF~NO$,=*$o$l$P

$B$b$&>/$7$@$1J#;($JJ8K!$G;n$7$F$_$h$&!#(B 

%token IF E S THEN END
%%
program : if

if      : IF expr THEN stmts END

expr    : E

stmts   : S
        | stmts S

$B%9%-%c%J$+$i$NF~NO$O$3$&$@!#(B 

IF  E  THEN  S  S  S  END

$B$3$N$H$-$N%;%^%s%F%#%C%/%9%?%C%/$NA+0\$r0J2<$K<($9!#(B

$B%9%?%C%/(B$BF0:n(B
$B:G=i$O6u(B
IFIF$B$r%7%U%H(B
IF EE$B$r%7%U%H(B
IF exprE$B"*(Bexpr$B$G4T85(B
IF expr THENTHEN$B$r%7%U%H(B
IF expr THEN SS$B$r%7%U%H(B
IF expr THEN stmtsS$B"*(Bstmts$B$G4T85(B
IF expr THEN stmts SS$B$r%7%U%H(B
IF expr THEN stmtsstmts S$B"*(Bstmts$B$G4T85(B
IF expr THEN stmts SS$B$r%7%U%H(B
IF expr THEN stmtsstmts S$B"*(Bstmts$B$G4T85(B
IF expr THEN stmts ENDEND$B$r%7%U%H(B
ifIF expr THEN stmts END$B"*(Bif$B$G4T85(B
programif$B"*(Bprogram$B$G4T85(B
accept.

$B:G8e$K0l$D$@$1Cm0U!#4T85$G$O5-9f$,8:$k$H$O8B$i$J$$!#(B $B6u5,B'$,$"$k$H!VL5!W$+$i5-9f$,@8@.$5$l$k>l9g$b$"$k!#(B

$B%"%/%7%g%s(B

$B$5$F!"$3$3$+$i$,=EMW$J$H$3$m$@!#%7%U%H$@$m$&$,4T85$@$m$&$,!"%;%^%s%F%#%C(B $B%/%9%?%C%/$NCf$G%&%@%&%@$d$C$F$$$k$@$1$G$O2?$N0UL#$b$J$$!#2f!9$N:G=*L\(B $BI8$O9=J8LZ$r@8@.$9$k$3$H$@$C$?$+$i!"$=$l$K$D$J$,$C$F$/$l$J$$$H:$$k$N$@!#(B yacc$B$O$I$&Mn$H$7$^$($rIU$1$k$D$b$j$J$N$+!#!V%Q!<%5$,4T85$9$k=V4V$r%U%C(B $B%/$G$-$k$h$&$K$7$^$7$g$&!W$H$$$&$N$,(Byacc$B$N=P$7$?Ez$($@!#$=$N%U%C%/$r(B $B%Q!<%5$N%"%/%7%g%s!J(Baction$B!K$H8@$&!#%"%/%7%g%s$O 

program: A B C { /* $B$3$3$,%"%/%7%g%s(B */ }

{$B$H(B}$B$G0O$s$@ItJ,$,%"%/%7%g%s$@!#$3$&=q$$$F$*$/$H(BA B C$B$r(Bprogram$B$K(B $B4T85$9$k=V4V$K$3$N%"%/%7%g%s$r

$B5-9f$NCM(B

$B$=$7$F$3$3$+$i$,$5$i$K=EMW$J$N$@$,!"A4$F$N5-9f$K$O!V$=$NCM!W$H$$$&$b$N(B $B$,$"$k!#=*C<5-9f$bHs=*C<5-9f$b$@!#=*C<5-9f$O%9%-%c%J$+$iMh$k$+$i$=$NCM(B $B$b%9%-%c%J$+$i$b$i$&!#$=$l$ONc$($P5-9f(BNUMBER$B$KBP$7$F$O(B1$B$H$+(B9$B$H$+(B 108$B$+$b$7$l$J$$!#5-9f(BIDENTIFIER$B$KBP$7$F$O(B"attr"$B$H$+(B"name"$B$H$+(B "sym"$B$+$b$7$l$J$$!#$J$s$G$b$$$$$N$@!#$=$NCM$O5-9f$H$$$C$7$g$K%;%^%s(B $B%F%#%C%/%9%?%C%/$K@Q$^$l$k!#S$B$rCM$H0l=o$K%7%U%H$7(B $B$?$H$3$m$@!#(B 

IF    expr   THEN   stmts   S
$BCM(B    $BCM(B     $BCM(B     $BCM(B     $BCM(B

$B@hDx$N5,B'$K$h$l$P(Bstmts S$B$O(Bstmts$B$K4T85$G$-$k!#$b$7$=$N5,B'$K%"%/%7%g%s(B $B$,=q$$$F$"$l$P$=$l$, 

IF    expr   THEN   stmts  S      /* $B%9%?%C%/(B */
$BCM(B1   $BCM(B2    $BCM(B3    $BCM(B4    $BCM(B5
                    $B"-(B     $B"-(B
            stmts:  stmts  S      /* $B5,B'(B */
                    $B"-(B     $B"-(B
                  { $1  +  $2; }  /* $B%"%/%7%g%s(B */

$B$H!"$3$N$h$&$K%"%/%7%g%s$G$O(B$1$B!"(B$2$B!"(B$3$B!D!D(B $B$G5,B'1&JU$KAjEv$9$k5-9f$NCM$r$1$B$H$+(B$2$B$O%9%?%C%/$r;X$9I=8=$K(Byacc$B$,=q$-49$($F$/$l$k$o$1$@!#(B $B$b$C$H$b(BC$B8@8l$J$iK\Ev$O7?$N$3$H$H$+$$$m$$$m$"$k$N$@$1$l$I!"(B $BLLE]$J$N$GEvLL(Bint$B$H2>Dj$7$F$*$3$&!#(B

$B$=$7$F$$$B$HI=8=$5$l!"%"%/%7%g%s$rH4$1$?$H$-$N(B$$$B$NCM$,:8JU$N5-9f$NCM$H$J$k!#(B 

IF    expr   THEN   stmts  S      /* $B4T85D>A0$N%9%?%C%/(B */
$BCM(B1   $BCM(B2    $BCM(B3    $BCM(B4    $BCM(B5
                    $B"-(B     $B"-(B
            stmts:  stmts  S      /* $B1&JU$,KvHx$K%^%C%A$7$?5,B'(B */
              $B",(B    $B"-(B     $B"-(B
            { $$  = $1  +  $2; }  /* $B$=$N%"%/%7%g%s(B */


IF    expr   THEN   stmts         /* $B4T858e$N%9%?%C%/(B */
$BCM(B1   $BCM(B2    $BCM(B3    ($BCM(B4+$BCM(B5)

$B:G8e$K

yacc$B$H7?(B

$B$5$FYYSTYPE$B$H$$$&7?$K$J$k!#$-$C$H$3$l$O(B YY Stack TYPE$B$+!"$O$?$^$?(BSemantic value TYPE$B$+!"$I$A$i$+$NN,$K0c$$$J$$!#(B $B$=$7$F(BYYSTYPE$B$OEvA32?$+JL$N7?$N(Btypedef$B$G$"$k!#$=$N7?$H$O!"Dj5AIt$G(B %union$B$H$$$&L?Na$G;XDj$7$?6&MQBN$@!#(B

$B$@$,:#$^$G$O(B%union$B$J$s$F=q$$$F$$$J$+$C$?!#$=$l$J$N$K%(%i!<$K$J$i$J$+$C(B $B$?$N$O$I$&$$$&$o$1$@$m$&!#$=$l$O(Byacc$B$,5$$r$-$+$;$F>!int$B$@!#$H$$$&$3$H(B $B$G(BYYSTYPE$B$N%G%U%)%k%H$O(Bint$B$G$"$k!#(B

yacc$B$NK\$K=P$9Nc$dEEBn%W%m%0%i%`$/$i$$$J$i(Bint$B$N$^$^$G$b9=$o$J$$$N$@$,!"(B $B9=J8LZ$r:n$k$K$O9=B$BN$d%]%$%s%?$d$=$NB>$$$m$$$m$r;H$$$?$$!#$=$3$GNc$((B $B$P%union$B$r;H$&!#(B 

%union {
    struct node {
        int type;
        struct node *left;
        struct node *right;
    } *node;
    int num;
    char *str;
}

$B:#$O$OE,Ev$@!#IaDL$N(BC$B$H0c$C$F(B %union$B$N%V%m%C%/$N:G8e$K$O%;%_%3%m%s$,I,MW$J$$$N$GCm0U!#(B

$B$=$l$G!"$3$&=q$/$H(By.tab.c$B$G$O 

typedef union {
    struct node {
        int type;
        struct node *left;
        struct node *right;
    } *node;
    int num;
    char *str;
} YYSTYPE;

$B$=$&$9$k$H%;%^%s%F%#%C%/%9%?%C%/$O(B 

YYSTYPE yyvs[256];       /* $B%9%?%C%/$N



$B$H$$$&46$8$@$m$&$J!"$HM=A[$,IU$/!#(B
$B$=$l$J$i%"%/%7%g%s$K=P$F$/$k5-9f$NCM$b!D!D(B




/* yacc$B=hM}A0$N%"%/%7%g%s(B */
target: A B C { func($1, $2, $3); }

/* $BJQ498e!"(By.tab.c$B$G$NMM;R(B */
{ func(yyvsp[-2], yyvsp[-1], yyvsp[0]); ;





$BEvA3$3$&$J$k!#(B





$B$3$N>l9g$O%G%U%)%k%H$N(Bint$B$r;H$C$?$N$G%9%?%C%/$r;2>H$9$k$@$1$G$h$$$,!"(B
YYSTYPE$B$,6&MQBN$N>l9g$OF1;~$K$=$N%a%s%P$b;XDj$7$J$1$l$P%"%/%;%9$G$-(B
$B$J$$$O$:$G$"$k!#$=$l$K$O5-9fC10L$G7k$SIU$1$kJ}K!$H$=$NETEY;XDj$9$k(B
$BJ}K!$NFsDL$j$,$"$k!#(B





$B$^$:$O0lHLE*$J!"5-9fC10L$G;XDj$9$kJ}K!$+$i!#=*C<5-9f$N>l9g$O(B
%token$B$r!"Hs=*C<5-9f$N>l9g$O(B%type$B$r;H$C$F


%token<num> A B C    /* $BA4$F$N(BA B C$B$NCM$O(Bint$B7?(B */
%type<str> target    /* $BA4$F$N(Btarget$B$NCM$O(Bchar*$B7?(B */





$B0lJ}!"Kh2s;XDj$9$k>l9g$O$$B$N$r3d$j9~$^$;$k!#(B




%union { char *str; }
%%
target: { $<str>$ = "$B$h$&$9$k$K%-%c%9%H$_$?$$$J$b$N$5(B"; }





$B$3$A$i$NJ}K!$O$G$-$k$@$1;H$o$J$$$[$&$,$$$$!#(B
$B5-9fC10L$G%a%s%P$r7h$a$k$N$,4pK\$@!#(B






$B%Q!<%5$H%9%-%c%J$NO"7k(B




$B$3$l$G%Q!<%5$NCf$NCM$N%"%l%3%l$K$D$$$F$OA4$FOC$7$?!#$"$H$O%9%-%c%J(B
$B$H$NO"7k%W%m%H%3%k$rOC$;$P3K$H$J$k;v9`$OA4$F$*$7$^$$$@!#(B





$B$^$:3NG'$9$k$H!"%9%-%c%J$O4X?t(Byylex()$B$G$"$C$?!#(B
$B!J=*Cint$B$G!KJV$9!#(Byacc$B$,5-(B
$B9f$HF1$8L>A0$GDj?t$r(B#define$B$7$F$/$l$F$$$k$N$G!"5-9f(BNUMBER$B$J$i(BNUMBER$B$H(B
$B=q$/$@$1$G$$$$!#$=$7$F$=$NCM$O(Byylval$B$H$$$&%0%m!<%P%kJQ?t$KF~$l$FEO$9!#(B
$B$3$N(Byylval$B$b$^$?(BYYSTYPE$B7?$G!"%Q!<%5$N$H$-$HA4$/F1$8$3$H$,8@$($k!#$D$^(B
$B$j(B%union$B$GDj5A$9$k$H6&MQBN$K$J$k!#$7$+$7:#2s$O%a%s%P$r>!$r=q$+$J$$$H$@$a$@!#$D$^$jHs>o$K4JC1$J(B
$BNc$@$H


static int
yylex()
{
    yylval.str = next_token();
    return STRING;
}





$B$3$3$^$G$N4X78$r?^(B2$B$K$^$H$a$?$N$G0l$D0l$D3NG'$7$F$_$F$[$7$$!#(B
yylval$B!"(B$$$B!"(B$1$B!"(B$2$B!D!D$J$I!"%$%s%?!<%U%'%$%9$H$J$kJQ?t$OA4$F(B
YYSTYPE$B7?$G$"$k!#(B





(yaccvars)

$B?^(B2: yacc$B4XO"$NJQ?t!&4X?t$N4X78(B






$BKd$a9~$_%"%/%7%g%s(B




$B%"%/%7%g%s$O5,B'$N:G8e$K=q$/$b$N!"$H@bL@$7$?$,!"


target: A B { puts("embedded action"); } C D





$B$3$l$rKd$a9~$_%"%/%7%g%s$H8@$&!#(B
$BKd$a9~$_%"%/%7%g%s$O


target: A B dummy C D

dummy :     /* $B6u5,B'(B */
        {
            puts("embedded action");
        }





$B$3$B$H$7$F=P$F$/$k!#(B






















$B8=


$B>WFM(B




$B$b$&$3$l$G(Byacc$B$J$s$F62$/$J$$!#(B





$B$H;W$C$?$H$7$?$i$=$l$O$+$J$j4E$$!#$J$<(Byacc$B$,$3$l$[$I$^$G$K(B
$B62$l$i$l$k$N$+!"$=$NM}M3$O$3$N8e$K$"$k$N$@!#(B





$B$3$l$^$G$O!V5,B'$N1&JU$,%9%?%C%/@hC<$K%^%C%A$7$?$i!W$H2?5$$J$/=q$$$F(B
$B$-$?$,!"


target  : A B C
        | A B C





$BA B C$B$H$$$&5-9fNs$,=P$F$-$?$H$-!"$I$A$i$N5,B'$,%^%C%A$9$k$N$+(B
$B$o$+$i$J$/$J$k$O$:$G$"$k!#$3$s$J$b$N$O?M4V$K$@$C$FM}2r$G$-$J$$!#(B
$B=>$C$F(Byacc$B$b$o$+$i$J$$!#$3$&$$$&JQ$JJ8K!$rH/8+$9$k$H(Byacc$B$O(B
reduce/reduce conflict$B!J4T85!&4T85>WFM!K$,5/$-$?!"$HJ86g$r(B
$B8@$C$F$/$k!#J#?t$N5,B'$,F1;~$K4T852DG=$G$"$k$H$$$&0UL#$@!#(B




% yacc rrconf.y
conflicts:  1 reduce/reduce





$B$H$O$$$(IaDL$J$i$P;v8N0J30$K$3$s$J$3$H$O$7$J$$$H;W$&$,!"(B
$B


target  : abc
        | A bc

abc     : A B C

bc      :   B C





$B$3$l$J$i$PHf3SE*$"$j$&$k!#FC$K5,B'$r9M$($J$,$i%0%A%c%0%A%c0\(B
$BF0$7$F$$$k$HCN$i$:CN$i$:$N$&$A$K$3$s$J5,B'$,$G$-$F$7$^$&$b$N$@!#(B





$B;w$?%Q%?!<%s$G


target  : abc
        | ab C

abc     : A B C

ab      : A B





A B C$B$H$$$&5-9fNs$,8=$l$?>l9g!"(Babc$B0l$D$rA*$V$Y$-$+(Bab$B$H(BC$B$NAH$_(B
$B9g$o$;$K$9$Y$-$+$o$+$i$J$$!#$3$&$$$&$H$-(Byacc$B$O(B
shift/reduce conflict$B!J%7%U%H!&4T85>WFM!K$,5/$-$?$>!"$HJ86g$r?b$l$k!#(B
$B$3$A$i$O!"F1;~$K%7%U%H$G$-$k5,B'$H4T85$G$-$k5,B'$,$"$k$H$$$&0UL#$@!#(B




% yacc srconf.y
conflicts:  1 shift/reduce





shift/reduce conflict$B$NM-L>$JNc$,!V$V$i$5$,$j(Belse$BLdBj!W$G$"$k!#(B
$BNc$($P(BC$B8@8l$N(Bif$BJ8$G$3$NLdBj$,5/$3$k!#OC$rC1=c2=$7$F=q$$$F$_$h$&!#(B




stmt     : expr ';'
         | if

expr     : IDENTIFIER

if       : IF '(' expr ')' stmt
         | IF '(' expr ')' stmt  ELSE stmt





$B<0$O(BIDENTIFIER$B!JJQ?t!K$@$1!"(Bif$B$NK\BN$OJ80l$D$@$1$H$7$F5,B'$r:n$C$F$_$?!#(B
$B$5$F!"$3$NJ8K!$G


if (cond)
    if (cond)
        true_stmt;
    else
        false_stmt;





$B$3$&=q$$$F$7$^$&$H$J$s$H$J$/0lL\NFA3$K8+$($k$N$@$,!"(B
$B


if (cond) {
    if (cond)
        true_stmt;
}
else {
    false_stmt;
}





$B$D$^$j30B&$HFbB&$I$A$i$N(Bif$B$K(Belse$B$rIU$1$k$+$H$$$&LdBj$@!#(B





$B$?$@$7(Bshift/reduce conflict$B$O(Breduce/reduce conflict$B$KHf$Y$l$PHf3SE*L5(B
$B32$J>WFM$G$"$k!#$J$<$+$H$$$&$H!"$?$$$F$$$N>l9g$O%7%U%H$rA*$Y$P$&$^$/$$(B
$B$/$+$i$@!#%7%U%H$rA*$V$H$$$&$N$O!V$G$-$k$@$16a$$MWAGF1;N$rO"7k$9$k!W$H(B
$B$@$$$?$$F15A8l$G$"$j!"?M4V$ND>46$K%^%C%A$7$d$9$$!#else$B$b%7%U%H$7$F$*$1$P$&$^$/$$$/!#$=$&$$$&$o$1$G(Byacc$B$b$=$NN.$l$K=>$$(B
shift/reduce conflict$B$,5/$-$?$H$-$K$O%G%U%)%k%H$G%7%U%H$rA*$V$h$&$K$J$C(B
$B$F$$$k!#(B






$B@hFI$_(B




$B;n$7$Kyacc$B$K$+$1$F$_$F$[$7$$!#(B




%token A B C
%%
target  : A B C   /* $B5,B'(B1 */
        | A B     /* $B5,B'(B2 */





$B$I$&9M$($F$b>WFM$7$=$&$G$O$J$$$@$m$&$+!#(BA B$B$^$GFI$s$@;~E@$G(B
$B5,B'(B1$B$O%7%U%H$7$?$,$k$7!"5,B'(B2$B$O4T85$7$?$,$k!#(B
$B$D$^$j$3$l$O(Bshift/reduce conflict$B$K$J$k$O$:$@!#$H$3$m$,!D!D(B




% yacc conf.y
%





$B$*$+$7$$!">WFM$7$J$$!#$I$&$7$F$@$m$&!#(B





$Byacc$B$G:n$C$?%Q!<%5$O5-9f$r0l$D$@$1(B
$B!V@hFI$_!J(Blook ahead$B!K!W$G$-$k!#(B
$BK\Ev$K%7%U%H$d4T85$r$9$kA0$K



$B$@$+$i%Q!<%5@8@.;~$K$b$=$l$r9MN8$7$F$/$l$F!"0l$D$N@hFI$_$G6hJL(B
$B$G$-$k$J$i>WFM$5$;$J$$!#Nc$($P@hDx$N5,B'$J$i(BA B$B$NC$B$,Mh$l$P(B
$B5,B'(B1$B$7$+2DG=@-$O$J$$$N$G5,B'(B1$B$rA*$V!J%7%U%H$9$k!K!#F~NO$,=*$o$C(B
$B$?$i5,B'(B2$B$rA*$V!J4T85$9$k!K!#(B





$BCm0U$7$F$[$7$$$N$O!V@hFI$_!W$H$$$&C18l$K$OFsDL$j$N0UL#$,$"$k$3$H$@!#(B
$B0l$D$O(Byacc$B$G(B*.y$B$r=hM}$9$k$H$-$N@hFI$_!#$b$&0l$D$O@8@.$7$?%Q!<%5$r(B
$Byacc$B<+?H(B
$B$N@hFI$_$OHs>o$K$d$d$3$7$$!#$J$<$J$iJ8K!5,B'$@$1$+$i



$B$b$C$H$b!"yacc$B$,J8K!%U%!%$%k=hM};~$K(B
$B;H$C$F$$$k@hFI$_%"%k%4%j%:%`$O(BLALR(1)$B$H8@$$!"8=B8$9$k>WFM2r7h%"%k%4%j(B
$B%:%`$NCf$G$O$o$j$H6/NO$J$b$N$G$"$k!#(B





$B$$$m$$$m8@$C$?$,!"K\=q$G$d$k$N$O5,B'$rFI$`$@$1$G=q$/$3$H$G$O$J$$$N$G!"(B
$B$"$^$j?4G[$9$k$3$H$O$J$$!#$3$3$G@bL@$7$?$+$C$?$N$OJ8K!$r;H$C$?@hFI$_$G(B
$B$O$J$/




$B1i;;;RM%@h=g0L(B




$B$7$P$i$/Cj>]E*$JOC$,B3$$$?$N$G$3$3$i$G$b$&>/$76qBNE*$JOC$r$9$k!#(B+$B$d(B
*$B$J$I$NFs9`1i;;;R!J%$%s%U%#%C%/%97?1i;;;R!K$N5,B'$rDj5A$7$F$_$k$3$H(B
$B$K$7$h$&!#$3$l$K$bDj@P$,$"$k$N$G!"$*$H$J$7$/$=$l$K=>$C$F$*$1$P$$$$!#0J(B
$B2<$K;MB'1i;;$,;H$($kEEBn$N$h$&$J$b$N$rDj5A$7$?!#(B




expr    : expr '+' expr
        | expr '-' expr
        | expr '*' expr
        | expr '/' expr
        | primary

primary : NUMBER
        | '(' expr ')'





primary$B$O!V9`!W$H$+Lu$5$l$k!#0lHV>.$5$JJ8K!C10L$N$3$H$G$"$k!#(B
expr$B$r3g8L$G$/$/$k$H(Bprimary$B$K$J$k$H$$$&$H$3$m$,%]%$%s%H$@!#(B





$B$5$F!"$3$NJ8K!$rE,Ev$K%U%!%$%k$K=q$$$F%3%s%Q%$%k$9$k$H!"$3$&$J$k!#(B




% yacc infix.y
16 shift/reduce conflicts





$B7c$7$/>WFM$7$F$7$^$C$?!#8^J,$P$+$j9M$($F$$$l$P$o$+$k$H;W$&$,!"(B
$B$3$N5,B'$G$Ol9g$K:$$k$N$G$"$k!#(B




1 - 1 - 1





$B$3$l$O


(1 - 1) - 1
1 - (1 - 1)





$B?t<0$H$7$F<+A3$J$N$O$b$A$m$sA0yacc$B$,$d$k$N$O$"$/$^$G8+$?$a(B
$B$N=hM}$G$"$C$F!"$=$3$K0UL#$OA4$/F~$i$J$$!#(B-$B$H$$$&5-9f$N;}$D0UL#$J$s$F$3$l$C(B
$B$]$A$b9MN8$7$F$O$/$l$J$$$N$@!#?M4V$N0U?^$r@5$7$/H?1G$5$;$k$K$O!"$d$j$?(B
$B$$$3$H$rCOF;$K;X<($7$F$d$i$J$$$H$$$1$J$$!#(B





$B$G$O$I$&$7$?$i$$$$$+$H8@$&$H!"Dj5AIt$K$3$&=q$1$P$h$$!#(B




%left '+' '-'
%left '*' '/'





$B$3$NL?Na$O1i;;;R$NM%@h=g0L$H7k9g@-$NFs$D$rF1;~$K;XDj$9$k!#(B
$B=gHV$K@bL@$7$F$$$3$&!#(B





$BM%@h=g0L$H$$$&8@MU$O%W%m%0%i%`8@8l$NJ8K!$NOC$r$9$k$H$-$K$O$h$/=P$F$/$k(B
$B$H;W$&!#M}O@E*$KOC$9$H$d$d$3$7$$$N$GD>46E*$K8@$&$H!"l9g$K$I(B
$B$A$i$N1i;;;R$K3g8L$,IU$/$+$H$$$&OC$@!#(B




1 + 2 * 3





*$B$N$[$&$,M%@h=g0L$,9b$1$l$P!"$3$&$J$k!#(B




1 + (2 * 3)





+$B$N$[$&$,M%@h=g0L$,9b$1$l$P!"$3$&$J$k!#(B




(1 + 2) * 3





$B$3$N$h$&$K!"1i;;;R$K6/$$$b$N$H



$B$@$,$7$+$7!"F1$8>u67$K4Y$C$F$bM%@h=g0L$,F1$8$@$C$?$i$I$&$9$l$P$$$$(B
$B$@$m$&$+!#Nc$($P$3$N$h$&$K!#(B




1 - 2 - 3





$B:#EY$O$I$A$i$b(B-$B$J$N$GM%@h=g0L$OA4$/F1$8$@!#$3$&$$$&$H$-$K$O7k9g@-(B
$B$r;H$C$F2r7h$9$k!#7k9g@-$K$O(Bleft right nonassoc$B$N;0$l




$B7k9g@-(B$B2r


left$B!J:87k9g!K(B(1 - 2) - 3


right$B!J1&7k9g!K(B1 - (2 - 3)


nonassoc$B!JHs7k9g!K(B$B%Q!<%9%(%i!<(B






$B?t<0MQ1i;;;R$@$H$[$H$s$I:87k9g$G$"$k!#1&7k9g$O=$B$d(B
$BH]Dj$N(Bnot$B$G;H$&!#(B




a = b = 1    # (a = (b = 1))
not not a    # (not (not a))





nonassoc$B$NBeI=3J$OHf3S1i;;;R$@$m$&!#(B




a == b == c   # $B%Q!<%9%(%i!<(B
a <= b <= c   # $B%Q!<%9%(%i!<(B





$B$b$C$H$b(BPython$B$J$I$G$O;09`$NHf3S$,2DG=$J$N$G$3$N8B$j$G$O$J$$!#(B





$B$=$l$G@hDx$N(B%left$B!&(B%right$B!&(B%nonassoc$B$H$$$&L?Na$O!"(B
$BL>A0DL$j$N7k9g@-$r<($9$?$a$K;H$o$l$k!#$=$7$FM%@h=g0L$OJB$Y$k=g$G<($9!#(B
$B2<$K$"$k1i;;;R$[$IM%@h=g0L$,9b$$!#F1$8Ns$K$"$l$PF1$8=g0L$G$"$k!#(B




%left  '+' '-'    /* $B:87k9g$GM%@h=g0L(B3 */
%left  '*' '/'    /* $B:87k9g$GM%@h=g0L(B2 */
%right '!'        /* $B1&7k9g$GM%@h=g0L(B1 */







$B8f0U8+!&8f46A[!&8m?#$N;XE&$J$I$O(B
$B@DLZJvO:(B <[email protected]>
$B$^$G$*4j$$$7$^$9!#(B




$B!X(BRuby$B%=!<%9%3!<%I40A42r@b!Y(B
$B$O%$%s%W%l%9%@%$%l%/%H$G8fM=Ls!&8f9XF~$$$?$@$1$^$9(B ($B=q@R>R2p%Z!<%8$XHt$S$^$9(B)$B!#(B



Copyright (c) 2002-2004 Minero Aoki, All rights reserved.