shpory_spo 4йкурс

46 Нисходящий и восходящий синтаксические анализы.

Общий процесс трансляции: лексический анализ -> синтаксический и семантич. анализ -> генерация вых. кода.

Синтаксический разбор - построение дерева синтаксического разбора можно производить как сверху вниз - от начального нетерминала к предложению языка, так и снизу вверх - от предложения к начальному символу:

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

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

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

47 Автоматы со стековой памятью

Общий процесс трансляции это рис1 : лексический анализ -> синтаксический и семантич. анализ -> генерация вых. кода.

это рис2. автомат:

послед-ти символов вх. алфавита -> автомат конечный -> послед-ти символов вых. алфавита

СА или МПА

- множ-во внутренних состояний (конечное)

- множ. вх. символов

- множ вых. симвлов (с символом конца текста --|)

- стековая память

- набор символов для стека (с символом дна ▼)

- управляющий закон (описывает преходы)

По внутреннему состоянию, символу вершины стека и тек. вх. символу задаются опреации:

-изменение состояния памяти

-опер. над стеком

- опер. над входом

Операции над символами: keep - держать и next - дальше.

Промежуточный этап: A->aBcdE (мал.буква - термин. символ, больш. - синтаксический символ)

Пр. нахождения правильности последов-ти скобок. Вх алфавит: ‘(’, ‘)’, ‘[’, ‘]’, --|. Управляющий закон соотносит выход (Допустить или отвергнуть [Err - дальше стирать нельзя]. допустить - ок, вых. состояния - ок или err, алфавит для стека А (открыта круглая скобка), В (открыта квадратная скобка)

	(	)	[	]	--|
A	push A next	pop next	push B next	Err	Err
B	push A next	Err	push B next	pop next	Err
▼	push A next	Err	push B next	Err	OK

стек ( [ ) ] --|

▼

▼A [ ) ] --|

▼A B ) ] --|

▼A B Err

48 Понятия множеств SELECT, FOLLOW и FIRST для построения анализаторов грамматик.

Для формальн. системы построения дерева разбора необх. описать совокупность правил, кот. диктуют в какой ситуации какую продукцию следует использовать. Эти правила для анализир-го СА д.б. воплощены в таблице управляющего закона для СА.

Вводятся спец. множ.(множ-ва выбора) SELECT(A->α)= {терминальн. символы}, кот. задают выбор конкретной продукции из продукций с общ. левой частью. FIRST(α) - множ-во терминальн. символов стоящих в начале цепочек. FOLLOW(A) - множ-во Всех терминальн. символов следующих непосредств. за A, в цепочках, выводимых из начальн. символа. Правила для множества select:

SELECT(A-> α)=FIRST(α), если α≠ε

=FOLLOW(A), если α=ε

49 Построение управляющих таблиц для автомата со стековой памятью, предназначенного для LL-грамматики. Понятие LL-грамматики.

Left LeftMost. Грамматики, для кот. таблицы анализа не имеют неоднозначно определенных входов, наз-ся LL(1). Первое L означает сканирование входа слева - направо, второе L означает, что строится левый вывод, 1 - что на каждом шаге для принятия решения исп-ся один символ непросмотренной цепочки.

50. Устранение левой рекурсии в леворекурсивной грамматике. Грамматика леворекурсивна, если в ней имеется нетерминал A такой, что существует вывод A->Aα для некоторой строки α. т.е. происходит зацикливание: A -> Aα1 | Aα2 |…| Aαn A -> β1 | β2 |…| βm A не принадлеж. First(βk) Вводится новый нетерминал: R A -> β1 R | β2 R |…| βk R R -> α1 R | α2 R |…| αn R Пр. expr expr+term {print (‘+’)} - α1 expr expr+term {print (‘-’)} - α2 R - erest; A - expr. expr  term erest erest  + term {print(+)} erest erest  - term {print(-)} eres erest   … term  factor trest trest  * factor {print(*)} trest…

51 Нисходящий анализ методом рекурсивного спуска Предикативный анализатор «рекурсивный спуск» с анализом только одного текущего символа входа. Каждому нетерминалу соотв-ет процедура в рекурсивной архитектуре. Для символа А-> xy…t … A->ab…e Proc A ( ) в некот. curtoken - входящ. символ. {Анализ вх. символа исп-ся Select выбор варианта A-> α //для A >xy…t Если х - терминал проверяем curtoken==x при == next иначе Eror Если х - нетерминал вызов процедуры ProсX Далее по остальным символам правой части <y..t>…. выход из процедуры return;} Если х - символ действия, то его выполнить void ProcExpr( ); {по текущ. входному символу однозначно выбираем expr->expr * term}

52 Особенности программной реализации предиктивного анализатора. Устранение конечной рекурсии. int lookahead; - содержит токен, в частности код символа опер.(‘+’, ‘*’…) void expr (void) {term( ); trest();} void trest( ) {if (lookahead= =’+’) {match(‘+’); term(); putchar(‘+’); erest(); return;} if (lookahead= =’-‘) { match(‘-’); term(); putchar(‘-’); erest(); return;} //select для проц. erest->ε{‘+’,’)’} if (lookahead= =’)’) return; if (lookahead= =EOT) return; //error() EOT-конец } //переделка-упрощение void erest() {int t; t=lookahead; if(t= =’+’ || t= =’-’) { match(t); term( ); putchar(t); erest();return;} else if(t= =’)’ || t= =EOT) return; else error(); } void trest( ) {int t; t=lookahead; if(t= =’*’ || t= =’/’) { match(t); factor(); putchar(t); trest();return;} else if(t= =’+’ || t= =’-’ || t= =’)’ || t= =EOT) return; //select trest->ε else error(); } void factor() {if (lookahead= =’(‘) {match(‘(‘); expr(); match(‘)’); } else if (isdigit (lookahead) || salpha (lookahead)) {printf (“%c”, lookahead) ; } //next или воспольз-ся match (lookahead);} else error(); } int main() {lookahead = getchar(); expr(); putchar(‘\n’); return0; } void match(int t) {if (lookahead= =t) lookahead=getchar(); else error(); } void error() {printf(“\n syntax error \n”); exit(1) }

53 Принципы построения средств восходящего грамматического анализа. Операции свертки и переноса. В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной строки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как "свертку" строки к начальному символу грамматики. На кажд. шаге свертки подстрока, кот. можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на кажд. шаге выбир-ся правильная подстрока, то в обратном порядке прослеживается правосторонний вывод if a<b then a:=b ▼ if (начало опер if) - спец. символ состояния характериз-ий ситуацию (прячется в стек) ▼(if) (id) (нач. опер. if) (id начал. услов.) < b then ▼(if) (id) < (нач. if с независ. услов.) b then ▼(if) (id) < (id) (нач. опер. if с услов.) then ▼(if) cond (нач. if с услов.) - свертка reduce. cond -> id < id м.быт продукцией. A -> α…β В этом формальном процессе (восход. синтаксич. анализ) вып-ся две операции : свертка и сдвиг. Рис1

54. Понятие LR-грамматик В названии LR(k) символ L означает, что разбор осущ-ся слева - направо, R - что строится правый вывод в обратном порядке, k - число входных символов, на кот. заглядывает вперед анализатор при разборе. LR(1) грамматика обычно в модификации. 1-число анализир-ых токенов в начале текущей строки (еще не проанализ-ой). LeftRightMost в промежуточных преобраз-ях заменяется самая правая часть (формир-ся из возможности - правый символ). Рис1. При реализации вместо x->AB получим y->CD. Основа: это некоторая продукция A-> α вместе с местом правой части т.е. α в некоторой промежуточной цепочке правого вывода : при обработке исходного текста.

54 LR - анализаторы. Принципы построения. В названии LR(k) символ L означает, что разбор осущ-ся слева - направо, R - что строится правый вывод в обратном порядке, k - число входных символов, на кот. заглядывает вперед анализатор при разборе. Структура LR-анализатора рис1. Он состоит из входа, выхода, магазина, управляющей программы и таблицы анализа, которая имеет две части - действий и переходов. Управляющая программа одна и та же для всех анализаторов, разные анализаторы различаются таблицами анализа. Программа анализатора читает символы из входного буфера по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S0X1S1X2S2...XmSm (Sm - верхушка магазина). Каждый Xi - символ грамматики (терминальный или нетерминальный), а Si - символ, называемый состоянием. Каждый символ состояния выражает информацию, содержащуюся в магазине ниже него, а комбинация символа состояния на верхушке магазина и текущего входного символа используется для индексации таблицы анализа и определяет решение о сдвиге или свертке. В реализации символы грамматики не обязательно должны размещаться в магазине. Однако их использование удобно для упрощения понимания поведения LR- анализатора. Таблица анализа состоит из двух частей: действия (action) и переходов (goto). Начальное состояние этого ДКА - это состояние, помещенное на верхушку магазина LR-анализатора в начале работы. Конфигурация-LR анализатора - это пара, первая компонента которой - содержимое магазина, а вторая - непросмотренный вход: (S0 X1 S1 X2 S2 ... Xm Sm, Ai Ai+1 ... An $) Эта конфигурация соответствует правой сентенциальной форме X1 X2 ... Xm Ai Ai+1 ... An Префиксы правых сентенциальных форм, которые могут появиться в магазине анализатора, называются активными префиксами. Активный префикс - это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы. Очередной шаг анализатора определяется текущим входным символом Ai и символом состояния на верхушке магазина Sm. Элемент таблицы действий action[Sm,Ai] для состояния Sm и входа Ai, может иметь одно их четырех значений: 1) shift S, сдвиг, где S - состояние, 2) reduce A->w, свертка по правилу грамматики A -> w, 3) accept, допуск, 4) error, ошибка. Конфигурации, получающиеся после каждого из четырех типов шагов, следующие 1. Если action[Sm,Ai]=shift S, то анализатор выполняет шаг сдвига, переходя в конфигурацию (S0 X1 S1 X2 S2 ... Xm Sm Ai S, Ai+1 ... An $) В магазин помещаются как входной символ Ai, так и следующее состояние S, определяемое action[Sm,Ai]. Текущим входным символом становится Ai+1. 2. Если action[Sm,Ai]=reduce A->w, то анализатор выполняет свертку, переходя в конфигурацию (S0 X1 S1 X2 S2 ... Xm-r Sm-r A S, Ai Ai+1 ... An $), где S=goto[Sm-r,A] и r - длина w, правой части правила вывода. Функция goto таблицы анализа, построенная по грамматике G, - это функция переходов детерминированного конечного автомата, распознающего активные префиксы G. Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние Sm-r. Затем анализатор помещает в магазин как A - левую часть правила вывода, так и S - содержимое таблицы goto[Sm-r,A]. На шаге свертки текущий входной символ не меняется. Для LR- анализаторов Xm-r+1 ... Xm - последовательность символов грамматики, удаляемых из магазина, всегда соответствует w - правой части правила вывода, по которому делается свертка. После осуществления шага свертки генерируется выход LR- анализатора, т.е. исполняются семантические действия, связанные с правилом, по которому делается свертка, например печатаются номера правил, по которым делается свертка. 3. Если action[Sm,Ai]=accept, то разбор завершен. 4. Если action[Sm,Ai]=error, анализатор обнаружил ошибку, то выполняются действия по диагностике и восстановлению.

55 Компиляторы компиляторов типа yacc. Структура исходного файла компилятора для них. Yet an other compiler compiler. исходный описанный яз -> yacc -> текст на С. LR-анализатор. Нобходим еще лексический анализатор. Исходный текст проги для yacc: объявление (const, опредление token) %% правила %% программа

56 Семантические действия в разделе описания правил исходного файла для компилятора yacc. В состав правил могут включаться действия expr : expr + term { printf (“Production 1\n”)} Каждый грамматич. символ (термин. и синтаксич.) имеет значение. Общ. вид: expr : expr ‘+’ term {$$= $1+$3} На атрибут нетерминала левой части ссылка осущ-ся посредством значка $$, на атрибуты символов прав. части - $1, $2, причем номер соотв-ет порядку эл-ов. Служебные Си-подпрограммы Си-текст (кот. вместе со скобками %{ и %} может отсутствовать) обычно содержит Си-объявления (включая #include и #define), используемые в тексте ниже. Каждое правило трансляции имеет вид | альтернатива_1; {семантические действия 1} %{#include <ctype.h>%} % token DIGIT %% line: expr ‘\n’ {printf (“%d \n”, $1);} expr: expr ‘+’ term{$$=$1+$3;} | term term: term ‘*’ factor {$$=$1*$3;} |factor factor: ‘(’ expr ‘)’ {$$=$2;} |DIGIT %% int yylex( ) { int C; c=getchar( ) if(isdigit (c)) {yyval=c - ‘0’; return DIGIT;} int yyerror (char *S) {prinf (“Error Yacc\n”); printf (“%s\n”,s);} int main {yyparse ( ) prinf (“End work\n”);}