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

Содержание

Введение

1. Системы программирования. Классификация  и методы  

    Программирования.

    1.1 Основные понятия и определения

    1.2 Классификация языков программирования

    1.3 Функциональные языки программирования

       2. Синтаксический анализ.

    2.1 Цель синтаксического анализа

    2.2 Нисходящий  синтаксический анализ.

    2.3 Восходящий  синтаксический анализ.

Список используемой литературы

 

 

 

    

 

           

Введение

В настоящее время  широко стоит проблема синтаксического  анализа текстов. В данное время  существует много методов синтаксического  анализа. Одним из таких методов  является проверка по регулярным выражениям.

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

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

 

 

 

 

 

 

 

 

 

 

1.Системы программирования. Классификация  и методы программирования.

 

1.1.Основные понятия и  определения.

 

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

Место систем программирования в общей классификации

программного обеспечения.

  Система программирования  определяется следующими составными  частями: язык программирования, транслятор и интегрированная  среда разработки.

Язык программирования - это формальный язык, предназначенный  для

описания (кодирования) алгоритмов решения различных задач.

 Транслятор - это программа,  которая переводит текст исходной  программы в эквивалентную объектную  программу. Если объектный язык  представляет собой ассемблер  или некоторый машинный язык, то транслятор называется компилятором.

Интегрированная среда разработки  - это библиотека сервисных программ , предназначенных для автоматизации процессов разработки, программирования и отладки.

Понятие интегрированной  среды разработки возникло с появлением объектно-ориентированного программирования, однако, в том или ином виде это  понятие присутствует также в  процедурно-ориентированных системах программирования.

 

 

 

 

 

1.2. Классификация  языков  программирования.

 

     Существует  много разных способов классификации  языков 

программирования. Традиционно  все это сводится к следующему.

Универсальные и проблемно-ориентированные  языки 

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

Языки высокого и низкого  уровня. К языкам низкого уровня относятся

машинные языки и ассемблеры. Все остальные языки принято  относить

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

программирования C.

Машинно-ориентированные и машинно-независимые языки

программирования. Языки программирования , зависящие от специфики определенного типа компьютеров, называются машинно-ориентированными. Все остальные относятся к машинно-независимым языкам. К машинно-ориентированным языкам традиционно принято относить машинные языки и ассемблеры. Однако из этого вовсе не следует, что все остальные языки программирования автоматически можно отнести к  машинно-независимым языкам. Имеются языки программирования, в которых содержатся машинно-ориентированная и машинно-независимые части.

Операторные и функциональные языки программирования.

К операторным языкам программирования относится большинство 

традиционных языков (PASCAL, C и т.п.), в которых имеются понятия

операторов и функций. В отличие от операторных, в функциональных

языках программирования отсутствует понятие оператора,  а программа

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

является функциональный язык программирования LISP.

Процедурно- ориентированные  и объектно-ориентированные языки программирования. Процедурно- ориентированные языки

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

Языки компилируемого и интерпретируемого типов. Язык

программирования относится к языкам компилируемого типа, если в результате трансляции текста исходной программы получается объектная программа на ассемблере или на некотором машинном языке. Языки интерпретируемого типа предусматривают получение в результате трансляции так называемого промежуточного кода, выполнение которого осуществляется специальной программой, называемой интерпретатором. Иными словами , для языков интерпретируемого типа происходит частичная компиляция , завершаемая генерацией промежуточного кода. Например, язык LISP относится к языкам интерпретируемого типа , а язык PASCAL -к языкам компилируемого типа .

Приведенная классификация  никоим образом не претендует на полноту , так как кроме приведенных выше типов языков , существуют языки логического программирования, языки параллельного программирования , языки управления базами данных,

языки искусственного интеллекта и т.п.

 

 

 

 

1.3.Функциональные языки  программирования.

 

     Функциональное  программирование - это способ составления 

программ, в котором единственным действием является вызов функции,

единственным способом расчленения  на части - введение имени  для

функции и задание для  этого имени выражения, вычисляющего

значение функции, единственным правилом композиции - суперпозиция функций. В этом разделе предлагаются элементы функционального программирования на основе языка программирования LISP. Раздел

 никоим образом не  претендует на руководство по  программированию 

на языке LISP , его цель - знакомство с основными принципами функционального стиля программирования.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Синтаксический  анализ.

 

2.1. Цель синтаксического  анализа.

 

    Первоочередной  задачей синтаксического анализа  является 

нахождение порождения (если оно существует) конкретного предложения  языка с использованием данной грамматики.

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

     Если анализируемое  предложение не принадлежит языку, 

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

     Нисходящий  синтаксический анализ (top-down parsing) предусматривает построение синтаксического дерева, начиная

с вершины  (символа предложения) с развертыванием дерева в направлении предложения языка.

Восходящий синтаксический анализ (bottom-up  parsing)

предусматривает построение синтаксического дерева, начиная 

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

 

 

2.2 Нисходящий синтаксический  анализ.

 

 

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

Рассмотрим в качестве примера язык вида { x ^m y ⁿ |m, n > 0 }, определяемый следующими продукциями:

 

     S -> XY

     X -> xX

     X -> x 

     Y - >yY

     Y -> y

Предложение  xxxyy  можно сгенерировать с помощью следующего левого порождения:

 

S => XY => xXY => xxXY => xxxY => xxxyY => xxxyy    .

 

Алгоритм нахождения левого порождения можно наглядно

проиллюстрировать с помощью  приводимой таблицы.

 

    

 

 

_________________________________________________________

      Входная  строка              Продукция         Сентенциальная  форма

      _________________________________________________________

      xxxyy                                 S => XY              XY

      xxxyy                                 X => xX              xXY

      xxxyy                                 X => xX              xxXY

      xxxyy                                 X => x                xxxY

      xxxyy                                 X => x                xxxY

      xxxyy                                Y => yY               xxxyY

      xxxyy                                Y => yY               xxxyY

      _________________________________________________________

      Таблица. Алгоритм нахождения левого порождения.

 

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

После генерации знак предложения  подчеркивается во входной строке.

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

синтаксического анализа  все знаки входной строки подчеркнуты,

а сентенциальная форма полностью  совпадает с заданной строкой.

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

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

нисходящего синтаксического  анализа с одним символом предосмотра. Это так - называемые LL(1) -грамматики. Термин LL(1) означает следующее :первая буква L определяет направление чтения слева

( Left ) направо, вторая буква L определяет использование левых

( Leftmost) порождений, цифра 1- один символ предосмотра. Соответственно LL(1) - язык определяется как язык, генерируемый посредством LL(1) -грамматики.

 

2.3 Восходящий синтаксический  анализ.

 

     Задача восходящего  анализа, как правило, сводится к нахождению правого порождения. Рассмотрим в качестве примера рассмотренный

в предыдущих разделах язык  { x ^m y ⁿ |m, n > 0 }, определяемый следующими продукциями:

     S -> XY

     X -> xX

     X -> x 

     Y - >yY

     Y -> y   

Предложение  xxxyy  можно сгенерировать с помощью следующего правого порождения:

S => XY => XyY => Xyy => xXyy => xxX yy => xxxyy.

В отличие от нисходящего, при восходящем синтаксическом анализе

этапы порождения определяются в противоположном порядке, то есть:

xxxyy=> xxX yy=> xXyy=> Xyy=> XyY=> XY=> S         .

Применение продукции  грамматики на каждом этапе предусматривает 

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

     При восходящем  синтаксическом анализе правые  части продукции 

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

1. Занесение последнего считанного символа  в стек - действие 

      переноса (SA-shift action) .

2. Замена строки наверху стека посредством применения  продукции грамматики - действие свертки (RA - reduce action) .

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