Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции

• Название: Курс лекций по спецкурсу Методы трансляции
• Анкор: Курсовая Лексический анализатор
• Дата: 29.12.2019
• Размер: 0.64 Mb.
• Имя файла: Краткий курс лекций.doc
• Тип: Курс лекций; #102547
• страница: 9 из 19

Алгоритм грамматического разбора в грамматиках с простым предшествованием

Разбор предложений в грамматиках с простым предшествованием ведется с использованием стека терминальных и нетерминальных символов.

Пусть необходимо выполнить грамматический разбор для некоторой входной строки терминальных символов t₁...t_n. Строка ограничивается с двух сторон терминальным символом ┴, при этом считается, что для любого символа p: ┴ < p и p > ┴.

Формируется стек S, элементы которого s_i – терминальные и нетерминальные символы. В стек заносится символ левый ограничитель строки – ┴ (s₁=┴). Далее, на каждом промежуточном этапе действия определяются состоянием стека – s₁...s_k и остатком входного предложения – t_j...t_n┴. Проверяется отношение между верхним элементом стека s_k и очередным символом строки t_j. Если отношения нет, то входная строка некорректна. Если s_kj или s_k=t_j, то t_j заносится в стек. Если s_k>t_j, то отыскивается множество символов в вершине стека, удовлетворяющих отношению: s_i-1i=s_i+1=...=s_k>t_j. Элементы s_i...s_k принадлежат одной основе и могут быть свернуты по некоторому правилу грамматики: U → s_i...s_k. Выполняется свертка: отыскивается это правило, символы s_i...s_k удаляются из стека, а U – заносится. Процесс повторяется: символ U, как верхний элемент стека, сравнивается с t_j и т.д.

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

Пример разбора предложения ┴b((aa)a)b┴ :

Стек │ Остаток │ Отношение │ Основа │ Правило

--------│------------│-----------│---------------│---------

┴ │ b((aa)a)b┴ │ ┴ < b │ │

┴b │ ((aa)a)b┴ │ b < ( │ │

┴b( │ (aa)a)b┴ │ ( < ( │ │

┴b(( │ aa)a)b┴ │ ( < a │ │

┴b((a │ a)a)b┴ │ a > a │ ( < a > a │ M → a

┴b((M │ a)a)b┴ │ M = a │ └─┘ │

┴b((Ma │ )a)b┴ │ a = ) │ ┌─────┐ │

┴b((Ma) │ a)b┴ │ ) > a │ ( < M=a=) > a │ N → Ma)

┴b((N │ a)b┴ │ N > a │ ( < (=N > a │ M → (N

┴b(M │ a)b┴ │ M = a │ └───┘ │

┴b(Ma │ )b┴ │ a = ) │ ┌─────┐ │

┴b(Ma) │ b┴ │ ) > b │ ( < M=a=) > b │ N → Ma)

┴b(N │ b┴ │ N > b │ b < (=N > b │ M → (N

┴bM │ b┴ │ M = b │ └───┘ │

┴bMb │ ┴ │ b > ┴ │ ┴ < b=M=b > ┴ │ Z → bMb

┴Z │ ┴ │ конец │ └─────┘ │

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

Рассмотрим пример:

S → T | S+T

T → ид | T*ид

Так как существует правило S→S+T, то + = T. Но, исходя из того же правила и вывода TT*ид, имеем + < T.

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

S → T | S+T Здесь + = T, + < U

T → U

U → ид | U*ид

Однако здесь нет строго формальных методов преобразования, и, как правило, такое преобразование сильно увеличивает размер грамматики.

Другой способ – использование контекста при разборе. Например, пусть между S_i, S_i+1 существуют отношения S_i < S_i+1, S_i = S_i+1 и нужно определить, какое именно отношение нужно взять в контексте S_i S_i+1 S_i+2. Если существует правило, правая часть которого начинается с S_i+1S_i+2, значит надо взять отношение S_i < S_i+1. Иначе S_i = S_i+1.

Для приведенного примера:

+T* - здесь + < T, есть правило T → T*ид

+T+ - здесь + = T, нет правила → T+

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

Например:

S → T | S+T Имеются два правила с

T → ид | T*P одинаковыми правыми частями

P → ид

Тогда для входного предложения a*b+c идентификаторы a, c могут быть заменены только на T, b – только на P:

a*b+c T*b+c T*P+c T+c S+c S+T S

Задача выбора правила также решается путем дополнительного анализа контекста. Для заданного примера замена ид P должна проводиться только в контексте *ид *P.