В.М.Курочкин

Быстрый метод лексического анализа

Описание алгоритма (фрагмент статьи: В.М.Курочкин "Быстрый метод лексического анализа" // Программирование, 1997, N.5, стр.33-35.) Программа на Паскале

Алгоритмы вычисления атрибутов в атрибутных грамматиках

Описание алгоритма (фрагмент статьи: В.М.Курочкин "Алгоритмы вычисления атрибутов в атрибутных грамматиках" // Программирование, 1995, N.3, стр.3-8.) Программа на Паскале

Благодарность РФФИ

e-mail: kuroch@ccas.ru

---

Основные определения и обозначения.

Основой атрибутной грамматики АГ является контекстно- свободная (КС) грамматика G(V,T,P,S), где V-полный алфавит, T-терминальный алфавит, P-совокупность правил грамматики, имеющих вид p:a0->a1...al, S-аксиома.
Атрибутная грамматика AG(G,X,F)- это КС-грамматика G, в которой:
1. Каждому символу a из V сопоставлено конечное подмножество Xa множества X переменных x1,x2,..., называемых далее атрибутами. 2. Каждому правилу p:a0->a1...al из P сопоставлено конечное множество Fp функциональных зависимостей y=f(x...), выражающих значения одних из атрибутов символов a0,a1,...al, образующих данное правило p, через значения других атрибутов x... того же набора a0,a1,...al символов.
Основная задача, встающая при работе с АГ -это, коль скоро дано какое-то дерево вывода, вычислить значения всех атрибутов для всех узлов дерева.
В процессе выполнения описываемых далее алгоритмов вычисления атрибутов создается и трансформируется некоторый граф. Узлы X,Y,Z,... графа соответствуют атрибутам x,y,z,... вершин дерева вывода. С каждым узлом X связано несколько величин (узел удобно представлять себе как запись, а эти величины-как поля записи):
x-соответствующий узлу X атрибут,
а-логическая переменная; означает, что значение атрибута x еще не (или уже) вычислено.
b-логическая переменная; означает, что необходимость в значении атрибута x пока еще не (уже) ясна. Может оказаться что для данного конкретного дерева вывода нет необходимости вычислять все атрибуты, так как конечной целью является получение значений так называемых "выходных" атрибутов, а другие атрибуты вычисляются лишь постольку, поскольку они необходимы для вычисления "выходных". У ненужных атрибутов величина b так до конца и останется =0, а атрибут вычисляться не будет.
c-логическая переменная. c=true означает, что атрибут является выходным. После завершения работе алгоритма (или в процессе его выполнения как только выяснится, что какой-либо атрибут сам не является выходным и не нужен для вычисления значений других выходных атрибутов) все узлы с c=0 можно ликвидировать. Если c=1, то, конечно, и b=1.
n-целочисленная переменная, которая принимает значения 0,1 или 2, указывающие, сколько раз еще придется иметь дело с информацией в данном узле.
f-указатель на функцию, по которой можно вычислить значение данного атрибута, либо null, если эта функция пока еще не известна.
Узлы графа связываются ориентированными дугами. Дуга Y->X означает, что атрибут y непосредственно зависит от атрибута x, т.е. что y=f(..x..). Дуги могут быть четырех цветов: черные, синие, красные и зеленые. Предполагается, что сначала построен черный граф, содержащий все узлы-атрибуты всех вершин дерева вывода и все зависимости между атрибутами. Черный граф служит исключительно наглядным целям, он как бы является фоном для выполняемых построений. (В дальнейшем черный граф используется также для доказательства корректности алгоритма). Можно считать, что его нет, а в описываемых далее преобразованиях графа слова "черная дуга заменяется на синюю" читать "проводится синяя дуга". Смысл дуг следующий:
Синяя дуга Y->X, идущая от Y к X, означает, что есть прямая зависимость атрибута y от x: y=f(..x..), но пока неизвестно, надо ли будет вычислять y, так как Y.b=0.
Зеленая дуга Y->X означает, что есть прямая зависимость y от x: y=f(..x..), причем значение x уже известно (X.a=1), y пока не вычислено (Y.a=0), но y надо будет вычислять (Y.b=1), т.к. от него прямо или косвенно зависит один из выходных атрибутов.
Красная дуга, идущая от Y к X, означает, что есть прямая зависимость y от x, причем значение x ещ? не вычислено (X.a=0), а y надо будет вычислять (Y.b=1), как только будут известны значения всех его аргументов (атрибутов, от которых непосредственно зависит y).

---

Алгоритм построения и перестроения графа.

Вначале граф пустой (или построен черный граф, который, как было сказано, служит лишь фоном для последующих перестроений графа). Алгоритм не связан с каким-либо фиксированным порядком обхода дерева вывода. На вход алгоритма в произвольном порядке подаются все ветвления p: U0->U1...Uk дерева. Для каждого ветвления выполняется

Ветвление(p):

В1. Если вершина Uj (j=0,1...k) дерева вывода еще не обрабатывалась, то в графе добавляются узлы X, соответствующие всем атрибутам x вершины Uj. При этом полагается X.f=null; X.a=false; если атрибут x выходной, то X.b=X.c=true, иначе X.b=X.c=false. Если Uj терминальная вершина или аксиома, то X.n=1 иначе X.n=2.
В2. Для каждой связанной с p функциональной зависимостью y=f(x1...xm) выполняется зависимость(Y,f,X1...Xm), в результате чего, если нужно и можно, то вычисляется атрибут y, и происходит необходимое перестроение графа.
В3. Для всех атрибутов x всех вершин Uj (j=0,1...k) выполняется X.n:=X.n-1.
В4. Для всех атрибутов x всех вершин Uj (j=0,1...k) выполняется ли-граф(X), в результате чего будет ликвидирован узел X, если он уже не нужен для вычисления других атрибутов и сам не является выходным, а также все, что можно ликвидировать "ниже" X. (Здесь и далее "ниже" и "выше" означает движение в графе вдоль или напротив стрелок, что не может привести к недоразумениям, так как фоновый черный граф не содержал циклов ввиду незацикленности АГ.) Конец ветвления.

Зависимость(Y,f,X1...Xm):

З1. В узел Y помещается указатель на функцию f: Y.f:=f
З2. Для каждого i=1...m черная дуга Y->Xi заменяется на синюю (без фонового черного графа-проводится синяя дуга Y->Xi).
З3. Если Y.b=false, то конец Зависимости (т.к. y вычислять пока не надо).
З4. Выполняется Ниже(Y), перестраивая граф, расположенный ниже Y, включая Y.
1З05. Выполняется Выше(Y), перестраивая граф, расположенный выше Y.
Конец Зависимости.

Ниже(Y).

(Принять во внимание, что Y.b=1):
Н1. Для каждой выходящей из Y синей дуги Y->X
Н1.1. Если X.b=false, то X.b:=true, иначе переход к Н1.3.
Н1.2. Если X.f/=null и X.a=false, то выполнить Ниже(X).
Н1.3. Если X.a=true, то синяя дуга Y->X заменяется на зеленую, иначе (если X.a=false) на красную.
Н2. Если из узла Y не выходят красные дуги (т.е. выходят только зеленые или никаких нет), то вычисляется y, делается Y.a=true, ликвидируются все выходящие из Y дуги Y->X и для каждой из них выполняется Лик-уз(X), т.е. ликвидируется, если можно, узел Y.
Конец Ниже.

Выше(Y):

Вы1. Если Y.a=true и в Y входят красные дуги Z->Y, то
Вы1.1. Красная дуга заменяется на зеленую.
Вы1.2. Если из Z не выходит красных дуг, то вычисляется z, делается Z.a=true, ликвидируются все выходящие из Z дуги Z->X, для них выполняется Лик-уз(X).
Вы1.3. Выполняется Выше(Z).
Конец Выше.

Лик-уз(X).

(ликвидация узла, в котором вычислено значение атрибута и который более не нужен):
Если выполнены условия
X.a=true, X.c=false, X.n=0,
в X не входят синие и зеленые дуги (красные не могут, ибо X.a=true),
то узел X ликвидируется.

Ли-граф(Y).

(ликвидация узла и расположенной ниже его части графа):
Если выполняются условия
Y.n=0, Y.c=false,
в узел Y не входят никакие дуги,
то для всех выходящих из него синих (другие не могут!) дуг Y->X ликвидируется эта дуга Y->X, выполняется Ли-граф(X) и ликвидируется узел Y.

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

---

Реализация алгоритма (Паскаль 6.0-7.0)

 
 
Unit TrTyp;
{ в этом модуле описаны типы данных }
Interface
 
 { константы }
 const
 { максимальное число атрибутов у вершины }
 MaxNumAttributes = 10;
 
 { максимальное число вершин-потомков }
 MaxNumSuccessors = 10;
 
 { максимальное число аргументов у функций, вычисляющих атрибуты }
 MaxNumArguments = 10;
 
 
{ структуры данных }
type
 
 { категории атрибутов }
 AttCategory = (Synth,Inh);
 
 { указатель на атрибут }
 PAttribute = ^TAttribute;
 
 { указатель на вершину дерева вывода}
 PNode = ^TNode;
 
 { аргументы в зависимостях - пары вида (номер вершины, номер атрибута) }
 RelArg = record
 NoNode : integer;
 NoAtr : integer;
 end;
 
 { цвет ребра графа }
 TColor = (black,blue,green,red);
 
 { ребро графа }
 ColEdge = record
 target : PAttribute;
 color : TColor;
 end;
 
 
 { атрибут вершины дерева }
 TAttribute = Object
 
 { категория атрибута (синтезированный или унаследованный) }
 cat: AttCategory;
 
 { выходной или нет }
 out: Boolean;
 
 { указатель на вершину дерева, к которой этот атрибут относится }
 nod: PNode;
 
 { какой он там по счету }
 its_num : integer;
 
 { список аргументов, от которых данный атрибут явно зависит }
 arguments: array [1..MaxNumArguments] of RelArg;
 
 { сколько на самом деле аргументов }
 NumArgs: integer;
 
 {--- далее идут поля, относящиеся к вершине графа, }
 { которая соответствует данному атрибуту}
 
 { добавлена ли в граф соответствующая вершина }
 drawn: Boolean;
 
 { вычислено ли значение атрибута }
 a: Boolean;
 
 { нужно ли знать значение этого атрибута }
 b: Boolean;
 
 { является ли атрибут выходным }
 c: Boolean;
 
 { сколько раз обрабатывался данный узел }
 n: integer;
 
 { указатель на функцию задействован }
 f: Boolean;
 
 { ребра графа, ведущие из этого узла }
 edges: array[1..MaxNumArguments] of ColEdge;
 
 { массив указателей на атрибуты, которые явно зависят от данного атрибута }
 dep_attrs: array [1..MaxNumAttributes*(2*MaxNumSuccessors+1)] of PAttribute;
 
 { конструктор объекта}
 constructor Create;
 
 end;
 
 { вершина дерева вывода }
 TNode = object
 
 { указатели на атрибуты данной вершины }
 Attributes: array[1..MaxNumAttributes] of PAttribute;
 
 { указатель на вершину-предок }
 parent: PNode;
 
 { указатели на вершины-потомки }
 successors: array[1..MaxNumSuccessors] of PNode;
 
 { массив, показывающий, по каким ребрам вниз уже ходили }
 passed: array[1..MaxNumSuccessors] of Boolean;
 
 { рассматривалась ли уже эта вершина }
 examined: Boolean;
 
 { терминальная или нет }
 terminal: Boolean;
 
 { конструктор объекта}
 constructor Create;
 
 { сколько на самом деле атрибутов у вершины }
 function NumAttrs: integer; virtual;
 
 { сколько на самом деле потомков у этой вершины }
 function NumSuccesrs: integer; virtual;
 
 { процедура, вычисляющая атрибут номер j }
 procedure Evaluate(j: integer); virtual;
 
 end;
 
Implementation
 
constructor TAttribute.Create;
begin {...} end;
 
constructor TNode.Create;
begin {...} end;
 
function TNode.NumAttrs;
begin {...} end;
 
function TNode.NumSuccesrs;
begin {...} end;
 
procedure TNode.Evaluate(j : integer);
begin {...} end;
 
end.
 
{----------------}
 
Unit AttEval;
 
{ процедуры, реализующие алгоритм; названия заменены на английские }
 
interface
uses TrTyp;
 
procedure att_eval(var UserTree: TNode);
 
implementation
 
procedure del_node(var x: TAttribute);
 var z : Tattribute;
 i,j,l1 : integer;
 NoBlueGreenEdges : Boolean;
 begin
 if ( ( x.a ) and ( not x.c ) and ( x.n = 0 ) ) then
 begin
 { проверка того, что в узел x не входят синие и зеленые дуги }
 NoBlueGreenEdges := True;
 for i := 1 to MaxNumAttributes*(2*MaxNumSuccessors+1) do
 begin
 if x.dep_attrs[i] <> NIL then z:= x.dep_attrs[i]^;
 for l1 := 1 to z.numargs do
 if ( z.edges[l1].target = @x )
 and
 ( ( z.edges[l1].color = Blue)
 or
 ( z.edges[l1].color = Green) )
 then
 NoBlueGreenEdges := False;
 end {i};
 if NoBlueGreenEdges then x.drawn := False;
 end {if};
 end;
 
procedure del_graph(var y: TAttribute);
 var x,z : Tattribute;
 i,j,l,l1 : integer;
 NoEdges : Boolean;
 begin
 if ( ( y.n = 0 ) and ( not y.c ) ) then
 begin
 { проверка того, что в узел x не входят никакие дуги }
 NoEdges := True;
 for i := 1 to MaxNumAttributes*(2*MaxNumSuccessors+1) do
 begin
 if y.dep_attrs[i] <> NIL then z := y.dep_attrs[i]^;
 for l1 := 1 to z.numargs do
 if ( z.edges[l1].target = @x )
 and
 ( z.edges[l1].color <> Black)
 then
  NoEdges := False;
 end {i};
 if NoEdges then
 begin
 for l := 1 to y.numargs do
 if y.edges[l].color = Blue then
 begin
 x := y.edges[l].target^;
 y.edges[l].color := Black;
  Del_Graph(x); {рекурсия}
 end {l};
 y.drawn := False;
 end {if}
 end {if}
 end {del_graph};
 
procedure Higher(var y: TAttribute);
 
 var z : Tattribute;
 i,l,l1,j1 : integer;
 no_red_edges : Boolean;
 begin
 {h1}
 if y.a then
 begin
 for l:= 1 to MaxNumAttributes*(2*MaxNumSuccessors+1) do
 begin
 if y.dep_attrs[l] <> NIL then z:= y.dep_attrs[l]^;
 for l1 := 1 to z.numargs do
 if ( z.edges[l1].target = @y ) and ( z.edges[l1].color = Red) then
 begin
 {h1.1}
 z.edges[l1].color := Green;
 {h1.2}
 no_red_edges := True;
 for j1 := 1 to z.numargs do
 if z.edges[j1].color = Red then no_red_edges := False;
 if no_red_edges then
 begin
 z.nod^.Evaluate(z.its_num);
 z.a := true;
 for j1 := 1 to z.numargs do
 begin
  z.edges[j1].color := Black;
 del_node(z.edges[j1].target^);
 end {j1}
 end;
 {h1.3}
 Higher(z); { рекурсия }
 end {l1-if};
 end {l}
 end {if y.a=1};
 end;
 
 
procedure Lower(var y: TAttribute);
 var x : Tattribute;
 i : integer;
 no_red_edges : Boolean;
 label low_1_3;
 begin
 {l1}
 for i:= 1 to y.NumArgs do
 if y.edges[i].color = Blue then
 begin
  x := y.edges[i].target^;
 {l1.1}
 if x.b = false then x.b := true else goto low_1_3;
 {l1.2}
 if (x.f AND ( x.a = false )) then Lower(x); { рекурсия }
 {l1.3}
 low_1_3:
 if x.a = true then
 y.edges[i].color := Green else y.edges[i].color := Red;
 end {i-if};
 {l2}
 no_red_edges := True;
 for i:= 1 to y.NumArgs do
 if y.edges[i].color = Red then no_red_edges := False;
 if no_red_edges then
 begin
 y.nod^.Evaluate(y.its_num);
 y.a := false;
 for i:= 1 to y.NumArgs do
 begin
 y.edges[i].color := Black;
 Del_Node(y.edges[i].target^);
 end;
 end;
 end {lower};
 
 
procedure dependancy (var y: TAttribute);
 var i : integer;
 label finish;
 begin
 {d1}
 y.f := true;
 {d2}
 for i:= 1 to y.NumArgs do
 y.edges[i].color := Blue;
 {d3}
 if y.b = false then goto finish;
 {d4}
 Lower(y);
 {d5}
 Higher(y);
 {}
 finish:
 end {dependancy};
 
 
 
procedure branching (w: TNode);
 var w1,w2 : TNode;
 i,j,l,j1,l1 : integer;
 x1 : TAttribute;
 begin
 { b1 }
 if not w.examined then
 begin
 { в граф добавляются узлы, соответствующие атрибутам вершины U0 }
 for j:= 1 to w.NumAttrs do
 begin
 w.Attributes[j]^.drawn := true;
 w.Attributes[j]^.f:= False;
 w.Attributes[j]^.a:= False;
 if w.Attributes[j]^.out then
 { выходной атрибут }
 begin
 w.Attributes[j]^.b:= true;
 w.Attributes[j]^.c:= true;
 end
 else
 { невыходной атрибут }
 begin
 w.Attributes[j]^.b:= false;
 w.Attributes[j]^.c:= false;
 end;
 {}
 if w.terminal then w.Attributes[j]^.n:= 1 else w.Attributes[j]^.n:= 2;
 end {j};
 w.examined := true;
 end {if};
 
 { в граф добавляются узлы, соответствующие атрибутам вершин U1-Uk }
 for i := 1 to w.NumSuccesrs do
 begin
 w1:=w.successors[i]^;
 if not w1.examined then
 begin
 for j:= 1 to w1.NumAttrs do
 begin
 w1.Attributes[j]^.drawn := true;
 w1.Attributes[j]^.f:= false;
 w1.Attributes[j]^.a:= false;
 if w1.Attributes[j]^.out then
 { выходной атрибут }
 begin
 w1.Attributes[j]^.b:= true;
 w1.Attributes[j]^.c:= true;
 end
 else
  { невыходной атрибут }
 begin
 w1.Attributes[j]^.b:= false;
 w1.Attributes[j]^.c:= false;
 end;
 {}
 if w1.terminal then w1.Attributes[j]^.n:= 1 else w1.Attributes[j]^.n:= 2;
 end {j};
 w1.examined := true;
 end {if};
 end {i};
 
 {b3/2 заполнение массивов edges}
 {верхняя вершина}
 for j:= 1 to w.NumAttrs do
 if w.Attributes[j]^.cat = Synth then
 for l := 1 to w.Attributes[j]^.NumArgs do
 if w.Attributes[j]^.arguments[l].NoNode = 0 {аргумент лежит в верхней вершине}
 then begin
 w.Attributes[j]^.edges[l].target := w.Attributes[w.Attributes[j]^.arguments[l].NoAtr];
  w.Attributes[j]^.edges[l].color := Black;
 { обратная ссылка }
 x1 := w.Attributes[w.Attributes[j]^.arguments[l].NoAtr]^;
 l1 := 0;
 repeat
  l1 := l1 +1
 until x1.dep_attrs[l1] = NIL;
 x1.dep_attrs[l1] := w.Attributes[j];
 {}
 end {then}
 else {аргумент лежит в одной из нижних вершин}
  begin
 w1:=w.successors[w.Attributes[j]^.arguments[l].NoNode]^;
 w.Attributes[j]^.edges[l].target := w1.Attributes[w.Attributes[j]^.arguments[l].NoAtr];
 w.Attributes[j]^.edges[l].color := Black;
  { обратная ссылка }
 x1 := w.Attributes[w.Attributes[j]^.arguments[l].NoAtr]^;
 l1 := 0;
 repeat
 l1 := l1 +1
 until x1.dep_attrs[l1] = NIL;
 x1.dep_attrs[l1] := w.Attributes[j];
 {}
 end {else};
 {остальные вершины}
 for i := 1 to w.NumSuccesrs do
 begin
 w1:=w.successors[i]^;
 for j:= 1 to w1.NumAttrs do
 if w1.Attributes[j]^.cat = Inh then
 for l := 1 to w1.Attributes[j]^.NumArgs do
 if w1.Attributes[j]^.arguments[l].NoNode = 0 {аргумент лежит в верхней вершине}
 then begin
 w1.Attributes[j]^.edges[l].target := w.Attributes[w1.Attributes[j]^.arguments[l].NoAtr];
 w1.Attributes[j]^.edges[l].color := Black;
 { обратная ссылка }
 x1 := w.Attributes[w1.Attributes[j]^.arguments[l].NoAtr]^;
 l1 := 0;
 repeat
 l1 := l1 +1
 until x1.dep_attrs[l1] = NIL;
 x1.dep_attrs[l1] := w1.Attributes[j];
  {}
 end {then}
 else {аргумент лежит в одной из нижних вершин}
 begin
 w2:=w.successors[w.Attributes[j]^.arguments[l].NoNode]^;
 w1.Attributes[j]^.edges[l].target := w2.Attributes[w1.Attributes[j]^.arguments[l].NoAtr];
 w1.Attributes[j]^.edges[l].color := Black;
 { обратная ссылка }
 x1 := w2.Attributes[w1.Attributes[j]^.arguments[l].NoAtr]^;
  l1 := 0;
 repeat
 l1 := l1 +1
 until x1.dep_attrs[l1] = NIL;
 x1.dep_attrs[l1] := w1.Attributes[j];
 {}
 end {else};
 end {i};
 
 {b2}
 for j:= 1 to w.NumAttrs do
 begin
 if w.Attributes[j]^.cat = Synth then
 dependancy(w.Attributes[j]^);
 end {j};
 for i := 1 to w.NumSuccesrs do
 begin
 w1:=w.successors[i]^;
  for j:= 1 to w1.NumAttrs do
 begin
 if w1.Attributes[j]^.cat = Inh then
 dependancy(w1.Attributes[j]^);
 end {j};
 end {i};
 {b3}
 for j:= 1 to w.NumAttrs do
 w.Attributes[j]^.n := w.Attributes[j]^.n -1;
 for i := 1 to w.NumSuccesrs do
 begin
 w1:=w.successors[i]^;
 for j:= 1 to w1.NumAttrs do
 w1.Attributes[j]^.n := w1.Attributes[j]^.n -1;
 end {i};
 {b4}
 for j:= 1 to w.NumAttrs do
 Del_Graph(w.Attributes[j]^);
 for i := 1 to w.NumSuccesrs do
 begin
 w1:=w.successors[i]^;
 for j:= 1 to w1.NumAttrs do
 Del_Graph(w1.Attributes[j]^);
 end {i};
 
 end;
 
 
procedure att_eval(var UserTree: TNode);
 
{ обход дерева вывода и вычисление атрибутов }
 
var w,w1 : TNode;
 i : integer;
begin
 w := UserTree;
 repeat
 if NOT w.examined then begin
 branching(w);
 w.examined := true;
 end;
 if w.passed[w.NumSuccesrs] then
 { наверх }
 begin
 w1:= w.parent^;
 w:= w1;
 end {then}
 else
 { вниз }
 begin
 i := 1;
 while w.passed[i] do
 i:= i+1;
 w1:=w.successors[i]^;
 w.passed[i] := true;
  w:= w1;
 end {else};
 until w.parent = NIL;
end {att_eval};
end.
 

---

В.М.Курочкин

Быстрый метод лексического анализа

Рассматривается быстрый метод лексического анализа, работающий по принципу табличного автомата. Алгоритм анализа затрачивает минимальное количество тактов на обработку каждого входного символа и не предусматривает никаких поисков в таблицах. За счет склеивания совпадающих лексем достигается максимальная экономия в составляемых таблицах .

Хотя организация лексического анализа в принципе довольно проста, это тем не менее относительно трудоемкий и медленный процесс (если сравнивать его, например, с однопроходным синтаксическим анализом в LL- или LR-грамматиках). Объясняется это тем, что, во-первых, как правило, сам лексический анализ объединяется и проводится одновременно с рядом других действий - заполнением таблицы индентификаторов и констант, поиском в этих таблицах (с помощью функции хеширования или без нее), переводом числовых констант из системы записи их на входном языке в двоичную систему, экономией констант и идентификаторов в соответствующих таблицах и т.п., а во-вторых, длина входного файла для лексического анализатора существенно больше, чем длина файла из лексем для синтаксического анализа.

Предлагаемый здесь метод лексического анализа основан на использовании автомата, работа которого управляется двумерной таблицей. Каждый встретившийся во входном тексте символ определяет вход в таблицу, и тем самым, как правило, один такт работы автомата. Более или менее при любой системе команд компьютера выделение клетки в двумерной таблице требует одного и того же, причем небольшого (2-5) числа операций машины. К этому и сводится, в основном, работа, выполняемая машиной при лексическом анализе текста программы. Число столбцов в таблице в процессе анализа не меняется и равно числу символов входного языка (можно считать его равным 256). Число строк таблицы автомата, правда, может возрастать, и при обработке больших программ может достигать нескольких тысяч. Более аккуратно - оно равно числу разных начал лексем в программе, и таким образом, по сравнению со стандартными методами, может увеличиться не более чем в число раз, равное максимальной длине используемых в программе идентификаторов. При этом время обработки одной лексемы зависит только от ее длины и не зависит от размера программы. Возможны два варианта организации и использования таблицы, в принципе не очень сильно отличающиеся один от другого. В одном из вариантов каждое появление нового, не встречавшегося до этого начала лексемы вызывает добавление в таблицу новой строки с некоторым начальным стандартным заполнением клеток этой строки. В другом варианте в самом начале работы анализатора для таблицы выделяется достаточно места в памяти ("с избытком") и производится ее стандартное заполнение. Если не учитывать времени "роста" таблицы и времен (необходимых и одинаковых при любом методе лексического анализа) для запоминания идентификаторов и (перевода и) запоминания констант, то время обработки всех встречающихся в дальнейшем, и, как правило, совпадающих с уже встретившимися ранее впервые лексем будет линейно зависеть от длины самих лексем и не будет зависеть от размера таблицы. При этом автоматически будет производится слияние совпадающих лексем - как идентификаторов, так и констант, независимо от их типа, например совпадающих по написанию строковых констант, чего не делает большинство из существующих лексических анализаторов.

Начальное заполнение таблицы автомата. Перед работой лексического анализатора производится стандартная для данного входного языка настройка автомата в соответствии с перечисленным в описании лексики языка набором служебных слов. К служебным словам целесообразно отнести (или по крайней мере чисто формально так же с ними работать) многосимвольные ограничители, такие как ** , := , >= b и т.п. Для каждого начала служебного слова в таблице автомата отводится строка, а в клетке, соответствующей символу возможного продолжения этого начала, пишется номер строки продолжения и ключ "продолжить чтение" (о ключах будет сказано ниже). Так, если номера строк, соответствующих началам e, el, els, else, elsi, elsif, en, end, ent, entr, entry, ex, exi, exit получили номера 2,3,4,5,6,7,12,13,14,15,16,21,22,23, то в клетках l, n, x строки 2 пишутся номера 3,12,21; в клетке s строки 3 - номер 4; в клетках e , i строки 4 - номера 5,6; в клетке f строки 6 - 7; в клетках d , t строки 12 - 13,14 и т.д.; в клетке t строки 22 - 23. В клетках, соответствующих ограничителю, например + , > , "пробел" и т.п., означающих конец служебного слова, пишется признак конца лексемы и ставится номер соответствующей лексемы - служебного слова. Для языка Ada , который имеет 63 служежбных слова и на котором моделировался описываемый метод, построенная таким образом таблица содержит 230 строк.

Регулярная работа автомата. Программа лексического анализа считывает из входного потока символ за символом. Считывание одного символа вызывает выполнение одного такта работы автомата, определяемого содержимым одной клетки таблицы автомата. Нужная клетка находится на пересечении текущей строки таблицы авомата и столбца, соответствующего считанному символу. В этой клетке находится ключ, определяющий вид работы автомата, и, возможно, номер строки одной из таблиц (с прямым входом!), содержащих необходимую дополнительную информацию. Возможные значения ключей:

- ошибочный символ во входном потоке (дополнительная информация - адрес программы реакции на соответствующую ошибку);

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

- конец служебного слова (дополнительная информация - номер служебного слова, которые предварительно были пронумерованы каким-либо произвольным способом; в выходной поток посылается тип лексемы, равный номеру служебного слова);

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

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

Если необходимо по синтаксису различать константы различных типов, например real, integer и др., то соответствующие сведения содержатся в ключе; со строковыми константами действуют совершенно аналогично. Все числовые константы, идентификаторы, строки и т.п. можно помещать в объединенную таблицу, а можно по тем или иным соображениям их разъединить. В любом случае номер лексемы означает прямой адрес этой лексемы в соответствующей таблице, а тип (т.е. ключ) определит, в какой именно таблице находится лексема. Возможны и небольшие вариации в организации таблицы автомата (например, можно не помещать в таблицу строковые константы, тем самым не производя слияния совпадающих строковых констант и экономя на размерах таблицы). Необходимо лишь сохранять основной принцип: каждый считанный из входного потока символ вызывает выполнение одного такта работы автомата, причем никаких поисков в таблицах не производится и нужная информация получается прямым входом в соответствующие таблицы.

Таким образом, предлагаемый метод позволяет значительно сократить время выполнения всех этапов лексического анализа, связанных с обработкой таблиц, что особенно существенно для программ большого объема.

---

Реализация алгоритма генерации лексического анализатора (Паскаль 7.0)
Комментарий к программе.
Здесь идут подряд три файла: собственно программа, затем файл res_words.txt с зарезервированными словами языка Паскаль, затем файл delim.txt с ограничителями. При работе нужно выставить в опциях компилятора Range Checking.

 
uses crt, DOS;
type
{type of the lexema}
{pointer to row}
prow = ^row;
{row of the table}
row = record
 lextype : string; {type of the lexema}
 n : word; {number of lexema of this type (if defined)}
 contents : string;
 nextrow : array [0..255] of prow;
 end;
{sets jf symbols}
sym_set = set of char;
 
var
 F: Text;
 s: string;
 spec_symbols, letters, ciphers : sym_set;
 pcurr_row, pinit_row, pnew_row : prow;
 i,j, counter_rw,counter_del,counter_ident,counter_const : integer;
 ch : char;
label
 next_symbol,next_line;
 
begin
 spec_symbols := [' ','+','-','*','/','=',',',':',';','<','>','[',']','(',')','{','}','^','@','$','#'];
 letters := ['a'..'z'];
 ciphers := ['0'..'9'];
 
 
{initial row}
 new (pcurr_row);
 pinit_row := pcurr_row;
 pcurr_row^.lextype := '';
 pcurr_row^.contents := '';
 for i := 0 to 32 do
 pcurr_row^.nextrow[i] := pinit_row;
 for i := 33 to 255 do
 pcurr_row^.nextrow[i] := NIL;
 
{reading the list of reserved words}
 assign(F,'c:\tpwork\reswords.txt');
 reset(F);
 counter_rw:=0;
 repeat
 counter_rw := counter_rw + 1;
 pcurr_row := pinit_row;
 readln(F,s);
 writeln(s,' ',length(s));
 for j := 1 to length(s) do
 begin
 if pcurr_row^.nextrow[ord(s[j])] = NIL
 then
 begin
 new (pnew_row);
 pnew_row^.lextype := '';
 for i := 33 to 255 do
 pnew_row^.nextrow[i] := NIL;
 pcurr_row^.nextrow[ord(s[j])] := pnew_row;
 pnew_row^.contents :=pcurr_row^.contents + s[j];
 end
 else
 begin
 pnew_row := pcurr_row^.nextrow[ord(s[j])];
 end;
 pcurr_row := pnew_row;
 {writeln (j,s[j]);}
 end {j};
 writeln(pcurr_row^.contents);
 pcurr_row^.lextype := 'reserv_word';
 pcurr_row^.n := counter_rw;
 until EOF(F);
 
{reading the list of delimiters}
 assign(F,'c:\tpwork\delim.txt');
 reset(F);
 counter_del:=0;
 repeat
 counter_del := counter_del + 1;
 pcurr_row := pinit_row;
 readln(F,s);
 writeln(s,' ',length(s));
 for j := 1 to length(s) do
 begin
 if pcurr_row^.nextrow[ord(s[j])] = NIL
 then
 begin
 new (pnew_row);
 pnew_row^.lextype := '';
 for i := 33 to 255 do
 pnew_row^.nextrow[i] := NIL;
 pcurr_row^.nextrow[ord(s[j])] := pnew_row;
 pnew_row^.contents :=pcurr_row^.contents + s[j];
  end
 else
 begin
 pnew_row := pcurr_row^.nextrow[ord(s[j])];
 end;
 pcurr_row := pnew_row;
 {writeln (j,s[j]);}
 end {j};
 writeln(pcurr_row^.contents);
 pcurr_row^.lextype := 'delimiter';
 pcurr_row^.n := counter_del;
 until EOF(F);
 
 writeln('reading the text of the program:');
{reading the text of the program}
 assign(F,'c:\tpwork\program.txt');
 reset(F);
 counter_ident:=0;
 counter_const:=0;
 repeat
  pcurr_row := pinit_row;
 readln(F,s);
 writeln('next line of the text: ',s,' length: ',length(s));
 for j := 1 to length(s) do
 begin
 
 writeln('s[j],ord(s[j]):',s[j],ord(s[j]));
 
 if pcurr_row^.nextrow[ord(s[j])] <> NIL {continuing already known lexem:}
 then
 begin
 pnew_row := pcurr_row^.nextrow[ord(s[j])];
 writeln('continuing already known lexem');
 writeln('contents:',pcurr_row^.contents,'|');
 pcurr_row := pnew_row;
 end
 
 else {pointer is empty: end of lexem or beginning or continuaton of a new lexem:}
 
 begin
 writeln('pointer is empty: end of a lexem or beginning or continuation of a new lexem');
 writeln('contents:',pcurr_row^.contents,'|');
 
 {end of res_word:}
 if pcurr_row^.lextype = 'reserv_word' then
 begin
 writeln('end of res_word');
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_symbol;
 end;
 
 {end of delimiter:}
 if pcurr_row^.lextype = 'delimiter' then
 begin
  writeln('end of delimiter');
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_symbol;
 end;
 
 {end of known identifyer:}
 if (pcurr_row^.lextype = 'identifyer')
 and (not ( (s[j] in (letters + ciphers) ) or (s[j] = #39) ))
 then
 begin
 writeln('end of known identifyer');
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_symbol;
 end;
 
 
 {beginning of new identifyer:}
 if (pcurr_row^.contents = '') and (s[j] in letters ) then
 begin
  writeln('beginning of new identifyer');
 new (pnew_row);
 pnew_row^.lextype := '';
 for i := 0 to 255 do
 pnew_row^.nextrow[i] := NIL;
 pcurr_row^.nextrow[ord(s[j])] := pnew_row;
 pnew_row^.contents :=pcurr_row^.contents + s[j];
 pcurr_row := pnew_row;
 goto next_symbol;
 end;
 
 {continuation of new identifyer:}
 if (pcurr_row^.contents[1] in letters) and (s[j] in (letters + ciphers)) then
 begin
 writeln('continuation of new identifyer');
 writeln ('contents:',pcurr_row^.contents,'|');
 new (pnew_row);
  pnew_row^.lextype := '';
 for i := 0 to 255 do
 pnew_row^.nextrow[i] := NIL;
 pcurr_row^.nextrow[ord(s[j])] := pnew_row;
 pnew_row^.contents :=pcurr_row^.contents + s[j];
 pcurr_row := pnew_row;
 goto next_symbol;
 end;
 
 {end of new identifyer:}
 if (pcurr_row^.contents[1] in letters) and (s[j] in spec_symbols) then
 begin
 writeln('end of new identifyer');
 counter_ident := counter_ident + 1 ;
 pcurr_row^.lextype := 'identifyer';
 pcurr_row^.n := counter_ident;
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
  pcurr_row := pinit_row;
 goto next_symbol;
 end;
 
 
 {end of known constant:}
 if ( pcurr_row^.lextype = 'constant' )
 and (not ( (s[j] in (letters + ciphers) ) or (s[j] = #39) ))
 then
 begin
 writeln('end of known constant');
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_symbol;
 end;
 
 {beginning of new constant:}
 if (pcurr_row^.contents = '') and ( (s[j] in (letters + ciphers) ) or (s[j] = #39) ) then
 begin
 writeln('beginning of new constant');
 new (pnew_row);
  pnew_row^.lextype := '';
 for i := 0 to 255 do
 pnew_row^.nextrow[i] := NIL;
 pcurr_row^.nextrow[ord(s[j])] := pnew_row;
 pnew_row^.contents :=pcurr_row^.contents + s[j];
  pcurr_row := pnew_row;
 goto next_symbol;
 end;
 
 
 {continuation of new constant:}
 if ( (pcurr_row^.contents[1] in ciphers) or (pcurr_row^.contents[1] = #39) )
 and ( (s[j] in (letters + ciphers) ) or (s[j] = #39) ) then
 begin
 writeln('continuation of new constant');
 new (pnew_row);
 pnew_row^.lextype := '';
 for i := 0 to 255 do
  pnew_row^.nextrow[i] := NIL;
 pcurr_row^.nextrow[ord(s[j])] := pnew_row;
 pnew_row^.contents :=pcurr_row^.contents + s[j];
 pcurr_row := pnew_row;
 writeln('special output: contents:',pcurr_row^.contents,'|');
 goto next_symbol;
 end;
 
 {end of new constant:}
 if ( (pcurr_row^.contents[1] in ciphers) or (pcurr_row^.contents[1] = #39) )
 and (s[j] in spec_symbols) then
  begin
 writeln('end of new constant');
 counter_const := counter_const + 1 ;
 pcurr_row^.lextype := 'constant';
 pcurr_row^.n := counter_const;
 writeln (pcurr_row^.lextype,pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_symbol;
 end;
 end;
 next_symbol:
 ch := ReadKey;
 end {j};
 {actions at the end of each line of the text}
 {end of res_word:}
 if pcurr_row^.lextype = 'reserv_word' then
 begin
 writeln('end of res_word');
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_line;
 end;
 
 {end of delimiter:}
 if pcurr_row^.lextype = 'delimiter' then
 begin
 writeln('end of delimiter');
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_line;
 end;
 
 {end of known identifyer:}
 if pcurr_row^.lextype = 'identifyer' then
 begin
  writeln('end of known identifyer');
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_line;
 end;
 
 {end of known constant:}
 if pcurr_row^.lextype = 'constant' then
 begin
 writeln('end of known constant');
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_line;
 end;
 
 {end of new identifyer:}
 if (pcurr_row^.contents[1] in letters) then
 begin
 writeln('end of new identifyer');
 counter_ident := counter_ident + 1 ;
 pcurr_row^.lextype := 'identifyer';
 pcurr_row^.n := counter_ident;
 writeln (pcurr_row^.lextype,' ',pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_line;
 end;
 
 {end of new constant:}
 if ( (pcurr_row^.contents[1] in ciphers) or (pcurr_row^.contents[1] = #39) )
 then
 begin
 writeln('end of new constant');
 counter_const := counter_const + 1 ;
 pcurr_row^.lextype := 'constant';
 pcurr_row^.n := counter_const;
 writeln (pcurr_row^.lextype,pcurr_row^.n);
 pcurr_row := pinit_row;
 goto next_line;
 end;
 
  next_line:
 
 until EOF(F);
end.

Файл с зарезервированными словами языка Турбо-Паскаль:

 
absolute
and
array
begin
case
const
div
do
downto
else
end
external
file
for
forward
function
goto
if
implementation
in
inline
interface
interrupt
label
mod
nil
not
of
or
packed
procedure
program
record
repeat
set
shl
shr
string
then
to
type
unit
until
uses
var
while
with
xor
 

Файл - список ограничителей языка Паскаль:

 
+
-
*
/
=
,
.
:
;
< 
> 
[
]
(
)
{
}
^
@
$
#
<> 
<=
>=
:=
(*
*)
(.
.)

---

Работа была выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты 93-12-573 и 96-01-01757).

---