[manual index][section index]

NAME

yacc - yet another compiler-compiler (Limbo version)

SYNOPSIS

yacc [ option ... ] grammar

DESCRIPTION

Yacc converts a context-free grammar and translation code into a set of tables for an LR(1) parser and translator. The grammar may be ambiguous; specified precedence rules are used to break ambiguities.

The output from yacc is a Limbo module y.tab.b containing the parse function yyparse which must be provided with a YYLEX adt providing the parser access to a lexical analyser routine lex(), an error routine error(), and any other context required.

The options are


-o output
Direct output to the specified file instead of y.tab.b.
-Dn
Create file y.debug, containing diagnostic messages. To incorporate them in the parser, give an n greater than zero. The amount of diagnostic output from the parser is regulated by value n:
1
Report errors.
2
Also report reductions.
3
Also report the name of each token returned by yylex.
-v
Create file y.output, containing a description of the parsing tables and of conflicts arising from ambiguities in the grammar.
-d
Create file y.tab.m, containing the module declaration for the parser, along with definitions of the constants that associate yacc-assigned `token codes' with user-declared `token names'. Include it in source files other than y.tab.b to give access to the token codes and the parser module.
-s stem
Change the prefix y of the file names y.tab.b, y.tab.m, y.debug, and y.output to stem.
-m
Normally yacc defines the type of the y.tab.b module within the text of the module according to the contents of the %module directive. Giving the -m option suppresses this behaviour, leaving the implementation free to define the module's type from an external .m file. The module's type name is still taken from the %module directive.
-n size
Specify the initial size of the token stack created for the parser (default: 200).

Differences from C yacc
The Limbo yacc is in many respects identical to the C yacc. The differences are summarised below:

Comments follow the Limbo convention (a # symbol gives a comment until the end of the line).

A %module directive is required, which replaces the %union directive. It is of the form:

%module modname {
module types, functions and constants
}
Modname will be the module's implementation type; the body of the directive, augmented with con definitions for the yacc-assigned token codes, gives the type of the module, unless the -m option is given, in which case no module definition is emitted.

A type YYSTYPE must be defined, giving the type associated with yacc tokens. If the angle bracket construction is used after any of the %token, %left, %right, %nonassoc or %type directives in order to associate a type with a token or production, the word inside the angle brackets refers to a member of an instance of YYSTYPE, which should be an adt.

An adt YYLEX must be defined, providing context to the parser. The definition must consist of at least the following:

	YYLEX: adt {
		lval: YYSTYPE;
		lex: fn(l: self ref YYLEX): int;
		error: fn(l: self ref YYLEX, msg: string);
	}
Lex should invoke a lexical analyser to return the next token for yacc to analyse. The value of the token should be left in lval. Error will be called when a parse error occurs. Msg is a string describing the error.

Yyparse takes one argument, a reference to the YYLEX adt that will be used to provide it with tokens.

The parser is fully re-entrant; i.e. it does not hold any parse state in any global variables within the module.

EXAMPLE

The following is a small but complete example of the use of Limbo yacc to build a simple calculator.
%{
    include "sys.m";
    sys: Sys;

    include "bufio.m";
    bufio: Bufio;
    Iobuf: import bufio;

    include "draw.m";

    YYSTYPE: adt { v: real; };
    YYLEX: adt {
        lval:   YYSTYPE;
        lex: fn(l: self ref YYLEX): int;
        error: fn(l: self ref YYLEX, msg: string);
    };
%}

%module Calc{
    init:   fn(ctxt: ref Draw->Context, args: list of string);
}

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

%type   <v> exp uexp term
%token  <v> REAL

%%
top :
    | top '\n'
    | top exp '\n'
    {
        sys->print("%g\n", $2);
    }
    | top error '\n'
    ;

exp : uexp
    | exp '*' exp   { $$ = $1 * $3; }
    | exp '/' exp   { $$ = $1 / $3; }
    | exp '+' exp   { $$ = $1 + $3; }
    | exp '-' exp   { $$ = $1 - $3; }
    ;

uexp    : term
    | '+' uexp  { $$ = $2; }
    | '-' uexp  { $$ = -$2; }
    ;

term    : REAL
    | '(' exp ')'
    {
        $$ = $2;
    }
    ;

%%

in: ref Iobuf;
stderr: ref Sys->FD;

init(nil: ref Draw->Context, nil: list of string)
{
	sys = load Sys Sys->PATH;
	bufio = load Bufio Bufio->PATH;
	in = bufio->fopen(sys->fildes(0), Bufio->OREAD);
	stderr = sys->fildes(2);
	lex := ref YYLEX;
	yyparse(lex);
}

YYLEX.error(nil: self ref YYLEX, err: string)
{
	sys->fprint(stderr, "%s\n", err);
}

YYLEX.lex(lex: self ref YYLEX): int
{
	for(;;){
		c := in.getc();
		case c{
		' ' or '\t' =>
			;
		'-' or '+' or '*' or '/' or '\n' or '(' or ')' =>
			return c;
		'0' to '9' or '.' =>
			s := "";
			i := 0;
			s[i++] = c;
			while((c = in.getc()) >= '0' && c <= '9' ||
			      c == '.' ||
			      c == 'e' || c == 'E')
				s[i++] = c;
			in.ungetc();
			lex.lval.v = real s;
			return REAL;
		* =>
			return -1;
		}
	}
}

FILES

y.output
y.tab.b
y.tab.m
y.debug
/lib/yaccpar
parser prototype

SOURCE

/appl/cmd/yacc.b

SEE ALSO

S. C. Johnson and R. Sethi, ``Yacc: A parser generator'', Unix Research System Programmer's Manual, Tenth Edition, Volume 2
B. W. Kernighan and Rob Pike, The UNIX Programming Environment, Prentice Hall, 1984

BUGS

The parser may not have full information when it writes to y.debug so that the names of the tokens returned by yylex may be missing.

YACC(1 ) Rev:  Thu Feb 15 14:42:47 GMT 2007