# Mythryl-Yacc Parser Generator (c) 1989 Andrew W. Appel, David R. Tarditi
# Compiled by:
# src/lib/std/standard.lib# base.api: Base api file for Mythryl-Yacc. This file contains apis that must
# be loaded before any of the files produced by Mythryl-Yacc are loaded
### When 'Omer smote 'is bloomin' lyre,
### He'd 'eard men sing by land an' sea;
### An' what he thought 'e might require,
### 'E went an' took -- the same as me.
###
### -- Rudyard Kipling,
### Barrack-Room Ballads--Introduction
# STREAM: api for a lazy stream.
api Stream {
Stream( A_xa );
streamify: (Void -> X) -> Stream(X);
cons: (X, Stream(X)) -> Stream(X);
get: Stream(X) -> (X, Stream(X));
};
# LR_TABLE: api for an LR Table.
# The list of actions and gotos passed to make_lr_table must be ordered by state
# number. The values for state 0 are the first in the list, the values for
# state 1 are next, etc.
api Lr_Table {
Pairlist (X,Y) = EMPTY
| PAIR (X, Y, Pairlist (X,Y));
State = STATE Int;
Terminal = TERM Int;
Nonterminal = NONTERM Int;
Action = SHIFT State
| REDUCE Int
| ACCEPT
| ERROR;
Table;
state_count: Table -> Int;
rule_count: Table -> Int;
describe_goto: Table -> State -> Pairlist( Nonterminal, State );
action: Table -> (State, Terminal) -> Action;
goto: Table -> (State, Nonterminal) -> State;
initial_state: Table -> State;
describe_actions: Table -> State ->
(Pairlist( Terminal, Action ), Action);
exception GOTO (State, Nonterminal);
make_lr_table: { actions: Rw_Vector( (Pairlist( Terminal, Action ), Action)),
gotos: Rw_Vector( Pairlist( Nonterminal, State ) ),
state_count: Int, rule_count: Int,
initial_state: State } -> Table;
};
# TOKEN: api revealing the internal package of a token. This api
# TOKEN distinct from the api { parser name }_TOKENS produced by Mythryl-Yacc.
#
# The { parser name }_TOKENS packages contain some types and functions to
# construct tokens from values and positions.
#
# The representation of token was very carefully chosen here to allow the
# typeagnostic parser to work without knowing the types of semantic values
# or line numbers.
#
# This has had an impact on the TOKENS package produced by Mythryl-Yacc, which
# is a package parameter to lexer generics. We would like to have some
# type Token(X) which functions to construct tokens would create. A
# constructor function for a integer token might be
#
# INT: (Int, X, X) -> Token(X)
#
# This is not possible because we need to have tokens with the representation
# given below for the typeagnostic parser.
#
# Thus our constructur functions for tokens have the form:
# INT: (Int, X, X) -> Token (Semantic_Value, X)
# This in turn has had an impact on the api that lexers for Mythryl-Yacc
# must match and the types that a user must declare in the user declarations
# section of lexers.
# Lr_Table is from src/app/yacc/lib/base.apiapi Token {
package lr_table: Lr_Table;
Token (X,Y) = TOKEN (lr_table::Terminal, ((X, Y, Y)));
same_token: (Token (X, Y), Token (X,Y)) -> Bool;
};
# LR_PARSER: api for a typeagnostic LR parser
api Lr_Parser {
#
package stream: Stream; # Stream is from src/app/yacc/lib/base.api package lr_table: Lr_Table; # Lr_Table is from src/app/yacc/lib/base.api package token: Token; # Token is from src/app/yacc/lib/base.api sharing lr_table == token::lr_table;
exception PARSE_ERROR;
parse
:
{ table: lr_table::Table,
lexer: stream::Stream( token::Token (Y, Z) ),
arg: A_arg,
void: Y,
saction
:
( Int,
Z ,
List ((lr_table::State, ((Y, Z, Z)))),
A_arg
)
->
( lr_table::Nonterminal,
(Y, Z, Z),
List( (lr_table::State, (Y, Z, Z)) )
),
error_recovery
:
{ is_keyword: lr_table::Terminal -> Bool,
no_shift: lr_table::Terminal -> Bool,
#
preferred_change: List( ( List lr_table::Terminal,
List lr_table::Terminal
) ),
errtermvalue: lr_table::Terminal -> Y,
show_terminal: lr_table::Terminal -> String,
terms: List lr_table::Terminal,
error: (String, Z, Z) -> Void
},
lookahead: Int # max amount of lookahead used in
# error correction
}
->
( Y,
(stream::Stream( token::Token(Y, Z)))
);
};
# Lexer: a api that most lexers produced for use with Mythryl-Yacc's
# output will match. The user is responsible for declaring type Token,
# type Source_Position, and type Semantic_Value in the user_declarations section of a lexer.
#
# Note that type Token is abstract in the lexer. This allows Mythryl-Yacc to
# create a TOKENS api for use with lexers produced by Mythryl-Lex that
# treats the type Token abstractly. Lexers that are generics parametrized by
# a 'tokens' package matching a 'Tokens' api cannot examine the package
# of tokens.
api Lexer {
#
package user_declarations :
api {
Token( X, Y );
Source_Position;
Semantic_Value;
};
make_lexer: (Int -> String) -> Void -> user_declarations::Token( user_declarations::Semantic_Value, user_declarations::Source_Position );
};
# ARG_LEXER: the %arg option of Mythryl-Lex allows users to produce lexers which
# also take an argument before yielding a function from Void to a token
api Arg_Lexer {
#
package user_declarations
:
api {
Token( X, Y );
Source_Position;
Semantic_Value;
Arg;
};
make_lexer
:
(Int -> String)
->
user_declarations::Arg
->
Void
->
user_declarations::Token(
user_declarations::Semantic_Value,
user_declarations::Source_Position
);
};
# Parser_Data: the api of parser_data packages in { parser name } lr_vals_fun
# produced by Mythryl-Yacc. All such packages match this api.
#
# The { parser name } lr_vals_g produces a package which contains all the values
# except for the lexer needed to call the typeagnostic parser mentioned
# before.
api Parser_Data {
Source_Position; # The type of line numbers.
Semantic_Value; # The type of semantic values.
Arg; # The type of the user-supplied argument to the parser.
# The intended type of the result of the parser.
# This value is produced by applying 'extract'
# from the package 'actions' to the final
# semantic value resultiing from a parse:
#
Result;
package lr_table: Lr_Table; # Lr_Table is from src/app/yacc/lib/base.api package token: Token; # Token is from src/app/yacc/lib/base.api sharing token::lr_table == lr_table;
# The 'actions' package contains the functions which
# maintain the semantic values stack in the parser.
# Void is used to provide a default value for the semantic stack.
#
package actions
:
api {
actions
:
( Int,
Source_Position,
List ( (lr_table::State, ((Semantic_Value, Source_Position, Source_Position)))),
Arg
)
->
( lr_table::Nonterminal,
(Semantic_Value, Source_Position, Source_Position),
(List ((lr_table::State, (Semantic_Value, Source_Position, Source_Position))))
);
void: Semantic_Value;
extract: Semantic_Value -> Result;
};
# Package 'error_recovery' contains information
# used to improve error recovery in an
# error-correcting parser:
#
package error_recovery
:
api {
is_keyword: lr_table::Terminal -> Bool;
no_shift: lr_table::Terminal -> Bool;
errtermvalue: lr_table::Terminal -> Semantic_Value;
show_terminal: lr_table::Terminal -> String;
terms: List( lr_table::Terminal );
preferred_change: List( ( List( lr_table::Terminal ),
List( lr_table::Terminal )
) );
};
table: lr_table::Table; # The LR table for the parser.
};
# api PARSER is the api that most user parsers created by
# Mythryl-Yacc will match.
api Parser {
#
package token: Token; # Token is from src/app/yacc/lib/base.api package stream: Stream; # Stream is from src/app/yacc/lib/base.api exception PARSE_ERROR;
Source_Position; # Type Source_Position is the type of line numbers.
Result; # Type Result is the type of the result from the parser.
Arg; # The type of the user-supplied argument to the parser.
Semantic_Value; # type Semantic_Value is the type of semantic values
# for the semantic value stack
make_lexer # make_lexer is used to create a stream of tokens for the parser
:
(Int -> String)
->
stream::Stream (token::Token (Semantic_Value, Source_Position) );
# 'parse' takes a stream of tokens
# and a function to print errors
# and returns a Result and a stream
# containing the unused tokens:
#
parse
:
( Int,
(stream::Stream( token::Token (Semantic_Value, Source_Position))),
((String, Source_Position, Source_Position) -> Void),
Arg
)
->
( Result,
stream::Stream( token::Token (Semantic_Value, Source_Position))
);
same_token
:
( token::Token (Semantic_Value, Source_Position),
token::Token (Semantic_Value, Source_Position)
)
->
Bool;
};
# api Arg_Parser is the api that will be matched by parsers whose
# lexer takes an additional argument.
api Arg_Parser {
#
package token: Token; # Token is from src/app/yacc/lib/base.api package stream: Stream; # Stream is from src/app/yacc/lib/base.api exception PARSE_ERROR;
Arg;
Lex_Arg;
Source_Position;
Result;
Semantic_Value;
make_lexer
:
(Int -> String)
->
Lex_Arg
->
stream::Stream( token::Token (Semantic_Value, Source_Position) );
parse
:
( Int,
stream::Stream( token::Token (Semantic_Value, Source_Position) ),
(String, Source_Position, Source_Position) -> Void,
Arg
)
->
( Result,
stream::Stream (token::Token (Semantic_Value, Source_Position))
);
same_token
:
( token::Token (Semantic_Value, Source_Position),
token::Token (Semantic_Value, Source_Position)
)
->
Bool;
};