"-" ,
expr*expr.
:
. 1
.
,
expr -
(3),
expr (4).
- 20 -
expr*expr
(4), expr,
.
1 .
(3) -
expr.
"/". (
,
. -
/ ,
expr-expr-expr.
"-" - .
, ,
, , , -
. ,
; -
"/".
,
:
const: const_10 /*1*/
| const_16 ; /*2*/
const_10: dec_sequence; /*3*/
const_16: hex_sequence 'x'; /*4*/
dec_sequence:digit /*5*/
| dec_sequence digit; /*6*/
hex_sequence:digit /*7*/
| ABCDEF /*8*/
|hex_sequence digit /*9*/
|hex_sequence ABCDEF; /*10*/
ABCDEF : 'A'|'B'|'C'|'D'|'E'|'F';
digit:'0'|'1'|'2'|'3'|'4'|'5'|'6'
|'7'|'8'|'9';
(
) -
digit
: dec_sequence -
(5) hex_sequence -
(7). , , e -
,
-
const . ,
1 -
. ,
-
yacc . -
,
- 21 -
. (.. -
), -
"/" "/
", yacc -
. yacc
,
y.output ( )
. , yacc
-
,
.
yacc
. (..
) -
-
:
/
.
/ -
,
.
,
, ""
. ,
.
digit dec_sequence
, , -
, A F "x"
.
,
. , -
,
:
: if '(' ')' /*1*/
|
if '(' ')' else
; /*2*/
:
if(C1) if(C2) S1 else S2
/
- 22 -
else. -
:
if () if ()
(1), :
if ()
(, (1) -
else). S2
:
if () else
(2).
:
if (C1) {if(C2) S1} else S2
else -
:
if () if ()
else
(2),
:
if ()
(1).
:
if (C1) {if(C2) S1 else S2}
,
( else
if). , ,
, .
,
/ -
, -
.
/, -
,
.
- 23 -
, yacc
,
-
yacc .
y.output, -
. , -
,
. /
;
/
-
.
-
.
,
-
, .
:
expr: expr1
|
expr '+' expr1
|
expr '-' expr1;
expr1: CONST
|
expr1 '*' CONST
|
expr1 '/' CONST;
,
( ).
:
const: const_10
| const_16;
const_10: dec_sequence ;
const_16: hex_sequence 'x'
| dec_sequence 'x';
dec_sequence: digit
| dec_sequence digit;
hex_sequence: ABCDEF
| dec_sequence ABCDEF
| hex_sequence ABCDEF
|hex_sequence dec_sequence;
ABCDEF:...
digit:...
- 24 -
yacc -
,
. -
:
;
.
, ,
-
; / yacc
-
. , 1,
-
. , , -
: , -
, -
, . , -
(
).
,
, .
/ -
, yacc -
( - , -
, -
) .
yacc
.
() ( )
, -
. yacc -
, .
.
,
.
, yacc -
,
. yacc, -
, , -
y.output .
:
- 25 -
%left <_>
%right <_>
%nonassoc <_>
. %left %right
-
. %nonassoc
. -
,
.
:
%token OR NOR XOR AND NAND
%right '='
%left OR NOR XOR
%left AND NAND
%left '+' '-'
%left '*' '/'
/* "=",
- "*" "/"
*/
-
. -
, -
. -
(
) :
%prec <>
(
). , :
expr: '-' expr %prec '*';
%prec "*" ( "-"
, -
; %prec
. ,
,
, ,
,
. , -
, " "
UMINUS).
- 26 -
yacc
/
(,
/ ):
, -
.
,
.
,
-
:
, - .
( %nonassoc)
-
.
/
,
, .
, -
:
%left '+' '-'
%left '*' '/'
%%
expr: CONST
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr;
9. y.output
-
.
:
-
(
,
). -
"_" (
). , :
expr: expr +_expr
- 27 -
-
expr+.
-
.
:
<> <_> -
;
<> <_> -
-
;
<> error -
("-
") -
1 ( );
<> accept -
0
( ). ,
, -
"." , -
,
. :
. error
,
.
- . -
<_> <_>
,
,
.
,
yacc -
. -
(/ /), -
(
, - ) ,
. ,
- 28 -
,
.
:
8: / ( 5, 2) +
8
a:a_+a
a:a+a_ (2)
+ 5
. 2
8 , -
a: a '+' a
K -
5 "+" .
.
-
( ), .. -
,
. -
.
, .
,
,
, -
().
10.
-
, ,
, .
-
.
, -
, -
.
(" ")
. ,
, -
, yyerror. , -
, -
,
- 29 -
, . yacc
;
, ,
-
( ).
-
. -
error.
:
a: b c d ; /*1*/
a: b c error; /*2*/
d: d1 d2 d3; /*3*/
,
a -
b c.
yacc , error,
, . -
error ( error).
, error -
.
(.. ,
error):
; yyer-
ror .
,
, ,
error.
, -
.
(
, ,
)
,
error.
, .
,
,
.
-
,
, .
- 30 -
,
, -
.
, , , -
,
error.
,
,
. ,
, ,
b c d1 d2 , -
:
a: b c_d;
a: b c_error;
(2).
, ,
. -
,
: error;
, -
, , . -
,
, -
, , ,
( -
). , -
:
: error ';'
";"
;
";" .
, error, -
. -
. -
, yyerror
yyclearin, yacc
. yyerror
. ,
" ".
, -
.
- 31 -
yyclearin -
, -
.
-
: error {resynch();
yyclearin;
yyerror;}
, resynch()
.
,
, ,
.
,
, :
_ : error '\n' {yyerrok;
printf(" \n");}
_ {$$=$4;}
, ,
, .
-
.
11.
yacc -
. -
, ":", -
-
.
yacc :
;
;
/usr/lib/yaccpar
yyparse;
;
;
,
, -
;
- 32 -
;
;
( -
,
, .).
- 33 -
1
yacc,
; 26
, a z -
, +, -,
*, /, % ( ), & ( ), | (
) . , ,
0, , - .
-
,
.
.
%token DIGIT LETTER /* */
%left '|' /* */
%left '&' /* */
%left '+' '-'
%left '*' '/' '%'
%left UMINUS /*
*/
%{ /* o, */
int base, regs[26]; /* */
%}
%% /* */
list:
| list stat '\n'
| list stat error '\n' {yyerrok; }
stat:
expr {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; }
| expr '%' expr { $$=$1%$3; }
| expr '&' expr { $$=$1&$3; }
| expr '|' expr { $$=$1|$3; }
| '-' expr %prec UMINUS { $$= -$2; }
| LETTER { $$=regs[$1]; }
| number;
number:
DIGIT { $$=$1; base=10;
if($1==0) base=8; }
- 34 -
| number DIGIT {$$=base*$1+$2; }
%% /* */
/*
*
*
* LETTER,
* yylval 0 25;
* - DIGIT,
* yylval 0 9;
*
*
*/
yylex()
{
int c;
while( (c=getchar()) == ' ' );
if( c>='a' && c<='z' ) {
yylval = c - 'a';
return(LETTER);
}
if( c>='0' && c<='9' ) {
yylval = c - '0';
return(DIGIT);
}
return(c);
}
- 35 -
2
-
.
:
c1X1+c2X2+...+cnXn -> min(max)
a11x1+a12X2+...+a1nXn=b1
am1X1+am2X2+...+amnXn=bm
:
C: c1 c2 ... cn
A: a11 a12 ... a1n
...
am1 am2 ... amn
B: b1 b2 ... bm
,
-
.
.
.
%token Xi
%%
: '\n' _
{final();}
| _ '\n'
{ final();}
: _ {stf();}
/* - */
| '(' _ ')'
{if($1) conv(); stf();}
/* conv() */
| _ '-''>'
{if($4) conv();stf();}
_: 1
| _ ;
: Xi {stc($1*$2,$3); }
| Xi '*' { stc($1*$4,$2);}
| Xi { stc($1,$2);}
/* */
1:
| Xi { stc($1,$2);}
| Xi '*' { stc($3,$1);}
- 36 -
| Xi { stc(1,$1); }
: '+' {$$=1; }
| '-' {$$= -1;}
_: '\n'
| _ '\n'
| _ error '\n'
{aclear();yyerrok;
printf(" \n");}
/* : . ,
*/
: _ '='
{ stcb($3);}
| _ '='
{ if($3<0) conv(); stcb($4);}
/* bi<0, conv() */
%%
#include "stdio.h"
#define MAXM 100 /* */
#define MAXN 100 /* .*/
int c[MAXN],b[MAXM],a[MAXM+1][MAXN],
neqs,nx,x[MAXN];
/* :
* - ,
* yylval . ;
* . xi, i=1,2,...XI*
* yylval . ;
* max/min - ,
* yylval 1 0
*/
yylex() {
char c,i;
while((c=getc(stdin))==' ');
switch(c) {
case'0':
case'1':
case'2':
case'3':
case'4':
case'5':
case'6':
case'7':
case'8':
case'9': yylval=c-'0';
while((c=getc(stdin))<='9'&&c>='0')
yylval=yylval*10+c-'0';
ungetc(c,stdin); return();
- 37 -
case'm': if((c=getc(stdin))=='i') yylval=0;
else if(c=='a') yylval=1;
else return('m');
while((c=getc(stdin))<='z'&&c>='a');
ungetc(c,stdin); return();
case'X':
case'x': if((c=getc(stdin))<'0' || c>'9')
return('x');
yylval=0;
while(c<='9'&&c>='0')
{yylval=yylval*10+c-'0';c=getc(stdin);}
ungetc(c,stdin);
for(i=0;i<nx;i++)
if(x[i]==yylval){yylval=i;return(Xi);}
x[nx]=yylval; yylval=nx++;return(Xi);
}
return(c);
}
/* */
final() {
char i,j;
printf("c:\n");
for(i=0;i<nx;i++) printf("%8d",c[i]);
printf("\na:\n");
for(i=0;i<neqs;i++) {
for(j=0;j<nx;j++) printf("%8d",a[i][j]);
printf("\n"); }
printf("b:\n");
for(i=0;i<neqs;i++) printf("%8d",b[i]);
}
/* */
conv() {
char i;
for(i=0;i<nx;i++) a[neqs][i]*=(-1);
}
/* */
stf() {
char i;
for(i=0;i<nx;i++)
{ c[i]=a[neqs][i]; a[neqs][i]=0; }
}
/* */
stc(nmb,adr) {
a[neqs][adr]=nmb; }
/* */
stcb(nmb) {
b[neqs++]=nmb; }
- 38 -
/* */
aclear(){
char i;
for(i=0;i<nx;i++)
a[neqs][i]=0;
}
- 39 -
3
.
_:
_ '%''%'
'\n' _ '%''%'
'\n' _
| _ '%''%'
'\n' _ ;
_:
| _ __
'\n' ;
__:
'%''{''\n'_
'\n''%''}'
| '%''s''t''a''r''t'
| '%''t''o''k''e''n'__
| _ ;
:
'%''l''e''f''t'
| '%'''r''i''g''h''t'
| '%''n''o''n''a''s''s''o''c' ;
__:
| __
| __
__ ;
_:
_
| _ _ ;
__:
| __;
_:
_
| _;
_:
| __;
_:
_
| '%''{''\n'_'\n''%''}'
'\n' _ '\n' ;
_:
| _ ';' ;
:
_ ':'
| '|' ;
_: ;
:
- 40 -
_
| _ _
| _ _
| _ ;
_:
| _ __
| _ __;
_:
_:
_ ;
-
,
: , ,
. ,
-,
( , -). -
- -
. _
, -
( 4.3).
- 41 -
. ......................................... 2
1. yacc .............................. 3
2. ,
....................................... 4
3. .. 5
4. yacc ................... 6
4.1. ............... 6
4.2. ................................... 7
4.3. ............................... 12
5. ............................ 13
6. ... 13
7. ............... 15
7.1. ................................. 15
7.2. ...... 17
8. ................. 20
9.
y.output .......................................... 27
10.