Методические указания (1114907), страница 10

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

Текст из файла (страница 10)

Определение: Грамматика, в которой нет продукций, правые части которых представляют собой ε или имеют два соседних нетерминала, называются операторными грамматиками (operator grammar).

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

Определение: При синтаксическом анализе приоритета операторов мы определим три непересекающихся отношения приоритетов (predence relations) - ∙>, <∙, - между терминалами. Эти отношения приоритетов управляют выбором основ и имеют следующее содержание.

В отличие от арифметических отношений “меньше”, “равно”, “больше”, отношения приоритетов имеют совершенно иные свойства. Например, в одном и том же языке может быть так, что a <∙ b, и a ∙> b, или для некоторых терминалов a и b не выполняется ни одно из отношений a <∙ b, a ∙> b и a b.

Имеется два обычных способа определения отношений приоритетов, которые должны выполняться между терминалами. Первый метод – интуитивный. Он основан на традиционных понятиях ассоциативности и приоритета операторов. Например, если * имеет приоритет выше, чем +, то

* ∙> +. Такой подход разрешает неоднозначности грамматики и позволяет написать для нее анализатор приоритета операторов (хотя унарный минус и вызывает определенные проблемы).

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

В данной задаче будет рассмотрен первый метод.

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

Вход. Входная строка w и таблица отношений приоритетов.

Выход. В случае корректной строки w – скелетное дерево разбора с маркером – нетерминалом E, помечающим внутренние узлы; в противном случае – сообщение об ошибке.

Алгоритм. Вначале стек содержит $, а входной буфер – w$.

Устанавливаем указатель ip на первый символ w$.

repeat forever

if на вершине стека находится $ и ip указывает на $

then return

else begin

Пусть a – терминал на вершине стека, а b – символ, на который указывает ip.

if a <∙ b или а b then begin

Поместить b в стек

Переместить ip к следующему входному символу

end

else if a ∙> b then

repeat

Снять со стека

until Терминал на вершине стека связан отношением <∙ с последним снятым терминалом

else error()

end

Алгоритм .1.

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

Правила построения таблицы приоритетов операторов.

1. Если оператор θ₁ имеет более высокий приоритет, чем оператор θ₁, определим, что θ₁ ∙> θ₂ и θ₂ <∙ θ₁.

2. Если θ₁ и θ₂ представляют собой операторы равного приоритета (в частности, это может быть один и тот же оператор), то устанавливаем, что θ₁ ∙> θ₂ и θ₂ ∙> θ₁, если операторы левоассоциативны, и θ₁ <∙ θ₂ и θ₂ <∙ θ₁ в случае правоассоциативности.

3. Для всех операторов θ определяем отношения θ <∙ id, id ∙> θ, θ <∙ (, ( <∙ θ, ) ∙> θ, θ ∙> ), θ ∙> $, $ <∙ θ. Кроме того считаем, что ( ), $ <∙ (, $ <∙ id, ( <∙ (, id ∙> $, ) ∙> $, ( <∙ id, id ∙> ), ) ∙> ).

Обработка унарных операторов.

Если в грамматике имеется унарный оператор типа ¬ (логическое отрицание), который не имеет бинарного аналога, то его можно внести в описанную выше схему для создания отношений приоритета операторов. Предполагая, что ¬ - унарный префиксный оператор, мы определяем, что θ ∙> ¬ для любого оператора θ, независимо от того, унарный он или бинарный. Кроме того, устанавливаем, что ¬ ∙> θ, если ¬ имеет более высокий приоритет, чем θ, и ¬ <∙ θ в противном случае.

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

Функции приоритета.

Компиляторы, использующие синтаксические анализаторы приоритета операторов не нуждаются в хранении отношений приоритетов. В большинстве случаев таблица может быть закодирована двумя функциями приоритетов (precedence functions) f и g, отображающими терминальные символы в целые числа. Мы пытаемся выбрать f и g такими, чтобы для символов a и b было справедливо:

• f(a) < g(b) при a <∙ b

• f(a) = g(b) при a b

• f(a) > g(b) при a ∙> b

Таким образом, отношение приоритетов между a и b можно определить сравнением числовых значений f(a) и g(b). Заметим, однако, что при этом теряется смысл пустых ячеек таблицы, информирующих об ошибке, поскольку всегда выполняется одно из трех приведенных условий, независимо от того, чему равны f(a) и g(b). Потеря возможности обнаружения ошибок, вообще говоря, не считается достаточно серьезной, чтобы отказаться от использования функций приоритета там, где это возможно; ошибки могут быть обнаружены при вызове процедуры свертки для необнаруженной основы.

Не всякая таблица отношений приоритетов имеет функции приоритета для ее кодирования, но обычно на практике эти функции существуют.

Алгоритм построения функций приоритетов.

Вход. Матрица приоритетов операторов.

Выход. Функции приоритетов, представляющие входную матрицу, либо сообщение, что такие функции не существуют.

Алгоритм.

1. Создаем символы f_a и g_a для каждого символа a, являющегося терминалом или $.

2. Разделим созданные символа на как можно большее число групп таким образом, что если a b, то f_a и g_b принадлежат одной группе. Возможно, нам придется поместить в одну группу символы, даже не связанные отношением . Например, если a b и b с, то f_a и f_c должны находиться в одной и той же группе, поскольку они оба находятся в той же группе, что и g_b. Если ,кроме того, c d, то f_a­ и g_d находятся в одной группе, даже если не выполняется условие a d

3. Создадим ориентированный граф, узлы которого представляют собой группы, найденные в (2). Для всех a и b, если a <∙ b, проведем дугу из группы f_a­ в g_b. Отметим, что дуга (или путь) от f_a к g_b означает, что f(a) превосходит g(b); путь от g_b к f_a означает, что g(b) должно превосходить f(a).

4. Если построенный в (3) граф имеет циклы, это говорит о том, что функции приоритетов для данной таблицы не существует. Если циклов нет, то значением f(a) служит длина самого длинного пути, начинающегося в группе f_a; соответственно, значение g(a) равно длине самого длинного пути из группы g_a.

Алгоритм .2.

Условие:

1. По операторной грамматике и описанию приоритетов и ассоциативности операторов построить таблицу приоритетов.

2. Построить функции приоритетов для данной грамматики.

3. Разобрать 3 выражения с помощью таблицы приоритетов. (1 правильное выражение, 2 неправильных)

Варианты:

Опишем операторную грамматику:

1. E -> E + E

2. E -> E – E

3. E -> E * E

4. E -> E / E

5. E -> E % E

6. E -> E ^ E

7. E -> E & E

8. E -> E # E

9. E -> + E

10. E -> - E

11. E -> * E

12. E -> / E

13. E -> % E

14. E -> ^ E

15. E -> & E

16. E -> # E

17. E -> (E)

18. E -> id

Приоритеты операторов возрастают снизу вверх:

+, -

*, /

%, ^

&, #

Ассоциативность операторов:

Левоассоциативные: +, -, *, /, %

Правоассоциативные: ^, #, &

1. acegirq

2. bcfhjrq

3. adfgkrq

4. bcfhlrq

5. acfgmrq

6. abcgnrq

7. abfgorq

8. cdegprq

9. abegirq

10. bcegjrq

11. acehkrq

12. bcehlrq

13. adehmrq

14. abchnrq

15. cdehorq

16. aefgprq

17. acefirq

18. cdfhjrq

19. abehkrq

20. adeglrq

21. bcfgmrq

22. adfhnrq

23. bdfgorq

24. abdgprq

25. abfhirq

26. cdfgjrq

27. abdhkrq

28. bdfhlrq

29. acfhmrq

30. bdegnrq

Пример построения операторной грамматики:

1. abcdfjqr:

• E -> E + E (a)

• E -> E – E (b)

• E -> E * E (c)

• E -> E / E (d)

• E -> E ^ E (f)

• E -> - E (j)

• E -> (E) (q)

• E -> id (r)

1. Для того, чтобы избежать конфликтов заменим правило E -> -E на E -> uE, где u обозначает унарный минус.

Построим таблицу приоритетов операторов для данной грамматики.

По условию:

+ <∙ *, - <∙ *, + <∙ /, - <∙ /, * <∙ ^, / <∙ ^, + <∙ ^, - <∙ ^, + <∙ u, - <∙ u, * <∙ u, / <∙ u, ^ <∙ u. Поэтому в силу правила 1* ∙> +, * ∙> -, / ∙> +, / ∙> -, ^ ∙> *, ^ ∙> /, ^ ∙> +, ^ ∙> -, u ∙> +, u ∙> -, u ∙> *, u ∙> /, u ∙> ^.

Операторы +, - имеют одинаковый приоритет, а также левоассоциативные, поэтому в силу правила 2 + ∙> +, + ∙> -, - ∙> +, - ∙> -.

Операторы *, / имеют одинаковый приоритет, а также левоассоциативные, поэтому в силу правила 2 * ∙> *, * ∙> /, / ∙> *, / ∙> /.

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

Оператор ^ является правоассоциативным, поэтому в силу правила 2 ^ <∙ ^.

Остальные ячейки таблицы заполняются в соответствии с правилом 3.

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

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

Характеристики

Список файлов книги