DIRECTORY IO: TYPE USING [STREAM], MTP1: TYPE --P1-- USING [ActionSeq, ActionStack, AssignDescriptors, EvalInit, Index, LinkSeq, LinkStack, nullNTValue, ProcessError, ProcessQueue, ScanInit, ScannerProc, ScanReset, StateSeq, StateStack, Token, TValue, Value, ValueSeq, ValueStack], MTParseTable: TYPE ParseTable USING [ActionEntry, ActionTag, defaultMarker, endMarker, finalState, initialState, NActionsRef, NLengthsRef, NStartsRef, NSymbolsRef,NTDefaultsRef, NTIndex, NTState, NTSymbol, ProdDataRef, State, TableRef,TActionsRef, TIndex, TLengthsRef, TStartsRef, TSymbol, TSymbolsRef], SafeStorage USING [GetSystemZone]; MTParserImpl: CEDAR PROGRAM IMPORTS MTP1, SafeStorage EXPORTS MTP1 = { OPEN P1~~MTP1, MTParseTable; tablePtr: TableRef; tStart: TStartsRef; tLength: TLengthsRef; tSymbol: TSymbolsRef; tAction: TActionsRef; nStart: NStartsRef; nLength: NLengthsRef; nSymbol: NSymbolsRef; nAction: NActionsRef; ntDefaults: NTDefaultsRef; prodData: ProdDataRef; InstallParseTable: PUBLIC SAFE PROC [base: TableRef] = TRUSTED { tablePtr _ base; tStart _ @tablePtr[tablePtr.parseTable.tStart]; tLength _ @tablePtr[tablePtr.parseTable.tLength]; tSymbol _ @tablePtr[tablePtr.parseTable.tSymbol]; tAction _ @tablePtr[tablePtr.parseTable.tAction]; nStart _ @tablePtr[tablePtr.parseTable.nStart]; nLength _ @tablePtr[tablePtr.parseTable.nLength]; nSymbol _ @tablePtr[tablePtr.parseTable.nSymbol]; nAction _ @tablePtr[tablePtr.parseTable.nAction]; ntDefaults _ @tablePtr[tablePtr.parseTable.ntDefaults]; prodData _ @tablePtr[tablePtr.parseTable.prodData]; }; errorLimit: NAT = 25; scanTag: ActionTag = [FALSE, 0]; inputSymbol: TSymbol; inputLoc: P1.Index; inputValue: P1.TValue; lastToken: P1.Token; nullSymbol: TSymbol = 0; zone: ZONE _ NIL; s: P1.StateStack _ NIL; l: P1.LinkStack _ NIL; v: P1.ValueStack _ NIL; top: CARDINAL; q: P1.ActionStack _ NIL; qI: CARDINAL; ParseInit: PROC [scratchZone: ZONE] = INLINE { zone _ scratchZone; s _ NIL; q _ NIL; ExpandStack[500]; ExpandQueue[250]; }; ParseReset: PROC = INLINE { EraseQueue[]; EraseStack[]; zone _ NIL}; -- * * * * Main Parsing Procedures * * * * -- Parse: PUBLIC PROC [source: IO.STREAM, Input: P1.ScannerProc] RETURNS [complete: BOOL, nTokens, nErrors: NAT] = TRUSTED { currentState: State; i, valid, m: CARDINAL; -- stack pointers action: ActionEntry; ParseInit[SafeStorage.GetSystemZone[]]; P1.ScanInit[source]; P1.EvalInit; nErrors _ 0; complete _ TRUE; i _ top _ valid _ 0; qI _ 0; s[0] _ currentState _ initialState; lastToken.class _ nullSymbol; [[inputSymbol, inputValue, inputLoc]] _ Input[]; WHILE currentState # finalState AND inputSymbol # endMarker DO BEGIN tI: TIndex _ tStart[currentState]; FOR tI IN [tI .. tI + tLength[currentState]) DO SELECT tSymbol[tI] FROM inputSymbol, defaultMarker => EXIT ENDCASE; REPEAT FINISHED => GO TO SyntaxError; ENDLOOP; action _ tAction[tI]; IF ~action.tag.reduce THEN { -- scan or scan reduce entry IF qI > 0 THEN { FOR k: CARDINAL IN (valid..i] DO s[k] _ s[top+(k-valid)] ENDLOOP; P1.ProcessQueue[qI, top]; qI _ 0}; IF (top _ valid _ i _ i+1) >= s.length THEN ExpandStack[256]; lastToken.class _ inputSymbol; v[i] _ [t~inputValue, n~P1.nullNTValue]; l[i] _ inputLoc; [[inputSymbol, inputValue, inputLoc]] _ Input[]}; WHILE action.tag # scanTag DO IF qI >= q.length THEN ExpandQueue[256]; q[qI] _ action; qI _ qI + 1; i _ i-action.tag.pLength; currentState _ s[IF i > valid THEN top+(i-valid) ELSE (valid _ i)]; BEGIN lhs: NTSymbol = prodData[action.transition].lhs; IF currentState <= NTState.LAST THEN { nI: NTIndex _ nStart[currentState]; FOR nI IN [nI..nI+nLength[currentState]) DO IF lhs = nSymbol[nI] THEN {action _ nAction[nI]; GO TO nFound}; ENDLOOP}; action _ ntDefaults[lhs]; EXITS nFound => NULL; END; i _ i+1; ENDLOOP; IF (m _ top+(i-valid)) >= s.length THEN ExpandStack[256]; s[m] _ currentState _ action.transition; EXITS SyntaxError => { nErrors _ nErrors + 1; -- Collect up all the parser State and save it. P1.ProcessError[top, inputValue]; EXIT; }; END; ENDLOOP; P1.ProcessQueue[qI, top]; nErrors _ nErrors + ([nTokens~nTokens] _ P1.ScanReset[]).nErrors; ParseReset[]; RETURN}; ExpandStack: PROC [delta: NAT] = { oldSize: NAT = (IF s = NIL THEN 0 ELSE s.length); newSize: NAT = oldSize + delta; newS: P1.StateStack = zone.NEW[P1.StateSeq[newSize]]; newL: P1.LinkStack = zone.NEW[P1.LinkSeq[newSize]]; newV: P1.ValueStack = zone.NEW[P1.ValueSeq[newSize]]; FOR i: NAT IN [0..oldSize) DO newS[i] _ s[i]; newL[i] _ l[i]; newV[i] _ v[i] ENDLOOP; EraseStack[]; s _ newS; l _ newL; v _ newV; P1.AssignDescriptors[qd~q, vd~v, ld~l, pp~prodData]}; EraseStack: PROC = { IF s # NIL THEN TRUSTED {zone.FREE[@v]; zone.FREE[@l]; zone.FREE[@s]}}; ExpandQueue: PROC [delta: NAT] = { oldSize: NAT = (IF q = NIL THEN 0 ELSE q.length); newSize: NAT = oldSize + delta; newQ: P1.ActionStack = zone.NEW[P1.ActionSeq[newSize]]; FOR i: NAT IN [0..oldSize) DO newQ[i] _ q[i] ENDLOOP; EraseQueue[]; q _ newQ; P1.AssignDescriptors[qd~q, vd~v, ld~l, pp~prodData]}; EraseQueue: PROC = {IF q # NIL THEN TRUSTED {zone.FREE[@q]}}; }. vfile MTParserImpl.mesa derived from ProtoParser.mesa HGM, May 31, 1984 10:58:42 pm PDT Satterthwaite, June 6, 1983 2:40 pm Nichols, July 13, 1983 6:12 pm Cedar/Mesa parser with error recovery table installation transition tables for terminal input symbols transition tables for nonterminal input symbols production information parser state initialization/termination ÊߘJšœ™šœ™Jšœ!™!Jšœ#™#Jšœ™—J˜šÏk ˜ Jšœœœœ˜JšœœÏcœœß˜öJšœœ œŒ˜¯Jšœ œ˜"J˜—šœ ˜Jšœ˜Jšœ ˜Jšœ%™%Jšœ˜J˜—Jšœ™˜J˜J˜Jšœ,™,J˜J˜J˜J˜J˜J˜Jšœ/™/J˜J˜J˜J˜J˜J˜J˜Jšœ™J˜J˜J˜J˜š Ïnœœœœœ˜@J˜J˜/J˜1J˜1J˜1J˜/J˜1J˜1J˜1J˜7J˜3J˜J˜J˜——Jšœ ™ ˜Jšœ œ˜J˜Jšœœ˜ J˜J˜J˜J˜J˜J˜J˜J˜J˜Jšœœœ˜J˜Jšœœ˜Jšœœ˜Jšœœ˜Jšœœ˜J˜Jšœœ˜Jšœœ˜ J˜—Jšœ™˜šŸ œœœœ˜.J˜Jšœœœ'˜8Jšœ˜J˜—šŸ œœœ˜J˜Jšœœ˜ J˜J˜——Jšž.˜.˜š Ÿœœœ œœ˜=Jšœ œœœ˜;J˜Jšœ œž˜)J˜J˜J˜'J˜J˜ Jšœœ˜J˜J˜BJ˜0J˜šœœ˜>Jš˜J˜"šœœ$˜/Jšœ œœœ˜Cš˜Jšœœœ ˜—Jšœ˜J˜—J˜šœœž˜9šœœ˜Jš œœœ œœ˜AJ˜#—Jšœ%œ˜=J˜J˜9J˜2J˜—šœ˜Jšœœ˜(J˜J˜šœœ œœ˜CJš˜J˜0šœœœ˜&J˜#šœœ ˜+Jšœœœœ ˜?Jšœ˜ ——J˜š˜Jšœ œ˜—Jšœ˜—J˜Jšœ˜—Jšœ!œ˜9J˜(š˜˜Jšœ˜J˜/J˜!Jšœ˜Jšœ˜——Jšœ˜—Jšœ˜J˜J˜J˜AJ˜ Jšœ˜J˜J˜—šŸ œœ œ˜"Jš œ œœœœœ ˜1Jšœ œ˜Jšœœ˜5Jšœœ˜3Jšœœ˜5šœœœ˜Jšœ/œ˜7—J˜ J˜J˜5J˜—šŸ œœ˜Jšœœœœœ œ œ˜GJ˜—šŸ œœ œ˜"Jš œ œœœœœ ˜1Jšœ œ˜Jšœœ˜7Jš œœœœœ˜5J˜ J˜ J˜5J˜—JšŸ œœœœœœœ˜=J˜J˜J˜——…—Ö+