Особенности языков программирования

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

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

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

Язык, определяемый распознавателем  – это множество всех цепочек, которые допускает этот распознаватель.

 

Основные компоненты распознавателя.

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

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

Конфигурация распознавателя определяется следующими параметрами:

· содержимое входной цепочки символов и положение считывающей головки в ней;

·   состояние УУ;

·   содержимое внешней  памяти.

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

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

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

 

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

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

По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.

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

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

По видам устройства управления распознаватели бывают детерминированные и недетерминированные.

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

·          распознаватели без внешней памяти;

·          распознаватели с ограниченной внешней  памятью;

·          распознаватели с неограниченной внешней  памятью.

У распознавателей без  внешней памяти эта память полностью  отсутствует. В процессе их работы используется только конечная память устройства управления, доступ к внешней памяти не выполняется. Для распознавателей с ограниченной внешней памятью размер внешней  памяти ограничен в зависимости от длины исходной цепочки символов. Эти ограничения могут налагаться некоторой зависимостью объема памяти от длины цепочки. Кроме того, для таких распознавателей может быть указан способ организации внешней памяти — стек, очередь, список и т. п.Распознаватели с неограниченной внешней памятью предполагают, что для их работы может потребоваться внешняя память неограниченного объема (как правило, вне зависимости от длины входной цепочки). У таких распознавателей предполагается память с произвольным методом доступа. Вместе эти три составляющих позволяют организовать общую классификацию распознавателей. Например, в этой классификации возможен такой тип: «двусторонний недетерминированный распознаватель с линейно ограниченной стековой памятью».Чем выше в классификации стоит распознаватель, тем сложнее создавать алгоритм, обеспечивающий его работу. Разрабатывать двусторонние распознаватели сложнее, чем односторонние. Можно заметить, что недетерминированные распознаватели по сложности выше детерминированных. Зависимость затрат на создание алгоритма от типа внешней памяти также очевидна. Классификация распознавателей по типам распознаваемых языков Классификация распознавателей (вид входящих в состав распознавателя компонентов) определяет сложность алгоритма работы распознавателя. Но сложность распознавателя также напрямую связана с типом языка, входные цепочки которого может принимать (допускать) распознаватель. Для языков с фразовой структурой (тип 0) необходим распознаватель, равномощный машине Тьюринга — недетерминированный двусторонний автомат, имеющий неограниченную внешнюю память. Поэтому для языков данного типа нельзя гарантировать, что за ограниченное время на ограниченных вычислительных ресурсах распознаватель завершит работу и примет решение о том, принадлежит или не принадлежит входная цепочка заданному языку. Практическая реализация таких распознавателей чрезвычайно сложна. Для контекстно-зависимых языков (тип 1) распознавателями являются двусторонние недетерминированные автоматы с линейно ограниченной внешней памятью. Автоматы данного типа имеют экспоненциальную сложность: время, необходимое на разбор входной цепочки, экспоненциально зависит от длины входной цепочки символов. Такой алгоритм распознавателя может быть реализован в программном обеспечении компьютера — зная длину входной цепочки, всегда можно сказать, за какое максимально возможное время будет принято решение о принадлежности цепочки данному языку и какие вычислительные ресурсы для этого потребуются. Как правило, такие распознаватели применяются для автоматизированного перевода и анализа текстов на естественных языках, когда временные ограничения на разбор текста несущественны. После обработки естественно языковых текстов часто требуется ручное постредактирование.

Для контекстно-свободных  языков (тип 2) распознавателями являются односторонние детерминированные / недетерминированные автоматы с  магазинной (стековой) внешней памятью  — МП-автоматы. В общем случае, автоматы данного типа имеют экспоненциальную сложность, однако алгоритм можно усовершенствовать  так, чтобы его сложность стала  полиномиальной (кубической). Среди  всех КС-языков можно выделить класс  детерминированных КС-языков, распознавателями для которых являются детерминированные  автоматы с магазинной (стековой) внешней  памятью — ДМП-автоматы. Эти языки обладают свойством однозначности (доказано, что для любого детерминированного КС-языка всегда можно построить однозначную грамматику). Кроме того, для таких языков существует алгоритм работы распознавателя с квадратичной сложностью. Более того, среди детерминированных КС-языков существуют такие классы языков, для которых возможно построить линейный распознаватель (где время принятия решения о принадлежности цепочки языку имеет линейную зависимость от длины цепочки).

Для регулярных языков (тип 3) распознавателями являются детерминированные автоматы без внешней памяти — конечные автоматы (КА). Это очень простой тип распознавателя, который всегда предполагает линейную зависимость времени на разбор входной цепочки от ее длины. Кроме того, конечные автоматы имеют важную особенность: любой недетерминированный КА всегда может быть преобразован в детерминированный. Простота и высокая скорость работы распознавателей определяют широкую область применения регулярных языков.

 

Задача разбора

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

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

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

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

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

Теоретическая справка.

Недетерминированный конечный автомат (НКА) - это пятерка M = (Q, T, D, q₀, F), где

• Q - конечное множество состояний;
• T - конечное множество допустимых входных символов (входной алфавит);
• D - функция переходов (отображающая множество Q×(T {e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;
• q₀ Q - начальное состояние управляющего устройства;
• F Q - множество заключительных состояний.

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

 

 

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

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

Конечный автомат – это модель устройства с конечным числом состояний, которое отличает правильно образованные, или «допустимые» цепочки, от «недопустимых».

 

Составление формальной грамматики.

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

R0: <предложение> ::==< фраза>#

R1: <фраза> ::==< фраза>/< составное имя> | <идентификатор>

R2: <составное имя> ::==<составное имя>.<идентификатор>|<идентификатор>

R3: <идентификатор>::==<идентификатор><допустимый символ>|<начальный символ>

R4: <начальный символ>::==<буква>|<знак подчёркивания>

R5: <допустимый символ> :=:=<буква>|<цифра>|<знак подчёркивания>

R6:<буква>::==a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|

R7: <цифра>::==0|1|2|3|4|5|6|7|8|9|

R8:<знак подчёркивания>::==_

 

Таким образом, требуемую  грамматику можно описать следующей  структурой:

• Множество терминальных символов: 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,I,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,_, .,/,#
• Множество нетерминальных символов: <фраза>, < составное имя>, <идентификатор>, <допустимый символ>, <начальный символ>, <буква>, <цифра>,  <знак подчёркивания>.
• Множество правил вывода R0,R1, R2, R3, R4, R5, R6, R7, R8.

 

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

Между конечными  автоматами и автоматными грамматиками существует тесная связь: класс языков, допускаемых конечными автоматами, совпадает с классом языков, порождаемых  автоматными грамматиками.

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

Программное моделирование  работы конечного распознавателя.

#include "iostream.h"

#include "stdio.h"

#include "conio.h"

int main()

{  int i,j,kol,tsost,slsost,tsymb;

int tabl[9][40]={

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//da     {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//net     {1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,1,1,1},//sost imya     {7,7,7,7,7,7,7,7,7,7,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,2,1},//ident     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,1},//nach sim     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,1,1},//dop sim     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0},//bykva     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0},//cifra     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0}//znak

};printf("matrica\n");

for (i=0;i<9;i++) {for (j=0;j<40;j++) printf("%4d",tabl[i][j]); printf("\n");};

  char   ch, inpstr[80] ;

  printf("\n ENTER STRING  ");

  i=0;

 while ((ch=getch()) !=13 && i<80)

{putch(ch);

inpstr[i++]=ch;}

 inpstr[i]='\0';

 kol=i-1;

 printf("\n input string:");

 printf(inpstr);

 printf("\n");

     tsost=2;

     for (i=0;i<=kol;i=i+1)

     {   tsymb=inpstr[i];

     switch (tsymb)

 { case '0':  slsost=tabl[tsost][0]; break;

   case '1':  slsost=tabl[tsost][1]; break;

   case '2':  slsost=tabl[tsost][2]; break;

   case '3':  slsost=tabl[tsost][3]; break;