Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции
 Скачать 0.64 Mb.
|
|
Регулярные грамматики, диаграммы состояний Регулярные грамматики содержат правила вида U → t или U → Qt, где U, Q принадлежат VN – множеству нетерминальных символов, t принадлежит VT – множеству терминалов или t = λ – пустой цепочке. Пример регулярной грамматики: Z → P | F P → Pц | F. Грамматика описывает числовые F → Fц | Xц константы вида X → + | - | λ [+|-]целое[.[целое]] здесь ц – терминальный символ «цифра». В данном примере правила X → + | - | λ относятся к виду U → t, правила Z → P | F P → Pц | F. F → Fц | Xц к виду U → Qt. По регулярной грамматике может быть построена диаграмма состояний. Это ориентированный граф, в котором каждый нетерминал грамматики представлен узлом, или состоянием; кроме того добавляется узел для начального состояния – S. Каждому правилу Q → t сопоставляется дуга из S в Q, помеченная t. Каждому правилу Q → Rt сопоставляется дуга из R в Q, помеченная t. Диаграмма состояний для приведенного выше примера:  При наличии в грамматике правила вида Q → R (Q → λ) в диаграмме состояний присутствует ветвь, помеченная λ. Такую диаграмму нужно преобразовать по правилам: 1) если Q – заключительное состояние, то R также объявляется заключительным состоянием; 2) исключается дуга, помеченная λ, и в добавление к каждой дуге, помеченной t и ведущей из Q к некоторому состоянию P, добавляется дуга из R к P, также помеченная t.  Результат преобразования диаграммы состояний для грамматики числовых констант:  По диаграмме состояний может быть выполнен грамматический разбор предложения, в ходе которого проверяется его соответствие правилам грамматики. Грамматический разбор некоторой строки X начинается с состояния S. Для очередного символа строки отыскивается дуга, помеченная этим символом, и выполняется переход в следующее состояние. При отсутствии дуги, X не является правильным предложением языка. По концу строки текущее состояние должно быть заключительным. Примеры грамматического разбора:
В ходе реализации алгоритма грамматического разбора диаграмма представляется в виде матрицы состояний. Элемент матрицы: a[i][j]=k – номер состояния, в которое осуществляется переход из состояния i по терминалу j; a[i][j]=0, если дуги из состояния i по терминалу j нет.
Алгоритм разбора предложений в регулярных грамматиках: i = 1 – номер начального состояния; t = очередной_символ_предложения. Если предложение закончилось, то переход к пункту 5; j = номер_столбца_матрицы_A, соответствующего символу t. Если t не принадлежит VT, то фиксируется ошибка; i = a[i][j] – номер очередного состояния. Если i=0, то фиксируется ошибка. Иначе переход к пункту 2; если i не соответствует заключительному состоянию, то фиксируется ошибка. Иначе, конец разбора, предложение корректно. Одновременно с грамматическим разбором предложений может быть выполнен перевод содержащихся в них лексических единиц во внутримашинное представление. С этой целью должен быть разработан набор подпрограмм, вызываемых после распознавания очередного символа предложения. Номера вызываемых подпрограмм задаются матрицей B:
Вызов выполняется перед изменением состояния в п.4 алгоритма грамматического разбора. Задача грамматического разбора. Метод нисходящего разбора По завершению лексического анализа выполняется синтаксический и семантический анализ входной программы, переведенной во внутреннее представление. В некоторых трансляторах этот этап может быть отменен (трансляция завершена) при обнаружении уже в ходе лексического анализа очень серьезных ошибок в программе. Основной задачей блока синтаксического анализа в трансляторе является грамматический разбор исходной программы. Задача грамматического разбора заключается в том, чтобы для предложения построить дерево вывода, в вершине которого находится начальный символ грамматики, а в основании – терминальные символы входного предложения. Цель нисходящего грамматического разбора – найти вывод Z  a1...aN, где Z – начальный символ грамматики, а1...aN – входная строка. Алгоритм разбора:1) начальный символ грамматики заменяется по какому-либо правилу: Z→U1...UN; 2) в дальнейшем, если U1 – терминал, то он сравнивается с первым символом входной строки и при совпадении исключается из входной строки и из строки элементов разложения Z. Если U1 – нетерминал, то он заменяется по какому-либо правилу, и процесс повторяется. Пример грамматики для выражений, составленных из идентификаторов (ид – терминальный символ) и знаков +, *: S → T | T+S T → ид | ид*T Разбор предложения a+b*c представлен ниже: a+b*c S S → T+S ║ Указаны остатки входной строки a+b*c T+S T → ид ║ и строки разложения начального a+b*c ид+S ║ символа грамматики - S, а также +b*c +S ║ правила, применяемые для разло- b*c S S → T ║ жения левого нетерминального b*c T T → ид*T ║ символа. На последнем шаге оба b*c ид*T ║ остатка пусты, что соответ- *c *T ║ ствует правильному разбору. c T T → ид ║ c ид ║ λ λ ║ Так как разложение нетерминалов грамматики обычно может быть выполнено по нескольким правилам, необходимо осуществить полный перебор вариантов разложения: a+b*c S a+b*c T <──────────┴───────────> T+S a+b*c ид <───┴───> ид*T ид+S <────┴────> ид*T+S +b*c λ *T +S *T+S b*c ошибка ошибка S ошибка b*c T <──────────────────┴───> T+S b*c ид <───┴───> ид*T ид+S <────┴────> ид*T+S *c λ *T +S *T+S c ошибка ┌─────── T ошибка ┌──────── T+S c ид <───┴─────────> ид*T ид+S <────┴────> ид*T+S λ λ *T +S *T+S └───────┴──── правильный разбор Сократить перебор вариантов можно путем преобразования грамматики таким образом, чтобы правые части правил подстановки начинались с различных символов. Для этого правила вида X → ap|aq (a – символ, p и q – строки) заменяются на правила X → aY, Y → p|q. S → TP Преобразованная таким способом P → λ | +S грамматика для выражений из T → идR идентификаторов и знаков +, *. R → λ | *T Нисходящий разбор предложения a+b*c для преобразованной грамматики: a+b*c S ║ b*c S ║ c TP a+b*c TP ║ b*c TP ║ c идRP a+b*c идRP ║ b*c идRP ║ λ RP +b*c RP ║ *c RP ║ λ P<─┴─>*TP +b*c P<─┴─>*TP ║ *c P<─┴─────>*TP ║ λ λ<─┴─>+S ошибка +b*c λ<─┴─>+S ошибка ║ *c λ<─┴──>+S ║ │ │ ошибка b*c ошибка S ║ c ошибка ошибка TP ║ └──┴─ прав. Разбор |