Первичные фразы и их обнаружение

Алгоритм разбора на основе простого предшествования

Вычисление отношений операторного предшествования. Алгоритм разбора на основе операторного предшествования

Предшествование операторов

Операторное предшествование

При использовании грамматик простого предшествования отношения определялись между всеми символами как операндами, так и операторами. Техника предшествования операторов формализует понятие предшествования только между терминальными символами (операторами).

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

U: = …VW…, где V,WÎVN, то есть рядом не могут стоять два нетерминала. Никакая сентенциальная форма не содержит двух соседних нетерминальных символов:

1) R ≗ S, если U: = …RS…|…RVS…, где R,SÎVT, VÎVN.

2) R∘>S, если U: = …WS… и W=>+…R|…RV

3) R<∘S, если U: = …RW… и W=>+S…|VS…

Построим отношение для грамматики: E: = E+T|T; T: = T*F|F; F: = (E)|i.

Отношение Q ПЕТ R(R – первый терм из Q) имеет место тогда и только тогда, когда Q: = R…|VR…, а отношение Q ПОСТ R(R – последний терм из Q) имеет место тогда и только тогда, когда Q: = …R|…RV…, где V-нетерминальный символ.

U

… W S

∘>=(ПОСТ)^Т ´ (ПОС) ´ (≐)

…Q

…R|RV

U

R W

<∘ =(≐)´(ПЕ)⁺´(ПЕТ)

Q…

S…|VS

Для нахождения основ, состоящих из одного нетерминала, рассматриваемые отношения неприемлемы, так как по условию для нетерминалов их просто не существует. Основу с помощью операторного предшествования не отыскать. Введём подцепочку и назовём её первичной фразой.

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

E

E + T

|

E + T F

| | |

T T*F i

T+T*F+i – сентенциальная форма.

Введём первичную фразу. T+T+F – некоторая подцепочка, в ней основа Т, но она не будет первичной фразой, так как не содержит терминала.

T*F – будет первичной фразой, так как содержит терминал и нет других первичных фраз.

i – будет первичной фразой, так как содержит терминал и нет других первичных фраз.

Запишем сентенциальную форму в общем виде: #N₁T₁N₂T₂N₃T₃…N_nT_n#. (N- нетерминал, Т- терминал).

Сентенциальная форма, таким образом, состоит из n- терминалов, причём между каждым соседним символом находится не более одного нетерминала.

T_i-1<∘ N_iT_i…N_jT_jN_j+1∘>T_j+1 – первичная фраза.

Любой символ всегда находится в таком отношении: #<∘T_j∘># с дополнительными.

Сентенциальная форма	Отношения	Первичная фраза	К чему приводится
T+T*F+i	#<∘+<∘* ∘>+	T*F	Т

Нетерминалы, стоящие слева и справа, принадлежат первичной фразе.

Следующий шаг: T+T+i #<∘+∘>+ T+T (нет такого правила) E.

Поэтому в процедуру разбора надо ввести некоторые семантические состояния, то есть анализ правила на наличие одного терминального символа из правила, то есть проведём замену Т на Е, такое правило есть:

# E+i #	# <∘+<∘i∘> #	i	F;
# E+F #	#<∘+∘>#	E+F	E.

Структура цепочки правильная и разбор окончен, если между # стоит нетерминал.