A small, but not quite correct, changes in CheckTop() and Compile() functions
in presented above compiler allows recognition of
the operator precedence in expressions:
word CheckTop(word L1) is
word R:=nRight;
word I:=pPoint[nStk];
while I< nPoint do
if Right[Point[I]]=L1 then
return nRight;
end
if Right[Point[I]]=0 then
if R<nRight then
Stop();
end
R:=Point[I];
end
I:=I+1;
end
return R;
end
word Compile() is
Heap [ 66]:='p';
Heap [ 67]:='r';
Heap [ 68]:='g';
hFile := open();
pText := 0;
nText := 0;
nLine := 1;
lFlag := 0;
rFlag := 0;
nCode := 0;
nData :=16640;
Emi1(0xE9); // jmp ?
Emi2(0x00);
Stk [0] := 1; // #
pPoint[0] := 0;
nStk := 0;
Point [0] := nRight;
nPoint := 1;
Left [nLeft]:= 1; // #
pRight[nLeft]:= nRight;
AddSym(pProg); // Program
AddSym(1); // #
AddSym(0);
nLeft := nLeft+1;
Closure(pPoint[nStk]);
while Stk[0]!=pProg do
Scan ();
Alter();
word R:=CheckTop(L);
while R< nRight do
Reduce(R);
Shift ();
R:=CheckTop(L);
end
Stk [nStk]:=L;
Val [nStk]:=V;
Shift();
end
close();
Heap [ 66]:='c';
Heap [ 67]:='o';
Heap [ 68]:='m';
hFile:=create();
write();
close();
end
In contrast to the previous parser which fixed the error in the presence of
the choice between shift and reduce, this parser performs reduce only if shift
will lead to an empty state (i.e. state with no points).
To take into account the opertors precedence next changes in file c.def may be done:
Expr : 190 Expr Op1 Term
| 0 Term
;
Term : 190 Term Op2 Value
| 0 Value
;
Op1 : 0 plus
| 0 minus
;
Op2 : 0 star
| 0 slash
| 0 pct
;
The modified parser also allow to remove the syntax sugar. For example semicolons,
is, then and do keywords may be removed from grammar (and from programs).
If you change the rule for Expr as follow
Expr : 190 Value Op Expr
| 0 Value
;
the expressions will be computed from right to left, i.e. as they are computed
in original Tiny Context language.
And adding to CheckTop() function correct choice between shift and reduce.
Unfortunately after that program exceeds one thousand lines of code limit:
word CanReduce(word Point1, word L1) is
word nPoint1:=nPoint;
AddPoint(nPoint1, Point1);
word I:=nPoint1;
while I< nPoint do
if Right[Point[I]]=0 then
word S:=Left[pLeft[Point[I]]];
word J:=0;
while J< nLeft do
word K:=pRight[J];
while Right[K]!=0 do
if Right[K]=S then
AddPoint(nPoint1, K+1);
end
K:=K+1;
end
J:=J+1;
end
end
I:=I+1;
end
Closure(nPoint1);
word J:=nPoint1;
while J< nPoint do
if Right[Point[J]]=L1 then
nPoint:=nPoint1;
return 0;
end
J:=J+1;
end
nPoint:=nPoint1;
return 1;
end
word CheckTop(word L1) is
word S:=0;
word R:=nRight;
word I:=pPoint[nStk];
while I< nPoint do
if Right[Point[I]]=L1 then
if R< nRight then
Stop();
end
S:=1;
end
if Right[Point[I]]=0 then
if CanReduce(Point[I], L1)=0 then
if S!=0 then
Stop();
end
if R< nRight then
Stop();
end
R:= Point[I];
end
end
I:=I+1;
end
if S=0 then
if R=nRight then
Stop();
end
end
return R;
end
In some cases these changes allow to choice one of several reduces.
For example, it will be possible to replace previously introduced terminal
symbols type, var, array and fn with corresponding non-terminal symbols
and rules for them:
Type : 270 char
| 270 byte
| 270 word
;
Var : 280 name
;
Array : 290 name
;
Fn : 300 name
;
In the new actions 270, 280, 290 and 300 need to search for a name in the dictionary
and verify that the symbol name are really Type, Var, Array or Fn. For example, when
trying to access a simple variable as an array element error must be fixed.
After that scaner and parser are made fully independent (scaner no longer need access
to the dictionary).
On modern computers, it is not very noticeable (but in DOSBox emulator are noticeable),
but the compiler is running slow. At each shift step it build new state (set of points)
and at each reduce step it destroy some states. To improve performance set of states
and transitions table must be build once. After that work speed may be comparable
to manually written recursive descent parser.