[_CDCSL_93-16_]<1>Cedar>release>MesaParser>MPParser.mesa

MPParser.mesa

derived from Compiler>Parser.Mesa

Satterthwaite, January 12, 1981 12:58 PM

Russ Atkinson (RRA) January 19, 1987 7:48:58 pm PST

JKF May 24, 1990 9:18:48 am PDT

Michael Plass, September 5, 1991 11:44 pm PDT

DIRECTORY

IO USING [Put1, PutRope, PutChar, STREAM],

MPP1 USING [Token, Value, ValueSeq, ValueStack, nullValue, nullToken, INTSeq, ActionEntrySeq, AssignDescriptors, Atom, ErrorContext, ProcessQueue, ResetScanIndex, ScanInit, ScanReset],

MPParseTable USING [ActionEntry, ActionTag, defaultMarker, endMarker, finalState, IndexTableRef, initialState, initialSymbol, InitIndexTable, InitNActions, InitNLengths, InitNStarts, InitNSymbols, InitNTDefaults, InitProdData, InitTActions, InitTLengths, InitTStarts, InitTSymbols, InitVocabulary, NActionsRef, NLengthsRef, NStartsRef, NSymbolsRef, NTDefaultsRef, NTIndex, NTState, NTSymbol, ProdDataRef, State, TActionsRef, TIndex, TLengthsRef, TStartsRef, TSymbol, TSymbolsRef, VocabularyRef],

Rope USING [ROPE];

MPParser: PROGRAM

IMPORTS IO, MPP1, MPParseTable

EXPORTS MPP1 = {

OPEN MPParseTable;

globals

ErrorLimit: CARDINAL = 10;

Scan: ActionTag = [FALSE, 0];

inputSymbol: TSymbol;

input: PROC [errPut: IO.STREAM] RETURNS [token: MPP1.Token];

inputLoc: INT Ź 0;

inputValue: MPP1.Value Ź MPP1.nullValue;

lastToken: MPP1.Token Ź MPP1.nullToken;

NullSymbol: TSymbol = 0;

firstInit: BOOL Ź TRUE;

s: REF StateSeq Ź NIL;

StateSeq: TYPE = RECORD[SEQUENCE length: CARDINAL OF State];

l: REF MPP1.INTSeq Ź NIL;

v: MPP1.ValueStack Ź NIL;

top: CARDINAL Ź 0;

q: REF MPP1.ActionEntrySeq Ź NIL;

qI: CARDINAL;

transition tables for terminal input symbols

vocabIndex: IndexTableRef Ź NIL;

vocabBody: VocabularyRef Ź NIL;

transition tables for terminal input symbols

tStart: TStartsRef Ź NIL;

tLength: TLengthsRef Ź NIL;

tSymbol: TSymbolsRef Ź NIL;

tAction: TActionsRef Ź NIL;

transition tables for nonterminal input symbols

nStart: NStartsRef Ź NIL;

nLength: NLengthsRef Ź NIL;

nSymbol: NSymbolsRef Ź NIL;

nAction: NActionsRef Ź NIL;

ntDefaults: NTDefaultsRef Ź NIL;

production information

prodData: ProdDataRef Ź NIL;

initialization/termination

ParseInit: PROC [source: Rope.ROPE] = {

IF vocabIndex = NIL THEN [vocabIndex, vocabBody] Ź MPP1.ScanInit[source];

IF prodData = NIL THEN {

tStart Ź InitTStarts[];

tLength Ź InitTLengths[];

tSymbol Ź InitTSymbols[];

tAction Ź InitTActions[];

nStart Ź InitNStarts[];

nLength Ź InitNLengths[];

nSymbol Ź InitNSymbols[];

nAction Ź InitNActions[];

ntDefaults Ź InitNTDefaults[];

prodData Ź InitProdData[];

};

IF firstInit THEN {

ExpandStack[64];

ExpandQueue[64];

firstInit Ź FALSE;

};

InputLoc: PUBLIC SAFE PROC RETURNS [INT] = TRUSTED {RETURN [inputLoc]};

* * * * Main Parsing Procedures * * * * --

Parse: PUBLIC SAFE PROC [source: Rope.ROPE, errPut: IO.STREAM] RETURNS [complete: BOOL, nTokens, nErrors: CARDINAL] = TRUSTED {

currentState: State;

i, valid, m: CARDINAL; -- stack pointers

action: ActionEntry;

ParseInit[source]; input Ź MPP1.Atom;

nErrors Ź 0; complete Ź TRUE;

i Ź top Ź valid Ź 0; qI Ź 0;

s[0] Ź currentState Ź initialState; lastToken.class Ź NullSymbol;

inputSymbol Ź initialSymbol; inputValue Ź MPP1.nullValue; inputLoc Ź 0;

WHILE currentState # finalState DO

{

tI: TIndex Ź tStart[currentState];

FOR tI IN [tI .. tI + tLength[currentState])

DO

SELECT tSymbol[tI] FROM inputSymbol, defaultMarker => EXIT ENDCASE;

REPEAT

FINISHED => GOTO syntaxError;

ENDLOOP;

action Ź tAction[tI];

IF ~action.tag.reduce -- scan or scan reduce entry

THEN {

IF qI > 0

THEN {

FOR k: CARDINAL IN (valid..i] DO s[k] Ź s[top+(k-valid)] ENDLOOP;

MPP1.ProcessQueue[qI, top]; qI Ź 0};

IF (top Ź valid Ź i Ź i+1) >= s.length THEN ExpandStack[64];

lastToken.class Ź inputSymbol; v[i] Ź inputValue; l[i] Ź inputLoc;

[[inputSymbol, inputValue, inputLoc]] Ź input[errPut]};

WHILE action.tag # Scan

DO

IF qI >= q.length THEN ExpandQueue[64];

q[qI] Ź action; qI Ź qI + 1;

i Ź i-action.tag.pLength;

currentState Ź s[IF i > valid THEN top+(i-valid) ELSE (valid Ź i)];

{

lhs: NTSymbol = prodData[action.transition].lhs;

IF currentState <= LAST[NTState]

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;

};

i Ź i+1;

ENDLOOP;

IF (m Ź top+(i-valid)) >= s.length THEN ExpandStack[64];

s[m] Ź currentState Ź action.transition;

EXITS

syntaxError => {

lastToken.value Ź v[top]; lastToken.index Ź l[top];

top Ź top - 1;

complete Ź SyntaxError[(nErrorsŹnErrors+1)>ErrorLimit, errPut];

i Ź valid Ź top; qI Ź 0; lastToken.class Ź NullSymbol;

currentState Ź s[i];

[[inputSymbol, inputValue, inputLoc]] Ź input[errPut];

IF ~complete THEN EXIT};

};

ENDLOOP;

MPP1.ProcessQueue[qI, top];

{n: CARDINAL; [nTokens, n] Ź MPP1.ScanReset[]; nErrors Ź nErrors + n};

RETURN};

ExpandStack: PROC [delta: CARDINAL] = {

newS: REF StateSeq;

newL: REF MPP1.INTSeq;

newV: MPP1.ValueStack Ź NIL;

newSize: CARDINAL = (IF s = NIL THEN 0 ELSE s.length) + delta;

newS Ź NEW[StateSeq[newSize]];

newL Ź NEW[MPP1.INTSeq[newSize]];

newV Ź IF v # NIL AND v.length >= newSize

THEN v

ELSE NEW[MPP1.ValueSeq[newSize]];

IF s # NIL THEN FOR i: CARDINAL IN [0..s.length)

DO newS[i] Ź s[i]; newL[i] Ź l[i]; newV[i] Ź v[i] ENDLOOP;

s Ź newS; l Ź newL; v Ź newV;

MPP1.AssignDescriptors[qd:q, vd:v, ld:l, pp:prodData]};

ExpandQueue: PROC [delta: CARDINAL] = {

newSize: CARDINAL = (IF q = NIL THEN 0 ELSE q.length) + delta;

newQ: REF MPP1.ActionEntrySeq Ź NEW[MPP1.ActionEntrySeq[newSize]];

IF q # NIL THEN FOR i: CARDINAL IN [0..q.length) DO newQ[i] Ź q[i] ENDLOOP;

q Ź newQ;

MPP1.AssignDescriptors[qd:q, vd:v, ld:l, pp:prodData]};

* * * * Error Recovery Section * * * * --

parameters of error recovery

MinScanLimit: CARDINAL = 4;

MaxScanLimit: CARDINAL = 12;

InsertLimit: CARDINAL = 2;

DiscardLimit: CARDINAL = 10;

TreeSize: CARDINAL = 256;

CheckSize: CARDINAL = MaxScanLimit+InsertLimit+2;

debugging

ParserID: PUBLIC SAFE PROC RETURNS [Rope.ROPE] = TRUSTED {RETURN ["Flako!"]};

tree management

NodeIndex: TYPE = CARDINAL [0..TreeSize);

NullIndex: NodeIndex = 0;

StackNode: TYPE = RECORD[

father: NodeIndex,

last: NodeIndex,

state: State,

symbol: TSymbol,

aLeaf, bLeaf: BOOLEAN,

link: NodeIndex];

tree: REF ARRAY [0..TreeSize) OF StackNode;

nextNode: NodeIndex Ź 0;

maxNode: NodeIndex Ź 0;

treeLimit: CARDINAL Ź 0;

TreeFull: SIGNAL = CODE;

Allocate: PROC [parent, pred: NodeIndex, terminal: TSymbol, stateNo: State] RETURNS [index: NodeIndex] = {

IF (index Ź nextNode) >= treeLimit THEN SIGNAL TreeFull;

maxNode Ź MAX[index, maxNode];

tree[index] Ź StackNode[

father: parent,

last: pred,

state: stateNo,

symbol: terminal,

aLeaf: FALSE, bLeaf: FALSE,

link: NullIndex];

nextNode Ź nextNode+1; RETURN};

HashSize: INTEGER = 64; -- should depend on state count ?

hashTable: REF ARRAY [0..HashSize) OF NodeIndex;

ParsingMode: TYPE = {ATree, BTree, Checking};

parseMode: ParsingMode Ź Checking;

LinkHash: PROC [n: NodeIndex] = {

htIndex: [0..HashSize) = tree[n].state MOD HashSize;

tree[n].link Ź hashTable[htIndex]; hashTable[htIndex] Ź n};

ExistingConfiguration: PROC [stack: StackRep] RETURNS [NodeIndex] = {

n, n1, n2: NodeIndex;

s1, s2: State;

htIndex: [0..HashSize);

aTree: BOOLEAN;

SELECT parseMode FROM

ATree => aTree Ź TRUE;

BTree => aTree Ź FALSE;

ENDCASE => RETURN [NullIndex];

htIndex Ź stack.extension MOD HashSize;

FOR n Ź hashTable[htIndex], tree[n].link UNTIL n = NullIndex

DO

IF (IF aTree THEN tree[n].aLeaf ELSE tree[n].bLeaf)

THEN {

s1 Ź stack.extension; s2 Ź tree[n].state;

n1 Ź stack.leaf; n2 Ź tree[n].father;

DO

IF s1 # s2 THEN EXIT;

IF n1 = n2 THEN RETURN [n];

s1 Ź tree[n1].state; s2 Ź tree[n2].state;

n1 Ź tree[n1].father; n2 Ź tree[n2].father;

ENDLOOP};

ENDLOOP;

RETURN [NullIndex]};

FindNode: PROC [parent, pred: NodeIndex, stateNo: State] RETURNS [index: NodeIndex] = {

index Ź ExistingConfiguration[[leaf:parent, extension:stateNo]];

IF index = NullIndex

THEN {

index Ź Allocate[parent, pred, 0, stateNo];

SELECT parseMode FROM

ATree => {tree[index].aLeaf Ź TRUE; LinkHash[index]};

BTree => {tree[index].bLeaf Ź TRUE; LinkHash[index]};

ENDCASE => NULL};

RETURN};

parsing simulation

ExtState: TYPE = [FIRST[State] .. LAST[State]+1];

NullState: ExtState = LAST[ExtState];

StackRep: TYPE = RECORD[

leaf: NodeIndex,

extension: ExtState];

GetNTEntry: PROC [state: State, lhs: NTSymbol] RETURNS [ActionEntry] = {

IF state <= LAST[NTState]

THEN {

nI: NTIndex Ź nStart[state];

FOR nI IN [nI..nI+nLength[state])

DO IF lhs = nSymbol[nI] THEN RETURN [nAction[nI]] ENDLOOP};

RETURN [ntDefaults[lhs]]};

ActOnStack: PROC [stack: StackRep, action: ActionEntry, nScanned: [0..1]] RETURNS [StackRep] = {

currentNode, thread: NodeIndex Ź stack.leaf;

count: CARDINAL Ź nScanned;

currentState: State;

IF stack.extension = NullState

THEN currentState Ź tree[currentNode].state

ELSE {currentState Ź stack.extension; count Ź count + 1};

UNTIL action.tag = Scan

DO

IF count > action.tag.pLength -- can be one greater

THEN {

currentNode Ź FindNode[currentNode, thread, currentState];

count Ź count - 1};

UNTIL count = action.tag.pLength

DO currentNode Ź tree[currentNode].father; count Ź count + 1 ENDLOOP;

currentState Ź tree[currentNode].state; count Ź 1;

action Ź GetNTEntry[currentState, prodData[action.transition].lhs];

ENDLOOP;

IF count > 1

THEN currentNode Ź FindNode[currentNode, thread, currentState];

stack.leaf Ź currentNode; stack.extension Ź action.transition;

RETURN [stack]};

ParseStep: PROC [stack: StackRep, tSmb: TSymbol] RETURNS [StackRep] = {

currentState: State Ź IF stack.extension = NullState

THEN tree[stack.leaf].state

ELSE stack.extension;

scanned: BOOLEAN Ź FALSE;

WHILE ~scanned

DO

action: ActionEntry;

count: [0..1];

tI: TIndex Ź tStart[currentState];

FOR tI IN [tI..tI+tLength[currentState])

DO

SELECT tSymbol[tI] FROM tSmb, defaultMarker => EXIT ENDCASE;

REPEAT

FINISHED => RETURN [[NullIndex, NullState]];

ENDLOOP;

action Ź tAction[tI];

IF ~action.tag.reduce

THEN {count Ź 1; scanned Ź TRUE} -- shift or shift reduce

ELSE count Ź 0;

stack Ź ActOnStack[stack, action, count];

currentState Ź stack.extension;

ENDLOOP;

RETURN [stack]};

text buffer management

Insert: TYPE = ARRAY [0 .. 1+InsertLimit) OF MPP1.Token;

newText: REF Insert;

insertCount: CARDINAL Ź 0;

Buffer: TYPE =

ARRAY [0 .. 1 + DiscardLimit + (MaxScanLimit+InsertLimit)) OF MPP1.Token;

sourceText: REF Buffer;

scanBase, scanLimit: CARDINAL Ź 0;

Advance: PROC [errPut: IO.STREAM] =

{sourceText[scanLimit] Ź input[errPut]; scanLimit Ź scanLimit+1};

Discard: PROC = {scanBase Ź scanBase+1};

UnDiscard: PROC = {scanBase Ź scanBase-1};

RecoverInput: PROC [errPut: IO.STREAM] RETURNS [token: MPP1.Token Ź MPP1.nullToken] = {

IF insertCount <= InsertLimit

THEN {

token Ź newText[insertCount];

IF (insertCount Ź insertCount+1) > InsertLimit

THEN newText Ź NIL}

ELSE {

token Ź sourceText[scanBase];

IF (scanBase Ź scanBase+1) = scanLimit

THEN {sourceText Ź NIL; input Ź MPP1.Atom}};

RETURN};

acceptance checking

best: RECORD [

nAccepted: CARDINAL Ź 0,

nPassed: [0..1] Ź 0,

node: NodeIndex Ź 0,

mode: ParsingMode Ź Checking,

nDiscards: CARDINAL Ź 0];

RightScan: PROC [node: NodeIndex] RETURNS [stop: BOOLEAN] = {

savedNextNode: NodeIndex = nextNode;

savedMode: ParsingMode = parseMode;

savedLimit: CARDINAL = treeLimit;

stack: StackRep Ź [leaf:node, extension:NullState];

state: State Ź tree[node].state;

nAccepted: CARDINAL Ź 0;

parseMode Ź Checking; treeLimit Ź TreeSize;

FOR i: CARDINAL IN [scanBase .. scanLimit)

DO

IF state = finalState

THEN {

nAccepted Ź IF (sourceText[i].class = endMarker)

THEN scanLimit-scanBase

ELSE 0;

EXIT};

stack Ź ParseStep[stack, sourceText[i].class];

IF stack.leaf = NullIndex THEN EXIT;

nAccepted Ź nAccepted + 1; state Ź stack.extension;

ENDLOOP;

nextNode Ź savedNextNode; treeLimit Ź savedLimit;

SELECT (parseMode Ź savedMode) FROM

ATree =>

IF nAccepted + 1 > best.nAccepted + best.nPassed

THEN best Ź [nAccepted, 1, node, ATree, scanBase-1];

BTree =>

IF nAccepted > best.nAccepted + best.nPassed

THEN best Ź [nAccepted, 0, node, BTree, scanBase];

ENDCASE;

RETURN [nAccepted >= MaxScanLimit]};

strategy management

RowRecord: TYPE = RECORD [

index, limit: CARDINAL,

stack: StackRep,

next: RowHandle];

RowHandle: TYPE = REF RowRecord;

NextRow: PROC [list: RowHandle] RETURNS [row: RowHandle] = {

t: TSymbol Ź TSymbol.FIRST;

row Ź NIL;

FOR r: RowHandle Ź list, r.next UNTIL r = NIL

DO

IF r.index < r.limit

THEN {

s: TSymbol = tSymbol[r.index];

IF row = NIL OR s < t THEN {row Ź r; t Ź s}};

ENDLOOP;

RETURN};

Position: TYPE = {after, before};

Length: TYPE = CARDINAL [0..InsertLimit];

levelStart: ARRAY Position OF ARRAY Length OF NodeIndex Ź [ALL[0], ALL[0]];

levelEnd: ARRAY Position OF ARRAY Length OF NodeIndex Ź [ALL[0], ALL[0]];

AddLeaf: PROC [stack: StackRep, s: TSymbol, thread: NodeIndex]

RETURNS [stop: BOOLEAN] = {

saveNextNode: NodeIndex = nextNode;

stack Ź ParseStep[stack, s];

IF stack.leaf = NullIndex OR ExistingConfiguration[stack] # NullIndex

THEN {nextNode Ź saveNextNode; stop Ź FALSE}

ELSE {

newLeaf: NodeIndex = Allocate[stack.leaf, thread, s, stack.extension];

SELECT parseMode FROM

ATree => tree[newLeaf].aLeaf Ź TRUE;

BTree => tree[newLeaf].bLeaf Ź TRUE;

ENDCASE => ERROR;

LinkHash[newLeaf];

stop Ź RightScan[newLeaf]};

RETURN};

GrowTree: PROC [p: Position, n: Length] RETURNS [stop: BOOLEAN] = {

tI, tLimit: TIndex;

stack: StackRep;

state: State;

rowList, r: RowHandle;

rowList Ź NIL;

FOR i: NodeIndex IN [levelStart[p][n-1] .. levelEnd[p][n-1])

DO

IF tree[i].symbol # 0 OR n = 1

THEN {

rowList Ź NIL;

stack Ź [leaf:i, extension:NullState]; state Ź tree[i].state;

DO

tI Ź tStart[state]; tLimit Ź tI + tLength[state];

r Ź NEW[RowRecord Ź [index: tI, limit: tLimit, stack: stack, next: rowList]];

rowList Ź r;

IF tI = tLimit OR tSymbol[tLimit-1] # defaultMarker THEN EXIT;

r.limit Ź r.limit - 1;

stack Ź ActOnStack[stack, tAction[tLimit-1], 0];

state Ź stack.extension;

ENDLOOP;

UNTIL (r Ź NextRow[rowList]) = NIL

DO

IF AddLeaf[r.stack, tSymbol[r.index], i] THEN GO TO found;

r.index Ź r.index + 1;

ENDLOOP};

REPEAT

found => stop Ź TRUE;

FINISHED => stop Ź FALSE;

ENDLOOP;

rowList Ź NIL;

RETURN};

CheckTree: PROC [p: Position, n: Length] RETURNS [stop: BOOLEAN] = {

FOR i: NodeIndex IN [levelStart[p][n] .. levelEnd[p][n])

DO

ENABLE TreeFull => CONTINUE;

IF RightScan[i] THEN GO TO found;

REPEAT

found => stop Ź TRUE;

FINISHED => stop Ź FALSE;

ENDLOOP;

RETURN};

Accept: PROC [put: IO.STREAM] RETURNS [success: BOOL] = {

s: TSymbol;

discardBase: CARDINAL = best.nPassed;

insertCount Ź 1+InsertLimit;

FOR p: NodeIndex Ź best.node, tree[p].last WHILE p > rTop

DO

IF (s Ź tree[p].symbol) # 0

THEN {

insertCount Ź insertCount-1;

newText[insertCount] Ź MPP1.Token[s, MPP1.nullValue, inputLoc]};

ENDLOOP;

scanBase Ź discardBase;

IF best.nDiscards # 0

THEN {

put.PutRope["Text deleted is: "];

FOR j: CARDINAL IN [1 .. best.nDiscards]

DO

TypeSym[sourceText[scanBase].class, put]; scanBase Ź scanBase + 1;

ENDLOOP};

IF insertCount <= InsertLimit

THEN {

IF scanBase # discardBase THEN put.PutChar['\n];

put.PutRope["Text inserted is: "];

FOR j: CARDINAL IN [insertCount .. InsertLimit]

DO TypeSym[newText[j].class, put] ENDLOOP};

IF discardBase = 1

THEN {insertCount Ź insertCount-1; newText[insertCount] Ź sourceText[0]};

IF insertCount > InsertLimit THEN newText Ź NIL;

IF scanBase + best.nAccepted < scanLimit

THEN success Ź MPP1.ResetScanIndex[sourceText[scanBase+best.nAccepted].index]

ELSE success Ź TRUE;

scanLimit Ź scanBase + best.nAccepted;

input Ź RecoverInput};

TypeSym: PROC [sym: TSymbol, put: IO.STREAM] = {

put.PutChar[' ];

IF sym IN [1..endMarker)

THEN {

IF vocabIndex = NIL THEN vocabIndex Ź InitIndexTable[];

IF vocabBody = NIL THEN vocabBody Ź InitVocabulary[];

FOR i: NAT IN [vocabIndex[sym-1]..vocabIndex[sym]) DO

put.PutChar[vocabBody[i]];

ENDLOOP;

}

ELSE put.Put1[[integer[sym]]];

};

stack node indices

rTop: NodeIndex Ź 0;

Recover: PROC [errPut: IO.STREAM] = {

ModeMap: ARRAY Position OF ParsingMode = [ATree, BTree];

stack: StackRep;

treeLimit Ź TreeSize - CheckSize;

hashTable Ź ALL[NullIndex];

rTop Ź NullIndex; nextNode Ź maxNode Ź 1;

best.nAccepted Ź 0; best.nPassed Ź 1; best.mode Ź ATree;

sourceText[0] Ź lastToken;

sourceText[1] Ź MPP1.Token[inputSymbol, inputValue, inputLoc];

scanBase Ź 1; scanLimit Ź 2;

THROUGH [1 .. MaxScanLimit) DO Advance[errPut] ENDLOOP;

FOR i: CARDINAL IN [0 .. top)

DO rTop Ź Allocate[rTop, rTop, 0, s[i]] ENDLOOP;

parseMode Ź BTree;

levelStart[before][0] Ź rTop Ź FindNode[rTop, rTop, s[top]];

tree[rTop].bLeaf Ź TRUE;

levelEnd[before][0] Ź nextNode;

parseMode Ź ATree;

stack Ź ParseStep[[leaf:rTop, extension:NullState], lastToken.class];

rTop Ź FindNode[stack.leaf, rTop, stack.extension];

tree[rTop].symbol Ź lastToken.class;

tree[rTop].aLeaf Ź tree[rTop].bLeaf Ź TRUE;

levelStart[after][0] Ź rTop; levelEnd[after][0] Ź nextNode;

FOR level: Length IN [1 .. LAST[Length]] DO

FOR place: Position IN Position DO

parseMode Ź ModeMap[place];

IF place = before THEN UnDiscard[];

try simple insertion (inserts=level)

levelStart[place][level] Ź nextNode;

IF GrowTree[place, level !TreeFull => CONTINUE] THEN GO TO found;

levelEnd[place][level] Ź nextNode;

try discards followed by 0 or more insertions

THROUGH [1 .. level) DO

Discard[]; IF CheckTree[place, level] THEN GO TO found;

ENDLOOP;

Discard[];

IF place = after THEN Advance[errPut];

FOR inserts: CARDINAL IN [0 .. level]

DO IF CheckTree[place, inserts] THEN GO TO found ENDLOOP;

undo discards at this level

THROUGH [1..level] DO UnDiscard[] ENDLOOP;

IF place = before THEN Discard[];

ENDLOOP;

REPEAT

found => NULL;

FINISHED => {

threshold: CARDINAL Ź (MinScanLimit+MaxScanLimit)/2;

THROUGH [1..LAST[Length]] DO Discard[]; Advance[errPut] ENDLOOP;

UNTIL scanBase > DiscardLimit

DO

IF best.nAccepted >= threshold THEN GO TO found;

Discard[];

FOR inserts: CARDINAL IN Length

DO

FOR place: Position IN Position

DO

parseMode Ź ModeMap[place];

IF place = before THEN UnDiscard[];

IF CheckTree[place, inserts] THEN GO TO found;

IF place = before THEN Discard[];

ENDLOOP;

Advance[errPut];

threshold Ź IF threshold > MinScanLimit THEN threshold-1 ELSE MinScanLimit;

REPEAT

found => NULL;

FINISHED =>

IF best.nAccepted < MinScanLimit

THEN {best.mode Ź ATree; best.nPassed Ź 1};

ENDLOOP};

SyntaxError: PROC [abort: BOOL, put: IO.STREAM] RETURNS [success: BOOL] = {

IF abort

THEN {

MPP1.ErrorContext["Syntax Error", inputLoc, put];

put.PutRope["... Parse abandoned."]; put.PutChar['\n];

success Ź FALSE}

ELSE {

sourceText Ź NEW[Buffer Ź ALL[MPP1.nullToken]];

newText Ź NEW[Insert Ź ALL[MPP1.nullToken]];

tree Ź NEW[ARRAY [0..TreeSize) OF StackNode];

hashTable Ź NEW[ARRAY [0..HashSize) OF NodeIndex];

Recover[put ! TreeFull => CONTINUE];

hashTable Ź NIL;

MPP1.ErrorContext["Syntax Error",

sourceText[IF best.mode=BTree THEN 0 ELSE 1].index, put];

IF ~(success Ź best.nAccepted >= MinScanLimit) OR ~Accept[put]

THEN {

put.PutRope["No recovery found."];

newText Ź NIL; sourceText Ź NIL};

tree Ź NIL;

vocabIndex Ź NIL;

put.PutChar['\n]};

put.PutChar['\n];

RETURN};

}.