Пример 23

Нахождение отношений приоритетов операторов

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

1. Если оператор θ₁ имеет более высокий приоритет, чем оператор θ₂, определяем что θ₁ > θ ₂ и θ ₂ < •θ₁. Например, если оператор * имеет более высокий приоритет, чем оператор +, то * •> + и + <• *. Эти отношения гарантируют, что при получении выражения вида E+E*E+E основой является E*E, и именно E*E будет свернуто первым.

2. Если θ₁ и θ ₂ представляют собой операторы равного приоритета (это может быть один и тот же оператор), то устанавливаем, что θ₁ •> θ ₂ и θ ₂ •> θ₁, если операторы левоассоциативны, и θ₁ <• θ₂ и θ₂ <• θ₁ в случае правоассоциативности. Например для левоассоциативных + и - устанавливаем, что +•>-, -•>- и - •> +. Для правоассоциативного оператора ↑ следует принять, что ↑<• ↑. Такие отношения гарантируют, что в выражении E-E+E основой является E-E, а в e ↑ e ↑ e — последнее выражение E↑E.

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

(=) $<•($<• id

(<• ( id •> $) •> $

(<• id id •>)) •>)

Эти правила гарантируют, что и id, и (E) будут приведены к E. Кроме того, $ служит как левым, так и правым маркером конца строки, что заставляет основы находится между ними.

На рис. 34 приведены отношения приоритета операторов для грамматики (7.1) в предположении, что:

1. оператор ↑ имеет высший приоритет и правоассоциативен;

2. операторы * и / имеют приоритет следующего уровня и левоассоциативны;

3. операторы + и - имеют низший приоритет и левоассоциативны.

Пустые ячейки означают ошибки.

	+	-	*	/	↑	id	(	)	$
+	•>	•>	<•	<•	<•	<•	<•	•>	•>
-	•>	•>	<•	<•	<•	<•	<•	•>	•>
*	•>	•>	•>	•>	<•	<•	<•	•>	•>
/	•>	•>	•>	•>	<•	<•	<•	•>	•>
↑	•>	•>	•>	•>	<•	<•	<•	•>	•>
id	•>	•>	•>	•>	•>			•>	•>
(	<•	<•	<•	<•	<•	<•	<•	=
)	•>	•>	•>	•>	•>			•>	•>
$	<•	<•	<•	<•	<•	<•	<•

Рис. 34. Отношения приоритета операторов

7.4.5 Обработка ошибок переноса/свертки

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

Один из способов гарантировать отсутствие зацикливания — это обеспечить возможность переноса символа после восстановления (если текущий символ — $, следует убедиться, что во входной поток не вставляются новые символы, а стек в конце концов прекращается). Например, при ab в стеке и cd во входной строке, если а≤ • с, мы можем снять со стека b. Другой способ — удаление из входного потока с при b≤ • d. Третий способ заключается в поиске такого е, что b ≤ • е ≤ • с, и вставке е во входной поток с. В более общем виде, если единственный символ для вставки найти не удается, мы можем вставить строку символов, такую, что b ≤ •е ₁ ≤ • е_г≤ •… ≤ • e_n ≤ • с.

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

Дата добавления: 2014-12-27