DIRECTORY IO USING [int, Put, PutRope, PutChar, STREAM], PPP1 USING [ Token, Value, ValueSeq, ValueStack, NullValue, INTSeq, ActionEntrySeq, AssignDescriptors, Atom, ErrorContext, ProcessQueue, ResetScanIndex, ScanInit, ScanReset], PPParseTable USING [ ActionEntry, ActionTag, Handle, NTIndex, NTState, NTSymbol, ProdDataHandle, State, TIndex, TSymbol, DefaultMarker, EndMarker, InitialState, FinalState, InitialSymbol], Rope USING [ROPE]; PPParser: PROGRAM IMPORTS IO, P1: PPP1 EXPORTS PPP1 = BEGIN OPEN PPParseTable, Rope; ErrorLimit: CARDINAL = 10; Scan: ActionTag = [FALSE, 0]; inputSymbol: TSymbol; input: PROC [errPut: IO.STREAM] RETURNS [token: P1.Token]; inputLoc: INT; inputValue: P1.Value; lastToken: P1.Token; NullSymbol: TSymbol = 0; firstInit: BOOL _ TRUE; s: REF StateSeq _ NIL; StateSeq: TYPE = RECORD[SEQUENCE length: CARDINAL OF State]; l: REF P1.INTSeq _ NIL; v: P1.ValueStack _ NIL; top: CARDINAL _ 0; q: REF P1.ActionEntrySeq _ NIL; qI: CARDINAL; tablePtr: Handle; tStart: LONG POINTER TO ARRAY State OF TIndex _ NIL; tLength: LONG POINTER TO ARRAY State OF CARDINAL _ NIL; tSymbol: LONG POINTER TO ARRAY TIndex OF TSymbol _ NIL; tAction: LONG POINTER TO ARRAY TIndex OF ActionEntry _ NIL; nStart: LONG POINTER TO ARRAY NTState OF NTIndex _ NIL; nLength: LONG POINTER TO ARRAY NTState OF CARDINAL _ NIL; nSymbol: LONG POINTER TO ARRAY NTIndex OF NTSymbol _ NIL; nAction: LONG POINTER TO ARRAY NTIndex OF ActionEntry _ NIL; ntDefaults: LONG POINTER TO ARRAY NTSymbol OF ActionEntry _ NIL; prodData: ProdDataHandle _ NIL; ParseInit: PROC [source: ROPE, pth: Handle] = { tablePtr _ pth; P1.ScanInit[tablePtr, source]; tStart _ @tablePtr.parseTable.tStart; tLength _ @tablePtr.parseTable.tLength; tSymbol _ @tablePtr.parseTable.tSymbol; tAction _ @tablePtr.parseTable.tAction; nStart _ @tablePtr.parseTable.nStart; nLength _ @tablePtr.parseTable.nLength; nSymbol _ @tablePtr.parseTable.nSymbol; nAction _ @tablePtr.parseTable.nAction; ntDefaults _ @tablePtr.parseTable.ntDefaults; prodData _ @tablePtr.parseTable.prodData; 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, pth: Handle, errPut: IO.STREAM] RETURNS [complete: BOOL, nTokens, nErrors: CARDINAL] = TRUSTED { currentState: State; i, valid, m: CARDINAL; -- stack pointers action: ActionEntry; ParseInit[source, pth]; input _ P1.Atom; nErrors _ 0; complete _ TRUE; i _ top _ valid _ 0; qI _ 0; s[0] _ currentState _ InitialState; lastToken.class _ NullSymbol; inputSymbol _ InitialSymbol; inputValue _ P1.NullValue; inputLoc _ 0; WHILE currentState # FinalState DO BEGIN 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; P1.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)]; BEGIN 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; END; 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}; END; ENDLOOP; P1.ProcessQueue[qI, top]; {n: CARDINAL; [nTokens, n] _ P1.ScanReset[]; nErrors _ nErrors + n}; RETURN}; ExpandStack: PROC [delta: CARDINAL] = { newS: REF StateSeq; newL: REF P1.INTSeq; newV: P1.ValueStack _ NIL; newSize: CARDINAL = (IF s = NIL THEN 0 ELSE s.length) + delta; newS _ NEW[StateSeq[newSize]]; newL _ NEW[P1.INTSeq[newSize]]; newV _ IF v # NIL AND v.length >= newSize THEN v ELSE NEW[P1.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; P1.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 P1.ActionEntrySeq _ NEW[P1.ActionEntrySeq[newSize]]; IF q # NIL THEN FOR i: CARDINAL IN [0..q.length) DO newQ[i] _ q[i] ENDLOOP; q _ newQ; P1.AssignDescriptors[qd:q, vd:v, ld:l, pp:prodData]}; -- * * * * Error Recovery Section * * * * -- MinScanLimit: CARDINAL = 4; MaxScanLimit: CARDINAL = 12; InsertLimit: CARDINAL = 2; DiscardLimit: CARDINAL = 10; TreeSize: CARDINAL = 256; CheckSize: CARDINAL = MaxScanLimit+InsertLimit+2; ParserID: PUBLIC SAFE PROC RETURNS [ROPE] = TRUSTED {RETURN ["Flako!"]}; 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; maxNode: NodeIndex; treeLimit: CARDINAL; 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; 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}; 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]}; Insert: TYPE = ARRAY [0 .. 1+InsertLimit) OF P1.Token; newText: REF Insert; insertCount: CARDINAL; Buffer: TYPE = ARRAY [0 .. 1 + DiscardLimit + (MaxScanLimit+InsertLimit)) OF P1.Token; sourceText: REF Buffer; scanBase, scanLimit: CARDINAL; 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: P1.Token] = { 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 _ P1.Atom}}; RETURN}; best: RECORD [ nAccepted: CARDINAL, nPassed: [0..1], node: NodeIndex, mode: ParsingMode, nDiscards: CARDINAL]; 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]}; RowRecord: TYPE = RECORD [ index, limit: CARDINAL, stack: StackRep, next: RowHandle]; RowHandle: TYPE = REF RowRecord; NextRow: PROC [list: RowHandle] RETURNS [row: RowHandle] = { t: TSymbol; 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, levelEnd: ARRAY Position OF ARRAY Length OF NodeIndex; 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] _ P1.Token[s, P1.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 _ P1.ResetScanIndex[sourceText[scanBase+best.nAccepted].index] ELSE success _ TRUE; scanLimit _ scanBase + best.nAccepted; input _ RecoverInput}; TypeSym: PROC [sym: TSymbol, put: IO.STREAM] = { OPEN tablePtr.scanTable; vocab: LONG STRING = LOOPHOLE[@vocabBody]; put.PutChar[' ]; IF sym NOT IN [1..EndMarker) THEN put.Put[IO.int[sym]] ELSE FOR i: CARDINAL IN [vocabIndex[sym-1]..vocabIndex[sym]) DO put.PutChar[vocab[i]] ENDLOOP}; rTop: NodeIndex; 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] _ P1.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[]; levelStart[place][level] _ nextNode; IF GrowTree[place, level !TreeFull => CONTINUE] THEN GO TO found; levelEnd[place][level] _ nextNode; 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; 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; 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}; ENDLOOP}; SyntaxError: PROC [abort: BOOL, put: IO.STREAM] RETURNS [success: BOOL] = { IF abort THEN { P1.ErrorContext["Syntax Error", inputLoc, put]; put.PutRope["... Parse abandoned."]; put.PutChar['\n]; success _ FALSE} ELSE { sourceText _ NEW[Buffer]; newText _ NEW[Insert]; tree _ NEW[ARRAY [0..TreeSize) OF StackNode]; hashTable _ NEW[ARRAY [0..HashSize) OF NodeIndex]; Recover[put ! TreeFull => CONTINUE]; hashTable _ NIL; P1.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; put.PutChar['\n]}; put.PutChar['\n]; RETURN}; END. HPPParser.Mesa derived from Compiler>Parser.Mesa Satterthwaite, January 12, 1981 12:58 PM Russ Atkinson, November 12, 1982 2:44 pm Paul Rovner, August 25, 1983 4:50 pm transition tables for terminal input symbols transition tables for nonterminal input symbols production information initialization/termination parameters of error recovery debugging tree management parsing simulation text buffer management acceptance checking strategy management stack node indices try simple insertion (inserts=level) try discards followed by 0 or more insertions undo discards at this level ʧ˜J˜Jšœ ™ Jšœ!™!Jšœ)™)Jšœ(™(Jšœ$™$J˜šÏk ˜ Jšœœœ˜.šœœ˜ J˜FJ˜DJ˜—šœ œ˜J˜;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šœœ˜—š œœœœœœ˜0Jšœ4œ˜>—J˜J˜5J˜—šž œœ œ˜'Jš œ œœœœœ˜>Jšœœœ˜>Jšœœœœœœœœ˜NJ˜ J˜5J˜——JšŸ,˜,˜Jšœ™˜Jšœœ˜Jšœœ˜Jšœ œ˜Jšœœ˜Jšœ œ˜Jšœ œ˜1J˜—Jšœ ™ ˜Jšžœœœœœœœœ ˜HJ˜—Jšœ™˜Jšœ œœ˜)J˜J˜šœ œœ˜J˜J˜J˜J˜Jšœœ˜J˜J˜—Jšœœœœ ˜+J˜J˜Jšœ œ˜Jšœ œœ˜J˜šžœœ=˜KJšœ˜Jšœ!œœ ˜8Jšœ œ˜˜J˜J˜ J˜J˜Jšœœ œ˜J˜—Jšœœ˜ J˜J˜—Jšœ œŸ!˜@Jšœ œœœ ˜0J˜Jšœ œ˜-J˜J˜šžœœ˜!Jšœ'œ ˜4J˜š˜Jšœœ˜,—Jšœ˜—J˜šœ˜Jšœœ Ÿ˜AJšœ ˜—J˜)J˜Jšœ˜—Jšœ ˜J˜J˜——Jšœ™˜Jšœœœœ ˜6Jšœ œ˜Jšœ œ˜J˜šœœ˜Jšœ6œ ˜G—Jšœ œ˜Jšœœ˜J˜J˜šžœœ œœ˜#J˜AJ˜—Jšžœœ˜(J˜Jšž œœ˜*J˜š ž œœ œœœ˜Dšœ˜šœ˜J˜šœ,˜.Jšœ œ˜——šœ˜J˜šœ$˜&Jšœœ˜*———Jšœ˜J˜——Jšœ™˜šœœ˜Jšœ œ˜J˜J˜J˜Jšœ œ˜J˜—šž œœœœ˜=J˜$J˜#Jšœ œ ˜!J˜3J˜ Jšœ œ˜J˜,šœœœ˜+Jš˜šœ˜šœ˜šœ œ"˜0Jšœ˜Jšœ˜—Jšœ˜——J˜.Jšœœœ˜$J˜4Jšœ˜—J˜2šœ˜#˜šœ.˜0Jšœ0˜4——˜šœ*˜,Jšœ.˜2——Jšœ˜—Jšœ˜$J˜J˜——Jšœ™˜šœ œœ˜Jšœœ˜J˜J˜J˜—Jšœ œœ ˜ J˜šžœœœ˜Jšœœ˜J˜#J˜šœœ)˜EJšœ"œ˜-šœ˜J˜Fšœ ˜Jšœœ˜$Jšœœ˜$Jšœœ˜—J˜J˜——Jšœ˜J˜J˜—šžœœœœ˜CJ˜J˜J˜ J˜Jšœ œ˜šœœ*˜=Jš˜šœœ˜šœ˜Jšœ œ˜˜>Jš˜J˜2JšœœF˜MJ˜ Jšœ œ#œœ˜>J˜J˜0J˜Jšœ˜—šœœ˜#Jš˜Jšœ'œœœ˜:J˜Jšœ˜ ———š˜Jšœœ˜Jšœ œ˜—Jšœ˜—Jšœ œ˜Jšœ˜J˜—šž œœœœ˜Dšœœ%˜8Jš˜Jšœ œ˜Jšœœœœ˜!š˜Jšœœ˜Jšœ œ˜—Jšœ˜—Jšœ˜J˜J˜—š žœœœœœ œ˜9J˜ Jšœ œ˜%J˜šœ(œ ˜9Jš˜šœ˜šœ˜J˜J˜<——Jšœ˜—J˜šœ˜šœ˜J˜!šœœœ˜(Jš˜J˜CJšœ˜ ———šœ˜šœ˜Jšœœ˜0J˜"šœœœ˜/Jšœ"œ˜-———šœ˜JšœE˜I—Jšœœ œ˜0šœ&˜(JšœG˜KJšœ œ˜—J˜&J˜J˜—šžœœœœ˜0Jšœ˜Jšœœœœ ˜*J˜šœœœ˜Jšœ œ ˜š˜šœœœ%˜7Jšœœ˜#J˜——————šœ™J˜J˜šžœœ œœ˜%Jšœ œ œ˜8J˜J˜J˜!Jšœ œ ˜J˜*J˜J˜:J˜J˜šœ˜J˜"Jšœ œœ˜"——Jšœœ˜ J˜——J˜Jšœ˜J˜——Jšœ˜J˜J˜—…—Fª`™