-- ParserGen.mesa
-- last edited by: Jim Sasaki on August 24, 1983 3:50 pm
-- This is a small parser generator that takes the description of an operator precedence grammar and produces a viewer into which one can type strings to be parsed. An unparser reformats the input and underlines any parse error found.
Last Edited by: Beach, February 14, 1984 11:30:01 am PST
DIRECTORY Atom, Rope, ParseTable, Lexer;
ParserGen: DEFINITIONS
= BEGIN
OpList : TYPE = LIST OF REF OpRec ← NIL;
OpRec : TYPE = RECORD
[ op : ATOM
, indegree : INT ← 0
, prec : INT ← closefixPrec
, adj : LIST OF EdgeRec
, matches : REF OpRec ← NIL
, isInfix, isPrefix, isPostfix, isOpenfix, isClosefix, isLeftfix, isRightfix : BOOLFALSE
];
EdgeRec: TYPE = RECORD [n: INT, m: INT, oprec: REF OpRec];
-- n and m are the numbers of the rules whose conjunction caused the
-- precedence constraint represented by this edge.
closefixPrec : INT = -1; -- Must be less than precs of other types of operators.
-- An operator record contains the name of the operator, its matching closer (if any), its precedence, boolean flags to describe its fixities, an adjacency list for its operator precedence edges, and its indegree in the graph. (Note that the graph edges and indegree are destroyed by the routine that solves for the operator's precedence.)
ProdList : TYPE = LIST OF REF ProdRec ← NIL;
ProdRec : TYPE = RECORD
[ nonTerminal : ATOM
, rhsList : RuleList ← NIL
];
RuleList : TYPE = LIST OF REF RuleRec ← NIL;
RuleRec : TYPE = RECORD
[ kind : ATOM -- $infix, $prefix, $postfix, $openfix, $leftfix, or $rightfix
, seq : LIST OF REF ANY -- two to four atoms for the rhs of the rule.
, number: INT -- the rules in the input file should be numbered.
];
-- A production record holds all the right hand sides for a nonterminal, as in
nonterminal ::= rhs | rhs | ...
where the nonterminal is an atom and each rhs is one of the six kinds of
operator grammar rules. Each right hand side is stored in its own Rule record.
Culprit : TYPE = REF ANYNIL;
-- Routines return a nonNIL culprit only when errors occur. (Not all routines return culprits when they find an error; some just execute an ERROR.)
ROPE : TYPE = Rope.ROPE; -- Short name for Ropes.
List : TYPE = LIST OF REF ANY; -- Short name for LIST OF REF ANY
ParseTree : TYPE = REF ANY; -- abstract syntax trees stored in a lisp-like way.
Verdict: TYPE = {Yes, No, OfCourseNot}; -- Yes == innocent


-- WITH THE INTRODUCTION OF depth, WE RESTRICT OURSELVES TO
-- VERDICTS Yes and No.

-- [Yes, 0] is ofcoursenot.
-- [Yes, 1] is a "first-level no"
-- etc.

VerdictAndCulprit : TYPE = RECORD [verdict: Verdict, culprit: REF ANY, depth: INT];
-- culprit relevant only if verdict is No or OfCourseNot
GenParser:
PUBLIC PROCEDURE [ filename : ROPE ]
RETURNS [ Lexer.Handle, ParseTable.Handle, OpList, ProdList, Culprit ];
IsGeneratedBy:
PUBLIC PROCEDURE [ prL : ProdList, lhs : ATOM, p : ParseTree ]
RETURNS [ vc : VerdictAndCulprit ]
END.