DIRECTORY
IO USING [char, int, Put, PutChar, PutRope, rope, STREAM],
NPGS1 USING [ActionSeq, AssignDescriptors, ErrorContext, Index, InstallScanTable, LinkSeq, LinkStack, NextToken, nullValue, ProcessQueue, ResetScanIndex, ScanInit, ScanReset, ScanStats, StateSeq, StateStack, Token, TokenValue, Value, ValueSeq, ValueStack],
NPGSParseTable 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];
NPGSParser:
CEDAR
PROGRAM
IMPORTS IO, NPGS1, NPGSParseTable
EXPORTS NPGS1
= {
table installation
stuff for TypeSym
vocabIndex: NPGSParseTable.IndexTableRef ← NIL;
vocabBody: NPGSParseTable.VocabularyRef ← NIL;
transition tables for terminal input symbols
tStart: NPGSParseTable.TStartsRef;
tLength: NPGSParseTable.TLengthsRef;
tSymbol: NPGSParseTable.TSymbolsRef;
tAction: NPGSParseTable.TActionsRef;
transition tables for nonterminal input symbols
nStart: NPGSParseTable.NStartsRef;
nLength: NPGSParseTable.NLengthsRef;
nSymbol: NPGSParseTable.NSymbolsRef;
nAction: NPGSParseTable.NActionsRef;
ntDefaults: NPGSParseTable.NTDefaultsRef;
production information
prodData: NPGSParseTable.ProdDataRef;
InstallParseTable:
PUBLIC
PROC = {
IF prodData =
NIL
THEN {
tStart ← NPGSParseTable.InitTStarts[];
tLength ← NPGSParseTable.InitTLengths[];
tSymbol ← NPGSParseTable.InitTSymbols[];
tAction ← NPGSParseTable.InitTActions[];
nStart ← NPGSParseTable.InitNStarts[];
nLength ← NPGSParseTable.InitNLengths[];
nSymbol ← NPGSParseTable.InitNSymbols[];
nAction ← NPGSParseTable.InitNActions[];
ntDefaults ← NPGSParseTable.InitNTDefaults[];
prodData ← NPGSParseTable.InitProdData[];
NPGS1.InstallScanTable[];
};
};
parser state
errorLimit: NAT = 25;
scanTag: NPGSParseTable.ActionTag = [FALSE, 0];
inputSymbol: NPGSParseTable.TSymbol;
Input: PROC RETURNS [token: NPGS1.Token];
inputLoc: NPGS1.Index ← 0;
inputValue: NPGS1.Value;
lastToken: NPGS1.Token;
nullSymbol: NPGSParseTable.TSymbol = 0;
s: NPGS1.StateStack;
l: NPGS1.LinkStack;
v: REF NPGS1.ValueSeq;
top: CARDINAL;
q: REF NPGS1.ActionSeq;
qI: CARDINAL;
initialization/termination
InputLoc: PUBLIC PROC RETURNS[NPGS1.Index] = {RETURN[inputLoc]};
* * * * Main Parsing Procedures * * * * --
Parse:
PUBLIC
PROC[
source: IO.STREAM,
logger: PROC[PROC[log: IO.STREAM]],
prefixOk: BOOL, cusp: BOOL]
RETURNS[complete:
BOOL, nTokens, nErrors:
NAT] = {
currentState: NPGSParseTable.State;
i, valid, m: CARDINAL; -- stack pointers
action: NPGSParseTable.ActionEntry;
ParseInit:
PROC = {
NPGS1.ScanInit[source, logger];
s ← NIL;
q ← NIL;
ExpandStack[500];
q ← NIL;
ExpandQueue[250];
scanBuffer ← NIL;
};
ParseReset:
PROC = {
EraseQueue[];
EraseStack[];
IF scanBuffer # NIL THEN FREE[@scanBuffer];
NPGS1.ScanReset[];
};
ParseInit[];
{
-- ENABLE scope
ENABLE UNWIND => {ParseReset[]};
Input ← NPGS1.NextToken;
nErrors ← 0; complete ← TRUE;
i ← top ← valid ← 0; qI ← 0;
s[0] ← currentState ← NPGSParseTable.initialState;
lastToken.class ← nullSymbol;
inputSymbol ← NPGSParseTable.initialSymbol;
inputValue.s ← NPGS1.nullValue;
inputLoc ← 0;
UNTIL currentState = NPGSParseTable.finalState
AND (prefixOk
OR (inputSymbol = NPGSParseTable.endMarker))
DO
{
tI: NPGSParseTable.TIndex ← tStart[currentState];
FOR tI
IN [tI .. tI + tLength[currentState])
DO
SELECT tSymbol[tI] FROM inputSymbol, NPGSParseTable.defaultMarker => EXIT ENDCASE;
REPEAT
FINISHED => GO TO SyntaxError;
ENDLOOP;
action ← tAction[tI];
IF ~action.tag.reduce
THEN
TRUSTED {
-- scan or scan reduce entry
IF qI > 0
THEN {
FOR k: CARDINAL IN (valid..i] DO s[k] ← s[top+(k-valid)] ENDLOOP;
NPGS1.ProcessQueue[qI, top, cusp]; qI ← 0
};
IF (top ← valid ← i ← i+1) >= s.length THEN ExpandStack[256];
lastToken.class ← inputSymbol; v[i] ← inputValue; 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)]; {
lhs: NPGSParseTable.NTSymbol = prodData[action.transition].lhs;
IF currentState <= NPGSParseTable.NTState.
LAST
THEN {
nI: NPGSParseTable.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[256];
s[m] ← currentState ← action.transition;
EXITS
SyntaxError =>
TRUSTED {
lastToken.value ← v[top]; lastToken.index ← l[top];
top ← top - 1;
complete ← SyntaxError[logger, (nErrors←nErrors+1)>errorLimit];
i ← valid ← top; qI ← 0; lastToken.class ← nullSymbol;
currentState ← s[i];
[[inputSymbol, inputValue, inputLoc]] ← Input[];
IF ~complete THEN EXIT
};
};
ENDLOOP;
NPGS1.ProcessQueue[qI, top, cusp];
nErrors ← nErrors + ([nTokens: nTokens] ← NPGS1.ScanStats[]).nErrors;
}; -- of ENABLE scope
ParseReset[];
};
ExpandStack:
PROC[delta:
NAT] = {
oldSize: NAT = (IF s = NIL THEN 0 ELSE s.length);
newSize: NAT = oldSize + delta;
newS: NPGS1.StateStack = NEW[NPGS1.StateSeq[newSize]];
newL: NPGS1.LinkStack = NEW[NPGS1.LinkSeq[newSize]];
newV: NPGS1.ValueStack = NEW[NPGS1.ValueSeq[newSize]];
FOR i:
NAT
IN [0..oldSize)
DO
TRUSTED {
newS[i] ← s[i]; newL[i] ← l[i]; newV[i] ← v[i]
};
ENDLOOP;
EraseStack[];
s ← newS; l ← newL; v ← newV;
NPGS1.AssignDescriptors[qd:q, vd:v, ld:l, pp:prodData];
};
EraseStack:
PROC = {
IF s # NIL THEN {FREE[@v]; FREE[@l]; FREE[@s]};
};
ExpandQueue:
PROC[delta:
NAT] = {
oldSize: NAT = (IF q = NIL THEN 0 ELSE q.length);
newSize: NAT = oldSize + delta;
newQ: REF NPGS1.ActionSeq = NEW[NPGS1.ActionSeq[newSize]];
FOR i: NAT IN [0..oldSize) DO newQ[i] ← q[i] ENDLOOP;
q ← newQ;
NPGS1.AssignDescriptors[qd:q, vd:v, ld:l, pp:prodData];
};
EraseQueue: PROC = {IF q # NIL THEN FREE[@q]};
* * * * Error Recovery Section * * * * --
parameters of error recovery
errorStream: IO.STREAM ← NIL;
minScanLimit: NAT = 4;
maxScanLimit: NAT = 12;
insertLimit: NAT = 2;
discardLimit: NAT = 10;
treeSize: NAT = 250;
checkSize: NAT = maxScanLimit+insertLimit+2;
debugging
track: BOOL = FALSE;
DisplayNode:
PROC[n: NodeIndex] = {
IF track
THEN {
errorStream.PutRope["::new node::"];
errorStream.Put[IO.char['\t], IO.int[n]];
errorStream.Put[IO.char['\t], IO.int[tree[n].father]];
errorStream.Put[IO.char['\t], IO.int[tree[n].last]];
errorStream.Put[IO.char['\t], IO.int[tree[n].state]];
errorStream.PutChar['\t]; TypeSym[tree[n].symbol];
errorStream.PutChar['\n];
};
};
tree management
NodeIndex: TYPE = NAT [0..treeSize);
nullIndex: NodeIndex = 0;
StackNode:
TYPE =
RECORD[
father: NodeIndex,
last: NodeIndex,
state: NPGSParseTable.State,
symbol: NPGSParseTable.TSymbol,
aLeaf, bLeaf: BOOL,
link: NodeIndex];
TreeSpace: TYPE = ARRAY [0..treeSize) OF StackNode;
tree: REF TreeSpace;
nextNode: NAT [0..treeSize] ← 0;
maxNode: NodeIndex ← 0;
treeLimit: NAT [0..treeSize] ← 0;
TreeFull: ERROR = CODE;
Allocate: PROC[parent, pred: NodeIndex, terminal: NPGSParseTable.TSymbol, stateNo: NPGSParseTable.State]
RETURNS [index: NodeIndex] = {
IF (index ← nextNode) >= treeLimit THEN ERROR 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;
};
hashSize: NAT = 250; -- should depend on state count ?
HashIndex: TYPE = [0..hashSize);
HashSpace: TYPE = ARRAY HashIndex OF NodeIndex;
hashTable: REF HashSpace;
HashValue:
PROC[s: NPGSParseTable.State]
RETURNS[HashIndex] =
INLINE {
RETURN[s MOD hashSize];
};
ParsingMode: TYPE = {aTree, bTree, checking};
parseMode: ParsingMode ← checking;
LinkHash:
PROC[n: NodeIndex] = {
htIndex: HashIndex = HashValue[tree[n].state];
tree[n].link ← hashTable[htIndex];
hashTable[htIndex] ← n;
};
DelinkHash:
PROC[n: NodeIndex] = {
htIndex: HashIndex = HashValue[tree[n].state];
p: NodeIndex ← nullIndex;
FOR i: NodeIndex ← hashTable[htIndex], tree[i].link
UNTIL i = nullIndex
DO
IF i = n THEN GO TO delete;
p ← i;
REPEAT
delete =>
IF p = nullIndex
THEN hashTable[htIndex] ← tree[n].link
ELSE tree[p].link ← tree[n].link;
ENDLOOP
};
ExistingConfiguration:
PROC[stack: StackRep]
RETURNS[NodeIndex] = {
htIndex: HashIndex;
aTree: BOOL;
SELECT parseMode
FROM
$aTree => aTree ← TRUE;
$bTree => aTree ← FALSE;
ENDCASE => RETURN [nullIndex];
htIndex ← HashValue[stack.extension];
FOR i: NodeIndex ← hashTable[htIndex], tree[i].link
UNTIL i = nullIndex
DO
IF (
IF aTree
THEN tree[i].aLeaf
ELSE tree[i].bLeaf)
THEN {
s1: NPGSParseTable.State ← stack.extension;
s2: NPGSParseTable.State ← tree[i].state;
n1: NodeIndex ← stack.leaf;
n2: NodeIndex ← tree[i].father;
DO
IF s1 # s2 THEN EXIT;
IF n1 = n2 THEN RETURN [i];
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: NPGSParseTable.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
};
};
TrimTree:
PROC[newNext: NodeIndex] = {
WHILE nextNode > newNext
DO
nextNode ← nextNode-1; DelinkHash[nextNode] ENDLOOP
};
parsing simulation
ExtState: TYPE = [NPGSParseTable.State.FIRST .. NPGSParseTable.State.LAST+1];
nullState: ExtState = ExtState.LAST;
StackRep:
TYPE =
RECORD[
leaf: NodeIndex,
extension: ExtState];
GetNTEntry:
PROC[state: NPGSParseTable.State, lhs: NPGSParseTable.NTSymbol]
RETURNS[NPGSParseTable.ActionEntry] =
INLINE {
IF state <= NPGSParseTable.NTState.
LAST
THEN {
nI: NPGSParseTable.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: NPGSParseTable.ActionEntry, nScanned: [0..1]]
RETURNS[StackRep] = {
currentNode, thread: NodeIndex ← stack.leaf;
count: NAT ← nScanned;
currentState: NPGSParseTable.State;
IF stack.extension = nullState
THEN currentState ← tree[currentNode].state
ELSE {currentState ← stack.extension; count ← count + 1};
UNTIL action.tag = scanTag
DO
IF count > action.tag.pLength
THEN {
-- can be one greater
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, input: NPGSParseTable.TSymbol]
RETURNS[StackRep] = {
currentState: NPGSParseTable.State ← (
IF stack.extension = nullState
THEN tree[stack.leaf].state
ELSE stack.extension);
scanned: BOOL ← FALSE;
UNTIL scanned
OR currentState = NPGSParseTable.finalState
DO
action: NPGSParseTable.ActionEntry;
count: [0..1];
tI: NPGSParseTable.TIndex ← tStart[currentState];
FOR tI
IN [tI..tI+tLength[currentState])
DO
SELECT tSymbol[tI] FROM input, NPGSParseTable.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 NPGS1.Token;
newText: REF Insert;
insertCount: NAT ← 0;
Buffer: TYPE = ARRAY [0 .. 1+discardLimit+(maxScanLimit+insertLimit)) OF NPGS1.Token;
scanBuffer: REF Buffer;
scanBase, scanLimit: NAT ← 0;
Advance: PROC = {scanBuffer[scanLimit] ← Input[]; scanLimit ← scanLimit+1};
Discard:
PROC = {
IF track
THEN {
errorStream.PutRope["::discarding symbol: "];
TypeSym[scanBuffer[scanBase].class];
errorStream.PutChar['\n];
};
scanBase ← scanBase+1;
};
UnDiscard:
PROC = {
scanBase ← scanBase-1;
IF track
THEN {
errorStream.PutRope["::recovering symbol: "];
TypeSym[scanBuffer[scanBase].class];
errorStream.PutChar['\n];
};
};
RecoverInput:
PROC
RETURNS [token:
NPGS1.Token] = {
IF insertCount <= insertLimit
THEN {
token ← newText[insertCount];
IF (insertCount ← insertCount+1) > insertLimit THEN FREE[@newText];
}
ELSE {
token ← scanBuffer[scanBase];
IF (scanBase ← scanBase+1) = scanLimit
THEN {
FREE[@scanBuffer];
Input ← NPGS1.NextToken;
};
};
};
acceptance checking
best:
RECORD [
nAccepted: NAT ← 0,
nPassed: [0..1] ← 0,
node: NodeIndex ← 0,
mode: ParsingMode ← checking,
nDiscards: NAT ← 0];
RightScan:
PROC[node: NodeIndex]
RETURNS[stop:
BOOL] = {
savedNextNode: NodeIndex = nextNode;
savedMode: ParsingMode = parseMode;
savedLimit: NAT = treeLimit;
stack: StackRep ← [leaf:node, extension:nullState];
state: NPGSParseTable.State ← tree[node].state;
nAccepted: NAT ← 0;
parseMode ← $checking; treeLimit ← treeSize;
FOR i:
NAT
IN [scanBase .. scanLimit)
DO
IF state = NPGSParseTable.finalState
THEN {
nAccepted ← (
IF (scanBuffer[i].class = NPGSParseTable.endMarker)
THEN scanLimit-scanBase
ELSE 0);
EXIT
};
stack ← ParseStep[stack, scanBuffer[i].class];
IF stack.leaf = nullIndex THEN EXIT;
nAccepted ← nAccepted + 1; state ← stack.extension;
ENDLOOP;
TrimTree[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: NAT,
stack: StackRep,
next: RowHandle];
RowHandle: TYPE = REF RowRecord;
NextRow:
PROC[list: RowHandle]
RETURNS[row: RowHandle] =
INLINE {
t: NPGSParseTable.TSymbol ← NPGSParseTable.TSymbol.FIRST;
row ← NIL;
FOR r: RowHandle ← list, r.next
UNTIL r =
NIL
DO
IF r.index < r.limit
THEN {
s: NPGSParseTable.TSymbol = tSymbol[r.index];
IF row = NIL OR s < t THEN {row ← r; t ← s}
};
ENDLOOP;
};
FreeRowList:
PROC[list: RowHandle]
RETURNS[row: RowHandle] = {
r: RowHandle ← NIL;
UNTIL r =
NIL
DO
next: RowHandle = r.next;
FREE[@r]; r ← r.next;
ENDLOOP;
RETURN [NIL];
};
Position: TYPE = {after, before};
Length: TYPE = NAT [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: NPGSParseTable.TSymbol, thread: NodeIndex]
RETURNS[stop:
BOOL] = {
saveNextNode: NodeIndex = nextNode;
stack ← ParseStep[stack, s];
IF stack.leaf = nullIndex OR ExistingConfiguration[stack] # nullIndex
THEN {
TrimTree[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];
IF track THEN DisplayNode[newLeaf];
stop ← RightScan[newLeaf];
};
};
GrowTree:
PROC[p: Position, n: Length]
RETURNS[stop:
BOOL] = {
rowList: RowHandle ← NIL;
IF track
THEN {
errorStream.Put[IO.rope["::generating length: "], IO.int[n]];
errorStream.PutChar[IF p = $before THEN 'B ELSE 'A]; errorStream.PutChar['\n]
};
FOR i: NodeIndex
IN [levelStart[p][n-1] .. levelEnd[p][n-1])
DO
IF tree[i].symbol # 0
OR n = 1
THEN {
ENABLE UNWIND => {rowList ← FreeRowList[rowList]};
stack: StackRep ← [leaf:i, extension:nullState];
state: NPGSParseTable.State ← tree[i].state;
r: RowHandle;
DO
tI: NPGSParseTable.TIndex = tStart[state];
tLimit: NAT = tI + tLength[state];
r ← NEW[RowRecord];
r^ ← RowRecord[index:tI, limit:tLimit, stack:stack, next:rowList];
rowList ← r;
IF tI = tLimit OR tSymbol[tLimit-1] # NPGSParseTable.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;
rowList ← FreeRowList[rowList]
};
REPEAT
found => stop ← TRUE;
FINISHED => stop ← FALSE;
ENDLOOP;
rowList ← FreeRowList[rowList];
};
CheckTree:
PROC[p: Position, n: Length]
RETURNS[stop:
BOOL] = {
IF track
THEN {
errorStream.Put[IO.rope["::checking length: "], IO.int[n]];
errorStream.PutChar[IF p = $before THEN 'B ELSE 'A]; errorStream.PutChar['\n]
};
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;
};
Accept:
PROC
RETURNS[success:
BOOL] = {
s: NPGSParseTable.TSymbol;
discardBase: NAT = 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] ← NPGS1.Token[s, NPGS1.TokenValue[s], inputLoc]
};
ENDLOOP;
scanBase ← discardBase;
IF best.nDiscards # 0
THEN {
errorStream.PutRope["Text deleted is: "];
FOR j:
NAT
IN [1 .. best.nDiscards]
DO
TypeSym[scanBuffer[scanBase].class]; scanBase ← scanBase + 1;
ENDLOOP
};
IF insertCount <= insertLimit
THEN {
IF scanBase # discardBase THEN errorStream.PutChar['\n];
errorStream.PutRope["Text inserted is: "];
FOR j:
NAT
IN [insertCount .. insertLimit]
DO
TypeSym[newText[j].class] ENDLOOP
};
IF discardBase = 1 THEN {insertCount ← insertCount-1; newText[insertCount] ← scanBuffer[0]};
IF insertCount > insertLimit THEN FREE[@newText];
IF scanBase + best.nAccepted < scanLimit THEN
success ←
NPGS1.ResetScanIndex[scanBuffer[scanBase+best.nAccepted].index]
ELSE success ← TRUE;
scanLimit ← scanBase + best.nAccepted;
Input ← RecoverInput;
};
TypeSym:
PROC [sym: NPGSParseTable.TSymbol] = {
errorStream.PutChar[' ];
IF sym IN [1..NPGSParseTable.endMarker)
THEN {
IF vocabIndex = NIL THEN vocabIndex ← NPGSParseTable.InitIndexTable[];
IF vocabBody = NIL THEN vocabBody ← NPGSParseTable.InitVocabulary[];
FOR i:
NAT
IN [vocabIndex[sym-1]..vocabIndex[sym])
DO
errorStream.PutChar[vocabBody[i]];
ENDLOOP;
}
ELSE errorStream.Put[[integer[sym]]];
};
stack node indices
rTop: NodeIndex ← 0;
Recover:
PROC = {
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;
scanBuffer[0] ← lastToken;
scanBuffer[1] ← NPGS1.Token[inputSymbol, inputValue, inputLoc];
scanBase ← 1; scanLimit ← 2;
THROUGH [1 .. maxScanLimit) DO Advance[] ENDLOOP;
FOR i:
NAT
IN [0 .. top)
DO
rTop ← Allocate[rTop, rTop, 0, s[i]];
IF track THEN DisplayNode[rTop];
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;
IF track THEN DisplayNode[rTop];
FOR level: Length
IN [1 .. Length.
LAST]
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[];
FOR inserts:
NAT
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: NAT ← (minScanLimit+maxScanLimit)/2;
THROUGH [1..Length.LAST] DO Discard[]; Advance[] ENDLOOP;
UNTIL scanBase > discardLimit
DO
IF best.nAccepted >= threshold THEN GO TO found;
Discard[];
FOR inserts:
NAT
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;
ENDLOOP;
Advance[];
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
};
ENDLOOP;
};
SyntaxError:
PROC[
logger: PROC[PROC[IO.STREAM]], abort: BOOL] RETURNS [success: BOOL ← FALSE] = {
Inner:
PROC[log:
IO.
STREAM] = {
errorStream ← log;
IF abort
THEN {
NPGS1.ErrorContext[errorStream, "syntax error", inputLoc];
errorStream.PutRope["... parse abandoned."]; errorStream.PutChar['\n];
success ← FALSE;
}
ELSE {
scanBuffer ← NEW[Buffer];
newText ← NEW[Insert];
tree ← NEW[TreeSpace];
hashTable ← NEW[HashSpace];
Recover[ ! TreeFull => {CONTINUE}];
FREE[@hashTable];
NPGS1.ErrorContext[errorStream, "syntax error",
scanBuffer[IF best.mode=$bTree THEN 0 ELSE 1].index];
IF ~(success ← best.nAccepted >= minScanLimit
AND Accept[])
THEN {
errorStream.PutRope["No recovery found."];
FREE[@newText];
FREE[@scanBuffer];
};
FREE[@tree];
errorStream.PutChar['\n];
};
errorStream.PutChar['\n];
errorStream ← NIL;
};
logger[Inner];
};
}.