Восходящие методы анализа. Свертка-перенос
Восходящие методы синтаксического анализа состоят в том, что в цепочке (промежуточной или терминальной) ищется правая часть очередного правила, которое должно быть заменено своим нетерминалом. Очевидно, что не любая правая часть правила может быть свернута в любое время. Если посмотреть на дерево синтаксического разбора, то нетрудно заметить, что свертку необходимо производить регулярно, путем обхода дерева слева направо.
.
Z
|
E
|
T
-------------
T * F
| --------
F ( E )
-----
E + T
| |
T F
|
F
В данном дереве необходимо выполнить свертку по самому левому правилу T::=F в цепочке. Правая часть такого правила называется ОСНОВОЙ. Таким образом, основа - это полная правая часть первого правила при просмотре цепочки слева направо. Найденная в цепочке основа должна быть заменена на нетерминал из левой части соответствующего правила. Для более полного понимания принципа приведем последовательность основ цепочек при выполнении такого процесса свертки.
.
F * (F + F)
---
T * (F + F)
---
T * (T + F)
---
T * (E + F)
---
T * (E + T)
-----
T * (E)
---
T * F
-----
T
---
E
---
Z
---
Способ нахождения основы цепочки реализован в методе восходящего разбора "свертка-перенос":
В процессе анализа используется магазинный автомат (КА со стеком);
На каждом шаге работы автомата сравнивается пара символов - текущий символ входной цепочки (I) и текущий символ в стеке (М). По результату сравнения возможны два действия:
Перенос терминального символа из строки в стек: PUSH((I), NEXT(I) - в соответствии с принятыми для МА обозначениями.
Свертка правой части правила, которое в данный момент находится в стеке.
T:T/F","T:F","F:i","F:c","F:(E)",NULL };
char TS[]= "+-*/()ic#" ;
char NTS[]= "+-*/()ic#FTEZ" ;
char s[100]; int ns;
char m[100]; int sp;
Двумерный массив определяет действия МА на каждую пару сочетаний символа в стеке и во входной цепочке: 0 - ошибка, 1-перенос, 2-свертка, 3-успешный разбор.
int TBL[14][10]={
/* + - * / ( ) i c # err */
/* + */ { 0,0,0,0,1,0,1,1,0,0 },
/* - */ { 0,0,0,0,1,0,1,1,0,0 },
/* * */ { 0,0,0,0,1,0,1,1,0,0 },
/* / */ { 0,0,0,0,1,0,1,1,0,0 },
/* ( */ { 0,0,0,0,1,0,1,1,0,0 },
/* ) */ { 2,2,2,2,0,2,0,0,2,0 },
/* i */ { 2,2,2,2,0,2,0,0,2,0 },
/* c */ { 2,2,2,2,0,2,0,0,2,0 },
/* # */ { 0,0,0,0,1,0,1,1,0,0 },
/* F */ { 2,2,2,2,0,2,0,0,2,0 },
/* T */ { 2,2,1,1,0,2,0,0,2,0 },
/* E */ { 1,1,0,0,0,1,0,0,2,0 },
/* Z */ { 0,0,0,0,0,0,0,0,3,0 },
/*err*/ { 0,0,0,0,0,0,0,0,0,0 },
};
Вспомогательная функция STS определяет номер символа в строке терминальных символов или всех символов грамматики
int STS(char c,char T[]) {. . .}
Функция main буквально повторяет приведенный выше алгоритм разбора. Для каждой пары символов в строке и в вершине стека вызывает действие, определенное для них в таблице.
void main()
{ int i,j,stop;
printf("Строка:"); gets(s); strcat(s,"#");
ns=0; sp=0; m[0]='#'; m[1]='\0';
nts=strlen(TS); stop=0;
while(!stop)
{ i=TBL[ STS(m[sp],NTS) ][ STS(s[ns],TS) ];
switch (i) {
case 1: sp++; m[sp]=s[ns]; m[sp+1]='\0';
ns++; break; // Перенос
case 2: if (TESTGR()==0) // Свертка
stop++; break;
case 3: stop++; break;
default: stop++; break;
}}}
Функция TESTGR реализует самый общий принцип свертки: она просматривает список правил и ищет первое из них, которое содержит в вершине стека свою правую часть, после чего заменяет его на левую.
То есть последовательность расположения правил с одинаковой правой частью в списке может влиять на правильность синтаксического разбора. А именно: если есть два правило с одинаковым окончанием правой части, то более длинное должно находиться в начале списка.
int TESTGR()
{ char *ss,*q; int n,j;
for (n=0; GR[n] !=NULL; n++) // Поиск правила
{ for (q=ss=GR[n]+2; *ss !='\0'; ss++);
ss--;
for(j=sp; (ss>=q) && (m[j]==*ss); j--,ss--);
if (q== ss+1) // Свертка
{ j++; sp=j; m[sp]=*GR[n];
m[sp+1]='\0'; return(1); }
}
return (0);}
4. Семантический анализ
Семантический анализ является наименее формализуемой частью процесса трансляции, поскольку касается “смысла” тех конструкций языка, которые анализируются на этапах лексического и синтаксического анализа. Если же подходить к этому процессу с точки зрения “здравого смысла”, то транслятор должен построить в процессе трансляции в памяти некоторую структуру данных, в которой зафиксировать все смысловые (семантические) взаимоотношения между объектами программы. Обычно объектами программы являются типы, переменные и функции (процедуры), которые обозначаются именами (идентификаторами). Для них уже на этапе лексического анализа может быть составлена таблица, которая на этапе семантического анализа дополняется данными о семантике объектов. Отсюда вырисовывается общая схема взаимодействия фаз транслятора:
- Обычно транслятор создает несколько семантических таблиц, по видам используемых в языке объектов, поскольку содержание их может быть в принципе различным. Например, в Си-компиляторе имеет смысл заводить таблицы типов, локальных и глобальных переменных, функций. Таблицы эти заполняются семантическими процедурами при свертывании соответствующих правил. Например, при свертывании определения переменной ее имя должно заноситься в таблицу локальных или глобальных имен;
- на этапе лексического анализа при обнаружении очередного идентификатора его значение (строка символов, имя) либо непосредственно сопровождает распознанную лексему, либо помещается в таблицу со ссылкой на нее в той же лексеме.
В обоих случаях значение лексемы (имя) сопровождает ее на этапе синтаксического анализа, где лексема выступает как терминальный символ и передается далее фазе семантического анализа.
- в процессе синтаксического анализа, при “свертывании” правила, в котором в качестве терминалов фигурируют имена, вызывается семантическая процедура, соответствующая этому правилу. Она должна получить ссылки на эти имена из соответствующих лексем;
- семантическая процедура по ссылкам на имена определяет, является ли операция, заданная правилом, допустимой для семантики этих имен. Кроме того, семантическая процедура может создать новые записи в таблицах, изменить их содержание, произвести поиск и т.д.. Поскольку любое правило при свертывании приводится к нетерминалу, стоящему в левой части, а он, в свою очередь, включается в другие, вышележащие правила, то семантическая процедура должна поставить ему в соответствие также некоторую семантику (смысл). Это делается также путем возвращения ссылки на элемент таблицы.
- фаза генерации кода или интерпретации обычно выполняется в виде такой же процедуры, как семантический анализ, в тех же самых условиях - в момент “свертки” правой части правила.
- элементы семантических таблиц в свою очередь могут быть связаны с некоторыми динамическими структурами данных, которые отражают внутреннюю семантику хранимых объектов. Это могут быть списки, массивы, деревья. В целом образуется некоторая семантическая сеть, по структуре которой семантические процедуры и производят анализ тех или иных частей программы.
