11. Синтаксический анализ для кс-языков

Может рассматриваться синтаксический анализ в широком или же узком смысле. Синтаксический анализ в узком смысле – по цепочке определить её структуру (или же построить синтаксическое дерево). Т.Е. задача сводится к построению вывода данной цепочки в данной грамматике.

Синтаксический анализ в широком смысле – определение, может ли данная цепочка быть построена с использованием данной грамматики. Это в общем случае гораздо более сложная задача.

Существующие алгоритмы синтаксического анализа классифицируются по:

1. Cпособу построения вывода : нисходящие, восходящие, смешанные

2. Способу выбора альтернативы: детерминированные и недетерминированные. В первом случае на каждом шаге выбирается правильная альтернатива, во втором – альтернатива выбирается наугад.

3. Способу возврата (для недетерминированного выбора альтернативы): разбор с быстрым или медленным возвратом.

4. По степени доступности цепочки: или цепочка доступна вся сразу, или же читается слева направо посимвольно (при этом доступно для анализа определенное число символов).

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

Типовая задача синтаксического анализа:

Имеется активный нетерминал Sи множество альтернатив:

S___kи текущее состояние анализируемой цепочкиY. Пусть выбрана альтернативаSX₁X₂…X_n,X_iV_NV_T, приi[1,n]. ЕслиX₁V_T, то он должен совпадать с первым символом цепочкиY. Если совпадает, то укорачиваем цепочку на этот символ и переходим кX₂. Если не совпадает, то переходим к другой альтернативе.

Если же X_iV_N, тогда изX_iнеобходимо вывести какое-нибудь начало цепочкиY. Если изX_iнельзя вывести никакое начало цепочкиY, то возможны 2 варианта:

1). Сразу перейти к X_i-1 и попытаться вывести изX_i-1другое начало и т.д. ( получаем полный перебор вариантов вывода) – разбор с медленным возвратом.

2). Сразу отказаться от альтернативы SX₁X₂…X_n(разбор с быстрым возвратом).

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

11.1 Ll(k)-грамматики

LL(k)-грамматиками называются грамматики, допускающие детерминированное построение левого разбора(left)при чтении анализируемой цепочки слева(left)направо, подсмат­ривая вперед не более чем наkсимволов.

Например, рассмотрим грамматику с множеством правил:

Sa SbB

B  b B

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

Грамматика называется разделённой, если все правила грамматики имеют вид

Aa₁₁a₂ ₂…a_k_k, причём a_ia_j при ij, a_iV_T, _i(V_TV_N)* при i[1,k]. Очевидно, что в случае разделённой грамматики строится детерминированный нисходящий разбор.

Очевидно, что разделённые грамматики принадлежат к классу LL(1) грамматик. Грамматики могут оказатьсяLL(k) грамматиками для различныхk, например, грамматика может бытьLL(3) грамматикой, но неLL(2) грамматикой. Бывают и грамматики, которые не являютсяLL(k) грамматикой ни для какогоk.

Например, рассмотрим грамматику с множеством правил:

S0 S0B

A  0 A ac L(G)= {0ⁿ⁺¹ c aⁿ, 0ⁿ⁺¹ d bⁿ, n 0}

B  0 B bd

S_l A ⁿ⁺¹0ⁿ⁺¹ с aⁿ

S_l B ⁿ⁺¹ 0ⁿ⁺¹ d bⁿ ( n  0 ).

Чтобы определить по заданной терминальной цепочке, ка­кое правило ( SAилиSB) было применено на первом шаге вывода, нужно прочитатьn+1 символ, следовательно данная грамматика не являетсяLL(k) ни при ка­комk

Дадим формальное определение LL(k) грамматики. Для этого введем определение

• определяются первые kсимволов терминальной цепочки. Т.к. для пустой цепочки это пустое множество, то определим для данной грамматики пополненную грамматику, к которой не будут встречаться пустые цепочки:

Для грамматики G=< V_T,V_N, S, R> соответствующая пополненная грамматика G’=< V_T{$},V_N{S’}, S’, R’>, где множество правилR’=R{S’ S $ }, где каждая цепочка имеет справа граничный маркер($).

Расширим определение множества firstтак, чтобы охватить произвольные цепочки(V_TV_N)*:

Для (V_TV_N)*First_k()= {x/*Z,ZV_T*,x=}.

Например, рассмотрим грамматику с множеством правил

S abAabB

A  ab A c L(G)= {(ab)ⁿc, (abc)ⁿ, n 1}

B  cab Bc

Правила соответствующей пополненной грамматики:

S’ S $

S ® abA½abB

A ® ab A ½c

B ® cab B½c

Для данной грамматики

First₁(S)={a}, First₁(A)={a, c}, First₁(B)={c}; First₂(S)={ab}, First₂(A)={ab, c$}, First₂(B)={c$, ca}, First₃(S)={abc}, First₃(A)={abc, c$}, First₃(B)={c$, cab}.

Тогда мы можем формально определить LL(k) грамматику как грамматику, для которой для любых двух левых выводов

S* A      * x

S* A      * y

AV_N, , x, y  V_T*,     (V_N  V_T)*, из условияFirst_k(x)=First_k(y) следует.

Несложно показать, что наше формальное определение соответствует не формальному.

Теорема:LL(k) грамматика является однозначной.

Неоднозначность грамматики противоречит LL(k) свойству. Неоднозначна – значит, существуют два вывода для некоторой цепочки, значит, не сможем определить поkсимволам, каое из правил следует применить.

Теорема: КС-грамматика G=< V_T,V_N, S, R>являетсяLL(k) грамматикойдля любых двух правил А₁и А₂First_k(₁)First_k(₂)=для любой цепочки, такой чтоS*A.

Использование LL(k) свойства при построении анализатора.

Пусть текущее состояние левого вывода цепочки z=yимеет видА, гдевыведенное терминальное начало цепочки, А – текущий нетерминал( самый левый нетерминал),yне просмотренная часть цепочки.

Рассмотрим First_k(y). Пусть для нетерминала А существуют альтернативы:

А₁₂_nR. Надо найти_iдля применения на данном шаге. Для этого надо вычислить=First_k(_i). Это множество может быть заранее вычислено для всех А,,_i. При этом изLL(k) свойства следует, чтоприij.

Выбираем _i, такое, чтоFirst_k(y)=First_k(_i). Если такого_iнет, тоzL(G).

Затем переходим к анализу полученной цепочки xy’y’, где’ – терминальное начало цепочки₁.

Шаги повторяются, пока не разберём всю цепочку, или не установим, что zL(G).

Пример:

Рассмотрим анализ цепочки acbbdв грамматике

Sac SbB

B  b Bd

Эта грамматика является LL(1) На первом шаге определяем, какое правило применялось вначале:First₁(acS)={a},First₁(bB)={b}, поэтому на первом шаге применяется правилоSacS, анализируемая цепочка принимает вид:bbd,First₁(bbd)={b}, поэтому применяется правилоSbB, и анализируемая цепочка принимает видbd. ОпределяемFirst₁(bB)={b},First₁(d)={d}, поэтому применяемое правилоBbB, анализируемая цепочка принимает видd, применяем правилоBd, остается пустая цепочка как в выводе, так и анализируемая цепочка, поэтому анализируемая цепочка принадлежит языку, порождаемому грамматикой.

Проблемы, возникающие при построении анализатора для LL(k) грамматик:

1. При k1может стать неприемлемо большой , т.к.пропорциональнаk.

2. является функцией от трёх переменных: А,_i,- т.е. велик сам объём предварительных вычислений.

Однако можно упростить задачу, усилив условия, накладываемые на грамматику:

Обозначим и потребуем, чтобыприij.

Грамматика Gназывается строгоLL(k) грамматикой, если для любых двух левых выводов

S*₁ A ₁ ₁  ₁ *₁x

S*₂A ₂  ₂  ₂  *₂ y

AV_N, ₁, ₂, x, y  V_T*, ₁ ₂    (V_N  V_T)*, из условияFirst_k(x)=First_k(y) следует . Несложно показать, чтоGявляется строгоLL(k) грамматикойдля любогоAV_Nиз того, чтоAR,AR,, следует, чтоM_A^M_A^=.

Теорема:LL(1) грамматика всегда строгоLL(1) грамматика.

Доказательство:

Предположим, что некоторая грамматика G-LL(1) грамматика, но не строгоLL(1) грамматика. Тогда существуют два вывода

S*₁ A ₁ ₁  ₁ *₁x₁₁ *₁x₁y₁

S*₂A ₂  ₂  ₂  *₂ x₁₂ *₁ x₂y₂,

Такие, что First₁(x₁y₁)=First₁(x₂y₂) &- Условие (*).

Но т.к. G-LL(1) грамматика, тоS*₁ A ₁ ₁  ₁ *₁x₁₁ *₁x₁y₁

S*₁ A ₁ ₁  ₁ *₁x₂₁ *₁x₂y₁

и из First₁(x₁y₁)=First₁(x₂y₁) следует, что- Условие (**).

Покажем, что условия (*) и (**) несовместны.

Рассмотрим следующие случаи:

1. x₁, x₂ , тогда First₁(x₁y₁)=First₁(x₁), First₁(x₂y₂)=First₁(x₂), First₁(x₁ )=First₁(x₂)по условию (*) .

С другой стороны, по условию (**) First₁(x₁ )=First₁(x₂). Противоречие.

2. x₁=,x₂=приводит к неоднозначности грамматики.

3. Пусть x₁=,x₂. Тогда в условии (*)First₁(x₁y₁)=First₁(y₁)= First₁(x₂y₂)=First₁(x₂) & 

По условию (**) First₁(x₁y₁)=First₁(y₁)=First₁(x₂y₁)=First₁(x₂) &=. Противоречие.

Случай 4, x₁¹l,x₂=lразбирается аналогично случаю 3.

Из теоремы следует критерий принадлежности грамматики классу LL(1):

G–LL(1)M_A^M_A^=придля всехAV_N, гдеM_A^b=

При этом если

а) ,*,, тоM_A^=First₁()

b) *, M_A^=First₁()

Т.К. рассматриваем пополненную грамматику, то (First₁()=).

Определим множество Follow₁(X)={a/S⁺Xa&aV_T}, X(V_NV_T).

Т.о. G - LL(1) грамматика  AV_N, , AR&AR&  M_A^M_A^=.

Определения и алгоритмы нахождения множеств FirstиFollow

1. First₁()

1. First₁()=

2. aV_T First₁(a)=a

3. First₁(A)={ First₁(x_i)/Ax₁x₂…x_nR&i=1i=m&x₁…x_m-1⁺}

4. First₁(x₁x₂…x_n)={ First₁(x_i)/ First₁(x₁)& i=1i=m&x₁…x_m-1⁺}

Например, рассмотрим грамматику:

S ABCCA

Aa

B  b B

CcCd

В пополненной грамматике добавляется начальной правило S’S$.

S’ S

S  ABCCA

Aa

B  b B

CcCd

First₁(A)={a};

First₁(B)={b};

First₁(C)={c,d};

First₁(S)= First₁(ABC) First₁(AC)={a, b, c, d}

2. Follow₁(A)= ={First₁()/ S * A  }

Рассматриваем грамматику без непроизводящих правил, тогда если S*BA, тоFirst₁()Follow₁(A).

1. Неверно, что *, тогдаFirst₁()=First₁().

2. *, тогда First₁()=First₁()First₁().

Поэтому Follow₁(A)={ First₁(Xm)/ B A X₁ X₂…X_nR&m=1X₁X₂…X_m*} {Follow₁(B)/B A  R &*}

Т.е. просматриваются все правые части правил, в которые входит исследуемый нетерминал.

Рассмотрим грамматику

S’S $

S  ABCCA

Aa

B  b B

CcCd

Здесь N_={A,B}

Follow₁(S)={$},

Follow₁(A)= First₁(B) First₁(C)  Follow₁(S)={b, c, d, $},

Follow₁(B)= First₁(C)={c,d},

Follow₁(C)= First₁(A) ) Follow₁(S)={a,$}.

Проанализируем LL(1) свойство грамматики:

M_S^ABC= First₁(A) First₁(B) First₁(C)={a, b, c, d},

M_S^CA= First₁(C)={c,d}.

Т.к. M_S^ABCM_S^CA, то грамматика не являетсяLL(1) –грамматикой.

Восходящий анализ.

При восходящем анализе цепочка сворачивается путем применения правил в обратном порядке (дерево вывода строится снизу вверх).

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

Если свёртываемая основа выбирается случайно, то может потребоваться возврат, и число шагов построения вывода пропорционально длине цепочки.

Среди грамматик выделяется класс LR(k) грамматик - тот тип грамматик, для которых однозначно восстанавливается правый вывод (R) при чтении цепочки слева (L) направо, при подглядывании вперёд не более чем наkсимволов.

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

Пусть цепочка Xполучена G=< V_T,V_N, S, R>с помощью правого вывода:

S₁₂…._n=X (V_T)*.

Тогда при восходящем анализе будем иметь

X=_n ├ _n-1 …├ ₀ = S.

Выделим i-ый шаг выводаS*Ay (=_i-1)   y (=_i)*x y, здесьAyтекущее состояние правого вывода,A– самый правый нетерминал в выводе. Свёртка состоит в переходе от  yкaAy, (a j y├aAy) т.е. мы должны выделить подцепочкуj, которая сворачивается в нетерминалAприменением правилаAjв обратном порядке.

Пример разбора цепочки для грамматики с арифметикой.

Для ГПП техника выделения основы следующая:

Строится матрица отношений предшествования между символами V_TV_N. При этом между парой символов х иyможет существовать не более одного отношения предшествования, обозначаемого символами <,≗, >.

Грубо говоря, отношения предшествования отражают порядок появления символов в правом выводе.

Если ajy– текущее состояние цепочки, гдеj– основа, то

Между всеми смежными символами цепочки , выпол­няется отношение <или≗.

2. Между последним символом цепочки и первым символом цепочки(основы) выполняется отношение <.

3. Между смежными символами основы выполняются отношения ≗.

4. Между последним символом основы и первым символом цепочки у выполняется отношение >.

Если такое свойство отношений имеет место и для каждой пары символов определено не более одного отношения, то осно­ву легко выделить, просматривая цепочку   yслева направо до тех пор, пока впервые не встретится отношение>. Для нахождения левого конца основы надо возвращаться назад, пока впервые не встретится отношение <.Цепочка, заключенная между<и>и будет основой. Если в грамматике нет правил с одинаковыми правыми частями, то однозначно находится нетер­минал А такой, чтоA  , что позволяет свернуть основу, полу­чая цепочку_i-1.

Этот процесс продолжается до тех пор, пока цепочка либо не свернется к начальному символу S, либо дальнейшие свертки окажутся невозможными.

Отношения простого предшествования с указанными свойствами могут быть определены на V_NV_Tследующим образом [1]:

X < Y, если в Rесть правилоA  X B , и при этом B^Y;

X ≗ Y, если вR есть правилоA  X Y .

Отношение > определяется на(V_NV_T) V_T, так как непосредственно справа от основы может быть только терминальный символ.

X  > a, если в R есть правилоA  X Y , и B ⁺  X,Y* a . Так как основа может совпадать с правым или левым кон­цом цепочки, то удобно заключить анализируемую цепочку в концевые маркеры $ и $ , положив дляX V_NV_T, X > $ для всехX, для которыхS ^  XиX< $для всехX, для которыхS ^ X .

Грамматика Gназывается грамматикой простого предшествования, если она не содержит-правил, для любой пары символов изV_NV_Tвыполняется не более одного отношения простого предшествования и в ней нет правил с одинаковыми правыми частями.

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

Пример. Пусть множество правил грамматики:S a S S b,S c. Для заключения цепочки в маркеры вводим новый начальный символS’и правилоS’$S$. Отношения предшествования для этой грамматики приведены в табл.1.

	S	a	b	c	$
S	≗	<	≗	<
a	≗	<		<
b		>	>	>	>
c		>	>	>	>
$		<		<

Разбор цепочки $accb$.$<a<c>cb$├$<a≗S<co>b$├$<a≗S≗S≗bo>$├$S$

Вывод, соответствующий этому разбору:

S’ $ S $$ a S S b $$ a S c b $$ a c c b $ Способ построения свёртки для цепочки связан с использованием стека, куда посимвольно переносится информация из входного буфера, до тех пор, пока не встретится отношение >. Тогда к цепочке от отношения > до ближайшего слева отношения < должна применяться свёртка.

Алгоритм разбора для ГПП:

1. Анализируемая цепочка заключается в маркеры.

2. Берём очередной символ из входного буфера (слева направо). Если между верхним символом стека и первым символом входной цепочки отношение<o или ≗ , то заносим этот символ из входной цепочки в стек и возвращаемся к шагу 2, если же между верхним символом стека и первым символом входной цепочки отношение o>, то переходим к шагу 3. Если между символами нет никакого отношения предшествования, то цепочка не принадлежит языку, порождаемому грамматикой.

3. Обратное движение: из стека вынимаются символы до первого отношения <o между первым символом стека и символом цепочки во входном буфере. Если такой символ появился, то переходим к шагу 4, иначе цепочка не принадлежит языку, порождаемому грамматикой.

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

Если в результате применения свёртки мы приходим к цепочке $ S $, то исходная цепочка принадлежит языку, порождаемому грамматикой, в противном случае цепочка не принадлежит языку, порождаемому грамматикой.

Обозначим

Head(A)={X/A⁺X} (First1(A)=Head(A) V_T),

Tail(A)= {X/A⁺  X}, тогда

X <o Y  A X B  & Y Head(B)

X  > a  A B C  & X Tail(B) & aFirst1(C).

Пример разбора цепочки aaccbbcb с использованием построенной таблицы отношений предшествования приведен в табл.2.

Таблица 2

	Отношение	Входная
Стек	предшествования	строка	Операция
$	<	aaccbcb$	сдвиг
$a	<	accbcb$	сдвиг
$aa	<	ccbcb$	сдвиг
$aac	>	cbcb$	«Свертка»
$aaS	<	cbcb$	сдвиг
$aaSc	>	bcb$	«Свертка»
$aaSS	≗	bcb$	сдвиг
$aaSSb	>	cb$	«Свертка»
$aS	<	cb$	сдвиг
$aSc	>	b$	«Свертка»
$aSS	≗	b$	сдвиг
$aSSb	>	$	«Свертка»
$S		$	«Конец»