yacc

Overview

Compile commands:

        yacc translate.y
        cc y.tab.c -ly
        ./a.out

Source file format

        declarations
        %%
        translation (grammar) rules
        %%
        supporting C code

Expression Parser

yacc specification for expression grammar (4.1).

ibm1% cat ex_4.45.y

        /* YACC input for simple expression parser      */
        /* Aho, Sethi, Ullman: Example 4.45, pg 251     */
%{
#include <stdio.h>
%}
				/* DECLARATIONS	*/
%token ID
%%				/*    RULES	*/
E	:    E '+' T	{ printf("(1): E -> E + T\n"); }
	|    T		{ printf("(2): E -> T\n"); }
	;
T	:    T '*' F	{ printf("(3): T -> T * F\n"); }
	|    F		{ printf("(4): T -> F\n"); }
	;
F	:    '(' E ')'	{ printf("(5): F -> ( E )\n"); }
	|    ID		{ printf("(6): F -> id\n"); }
	;
%%				/*    CODE	*/

main()				/* main program	*/
{
  return(yyparse());
}

yylex()				/* lexical analyzer	*/
{
  extern int yylval;
  int c;
  c = getchar();
  yylval = c;
  if (c == 'a' || c == 'b')	/* id -> a | b	*/
    return(ID);
  else
    return(c);
}
				/*   End YACC	*/

ibm1% yacc -v ex_4.45.y
ibm1% gcc y.tab.c -ly
ibm1% ./a.out
a+b
(6): F -> id
(4): T -> F
(2): E -> T
(6): F -> id
(4): T -> F
(1): E -> E + T
syntax error

ibm1% ./a.out
a
(6): F -> id
(4): T -> F
(2): E -> T
syntax error

ibm1% cat y.output

/* Expression grammar of example 4.45, pg 251	*/
/*         LALR(1) Collection of Items		*/
state 0
	$accept : _E $end 

	id  shift 5
	(  shift 4
	.  error

	E  goto 1
	T  goto 2
	F  goto 3

state 1
	$accept :  E_$end 
	E :  E_+ T 

	$end  accept
	+  shift 6
	.  error


state 2
	E :  T_    (2)
	T :  T_* F 

	*  shift 7
	.  reduce 2


state 3
	T :  F_    (4)

	.  reduce 4


state 4
	F :  (_E ) 

	id  shift 5
	(  shift 4
	.  error

	E  goto 8
	T  goto 2
	F  goto 3

state 5
	F :  id_    (6)

	.  reduce 6


state 6
	E :  E +_T 

	id  shift 5
	(  shift 4
	.  error

	T  goto 9
	F  goto 3


state 7
	T :  T *_F 

	id  shift 5
	(  shift 4
	.  error

	F  goto 10

state 8
	E :  E_+ T 
	F :  ( E_) 

	+  shift 6
	)  shift 11
	.  error


state 9
	E :  E + T_    (1)
	T :  T_* F 

	*  shift 7
	.  reduce 1


state 10
	T :  T * F_    (3)

	.  reduce 3


state 11
	F :  ( E )_    (5)

	.  reduce 5


7/3000 terminals, 3/1000 nonterminals
7/2000 grammar rules, 12/5000 states
0 shift/reduce, 0 reduce/reduce conflicts reported
7/1400 working sets used
memory: states,etc. 64/40000, parser 8/70000
8/600 distinct lookahead sets
4 extra closures
13 shift entries, 1 exceptions
6 goto entries
3 entries saved by goto default
Optimizer space used: input 37/40000, output 218/70000
218 table entries, 206 zero
maximum spread: 257, maximum offset: 43

Notes:

• yacc actions print reduction steps during parsing.
  
• gcc -ly links default yyerror() routine from yacc library.
  
• No whitespace/newline processing in yylex() gives "syntax error".
  
• yacc -v produces parse table in y.output.
  
  

Desk Calculator

	/* Yacc specification of calculator  */
	/* Figure 4.58, Aho, 2nd ed., pg 289 */
%{
#include <stdio.h>
#include <ctype.h>
%}
%token DIGIT
%%
line	: expr '\n'	{ printf("%d\n",$1);}
	; /* allows printing of the result */
expr	: expr '+' term	{ $$ = $1 + $3;}
	| term	        { $$ = $1;}
	;
term	: term '*' factor { $$ = $1 * $3; }
	| factor	{ $$ = $1;}
    	;
factor	: DIGIT		{ $$ = $1; }
      	| '(' expr ')'	{ $$ = $2; }
	;
%%
main()
{ return yyparse();
}

int yylex(void)
{ int c;
  c = getchar();
  if ( isdigit(c) ) {
    yylval = c - '0';
    return DIGIT;
  }
  /* if (c == '\n') return 0;*/
  /* makes the parse stop */
  return c;
}

Ambiguous Grammars

Ambiguous expression grammar (4.3):

$E \rightarrow E + E \mid E * E \mid ( E ) \mid \mathbf{id}$

Shift/Reduce conflicts in states $I_7$ and $I_8$.

Default Rules:

1. Reduce/Reduce - choose rule listed first in yacc source file.
2. Shift/Reduce - choose shift.

Note: Rule #2 correctly resolves dangling-else conflict.

Default rules produce right associative '+', '*'; no precedence.

Use precedence/associativity of '+' and '*' to resolve conflicts.

Figure 4.49: Parse table for ambiguous grammar (4.3).

Token precedences assigned using %token declarations.

Figure 4.59: yacc calculator specification using ambiguous grammar.

	/* Yacc specification of calculator  */
	/* using ambiguous expression grammar*/
	/* Figure 4.59, Aho, 2nd ed., pg 292 */
%{
#include <stdio.h>
#include <ctype.h>
#define YYSTYPE double  /* double type for Yacc stack */
%}
%token NUMBER

%left '+' '-'
%left '*' '/'
%right UMINUS

%%

lines	: lines expr '\n'	{ printf("%g\n",$2); /* print result */ }
	| lines '\n'		{ ; /* allow blank lines */ }
	| 			{ ; /* empty string */ }
	; 
expr	: expr '+' expr	{ $$ = $1 + $3;}
	| expr '-' expr	{ $$ = $1 - $3;}
	| expr '*' expr	{ $$ = $1 * $3;}
	| expr '/' expr	{ $$ = $1 / $3;}
      	| '(' expr ')'	{ $$ = $2; }
	| '-' expr  %prec UMINUS { $$ = - $2;}
	| NUMBER
	;
%%
int yylex(void)
{ int c;
  while ( (c = getchar()) == ' ' );	/* skip spaces */
  if ( (c == '.') || isdigit(c) ) {
    ungetc(c, stdin);
    scanf("%lf", &yylval);  /* input a double */
    return NUMBER;
  }
  return c;
}

yacc/lex

Error Handling