SLR(1)-анализатор

Небольшое, но не совсем честное, изменение функций CheckTop и Compile в приведенном выше компиляторе позволит распознавать выражения с учетом приоритета операторов:

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

В отличие от предыдущего анализатора, который фиксировал ошибку при наличии выбора между переносом и сверткой, этот выполняет свертку только если перенос приведет к пустому состоянию (т.е. состоянию, не содержащему ни одного пункта).

Чтобы учитывать приоритеты операторов достаточно в файле c.def заменить правила для Expr и Op:

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 ;

Правила для вызова функции теперь также можно упростить:

Call : 230 Fn lcb Params rcb | 230 Fn lcb rcb ; Params : 250 Params comma Expr | 250 Expr ; Fn : 260 fn ;

Измененный анализатор также может обходиться без синтаксического сахара. Можно исключить из грамматики (и из программ) точки с запятой, cлова is, then и do.

Если изменить правило для Expr следующим

Expr : 190 Value Op Expr | 0 Value ;

выражения станут вычисляться справа налево, т.е. так, как они вычисляются языке Tiny Context.

Осталось добавить в функцию CheckTop проверку отсутствия конфликтов между переносом и сверткой. К сожалению после этого длина программы превысит тысячу строк:

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

Эти изменения в ряде случаев также позволят выбирать одну из нескольких сверток. Например, станет возможно внеся лишь незначительные изменения в исходный текст компилятора исключить введенные ранее терминальные символы type, var, array и fn соответствующими нетерминальными символами и правилами преобразования в них:

Type : 270 char | 270 byte | 270 word ; Var : 280 name ; Array : 290 name ; Fn : 300 name ;

В новых действиях 270, 280, 290 и 300 нужно выполнять поиск имени в словаре и проверять, что символ name является тем, во что он будет преобразован. В частности, при попытке обратиться к простой переменной как к элементу массива должна фиксироваться ошибка.

За счет этого будет достигнуто разделение лексического и синтаксического анализаторов (лексическому анализатору более не нужен доступ к словарю).

На современных компьютерах это не очень заметно (а в эмуляторе DOSBox заметно), но приведенный компилятор работает медленно. Это связано с тем, что на каждом шаге он строит новое состояние. При каждой свертке часть построенных состояний уничтожается, затем они строятся вновь. Если построить множество состояний, таблицу переходов и сверток заранее, скорость работы компилятора станет стравнимой со скоростью работы компилятора, использующего метод рекурсивного спуска. Скорость можно увеличить еще если вместо перебора использовать какой-либо быстрый алгоритм поиска в словаре, например использовать хэш-таблицу.



Сайт создан в системе uCoz