Tiêu đề 6 - Грамматика с огр. контекстом. Правила Флойда.pdf ✅

Синтаксический анализ предложений для грамматик с ограниченным контекстом 1. Понятие грамматик с ограниченным контекстом 2. Структура правил подстановки Флойда 3. Построение правил подстановки Флойда 4. Грамматический разбор с использованием правил подстановки Флойда 1 Понятие грамматик с ограниченным контекстом Грамматики, для которых основа в предложении определяется не более чем m символами, находящимися слева от основы, и не более чем n символами справа от основы называется грамматикой с (m,n) ограниченным контекстом. В частности, грамматики с простым предшествованием представляют собой грамматики с (1,1) ограниченным контекстом (в ходе проверки отношений рассматривается один символ слева от основы и один символ справа от неё). Грамматики, для которых основа определяется всей находящейся слева от нее частью приводимой строки и не более, чем n расположенными справа терминальными символами, называется LR(n)-грамматикой. Для любой LR(n)- грамматики существует эквивалентная ей LR(1)-грамматика. Алгоритм грамматического разбора для LR(n)-грамматик основан на предварительном переводе грамматик на некоторый метаязык, называемый языком правил подстановки Флойда. 2 Структура правил подстановки Флойда Правила подстановки Флойда для LR(1)-грамматик записываются в следующем формате: M1 x1...xk y1...ym СП * M2 где M1 – метка правила (может отсутствовать); x1...xk – образец для сравнения с частью приводимой строки. Может содержать символ  – любой символ; y1...ym – строка, которая заменяет часть приводимой строки x1...xk (может отсутствовать); СП – имя семантической подпрограммы (может отсутствовать). Это может быть фиксация обнаруженной ошибки, выход по концу разбора и т.п.; * – знак, предписывающий прочитать следующий символ входной строки (может отсутствовать); M2 – метка правила, к которому нужно перейти после успешного применения данного правила (может отсутствовать). Грамматический разбор предложений для LR(n)-грамматик ведется с использованием стека терминальных и нетерминальных символов. Возможность применения отдельных правил подстановки Флойда определяется совпадением образца x1...xk из правила с k верхними символами стека.
Завершение грамматического разбора осуществляется путем вызова специальной семантической подпрограммы – «Выход». Для обеспечения автоматического вызова этой подпрограммы исходная грамматика дополняется правилом вида: Z → S┴, где S – начальный символ исходной грамматики, ┴ – ограничитель, добавляемый к входной строке. 3 Построение правил подстановки Флойда Алгоритм построения правил подстановки Флойда для LR(1)-грамматик предполагает построение двух типов правил: 1) помеченных S0, которые строятся для нетерминала S, если верхний терминальный символ стека определяет начало строки, которая может быть свернута в S; 2) помеченных S1, если символ S (терминал или нетерминал) находится в следующей за вершиной позицией стека. Обозначения: L0 – множество символов S, для которых нужно построить правила S0; L0* – множество символов S, для которых уже построены правила S0; L1 – множество символов S, для которых нужно построить правила S1; L1* – множество символов S, для которых уже построены правила S1. Первоначально: L0 ={Z} – начальный символ грамматики; L0*, L1 , L1* – пустые множества. Образование S0-правил. 0.1. Если L0\L0* – пусто, то перейти к пункту 1.1. 0.2. Для символа H ∈ L0\L0*, для каждого t из LT(H) найти множество правил грамматики: K ∶ K → tp, p ∈ V ∗ Пусть таких правил будет n. 0.3.Если n > 1, то сформировать правило подстановки Флойда H0 t * t1 и включить t в L1. 0.4.Если n = 1, то в зависимости от вида правила: 0.4.1. K → t H0 t K * K1 и включить K в L1 0.4.2. K → tbp H0 t K * t1 и включить t в L1 b ∈ VT, p ∈ V ∗ 0.4.3. K → tUp H0 t * U0 и включить U в L0 U ∈ VN, p ∈ V ∗ 0.5. Уничтожить метку H0 во всех правилах, кроме первого. Добавить правило H0 ∀ error Включить H в L0*. Перейти к пункту 0.1.
Образование S1-правил. 1.1.Если L1\L1* – пусто, то конец работы. 1.2.Для каждого символа X из L1\L1* выделить все правила грамматики, содержащие в правых частях символ X. 1.3.Для каждого выделенного правила U → pXq образовать правило подстановки Флойда в зависимости от вида правила грамматики: 1.3.1. Z → S┴ S1 S┴ Z Exit и включить S в L1 1.3.2. U → pX X1 pX∀ U∀ U1 и включить U в L1 1.3.3. U → pXq X1 pXq U * U1 и включить U в L1 1.3.4. U → pXHq X1 pXt H0 и включить H в L0 Для каждого t из LT(H) 1.3.5. U → pXtbw X1 pXt * t1 и включить t в L1 t,b - терминалы 1.3.6. U → pXtHq X1 pXt * H0 и включить H в L0 1.4. Правила с символом  в конце образца поместить после остальных, упорядочив по убыванию длины образца. 1.5. Уничтожить метку X1 во всех правилах, кроме первого. Добавить правило X1 ∀ error Включить X в L1'. Перейти к пункту 0.1. Рассмотрим пример грамматики для выражений из идентификаторов и знаков +, *. Символ ┴ – ограничитель конца строки Z → S┴ S → T | S+T T → ид | T*ид Грамматика для выражений из идентификаторов и знаков +, *. Символ ┴ – ограничитель конца строки. Построение правил подстановки Флойда U L(U) LT’ (U ) Z S, T, ид ид S T, ид ид T ид, T ид
L0 L0' L1 L1' Правило грамматики Пун кт алго рит ма Правило подстановки Флойда Z T → ид 0.3.2 .1 (1) Z0 ид T * T1 Z T 0.4 (2)  ош1 Z Z T S → T 1.3.2 (3) T1 T  S  S1 Z Z T,S S→ S+T 1.3.2 (4) T1 S+T  S  S1 Z Z T,S T→ T*ид 1.3.5 (5) T1 T* * *1 Z Z T,S,* 1.4 Упорядочение правил 5,4,3 Z Z T,S,* 1.5 (6)  ош2 Z Z T,S,* T Z → S┴ 1.3.1 (7) S1 S┴ Z вых Z Z T,S,* S → S+T 1.3.6 (8) S1 S+ * T0 Z,T Z T,S,* T 1.5 (9)  ош3 Z,T Z T,S,* T,S T → ид 0.3.2 .1 (10)T0 ид T * T1 Z,T Z T,S,* T,S 0.4 (11)  ош4 Z,T Z,T T,S,* T,S T → T*ид 1.3.3 (12)*1 T*и д T * T1 Z,T Z,T T,S,* T,S 1.5 (13)  ош5 Z,T Z,T T,S,* T,S,* конец 4 Грамматический разбор с использованием правил подстановки Флойда Программа грамматического разбора использует таблицу правил подстановки и стек, содержащий уже рассмотренную и возможно частично свернутую часть строки. Исходная строка дополняется ограничителем ┴, первый символ строки заносится в стек. Применение очередного правила начинается с сопоставления k верхних символов стека с образцом x1...xk. При несовпадении применяется следующее по порядку правило. При совпадении x1...xk заменяется на y1...ym (если y1...ym пусто, то замена не производится). Далее, при необходимости, выполняется семантическая подпрограмма. Затем, если задан символ *, то в вершину стека добавляется очередной символ входной строки. Выполняется переход к правилу, помеченному M2.