Учебное пособие: Разработка в структурно логической схемы микропроцессора

S→bY

Y→bY

Y→b

S →ξ

G3=({a,b},{S,Y},P3,S)

Две грамматики генерирующие один и тот же язык называются эквивалентные грамматики.

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

Синтаксические диаграммы.

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

Пример определения символического имени.

Синтаксический анализ языков программирования.

После того, как на этапе лексического анализа, программа разбивается на ее основные элементы, следующая фаза компилятора должна распознать структуру выражения, состоящая из этих элементов и интерпретировать их. Синтаксический анализ, представляет собой задачу противоположную задачи порождения (вывода). Задача разбора формулируется следующим образом: определить соответствует ли данная конструкция некоторого языка, грамматике этого языка. Является ли данная конструкция правильным предложением языка, то есть не содержит синтаксических ошибок. Различают два типа разбора. Левосторонний и правосторонний.

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

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

Синтаксическое дерево разбора

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

Лекция 23.11.07

Базовые методы синтаксического анализа.

Вариант построения синтаксического анализа.

Нисходящий разбор - синтаксическое дерево строится от корня к листьям, его отличительная черта является целенаправленность, так как отправляясь от нетерминального символа языка, мы стремимся найти такую подстановку, которая бы привела к части цепочки терминальных символов. Достигается это путем направленного перебора различных вариантов. В списке правил подстановке отыскивается правило, которые в левой части содержат не терминальные символы, а в правой части символы терминальные анализируемого предложения. Если такое правило есть, то дерево не рассчитывается и правило повторяется. Если правило не найдено, то возвращаемся на один или несколько шагов назад, пытаясь изменить выбор сделанный ранее. Процесс разбора заканчивается в одном из двух случае.

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

Распознаватель переработал все возможные варианты, но так и не пришел к дереву, значит анализируемое предложение не принадлежит данному языку или содержит ошибку.

«константа»:: = «КФТ» | «знак» «КФТ»

Шаг 1 константа

Шаг 2 КФТ

Восходящий разбор – дерево строится от листьев к корню, то есть алгоритм отправляется от заданной строки, пытается применить правило подстановки с лева на право и все это привести к начальному символу грамматики. Часть строки, которую можно привести к нетерминальному символу называют фразой. Если приведение осуществляется приведением одного правило подстановки, фраза называется непосредственно приводимой. Самая левая непосредственная фраза называется основой. Алгоритм разбора заключается в следующем: в исходном предложении отыскивается основа и приводится к нетерминальному символу. Эта операция применяется до тех пор, пока не получим единый символ и он должен быть начальным символом грамматики. Либо в цепочке не может быть найдена фраза, в этом случаи делается возврат на один или несколько шагов, выбирается другая основа, если все возможные варианты перебраны, а корень дерева так и не построен, делается вывод об наличии ошибки. Восходящий разбор представляет собой перебор вариантов, но они не целенаправленны.

Нисходящие и восходящие методы требуют большого количества перебора. Поэтому требую только детерминированные методы.

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

Лекция 30.11.07

Ll(1) – грамматика

Контекстно-свободные грамматики традиционно служат основой создания синтаксических анализаторов. Для того чтобы построить де терминированный анализатор работающий по принципу сверху в низ используется Ll(1) грамматика. Первая l означает, что исходная строка разбивается с лево на право, вторая буква – левосторонний разбор, а цифра означает, что варианты порождающих правил выбирается с помощью одного предварительного просматриваемого символа.