yacc
-
" "
/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 -
A: B C { 1} D { 2}
K { 3}
A: B C EMPTY1 D EMPTY2 K;
EMPTY1: { 1}
EMPTY2: { 2}
, ,
- 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
-