Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции
 Скачать 0.64 Mb.
|
T+S  ST → ид | ид*T Основная проблема – нахождение основы. Так, если первой выполнить свертку a*b+c T*b+c, т.е. за основу принять символ ‘a’, то в дальнейшем полностью свернуть предложение к начальному символу грамматики уже не удастся. Нахождение основы может быть выполнено различными методами, в частности, путем определения отношений предшествования между символами.Далее будет рассмотрен определенный класс грамматик – грамматики с предшествованием. С помощью таких грамматик может быть представлен синтаксис большинства языков программирования. Основа – самая левая часть строки, приводимая к нетерминалу. Между любыми двумя последовательными символами приводимой строки p и q могут существовать три отношения: p └ основа → p>q, если p – самый правый символ некоторой основы: ...pq ← основа ─┘ p=q, если символы p и q находятся внутри основы: ...pq... └ основа ┘ Отношения <, >, = называются отношениями предшествования. Пусть p, q – любые символы (терминальные или нетерминальные), U, C, D – нетерминальные символы, x, y, z, w – любые строки, возможно пустые. Грамматика называется грамматикой с простым предшествованием, если правые части всех правил грамматики различны и для каждой упорядоченной пары символов существует не более чем одно из трех отношений предшествования: p=q, если существует правило U → xpqy; p  qz;p>q, если существует правило U → xCqy и вывод C zp или правило U → xCDy и выводы Czp, Dqw.Пусть U, C, D – нетерминальные символы, x, y, z, w – любые строки, возможно пустые. Грамматикой с простым предшествованием называют такую грамматику, в которой: для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования: Si = Sj, если существует правило U->xSiSjy Si < Sj, если существует правило U->xSiDy и вывод D=>+Sjz Si > Sj, если существует правило U->xCSjy и вывод C=>+zSi или правило U->xCDy и выводы C=>+zSi, D=>+Sjw разные правила имеют различные правые части. Это условие обеспечивает однозначность замены основ на нетерминальные символы. |