-
" "
/P 2.1
yacc
1988
,
,
. ,
( -
),
. -
, (-
) -
. yacc
-
.
,
() ,
,
( , ), , -
yacc, ( -
) .
,
, ,
,
..
yacc -
() ,
- ().
, -
, .
(-
). -
,
, . -
() -
. , -
, , -
-
. ( -
; ,
-
). -
, B
. -
-
.
, . -
,
,
. -
- -
-
.
, yacc
. ,
.
yacc
() , -
.
( -
,
, -
) yacc
, ,
.
, yacc
() , -
, , ,
,
( ). K -
( ),
-
.
yacc
.
-
yacc,
/lib/liby.a, /usr/lib/yaccpar.
.
1. yacc
, yacc,
LALR(1)-, -
" " -
LR(k)- ( L(eft) R(ight)
-
. -
-
).
- 3 -
" " (
) -
( ) "
" (
4.1) .
,
,
. -
: , ..
, , .. -
-
, . yacc
, -
.
. yacc -
LALR(1). LALR(1)-
, LR(1)-,
-
,
- (,
,
-
). -
yacc ( 5).
, , , -
,
, yacc
,
( 5).
2. , -
yacc
, 4.
-
y.tab.c
-, . -
y.tab.c yyparse,
. yacc
/usr/lib/yaccpar,
. yyparse, y.tab.c yacc -
,
.
- 4 -
yyparse
, 0 1. 0 -
, 1-
. yyparse -
yylex,
y.tab.c -
, .
yyparse -
yacc main, -
yyparse . -
main,
, yyparse
( , , -
), ,
yyparse ;
, , ,
, yyparse.
main
- .
y.tab.c, yacc
:
y.output
( 6)
y.tab.h
( 4.3).
-
yacc.
3.
.
yacc,
yacc [-vd] yfile
yfile - , -
:
v - y.output -
;
- 5 -
d - y.tab.h . -
y.output y.tab.h -
-
.
yacc - yyparse
- y.tab.c. -
-
a.out
y.tab.c :
cc y.tab.c [cfile...ofile...lfile...] -ly
cfile, ofile, lfile - , -
, . -
yacc
/lib/liby.a,
ly. .
4. yacc
4.1.
, -
, -
:
%%
%%
-
.
"%%"; -
,
:
%%
, -
, . ,
"/*" "*/" ,
.
- 6 -
-
. -
-
.
-
.
-
, -
. ,
yylex -
, .
4.2.
, -
. -
, -
,
. , -
.
, ,
:
<__>: ;
":" ";" - yacc.
- -
( -
), . -
,
.
, - .
-
, .
:
P_Head: P_name '(' P_list ')';
P_Head 4- -
: , - -
. ,
. yacc
,
(.4.3).
- 7 -
, ..
.
, , ..
. -
, .
, :
statement : assign_stat ;
statement : if_then_stat;
statement : goto_stat;
-
, , -
"|". -
:
statement : assign_stat |
if_then_stat |
goto_stat;
-
- ,
.
.
, ..
:
<__>:
{};
.
, -
, .
-
.
statement: assign_stat
|
if_then_stat {printf("if_\n");}
|
goto_stat {kgoto++;
printf("goto_\n");}
- 8 -
, ,
. , -
.
, .
,
-
. -
, -
,
.
,
if_then_stat: if'(' expression ')' {1}
then statement ';' { 2}
,
if (a>b) then x=a;
1 ,
2 - .
, , ,
, ,
.. ,
. -
,
%{
%}
, -
.
statement ,
goto
- 9 -
%{
int kgoto;
%}
prog: DECLS {kgoto=0;}
stats {printf("%d\n",kgoto);}
stats: statement
| stats statement;
statement:assign_stat
...
|
if_then_stat
...
|
goto_stat {kgoto++;
... }
,
. , -, ,
(.4.3), , -,
(), -
-
. 4.5. -
-
, ..
. ,
. yacc
,
, .. , -
. -
. -
. -
yacc ,
. ,
, -
.
,
. -,
<__>: ;
.
,
,
.
,
- 10 -
. -
:
_: __ |
__ ;
: '+'|'-';
:
: {_} ;
-,
, ..
. -
:
<_>:<_>
<__>;
<_>:
<__>
<_>;
yacc ,
,
.
-
. -
:
:
| ;
: | ',' ;
- 11 -
, (
) -
, () - . -
,
, -
. ,
: |
'$' |
|
|
'_' ;
,
"_", "$".
,
,
.
:
:
| ;
-
, ,
( 5) - -
, -
.
4.3.
: - .
y.tab.c -
. -
, ,
, ..
, , .
- "%" (
yacc esc-).
- 12 -
%{
%}
.
-
.
5.
%token <__>
,
-
,
() .
, ,
. -
%token yacc
. ,
, -
%token
-
(.4.4)
. :
%token IDENT CONST IF THEN GOTO
,
.
,
. -
.
6.
%left <_>
%right <_>
%nonassoc <_>
.
,
- 13 -
%token .
-
5 -
.
.
-
, .
yacc -
:
-
,
;
- , , -
,
257;
- error, -
( 7), 256.
, -
, yacc
y.tab.c
#define <_> <_>
-
#define, ,
%left 'z' 258
#define z 258
,
.
yacc -d -
#define y.tab.h.
,
.
- 14 -
7.
%start <__>
, -
.
7.1.
, -
. -
,
- y.tab.c
. ,
:
- - yylex();
- , ,
;
- main()
,
main() {return (yyparse();}
- yyerror() -
( ).
#include <stdio.h>
yyerror(s) char *s; {
fprintf(stderr, "%s\n", s);}
-
yylex -
-
. yylex
, ,
. -
-
( #define yacc -
),
(
- 15 -
).
()
( , -
, ).
, -
:
#include <stdio.h>
yylex() {char c;
while ((c=getc(stdin))==' '||c=='\n');
if(c>='0'&&c<='9'){
while((c=getc(stdin))>='0'&&c<='9');
ungetc(c,stdin));
return (CONST);}
if (c>='a'&&c<='z'){
while ((c=getc(stdin))>'a'&&c<='z'
||c>='0'&&c<='9');
ungetc(c,stdin); return (NAME);}
return (c); }
,
-
. -
, ,
:
yylex() {return (getchar());}
, , -
. -
.
, , .
, -
.
yyl-
val. yylex ,
:
extern int yylval;
- 16 -
,
, -
yylval; , yylex,
.
, ,
(
). ,
, yylval -
, -
yylval ( yylval
).
, 4.5.
7.2.
,
yacc -
,
-
.
(,
yylval).
, -
, ; -
-
. ,
-
. -
.
-
:
- ,
, .
$1,$2,..., $i
i- ;
, ,
P_Head: P_name '(' P_list ')';
$1,$2,$3,$4 -
P_name, '(', P_list, ')'.
- ,
$$. ,
- 17 -
expr: expr '+' expr { $$=$1+$3; }
expr
expr.
E $$
( ), -
, ..
$$=$1;
( )
%token DIGIT
%%
...
CONST: DIGIT
| CONST DIGIT {$$=$1*10+$2;}
...
%%
yylex()
{
char c;
if((c=getchar())>='0'&& c<='9') {
yylval = c-'0';
return (DIGIT);
}
...
}
CONST
,
yylex yylval;
CONST.
-
,
. yacc -
K { 3}
A: B C EMPTY1 D EMPTY2 K;
, ,
- 18 -
,
.
-
""
. , , -
,
.
3
B, C, D, K -
$1, $2, $4, $6; $3, $5
1 2. ,
, $i -
, -
.
(.. ) -
, $$,
-
. , $$
-
, :
$1.
1
B C (
$1 $2), 2 - B, C, D
1 $1, $2, $4,
$3.
:
%token 1 2
. . .
%%
_:
{printf(" %s\n",$1);};
:
{abc = creat($1,0666);}
1 2 {option($3,$4);}
_ '\n' {converse(0,$5,$6);
write($1,$6,80);}
{converse(1,$5,$8);
write($1,$6,$8);
close($1);};
_: ...
: ...
. . .
- 19 -
.
(
yylval).
8.
,
,
. , , ,
:
expr: CONST /*1*/
|
expr '+'expr /*2*/
|
expr '-'expr /*3*/
|
expr '*'expr /*4*/
|
expr '/'expr; /*5*/
-
, ,
. , :
expr*expr-expr
, -
:
expr*(expr-expr) (expr*expr) - expr
-
"-" ,
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],
/* :
* - ,
* 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. ....... 29
11. ................................ 32
1 ...................................... 34
2 ...................................... 36
3 ...................................... 40
- 42 -
Last-modified: Mon, 29 Jun 1998 14:15:22 GMT