43310

Обработка методами типа «перенос-опознание»

Курсовая

Информатика, кибернетика и программирование

Управление автоматом задается управляющей таблицей типа : перенос опознание которая задает операцию ПЕРЕНОС ОТВЕРГНУТЬ или процедуру опознания для каждой комбинации магазинного и входного символов. Каждая из процедур опознания просматривает несколько верхних символов магазина и либо выбирает одну из операций СВЕРТКА для некоторого правила либо ДОПУСТИТЬ или ОТВЕРГНУТЬ. Первая из них состоит в том чтобы решить какие элементы таблицы управления должны содержать операции ПЕРЕНОС какие процедуры опознания и какие операции...

Русский

2013-11-04

289.5 KB

6 чел.

Министерство образования Украины

Харьковский  авиационный институт им. Н.Е.Жуковского

кафедра  №506

КУРСОВОЙ

ПРОЕКТ

По предмету : «Основы трансляции»

 Тема: «Обработка методами типа

                                           «переносопознание»

 Выполнили:  ст. гр. 535-б   Джос А.А.

          Педан М.И.

 Проверил:  Орехов А.А.

1997

Содержание

Введение 3

Управление автоматом типа «переносопознание» 4    

Бессуффиксные ПО-грамматики 7

Грамматики слабого предшествования 9

Простые грамматики смешанной стратегии предшествования 12

Вычисление отношений ПОД и СВЕРТЫВАЕТСЯ-ПО 15

Обработка ошибок при разборе типа «переносопознание» 19

Синтаксический блок для языка MINI-BASIC 21

Замечания по литературе 28

Введение

Цель данного проекта - описание  метода восходящего анализа, который является особым типом процессоров с магазинной памятью, использующих метод «перенос опознание». Соответствующие автоматы называют автоматами типа «перенос опознание». Точнее, когда говорится об автомате типа «переносопознание» для данной грамматики, имеется в виду автомат с такими свойствами:

Магазинные символы автомата это все символы данной грамматики и маркер дна.

Входные символы автомата это терминальные символы данной грамматики и концевой маркер.  

Управление автоматом задается управляющей таблицей типа : «перенос опознание», которая задает операцию ПЕРЕНОС, ОТВЕРГНУТЬ или процедуру опознания для каждой комбинации магазинного и входного символов.

Каждая из процедур опознания просматривает несколько верхних символов магазина и либо выбирает одну из операций СВЕРТКА для некоторого правила, либо ДОПУСТИТЬ или ОТВЕРГНУТЬ.

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

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

1. Управление автоматом типа «переносопознание»

В начале необходимо описать методы построения автомата типа «перенос - опознание» по данной грамматике. Удобно разделить задачу построения автомата на две части. Первая из них состоит в том, чтобы решить, какие элементы таблицы управления должны содержать операции ПЕРЕНОС,  какие процедуры опознания и какие операции ОТВЕРГНУТЬ. Вторая часть задачи, а именно отыскание подходящих процедур опознания, обсуждается в последующих разделах.

Теперь предположим, что у нас есть автомат типа «перенос -  опознание» для данной грамматики с начальным символом <S>. На каждом шаге обработки этим автоматом некоторой входной цепочки справедливо в точности одно из следующих утверждений. 

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

Входная цепочка допустима, содержимое магазина -   <S>, и текущий входной символ концевой маркер. 

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

Входная цепочка недопустима.

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

       По данной контекстно-свободной грамматике с начальным символом <S> грамматики x мы определим два множества :

       1.  СЛЕД ( x )

- множество входных символов (возможно, включающее ---|), которые могут непосредственно следовать за х  в некоторой промежуточной цепочке, выводимой  из <S>  ---| ,

       2.ПЕРВ ( х  )

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

       Множества ПЕРВ и СЛЕД для символов грамматики, изображенной на рис. 1. приведены на     рис. 2. Вычисление множеств первых символов начинается терминалом. Каждый символ грамматики принадлежит своему собственному множеству ПЕРВ.

       Множество СЛЕД (<S>) содержит концевой маркер, так как он следует за <S> в цепочке <S>  ---| . Это множество содержит также символ c  , так как c  следует за вхождением  <S> в правой  части правила 3. Из того, что <S>  входит в правую часть правила 1, вытекает принадлежность множеству СЛЕД (<S>) всех терминалов множества ПЕРВ (<B>), последнее, однако, состоит из   единственного   символа  c .

       Чтобы вычислить СЛЕД (<A>), заметим, что  <A> встречается в правых частях правил 1, 2 и 5. Благодаря вхождению его в правило 1, в СЛЕД (<A>) включаются  терминалы из множества ПЕРВ (<S>), а именно символ b . Вхождение в правило 2 добавляет входные символы из СЛЕД (<S>), а именно c  и  --| . А вхождение в правило 5 добавляет символ a .

       Остальные множества СЛЕД можно вычислить аналогичным образом .

<S> b <A>  <S>  <B>

<S> b  <A>

<A> d  <S>  c  a

<A> e

<B> c  <A>  a

<B> c

   Начальный символ : <S>

         Рис.   1

     Многие элементы управляющей таблицы можно заполнить на  основе простого наблюдения, какие из символов в  правых частях правил встречаются только в самой правой позиции, а какие - только в  других позициях. Например, символы b, d и <S> ни в одной правой части не встречаются в качестве самых правых  символов, и поэтому b, d, <S>  на верху магазина не могут быть крайними правыми символами основы. Следовательно, если один из этих символов находится на верху магазина, автомат благополучно может выполнить перенос любого входного символа (отличного от концевого маркера), и, значит, можно соответствующим образом заполнить элементы управляющей таблицы.

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

       Подобные простые соображения относительно заполнения управляющей таблицы неприменимы лишь в тех случаях, когда на верху магазина находится <A> или с . Не терминал <A> встречается  один раз в крайней правой позиции (правило 2) и дважды в других позициях (правила 1 и 5). То же относится и к символу с.

ПЕРВ   (<S>)  =  {b , <S>}           СЛЕД   (<S>)  =  { с, --|}

ПЕРВ   (<A>)  =  {d, e, <A>}   СЛЕД   (<A>)  =  { a, b, c, --|}

              ПЕРВ   (<B>)  =  {c, <B>}   СЛЕД   (<B>)  =  { c, --|}

  ПЕРВ   (a)  =  {a}     СЛЕД   (a)  =  { a, b, c , --|}

ПЕРВ   (b)  =  {b}    СЛЕД   (b)  =  { d, e}

 ПЕРВ   (c)  =  {c}    СЛЕД   (c)  =  { a, c, d, e, --|}

ПЕРВ   (d)  =  {d}    СЛЕД   (d)  =  { b }

ПЕРВ   (e)  =  {e}    СЛЕД    (e)  =  {a, b, c, --|}

   Рис.   2.

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

       На рис. 3 показаны три различные конфигурации и соответствующие им подрезанные деревья вывода для случаев, когда <A> находится на верху магазина. В ситуации, изображенной на рис. 3, в, справедливо утверждение 1, а в остальных двух случаях на рис. 3 истинно утверждение 3. Рис. 3,в  показывает, что элемент строки управляющей таблицы, соответствующей символу <A>, для входного символа с должен содержать процедуру опознания, а из рис. 3, a  и b  следует, что элементы этой строки для входных символов а и Ь должны содержать ПЕРЕНОС.

        Сначала найдем все входные символы х, такие, что элемент управляющей таблицы в строке <A> и столбце x  должен содержать процедуру опознания. Это означает, что нужно найти все входные символы x , для которых может возникнуть ситуация, соответствующая утверждению 1 с символом <A> на верху магазина и х  в качестве текущего входного символа. Ввиду того, что единственным вхождением <A> в правую часть, которое может заканчивать основу, является вхождение в правило 2, мы должны найти входные символы, которые могут следовать за <A> из правила 2 в выводе, начинающемся с <S> --|. Поскольку частью правила 2 является <S>, эта задача эквивалентна отысканию множества таких х, что x может следовать в некотором выводе за любым вхождением <S>. Это следует из того, что если x  следует за <S>,

                   <S>                                                     <S>

  b    <A>         <S>     <B>                                   b      <A>      <S>        <B>

                           c      <A>      a                                     b         <A>            c

    b <A> <S> c <A>               a --|     

                                           a           e

Рис. 3.       б   b <A>      b e c --|

    <S>

       b           <A>        <S>         <B>

   

                      b      <A>     c

   b <A> b <A> c --|

       в

Рис. 3. (продолжение)             

то после применения правила 2 x будет следовать за <A>, и, наоборот, если x следует за <A>, то соответствующая СВЕРТКА(2) помещает <S> из левой части правила перед x . Таким образом, искомое множество входных символов это СЛЕД(<S>). Согласно  рис. 2,

                                             СЛЕД (<S>) = {c, --| }

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

Теперь найдем все входные символы у, такие, при которых управляющая таблица в строке <A> и столбце у содержит ПЕРЕНОС. Это те входные символы, которые могут следовать за вхождениями <A> в правилах 1 и 5. За вхождением в правило 5 может следовать только а, что вытекает непосредственно из правой части правила 5. За вхождением <A> в правило 1 следует вхождение <S>, поэтому за <A> могут следовать входные символы множества ПЕРВ(<S>), а именно Ь. Объединяя эти два случая, мы заключаем, что ПЕРЕНОС требуется только для символов a  и b. Можно также заключить, что при обработке допустимой входной цепочки элементы строки <A> для входных символов d  и e  не будут использоваться, и каждый из этих элементов может содержать либо ОТВЕРГНУТЬ, либо ПЕРЕНОС, либо процедуру опознания.

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

   

      a

      b

          c

      d

      e

    --|

<S>

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

<A>

ПЕРЕНОС

ПЕРЕНОС

ОПОЗНАТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

<B>

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

a

ОПОЗНАТЬ

ОПОЗНАТЬ

ОПОЗНАТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

 b

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

 c

ПЕРЕНОС

ОТВЕРГНУТЬ

ОПОЗНАТЬ

ПЕРЕНОС

ПЕРЕНОС

ОПОЗНАТЬ

 d

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

e

ОПОЗНАТЬ

ОПОЗНАТЬ

ОПОЗНАТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

 

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

                                             Рис. 4.

содержаться процедуры опознания для входных символов из множества СЛЕД(<B>), а именно для с  и |. В правиле 3 за вхождением с следует a, поэтому для входных символов из ПЕРВ(а), т. е. для самого а, требуется ПЕРЕНОС. В правиле 5 за  с   следует <A>, значит, ПЕРЕНОС нужен также для входных символов из ПЕРВ(<A>), а именно для d и е. Все входные символы, для которых нужен ПЕРЕНОС, отличны от символов, для которых требуются процедуры опознания, и, значит, при построении строки для магазинного символа с  конфликтов не возникает.

На рис. 4 показана управляющая таблица для данного примера, построенная с учетом всех приведенных соображений. Она содержит ПЕРЕНОС и ОПОЗНАНИЕ там, где это необходимо, а всюду, где есть возможность выбора, используется операция ОТВЕРГНУТЬ. Чтобы завершить построение, осталось разработать процедуры опознания, выполняющие операцию ОПОЗНАТЬ, указанную в таблице.

2. Бессуффиксные ПО-грамматики

Рассмотрим автомат типа «перенос опознание» для грамматики на рис.1. Правые части правил этой грамматики обладают следующим свойством:  никакая правая часть не является суффиксом какой-либо другой правой части или цепочки     <S>. Поэтому всякая цепочка магазинных символов может оканчиваться не более чем одной основой или подцепочкой  <S>. Например, если цепочка символов магазина оканчивается символом с  , то правило 6 является единственным правилом, чья правая часть с окончанием этой цепочки независимо от того, какие магазинные символы находятся ниже с . Если цепочка символов магазина оканчивается подцепочкой c<A>a , то независимо от остальных символов магазина единственным правилом, чья правая часть совпадает с окончанием этой цепочки, является правило 5. Если же цепочка символов магазина оканчивается подцепочкой     <S>, то ни одна правая часть не совпадает с окончанием этой цепочки.

       Когда в процессе обработки допустимой входной цепочки выбирается процедура опознания, верхняя часть магазина представляет основу или цепочку     <S>. Следовательно, верхняя часть магазина должна совпадать с правой частью основывающего правила или с цепочкой   <S>. А так как на верху магазина может находиться лишь одна правая часть или цепочка    <S>, само присутствие некоторой правой части па верху магазина указывает на то, что эта правая часть в действительности является основой. Таким образом, когда процедура опознания обнаруживает в верхней части магазина правую часть правила р , она должна выбрать операцию СВЕРТКА (р ). Аналогично присутствие на верху магазина цепочки    <S> несовместимо с наличием в магазине какой-либо основы, и в этом случае правильным действием для процедуры опознания будет выбор операции ДОПУСТИТЬ, при условии что текущим входным символом является концевой маркер --| . Процедура опознания должна только выяснить, какая правая часть (или цепочка    <S>) совпадает с верхней частью магазина, и выбрать соответствующую операцию свертки (или операцию ДОПУСТИТЬ).

       Таким образом, для грамматики на рис.1 можно построить распознаватель типа «перенос опознание» с одной - единственной процедурой опознания. Процедура просто проверяет несколько верхних символов магазина на совпадение с правой частью какого-либо правила или с цепочкой    <S>. Если обнаружено совпадение с правой частью правила р , процедура выполняет операцию СВЕРТКА(р ). Если два верхних символа магазина образуют цепочку    <S>, процедура проверяет, является ли текущий входной символ концевым маркером, и если это так, то допускает входную цепочку. Если ни одна из вышеперечисленных ситуаций не имеет места, процедура отвергает вход. Таким образом, построение управляющей таблицы на рис. 4 можно дополнить следующей единственной процедурой опознания:

если на верху магазина  b<A><S><B> то СВЕРТКА (1)

иначе если на верху магазина  b<A> то СВЕРТКА (2)

иначе если на верху магазина  d<S>ca то СВЕРТКА (3)  

иначе если на верху магазина е  то СВЕРТКА (4)

иначе если на верху магазина c<A> a то СВЕРТКА (5)

иначе если на верху магазина с   то СВЕРТКА (6)

иначе если на верху магазина    <S>

      и текущий входной символ| то ДОПУСТИТЬ

иначе ОТВЕРГНУТЬ

       Этот «метод одной процедуры» не единственный способ завершить построение управляющей таблицы, и в определенном смысле он неэффективен. Более эффективное построение показано на рис. 5

      a

       b

       c

      d

     e

    --|

<S>

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  1

<A>

ПЕРЕНОС

ПЕРЕНОС

ОПОЗНАТЬ  2

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  2

<B>

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  3

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  3

a

ОПОЗНАТЬ  4

ОПОЗНАТЬ  4

ОПОЗНАТЬ  4

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  4

 b

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

 c

ПЕРЕНОС

ОТВЕРГНУТЬ

ОПОЗНАТЬ  5

ПЕРЕНОС

ПЕРЕНОС

ОПОЗНАТЬ  5

 d

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

e

ОПОЗНАТЬ  6

ОПОЗНАТЬ  6

ОПОЗНАТЬ  6

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  6

 

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

   Начальное содержимое магазина :

ПЕРЕНОС: ВТОЛКНУТЬ (текущий входной символ), СДВИГ

ОПОЗНАТЬ 1: если на верху магазина    <S>  то ДОПУСТИТЬ     иначе   ОТВЕРГНУТЬ

ОПОЗНАТЬ 2: если на верху магазина   b <A>  то СВЕРТКА(2)     иначе   ОТВЕРГНУТЬ

ОПОЗНАТЬ 3: если на верху магазина   b <A><S><B>  то СВЕРТКА  (1)      иначе   ОТВЕРГНУТЬ

ОПОЗНАТЬ 4: если на верху магазина   d <S> c a   то СВЕРТКА  (3)   

     иначе если на верху магазина c <A> a  то   СВЕРТКА (5)      иначе  ОТВЕРГНУТЬ

ОПОЗНАТЬ 5: СВЕРТКА (6)

ОПОЗНАТЬ 6: СВЕРТКА (4)

   Рис.  5.

где для каждой строки, содержащей на рис. 4 элементы с процедурами опознания, дается отдельная процедура.

        Например, процедура ОПОЗНАТЬ2 вызывается только тогда, когда верхним символом в магазине является <A>, а сама процедура построена с учетом того обстоятельства, что только правая часть правила 2 имеет символ  <A> в качестве самого правого символа. Процедура просто выясняет, присутствует ли в верхней части магазина правая часть правила 2, и в зависимости от результатов проверки либо выполняет свертку, либо отвергает вход. Процедура ОПОЗНАТЬ5 вызывается только тогда, когда верхним символом магазина является с ; эта процедура просто выполняет операцию СВЕРТКА(6), так как символ с  наверху магазина образует правую часть правила 6. Процедура ОПОЗНАТЬ4 единственная, которой приходится выбирать между двумя правилами, правые части которых оканчиваются символом а. Использование на рис. 5. условных операторов объясняется удобством описания и не означает предпочтительности такой реализации.

       Описанные методы построения применимы к классу грамматик, которые называются «бессуффиксными». Цепочка называется суффиксом цепочки , если оканчивается цепочкой .

Грамматика,  не имеющая конфликтов переноса опознания - бессуффиксная ПО-грамматика.

Грамматика на рис. 1 —бессуффиксная ПО-грамматика.

Построим процедуры опознания, которые:

выполняют операцию СВЕРТКА (р) в тех случаях, когда  верху магазина находится правая часть правила р  ;

2.допускают вход тогда и только тогда, когда магазин содержит цепочку  <S>  (где <S> начальный символ грамматики) и текущим входным  символом является концевой маркер.
3. Грамматики слабого предшествования

Если данная грамматика без конфликтов «переноса опознания» не является бессуффиксной, то управляющий механизм типа  «перенос опознание» для этой грамматики будет в некоторых случаях выбирать процедуру опознания, когда на верху магазина находятся несколько правых частей правил. Пусть, например, нам дана грамматика, изображенная на рис. 6, и мы хотим построить процедуру опознания, которая должна вызываться в тех случаях, когда верхним символом магазина является <T>. Эта процедура опознания должна выбирать одну из операций СВЕРТКА (1), СВЕРТКА(2) и ОТВЕРГНУТЬ.

       Правая часть правила 2 является суффиксом правой части правила 1. Если три верхних символа магазина составляют цепочку <E> + <T>, то правая часть каждого из этих правил совпадает с верхней частью магазина. Ясно, что при этом в одних  случаях основывающим правилом является правило 1, в других     правило 2. Предположим, однако, что в ситуации, когда на верху магазина <E> + <T>, выполняется СВЕРТКА(2). При выполнении этой операции <T> выталкивается из магазина (так что верхним символом становится +), а затем на его место вталкивается левая правила 2—нетерминал <E>.

<E>    <E> + <T>

<E>    <T>

<T>    <T> * <P>

<T>    <P>

<P>    (<E>)

<P>    a

 Начальный символ : <E>

 Рис.  6.  

  

       В грамматике на рис.6 символ + входит только в правило 1, и за  ним следует символ <T>. Поэтому все символы, которые при обработке допустимой входной цепочки могут оказаться в магазине непосредственно над символом  + , принадлежат множеству ПЕРВ(>). Просмотрев грамматику, можно вычислить

ПЕРВ(<T>) = {<T>, <P>, ( , a }

Ввиду того что символ <E> не принадлежит этому множеству, он не может оказаться в магазине непосредственно над символом + при работке допустимой цепочки, и. значит, если в верхней части магазина находится цепочка <E> + <T>, то правило 2 не является основывающим. Поэтому процедуру опознания нужно строить таким образом, чтобы в этом случае она выбирала операцию СВЕРТКА (1).   

       Для  описания принципа, иллюстрируемого приведенным примером, pacширим отношение ПОД следующим образом:

Если A и x  символы некоторой заданной грамматики, пишем

                                                                 A ПОД х

тогда и только тогда, когда существует грамматический символ В, такой, что цепочка A B содержится в правой части некоторого правила грамматики, и х принадлежит множеству ПЕРВ(В). Если х — символ грамматики,  пишем

                      ПОД х

тогда и только тогда, когда х принадлежит множеству ПЕРВ (<S>), где <S> — начальный символ грамматики.

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

       Если для данной грамматики имеется распознаватель типа «перенос - опознание» и заданы два магазинных символа A и x , то допустимая цепочка , при обработке которой символ A , существует тогда  и только тогда, когда

    A ПОД x

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

       Если данная грамматика содержит два правила вида

   <A>       y  

   <B>      

где      и    -- цепочки, а  y --  символ  грамматики, и если отношение  y  ПОД <B> не имеет места, то второе правило не может быть основывающим, если на верху магазина  находится часть первого правила. Таким образом, процедуры опознания для автомата типа «перенос – опознание», основанного на данной грамматике, можно построить так, что, если на верху магазина находятся обе правые части, операция свертки, соответствующая второму правилу, выполняться не будет.

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

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

В грамматике нет конфликтов переноса  --  опознания.

Правые части любых двух правил не совпадают.

Для любых двух правил вида

                  <A>     y  

    <B>    

где       и        --  цепочки, а y  --  символ, отношение

  y  ПОД  <B>

не имеет места.

Неверно, что  <S> +<S>,  где <S>  --  начальный символ.

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

если наверху магазина <E> + <T> то СВЕРТКА (1)

иначе если наверху магазина <T> то СВЕРТКА (2)

но было бы неправильно писать :

если наверху магазина <T> то СВЕРТКА (2)

иначе если наверху магазина <E> + <T> то СВЕРТКА (1)

       Вернемся к нашему примеру. На рис. 7 изображены множества ПЕРВ  и СЛЕД для всех нетерминалов грамматики, приведенной на рис.6 .

  ПЕРВ  (<E>) = {( , a , <E>, <T>, <P>} 

  ПЕРВ  (<T>) = {( , a , <T>, <P>}

  ПЕРВ  (<P>) = {( , a , <P>}

  СЛЕД  (<E>) = {+ , ) , --|}

  СЛЕД  (<T>) = {+ , * , ) , --|}

  СЛЕД  (<P>) = {+ , * , ) , --|}

 

   Рис.  7.

Отношение ПОД для этой грамматики показано в виде матрицы на рис.8. Как было показано выше, отношение +ПОД<E> не выполняется, поэтому конфликт суффиксов между правилами 1 и 2 можно разрешить в пользу более длинного правила. Точно так же не имеет места отношение *ПОД<T>, и, значит, конфликт суффиксов между правилами 3 и 4 разрешается в пользу более длинного правила. Так как других конфликтов суффиксов, а также конфликтов переноса – опознания в грамматике нет, то она является грамматикой слабого предшествования.

На рис. 9 изображен автомат типа «перенос опознание» для данной грамматики .Отметим, что процедуры ОПОЗНДТЬ2 и ОПОЗНАТЬЗ сначала выполняют проверку для более длинных правых частей.

   Y

+ * a ( ) <E> <T> <P>

  +         1 1       1     1

  *   1 1        1

  a

X            (   1 1    1     1     1    

  )

<E> 1    1

<T>  1

<P>

    1 1    1    1     1

    Х  ПОД  Y

   Рис.  8.

       +

       *

       а

      (

      )

    --|

<E>

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ОПОЗНАТЬ  1

<T>

ОПОЗНАТЬ  2

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  2

ОПОЗНАТЬ  2

<P>

ОПОЗНАТЬ  3

ОПОЗНАТЬ  3

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  3

ОПОЗНАТЬ  3

 +

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

 *

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

 a

ОПОЗНАТЬ  4

ОПОЗНАТЬ  4

ПЕРЕНОС

ОТВЕРГНУТЬ

ОПОЗНАТЬ  4

ОПОЗНАТЬ  4

 (

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

)

ОПОЗНАТЬ  5

ОПОЗНАТЬ  5

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ  5

ОПОЗНАТЬ  5

 

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

 Начальное содержимое магазина :

ОПОЗНАТЬ 1:  если на верху магазина  <E> то ДОПУСТИТЬ  иначе  ОТВЕРГНУТЬ

ОПОЗНАТЬ 2:  если на верху магазина  <E> + <T> то СВЕРТКА (1)

            иначе  СВЕРТКА (2)

ОПОЗНАТЬ 3:  если на верху магазина <T>*<P> то СВЕРТКА(3)

                                иначе СВЕРТКА(4)

ОПОЗНАТЬ 3:  СВЕРТКА(6)

ОПОЗНАТЬ 4:  если на верху магазина <E> то СВЕРТКА(5)

                               иначе ОТВЕРГНУТЬ

ПЕРЕНОС :        ВТОЛКНУТЬ (текущий входной символ), СДВИГ

                                                       Рис. 9.

         

4.Простые грамматики смешанной стратегии предшествования

Если данная грамматика удовлетворяет всем условиям в определении грамматики слабого предшествования, кроме условия 2 (т. е . содержит несколько правил с одинаковыми правыми частями),то в некоторых случаях все же можно построить для этой грамматики  автомат типа «перенос опознание. Дана грамматикана рис. 10.

 <S>    <B> v

<S>    v <C>

<A>    u

<A>    v <B> <S>

<B>    u

<B>    yw

<C>    <B> v

<C>    y <A> w

  Начальный символ: <S>

   Рис. 10.

       Множества ПЕРВ и СЛЕД для  символов этой грамматики показаны на рис.11. Отношение ПОД изображено на рис.12, а на рис.13 показана управляющая таблица, построенная согласно этим отношениям. Конфликты переноса опознания отсутствуют. Эта грамматика не является грамматикой слабого предшествования, так как правила 1 и 7 имеют одну и ту же правую часть <B>v, а правила 3 и 5 одну и ту же правую часть u. Чтобы построить процедуры опознания для этой грамматики, нужны какие-то средства для определения основывающего правила в тех случаях, когда в верхней части магазина находится <B>v или u.

       Сначала рассмотрим ситуацию, в которой на верху магазина находится <B>v, а управляющий механизм вызывает процедуру  опознания.    Процедура    опознания должна выбрать операцию СВЕРТКА(1), если основывающим является правило 1, или операцию СВЕРТКА(7), если основывающим является правило 7. Покажем, каким образом процедура опознания может сделать такой выбор, используя символ, находящийся в магазине под <B>v. В частности, покажем, что правило 1 может быть основывающим только тогда, когда под <B>v в магазине находится <B> или    , а правило 7 — только тогда, когда под <B>v находится v. Поэтому процедура опознания, способная определить символ под правой частью <B>v, может сделать удовлетворительный выбор между операциями СВЕРТКА (1) и СВЁРТКА(7).

ПЕРВ (<S>) = {<S>, <B>, u, v, y}   СЛЕД (<S>) = { w, --| }

ПЕРВ (<A>) = {<A>, u, v}    СЛЕД (<A>) = { w }

ПЕРВ (<B>) = {<B>, u, y}      СЛЕД (<B>) = { u, v, y }

ПЕРВ (<C>) = {<B>, <C>, u, y}    СЛЕД (<C>) = { w, --| }

ПЕРВ (u) = { u }      СЛЕД (u) = { u, v, y, --| }

ПЕРВ (v) = {v}      СЛЕД (v) = { u, w, y, --| }

ПЕРВ (w) = {w}      СЛЕД (w) = { u, v, w, y, --| }

ПЕРВ (y) = {y}      СЛЕД (y) = { u, v, w }

   Рис. 11.

    Y

<S> <A> <B> <C> u v w y

<S>    

<A>        1

<B>    1     1  1 1  1

<C>

    X   u

  v      1    1  1   1

w

y        1    1 1 1

    1     1   1 1  1

    Х  ПОД  Y

   Рис.  12.

 

      u

          v

      w

     y

    --|

<S>

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

<A>

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

<B>

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

<C>

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

ОТВЕРГНУТЬ

ОПОЗНАТЬ

 u

ОПОЗНАТЬ

ОПОЗНАТЬ

ОПОЗНАТЬ

ОПОЗНАТЬ

ОТВЕРГНУТЬ

 v

ПЕРЕНОС

ОТВЕРГНУТЬ

ОПОЗНАТЬ

ПЕРЕНОС

ОПОЗНАТЬ

 w

ОПОЗНАТЬ

ОПОЗНАТЬ

ОПОЗНАТЬ

ОПОЗНАТЬ

ОПОЗНАТЬ

y

ПЕРЕНОС

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

ОТВЕРГНУТЬ

ПЕРЕНОС

ПЕРЕНОС

ОТВЕРГНУТЬ

ПЕРЕНОС

ОТВЕРГНУТЬ

   Рис. 13.

Чтобы показать, что правило 1 может быть основывающим только тогда, когда под <B>v в магазине находится <B> или , рассмотрим действие операции СВЕРТКА (1). Это действие состоит в заменe  <B>v левой частью <S>, после чего <S> оказывается в магазине над тем символом, который раньше находился под <B>v. Согласно принципу вталкивания, при обработке допустимой входной цепочки под символом <S> в магазине могут появиться только такие магазинные символы X, для которых Х ПОД <S>. Все такие символы приведены на рис.12, это <B> и . Чтобы показать, что правило 7 может быть основывающим только тогда, когда под <B>v находится символ v, заметим, что действие операции СВЕРТКА (7) состоит в замене <B>v на <С> и что v единственный магазинный символ X, для которого Х ПОД <C>.

       Теперь рассмотрим тот случай, когда на верху магазина находится и и выбирается процедура опознания. Левыми частями правил 3 и 5 являются соответственно символы <A> и <B>. На рис.12 видно, что при обработке допустимой входной цепочки под этими нетерминалами в магазине могут оказаться следующие символы:

У    ПОД <A>  

         <В>        ПОД <В>

            v          ПОД <В>

  ПОД <B>

       Поэтому, если под u находится у, то основывающим правилом может быть только правило 3, а если под и находится <B>, v или , то основывающим может быть только правило 5.

       Автомат типа «перенос опознание» для этого примера показан на рис. 14. 

А ПОД <B>

      u

       v

       w

      y

    --|

<S>

ОПОЗНАТЬ  1

ОПОЗНАТЬ  2

<A>

<B>

ПЕРЕНОС

ПЕРЕНОС

ПЕРЕНОС

<C>

ОПОЗНАТЬ  3

 u

ОПОЗНАТЬ  4

ОПОЗНАТЬ  4

ОПОЗНАТЬ  4

ОПОЗНАТЬ  4

 v

ПЕРЕНОС

ОПОЗНАТЬ  5

ПЕРЕНОС

ОПОЗНАТЬ  5

 w

ОПОЗНАТЬ  6

ОПОЗНАТЬ  6

ОПОЗНАТЬ  6

ОПОЗНАТЬ  6

ОПОЗНАТЬ  6

y

ПЕРЕНОС

ПЕРЕНОС

 

ОТВЕРГНУТЬ

ПЕРЕНОС

ПЕРЕНОС

 Начальное содержимое магазина:

ОПОЗНАТЬ 1: если на верху магазина v<B><S> то СВЕРТКА (4)

 иначе ОТВЕРГНУТЬ

ОПОЗНАТЬ 2: если на верху магазина <S> то ДОПУСТИТЬ

 иначе ОПОЗНАТЬ 1

ОПОЗНАТЬ 3: если на верху магазина v<C> то СВЕРТКА (2)

 иначе ОТВЕРГНУТЬ

ОПОЗНАТЬ 4: если на верху магазина yu то СВЕРТКА (3)

 иначе, если на верху магазина <B>u или vu или u то СВЕРТКА (5)

 иначе ОТВЕРГНУТЬ

ОПОЗНАТЬ 5: если на верху магазина <B><B>v или V<B>v то СВЕРТКА (1)

 иначе если на верху магазина v<B>v то СВЕРТКА (7)

 иначе ОТВЕРГНУТЬ

ОПОЗНАТЬ 6: если на верху магазина yw, то СВЕРТКА (6)

 иначе если на верху магазина y<A>w то СВЕРТКА (8)

 иначе ОТВЕРГНУТЬ

ПЕРЕНОС:  ВТОЛКНУТЬ (текущий входной символ), СДВИГ

Рис.14.
5. Вычисление отношений ПОД и СВЕРТЫВАЕТСЯ-ПО

Цель этого раздела построить процедуру вычисления отношений ПОД и СВЕРТЫВАЕТСЯ-ПО. Этой процедурой можно пользоваться для выявления конфликтов  переноса  опознания, для построения управляющего механизма, для про-

Построить отношение НАЧИНАЕТСЯ-ПРЯМО-С.

Построить отношение ПРЯМО-НА-КОНЦЕ.

Построить отношение ПРЯМО-ПЕРЕД.

Вычислить отношение  , определяемое как

   ПРЯМО-ПЕРЕДНАЧИНАЕТСЯ-ПРЯМО-С* 

Вычислить отношение •>, определяемое как

ПРЯМО-НА-КОНЦЕ+<=

           6.   Расширить  до отношения ПОД, добавив все пары (, X), такие, что

< S > НАЧИНАЕТСЯ-ПРЯМО-С* Х

  где < S >—начальный символ.

7.   Расширить •> до отношения СВЕРТЫВАЕТСЯ-ПО, добавив все пары (X,|), такие, что

  Х ПРЯМО-НА-КОНЦЕ* < S >

  где < S >— начальный символ.

Рис. 15. Процедура вычисления отношений ПОД и СВЕРТЫВАЕТСЯ-ПО.

верки принадлежности грамматики к классу грамматик слабого предшествования и к классу простых ССП-грамматик, а также для построения процедур опознания по простым ССП-грамматикам. Общая схема процедуры вычисления ПОД и СВЕРТЫВАЕТСЯ-ПО изображена на рис. 15. Процедура использует три примитивных отношения, которые вычисляются непосредственно по грамматике (шаги 1, 2 и 3), и операции над отношениями, описанные в приложении Б.

Шаг 1 состоит в построении отношения НАЧИНАЕТСЯ-ПРЯМО-С. Если в данной грамматике нет Е-правил, то для символов А и В мы пишем

А НАЧИНАЕТСЯ-ПРЯМО-С В

тогда и только тогда, когда грамматика содержит правило вида

А В

где    произвольная цепочка.

Отношение НАЧИНАЕТСЯ-ПРЯМО-С для грамматики рис.16 показано на рис.17. а.

Оно получается по грамматике путем перебора всех правил и заполнения соответствующих элементов матрицы. Например, левая часть правила 1 — это символ <S>, а правая часть этого правила начинается с<A>; поэтому элемент строки <S> и столбца <A> помечается единицей. Строки матрицы, соответствующие терминальным символам, не могут содержать единиц, так как терминал не может           быть левой частью правила, но для полноты эти строки на рисунке показаны.

 <S> <A> z

<S> y z

<A> <B><B><S>

<A> d

<B> y x <A>

<B> x <A>

   Начальный символ: <S>

    Рис. 16.

       Шаг 2 процедуры состоит в построении отношения ПРЯМО-НА-КОНЦЕ. Если в данной грамматике нет Е-правил, то для символов грамматики А и В мы пишем

А ПРЯМО-НА-КОНЦЕ В

тогда и только тогда, когда грамматика содержит правило вида

В   А

где произвольная цепочка.

Отношение ПРЯМО-НА-КОНЦЕ для рассматриваемой грамматики показано на рис. 17,б. Оно получается по грамматике путем перебора всех правил и заполнения соответствующих элементов матрицы. Например, левая часть правила 1 - это символ <S>, а правая часть оканчивается символом z. Поэтому элемент строки z и столбца <S> помечается единицей. Столбцы матрицы, соответствующие терминальным символам, не могут содержать помеченных элементов, но для полноты они также показаны на рисунке.

<S>  <A>  <B>    d    x    y    z   <S>  <A>  <B>    d    x    y    z

<S>    1      1     <S>            1

<A>          1     1      <A>         1

<B>             1    1     <B>

 d           d            1

 x            x

 y           y

 z           z   1

 начинается - прямо - с    прямо - на - конце    

  а      б

<S>  <A>  <B>    d    x    y    z   <S>  <A>  <B>    d    x    y    z

<S>        <S>

<A>                         1    <A>            1

<B>  1        1                    <B>   1       1      1      1     1    1

 d           d

 x   1         x            1      1      1     1    1

 y             1          1       y             1    1

 z           z

 

 прямо - перед      <=

  в      г.

<S>  <A>  <B>    d    x    y    z   <S>  <A>  <B>    d    x    y    z

<S>    1      1      1     1        1    1     <S>

<A>   1      1      1    1    1     1     <A>             1

<B>                      <B>    1      1      1      1    1     1

 d   1      1      1       1    1     1    1       d 

 x            x            1      1      1    1     1

 y           y       1    1

 z   1      1      1       1    1     1    1       z

          V    1      1      1      1    1     1

  >

  д      под

          е         Рис.  17.     

<S>  <A>  <B>    d    x    y    z   --|

<S>   1       1      1       1    1   1    1     1 

<A>   1       1      1       1    1    1      

<B>                      

 d  1       1      1       1    1    1    1          

 x            

 y           

 z  1       1      1       1    1    1    1     1         

 свертывается - по

  ж

      Рис.17.  (продолжение)

Шаг 3 описываемой процедуры состоит в построении отношения ПРЯМО-ПЕРЕД. Если в данной грамматике нет -правил, то для ее символов А и В мы пишем:

 А ПРЯЛЮ-ПЕРЕД В

тогда и только тогда, когда грамматика содержит правило вида

D   А В   

где и  -  произвольные цепочки.

Отношение ПРЯМО-ПЕРЕД для грамматик без Е-правил исторически получило обозначение = , которое иногда читают как «равно по предшествованию», хотя оно и не является отношением эквивалентности. На рис.17.в показано это отношение для рассматриваемой грамматики. Оно получается по грамматике путем перебора всех правых частей правил и заполнения элементов матрицы, соответствующих парам соседних символов. Так, посмотрев на правую часть правила 1, получаем

<A> ПРЯМО-ПЕРЕД z

Правило 3 дает

  <B> ПРЯМО-ПЕРЕД  <B>

 и

<B> ПРЯМО-ПЕРЕД  <S>

Шаг 4 нашей процедуры состоит в вычислении отношения  , определяемого как произведение отношений:

ПРЯМО-ПЕРЕД •НАЧИНАЕТСЯ-ПРЯМО-С *

Мы используем обозначение  ,так как это отношение является  объединением отношения = и еще одного отношения, обычно обозначаемого <• и определяемого как

ПРЯМО-ПЕРЕДНАЧИНАЕТСЯ-ПРЯМО-С +

(обратите внимание на + вместо *). Знак < иногда читают как «меньше по предшествованию», хотя обозначаемое им отношение и не является транзитивным, как арифметическое отношение «меньше». Чтобы вычислить  нужно взять рефлексивно - транзитивное замыкание отношения НАЧИНАЕТСЯ-ПРЯМО-С, а затем вычислить указанное  выше произведение. Для рассматриваемой грамматики результат показан на рис.17,г. Заметим, что рефлексивно-транзитивное замыкание отношения НАЧИНАЕТСЯ - ПРЯМО - С описывает множества ПЕРВ; т.е. символ В принадлежит ПЕРВ (С) тогда и только тогда, когда

 С  НАЧИНАЕТСЯ - ПРЯМО - С  *  В

Таким образом, указанное выше произведение связывает каждый грамматический символ А с символами множества ПЕРВ) для каждого С, непосредственно следующего за А в правой части правила. Другими словами,  это отношение ПОД, без маркера дна.

Шаг 5 процедуры состоит в вычислении отношения •> как произведения 

ПРЯМО-НА-КОНЦЕ +

Отношение > называют «больше по предшествованию», хотя в отличие от арифметического отношения «больше» оно не транзитивно. Результат указанного вычисления для рассматриваемой грамматики показан на рис. 17, д. Заметим, что отношение •> можно выразить как

ПРЯМО-НА-КОНЦЕ . (ПРЯМО-НА-КОНЦЕ *)

Отношение, заключенное в скобки, описывает множества СЛЕД без концевого маркера, т. е. символ грамматики В принадлежит СЛЕД (С) тогда и только тогда, когда

С(ПРЯМО-НА-КОНЦЕ *) В

Таким образом, отношение > связывает каждый символ грамматики А с символами множества СЛЕД (С) дли каждого нетерминала С, который является левой частью правила, оканчивающегося символом А. Поэтому для любого символа грамматики А и терминала х A СВЕРТЫВАЕТСЯ-ПО х тогда и только тогда, когда А > х .

Теперь можно сравнить отношения  и •> чтобы посмотреть, нет ли конфликтов переноса—опознания. Доопределение этих отношений до отношений ПОД и СВЕРТЫВАЕТСЯ-ПО путем включения маркера дна и концевого маркера не влияет на результат этой проверки.

Шаг 6 состоит в расширении до ПОД путем отыскания таких Х, что

<S> НАЧИНАЕТСЯ-ПРЯМО-С * Х

(где <S> - начальный символ) и заполнения единицами элементов, соответствующих таким Х в добавленной к матрице строке для маркера дна. Если в процессе вычисления на шаге 4 была получена матрица для отношения НАЧИНАЕТСЯ-ПРЯМО-С * то строку <S> этой матрицы можно добавить к матрице для в качестве строки маркера дна. Для нашего примера результат показан на рис. 17,е. Столбцы, представляющие нетерминалы, не используются при построении управляющей таблицы, но применяются при проверке грамматики на слабое предшествование и при построении процедур опознания для простых ССП-грамматтик.

Шаг 7 состоит в расширении •> до отношения СВЕРТЫВАЕТСЯ-ПО путем отыскания таких X, что

Х ПРЯМО-НА-КОНЦЕ * <S>

(где <S> начальный символ) и заполнения единицами элементов, соответствующих этим X, в добавленном к матрице столбце для концевого маркера. Для нашего примера результат показан рис. 17, ж. При этом столбцы для нетерминалов не включаются в матрицу отношения СВЕРТЫВАЕТСЯ-ПО, так как второй компонентой пары, входящей в это отношение, является по предложению входной символ. Шаг 7 завершает процедуру.
6.Обработка ош
ибок при разборе типа «переносопознание»

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

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

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

Существуют два типа ситуаций, в которых автомат типа «перенос - опознание» отвергает вход:

а) при обращении к элементу управляющей таблицы, содержащему операцию ОТВЕРГНУТЬ;

б) при вызове процедуры опознания, которая выбирает эту операцию.

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

       СЛЕДУЕТ ЗА

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

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

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

Пусть, например, грамматика содержит правило

  <S> IF <B> THEN <S1> ELSE <S1>

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

   ELSE <S1> 

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

  IF <B> THEN <S1> ELSE <S1> ELSE <S1>

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

ELSE <S1> ELSE <S1>

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

КОНСТРУКЦИЯНЕДОПУСТИМА

В результате получится

КОНСТРУКЦИЯ ELSE ОПЕРАТОР ELSE ОПЕРАТОР; НЕДОПУСТИМА

Если считается, что эта ошибка очень распространена, то обнаружение конструкции можно рассматривать как особый случай и сообщение об ошибке сделать более специальным:

ДВА ПОСЛЕДОВАТЕЛЬНЫХ ELSE-ПРЕДЛОЖЕНИЯ
7.
Синтаксический блок для языка MINI-BASIC

В этом разделе построим синтаксический блок для языка MINI-BASIC на основе     S-атрибутной грамматики польского перевода, входная грамматика которой является простой грамматикой смешанной стратегии предшествования. Работа синтаксического блока состоите том, что, полечив цепочку лексем, созданную лексическим блоком , он выдает в качестве выхода цепочку атомов, которая затем будет использована генератором кода.

Начнем с рассмотрения простой ССП-грамматики, лежащей в основе перевода. Эта грамматика приведена на рис. 18.

Множество терминалов грамматики состоит из лексем. Пять арифметических операций представлены пятью лексемами. Лексема ПРИСВ соответствует слову LET, за которым следует знак =, а лексема СТРОКА соответствует номеру строки, с которого она начинается.

Заметим, что правило 11 порождает как FOR-оператор, так и соответствующий ему NEXT-оператор. Правила для FOR-оператора построены таким образом, чтобы последующее введение символов действия привело к грамматике польского перевода.

Можно легко убедиться в том, что грамматика на рис.18 является простой ССП-грамматикой.

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

На рис. 19 приведена грамматика польского перевода, а на рис. 20 - S-атрибутная транслирующая грамматика. Смысл большинства атрибутов нетерминалов очевиден. Единственный нетерминал, имеющий более одного атрибута,—это FOR-оператор. Первым его атрибутом является указатель на табличный элемент для переменной цикла; второй атрибут это указатель на табличный элемент для значения шага цикла: третий и четвертый атрибуты это указатели на табличные элементы для двух меток, участвующих в цикле, а пятый атрибут содержит номер строки, в которой появляется FOR-оператор. Этот пятый атрибут используется процедурой действия {КОНТРОЛЬ} как часть предупредительного сообщения в том случае, если соответствующий NEXT-оператор ссылается на переменную, отличную от переменной цикла.

При построении атрибутной грамматики предполагалось, что существуют три процедуры для отведения табличных элементов: НОВТ, НОВТХ и НОВТАМ. НОВТ дает указатель на новый табличный элемент для промежуточного результата; НOBTX дает указатель на новый табличный элемент для результата атома ХРАНЕНИЕ; а НОВТАМ дает указатель на новый табличный элемент для метки. Каждый из этих типов табличных элементов содержит определенные поля, нужные генератору кода. В некоторые из этих полей процедуры НОВТ, НОВТХ и НОВТАМ должны при отведении элемента помещать начальные значения. Нам нужно  знать, что HOBT, HOBTX и HOBTAM дают соответствующие указатели.

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

Структура программы

<программа> <список операторов> КОНЕЦ

<список операторов> <список операторов> <оператор> СТРОКА

<список операторов> СТРОКА

Пустой оператор

<список операторов> <список операторов> СТРОКА

Оператор присваивания

<оператор>   ПРИСВОИТЬ <выражение>

GOTO-оператор

<оператор> ПЕРЕХОД НА

IF-оператор

<оператор> ЕСЛИ <выражение> ОТНОШЕНИЕ

<выражение>  <если-переход>

<если-переход>   ПЕРЕХОД НА

GOSUB-оператор

<оператор> ПЕРЕХОД НА ПОДПР

 RETURN-оператор

<оператор> ВОЗВРАТ

FOR-оператор

<оператор> <для-оператор> <список операторов> КОНЕЦ ЦИКЛА

<для-оператор> <для-предложение> <до-предложение> ШАГ <выражение>

<для-оператор> <для-предложение> <до-предложение>

<для-предложение> ДЛЯ <выражение>

<до-предложение> ДО <выражение>

REM-оператор

<оператор> КОММЕНТАРИЙ

Выражения

<выражение> <выражение> + <терм>

<выражение> <выражение> - <терм>

<выражение> + <терм>

<выражение> - <терм>

<выражение> <терм>

<терм> <терм> * <множитель>

<терм> <терм> / <множитель>

<терм> <множитель>

<множитель> <множитель> ^ <первичное>

<множитель> <первичное>

<первичное> (<выражение>)

<первичное> ОПЕРАНД

Начальный символ: <программа>

 Рис. 18. Простая ССП-грамматика для синтаксического блока

    MINI-BASIC-компилятора.


Структура программы

<программа> <список операторов> КОНЕЦ

<список операторов> <список операторов> <оператор> СТРОКА

{НОМСТРОК}{УСТАНОВИТЬ НОМЕР СТРОКИ}

<список операторов> СТРОКА {НОМСТРОК}{УСТАНОВИТЬ НОМЕР СТРОКИ}

Пустой оператор

<список операторов> <список операторов> СТРОКА {НОМСТРОК}{УСТАНОВИТЬ НОМЕР СТРОКИ}

Оператор присваивания

<оператор>   ПРИСВОИТЬ <выражение> {ПРИСВ}

GOTO-оператор

<оператор> ПЕРЕХОД НА {ПЕРЕХОД}

IF-оператор

<оператор> ЕСЛИ <выражение> ОТНОШЕНИЕ

<выражение>  <если-переход> {УСЛПЕРЕХОД}

<если-переход>   ПЕРЕХОД-НА

GOSUB-оператор

<оператор> ПЕРЕХОД НА ПОДПР {ХРАНПЕРЕХОД}

 RETURN-оператор

<оператор> ВОЗВРАТ {ВОЗВПЕРЕХОД}

FOR-оператор

<оператор> <для-оператор> <список операторов> КОНЕЦ ЦИКЛА {КОНТРОЛЬ} {УВЕЛИЧ} {ПЕРЕХОД} {МЕТКА}

<для-оператор> <для-предложение> <до-предложене> ШАГ <выражение> {ХРАНЕНИЕ} {МЕТКА} {ПРОВЕРКА}

<для-оператор> <для-предложение> <до-предложение>{ХРАНЕНИЕ} {МЕТКА} {ПРОВЕРКА}

<для-предложение> ДЛЯ <выражение> {ПРИСВ}

<до-предложение> ДО <выражение> {ХРАНЕНИЕ}

REM-оператор

<оператор> КОММЕНТАРИЙ

Выражения

<выражение> <выражение> + <терм> {СЛОЖ}

<выражение> <выражение> - <терм> {ВЫЧИТ}

<выражение> + <терм> {ПЛЮС}

<выражение> - <терм> {МИНУС}

<выражение> <терм>

<терм> <терм> * <множитель> {УМНОЖ}

<терм> <терм> / <множитель> {ДЕЛЕН}

<терм> <множитель>

<множитель> <множитель> ^ <первичное> {ЭКСП}

<множитель> <первичное>

<первичное> (<выражение>)

<первичное> ОПЕРАНД

Начальный символ: <программа>

 Рис. 19. Грамматика польского перевода для синтаксического блока

   MINI-BASIC-компилятора.

 Все атрибуты символов действия НАСЛЕДУЕМЫЕ.

Описание процедуры действия {УСТАНОВИТЬ НОМЕР СТРОКИ} p

   НОМЕР СТРОКИ  p

Описание процедуры действия {КОНТРОЛЬ} p, w, y

 IF p <> w THEN печатать предупреждающее сообщение

Структура программы

<программа> <список операторов> КОНЕЦ

<список операторов> <список операторов> <оператор> СТРОКА p1

{НОМ СТРОК p2} {УСТАНОВИТЬ НОМЕР СТРОКИ} p3

 (p2, p3) p1

<список операторов> СТРОКАp1 {НОМСТРОКp2} {УСТАНОВИТЬ НОМЕР СТРОКИ}p3

(p2, p3) p1

Пустой оператор

<список операторов> <список операторов> СТРОКАp1 {НОМСТРОКp2}            {УСТАНОВИТЬ НОМЕР СТРОКИ}p3

(p2, p3) p1

Оператор присваивания

<оператор>   ПРИСВОИТЬ p1 <выражение>q1 {ПРИСВ p2,q2}

p2   p1 q2 q1

GOTO-оператор

<оператор> ПЕРЕХОД НАp1 {ПЕРЕХОДp2}

p2 p1

IF-оператор

<оператор> ЕСЛИ <выражение>p1 ОТНОШЕНИЕ r1 <выражение>q1  <если-переход> s1 {УСЛПЕРЕХОД p2, q2, r2, s2}

p2 p1  q2 q1  r2 r1  s2 s1

<если-переход>s2   ПЕРЕХОД-НА s1

s2 s1

GOSUB-оператор

<оператор> ПЕРЕХОД НА ПОДПР p1 {ХРАНПЕРЕХОД}p2

p2 p1

 RETURN-оператор

<оператор> ВОЗВРАТ {ВОЗВПЕРЕХОД}

FOR-оператор

<оператор> <для-оператор> p1, t1, u1, v1, y1 <список операторов> КОНЕЦ ЦИКЛА w1 {КОНТРОЛЬ}p2, w2, y2 {УВЕЛИЧ p3, t2} {ПЕРЕХОД u2} {МЕТКА v2}

(p2, p3) p1 w2 w1 y2 y1

t2 t1  u2 u1  v2 v1

<для-оператор> p3, t3, u3, v3, y  <для-предложение>p1 <до-предложене>s1 ШАГ <выражение>x1 {ХРАНЕНИЕ x2, t1} {МЕТКА u1} {ПРОВЕРКА p2, s2, t2, v1}

(t1, t2, t3) HOBNX

(u1, u2) HOBTAM s2 s1

(v1, v2) HOBTAM y  НОМЕР СТРОКИ

(p2, p3) p1  x2 x1

<для-оператор>p3, t3, u2, v2, y   <для-предложение>p1 <до-предложение>p1 {ХРАНЕНИЕx, t1}  {МЕТКА u1} {ПРОВЕРКА p2, s2, t2, v1}

(t1, t2, t3) HOBTX

(u1, u2) HOBTAM s2 s1

(v1, v2) HOBTAM y – НОМЕР СТРОКИ

(p2, p3) p1

x указатель на табличный  элемент для константы 1

 Рис. 20.  S-атрибутная грамматика для синтаксического блока

   MINI-BASIC-компилятора.

<для-предложение>p3   ДЛЯ p1 <выражение>q1 {ПРИСВ p2, q2}

(p2, p3) p1 q2 q1

<до-предложение>s2  ДО <выражение>r1 {ХРАНЕНИЕ r2, s1}

r2 r1  (s1, s2) HOBTX

REM-оператор

<оператор> КОММЕНТАРИЙ

Выражения

<выражение> r2   <выражение>p1 + <терм>q1 {СЛОЖ p2, q2, r1}

(r1, r2) HOBT  p2   p1 q2  q1

<выражение> r2   <выражение>p1  - <терм>q1 {ВЫЧИТ p2, q2, r1}

(r1, r2) HOBT  p2   p1 q2  q1

<выражение>r2   + <терм>p1 {ПЛЮС p2, r1}

(r1, r2) HOBT  p2 p1

<выражение>r2   - <терм>p1 {МИНУС p2, r1}

(r1, r2) HOBT  p2 p1

<выражение>r2   + <терм>p1 

p2 p1

<терм> r2   <терм>p1 * <множитель>q1 {УМНОЖ p2, q2, r1}

(r1, r2) HOBT  p2   p1 q2  q1

<терм> r2   <терм>p1 / <выражение>q1 {ДЕЛЕН p2, q2, r1}

(r1, r2) HOBT  p2   p1 q2  q1

<терм>r2  <множитель>r1

r2 r1

<множитель>r2  <множитель>r1 ^ <первичное>q1 {ЭКСП p2, q2, r1}

(r1, r2) HOBT  p2 p1  q2 q1

<множитель>r2  <первичное>r1

r2 r1

<первичное>r2  (<выражение>r1)

r2 r1

<первичное>r1  ОПЕРАНД r1

r2 r1

Начальный символ: <программа>

 Рис.20. (продолжение)

 

Теперь можно описать процессор с магазинной памятью. На рис. 21 приведен магазинный алфавит с указанием полей всех символов.

На рис.22 показана управляющая таблица. Элементы, помеченные буквой П, соответствуют операции ПЕРЕНОС. Для каждой строки задана отдельная процедура опознания. Элементы, помеченные греческими буквами, соответствуют ошибочным ситуациям.

      СТРОКА       -

        Значение лексемы СТРОКА

     *

      ОПЕРАНД     

       Значение лексемы  ОПЕРАНД      /

         

              ОТНОШЕНИЕ       ^

       Значение лексемы ОТНОШЕНИЕ       <программа>

         

                   КОНЕЦ ЦИКЛА      <список операторов>

   Значение лексемы КОНЕЦ ЦИКЛА

           <оператор>

             ПРИСВОИТЬ     

    Значение лексемы ПРИСВОИТЬ     <для - оператор>

         #1

         ДЛЯ        #2

Значение лексемы ДЛЯ      #3

         #4

              ПЕРЕХОД  НА       #5

     Значение лексемы  ПЕРЕХОД  НА

        <для - предложение>

            ПЕРЕХОД  НА  ПОДПР      #1

Значение лексемы ПЕРЕХОД НА ПОДПР

    <до - предложение>

      (        #1

   

      )          <выражение>

         #1

 ЕСЛИ

                 <терм>

          ВОЗВРАТ       #1

 КОНЕЦ           <множитель>

         #1

   ДО     

            <первичное>

  ШАГ        #1

     КОММЕНТАРИЙ      <если - переход>

         #1

     +      

              

     Рис. 21.

          с      о    о      к     п    д     п     п     л      п       е      в      к     д      ш        к     +     -     *        /               о     к

          т      п    т      о     р    л     е     е      е      р      с       о      о     о      а        о                                              ш     о

          р е    н      н     и     я    р     р.    в .     а      л       з      н              г        м                                              и     н

          о     р    о      е     с            е                     в.     и       в      е                       м                                              б     ц

          к     а    ш      ц     в           х.     н     с                        р     ц                        е                                              к

          а     н    е                                   а     к      с       в       а                               н                                              а     м

  д   н       ц                  н             о      к       о       т                                т                                                     а

        и      и                  а      п     б      о       з                                        а                                                      р

         е      к           о     к      б.      в             р .                                                    к .

Строка  1               1     1     1     1     1                 1      1      1                  1                                          

операнд            2           2                  2                2                       2       2            2      2      2       2      2             

отношение               П                                  П                                              П      П                              

конец цикла           3                                                                                                                          

присв                П                                  П                                              П       П                             

для                П                                  П                                              П       П                             

переход на           4                                                                                                                          

переход на подпр           5                                                                                                                          

левая скобка               П                                  П                                              П        П                            

правая скобка           6          6                    6                6                        6     6            6         6     6        6      6           

если возврат               П                                  П                                              П        П                            

возврат            7                                                                                                                          

конец                                                                                                                                      

до                П                                   П                                              П       П                             

шаг                П                                   П                                              П       П                             

комментарий           9                                                                                                                           

+               П                                   П                                                                                   

-               П                                   П                                                                                   

*               П                                   П                                                                                    

 /               П                                   П                                                                                   

                П                                   П                                                                                   

<программа>                                                                                                                                           10

список операторов       П                П     П    П      П    П                П       П      П                   П                                        

оператор           П                                                                                                                                

для-оператор           П                                                                                                                                 

для-предложение                                                                                    П                                                        

до-предложение           11                                                                               П                                               

выражение                      12       П                      П               П                        12      12            П                                    

терм            13       13                    13             13                        13      13           13     13     П       П              

множитель           14       14                    14             14                        14      14           14     14    14      14     П        

первичное           15       15                    15             15                         15     15            15    15    15      15    15        

если-переход           16                                                                                                                                

             П                                                                                                                                     

     Рис. 22

    

8. Замечания по литературе

Ф. ЛЬЮИС, Д. РОЗЕНКРАНЦ, Р. СТИРНЗ «Теоретические  основы  проектирования   компиляторов»

Глава 12.  Обработка методами типа          «перенос-опознание»


 

А также другие работы, которые могут Вас заинтересовать

13530. Сокрытие информации в субтитрах 198.5 KB
  Сокрытие информации в субтитрах Подготовка к работе По указанной литературе и методическим указаниям изучить основные понятия стеганографии и криптографии уяснить принцип сокрытия информации в субтитрах. Ответить на контрольные вопросы. Контроль
13531. Проведення реєстрації осіб, які виявили бажання пройти зовнішнє незалежне оцінювання 172 KB
  Урок інформатики Проведення реєстрації осіб які виявили бажання пройти зовнішнє незалежне оцінювання в 2013 році. Робота з програмою створення заявиреєстраційної картки. Тема уроку: Проведення реєстрації осіб які виявили бажання пройти зовнішнє незалежне оцін...
13532. Системы счисления и двоичное представление информации в памяти компьютера 218 KB
  Системы счисления и двоичное представление информации в памяти компьютера. Что нужно знать: перевод чисел между десятичной двоичной восьмеричной и шестнадцатеричной системами счисления см. презентацию Системы счислени
13533. Использование информационных моделей (таблицы, диаграммы, графики) 822 KB
  Тема: Использование информационных моделей таблицы диаграммы графики. Перебор вариантов выбор лучшего по какомуто признаку. Что нужно знать: в принципе особых дополнительных знаний кроме здравого смысла и умения перебирать варианты не пропустив ни од...
13534. Построение таблиц истинности логических выражений 501.5 KB
  Тема: Построение таблиц истинности логических выражений. Про обозначения К сожалению обозначения логических операций И ИЛИ и НЕ принятые в серьезной математической логике  неудобны интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Ав...
13535. Файловая система 188.5 KB
  Тема: Файловая система. Что нужно знать: данные на дисках хранятся в виде файлов наборов данных имеющих имя чтобы было удобнее разбираться с множеством файлов их объединяют в каталоги в Windows каталоги называются папками каталог можно воспринимать как ко...
13536. Проверка закономерностей методом рассуждений 134 KB
  A5 базовый уровень время – 2 мин Тема: Проверка закономерностей методом рассуждений. Что нужно знать: в общемто никаких знаний из курса информатики здесь не требуется эту задачу можно давать детям начальной школы для развития логического мышления в задачах ...
13537. Поиск и сортировка информации в базах данных 1.19 MB
  Тема: Поиск и сортировка информации в базах данных. Что нужно знать: при составлении условия отбора можно использовать знаки отношений меньше или равно больше или равно не равно последовательность выполнения логических операций в сложных ...
13538. Электронные таблицы 455 KB
  Тема: Электронные таблицы. Что нужно знать: адрес ячейки в электронных таблицах состоит из имени столбца и следующего за ним номера строки например C15 формулы в электронных таблицах начинаются знаком = равно знаки –/ и в формулах означают соответстве...