Простой парсер приоритета - Simple precedence parser

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

Реализация парсера очень похожа на общую восходящий парсер. Стек используется для хранения жизнеспособный префикс из сентенциальная форма из крайнее правое происхождение. Символы ${\displaystyle \lessdot }$, ${\displaystyle {\dot {=}}}$ и ${\displaystyle \gtrdot }$ используются для определения вращаться, и знать, когда Сдвиг или когда Уменьшать.

Выполнение

• Вычислить Отношение приоритета Вирта – Вебера стол.
• Начните со стека только с начальный маркер $.
• Начните с анализируемой строки (Вход) закончился конечный маркер $.
• Пока нет (стек равен $ S, а вход равен $) (S = начальный символ грамматики)
  • Найдите в таблице взаимосвязь между Top (стек) и NextToken (Input)
  • если отношения ${\displaystyle {\dot {=}}}$ или же ${\displaystyle \lessdot }$
    • Сдвиг:
    • Толкать (Стек, отношения)
    • Нажать (стек, следующий токен (ввод))
    • RemoveNextToken (ввод)
  • если отношения ${\displaystyle \gtrdot }$
    • Уменьшать:
    • SearchProductionToReduce (стек)
    • RemovePivot (Стек)
    • Найдите в таблице взаимосвязь между нетерминалом из производственной среды и первым символом в стеке (начиная с вершины)
    • Толкать (Стек, отношения)
    • Нажать (стек, без терминала)

SearchProductionToReduce (стек)

• искать Вращаться в стеке ближайший ${\displaystyle \lessdot }$ сверху
• искать в продуктах грамматики, одна из которых имеет ту же правую часть, что и Вращаться

Пример

Учитывая язык:

E -> E + T '| T'T '-> TT -> T * F | FF -> (E ') | numE '-> E

число это терминал, а лексер проанализировать любое целое число как число.

и таблица синтаксического анализа:

	E	E '	Т	Т '	F	+	*	(	)	число	$
E						${\displaystyle {\dot {=}}}$			${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$
E '									${\displaystyle {\dot {=}}}$
Т						${\displaystyle \gtrdot }$	${\displaystyle {\dot {=}}}$		${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$
Т '						${\displaystyle \gtrdot }$			${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$
F						${\displaystyle \gtrdot }$	${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$
+			${\displaystyle \lessdot }$	${\displaystyle {\dot {=}}}$	${\displaystyle \lessdot }$			${\displaystyle \lessdot }$		${\displaystyle \lessdot }$
*					${\displaystyle {\dot {=}}}$			${\displaystyle \lessdot }$		${\displaystyle \lessdot }$
(	${\displaystyle \lessdot }$	${\displaystyle {\dot {=}}}$	${\displaystyle \lessdot }$	${\displaystyle \lessdot }$	${\displaystyle \lessdot }$			${\displaystyle \lessdot }$		${\displaystyle \lessdot }$
)						${\displaystyle \gtrdot }$	${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$
число						${\displaystyle \gtrdot }$	${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$		${\displaystyle \gtrdot }$
$	${\displaystyle \lessdot }$		${\displaystyle \lessdot }$	${\displaystyle \lessdot }$	${\displaystyle \lessdot }$			${\displaystyle \lessdot }$		${\displaystyle \lessdot }$

ПРОЦЕДУРА СТЕКА ВХОДНОЕ ДЕЙСТВИЕ $ <2 * (1 + 3) $ SHIFT $ <2> * (1 + 3) $ REDUCE (F -> num) $  * (1 + 3) $ REDUCE (T -> F ) $  + 3) $ УМЕНЬШИТЬ 4 раза (F -> число) (T -> F) (T '-> T) (E -> T') $ ) $ УМЕНЬШИТЬ 3 раза (F -> число) (T -> F) (T '-> T) $ ) $ УМЕНЬШИТЬ 2 раза (E -> E + T) (E '-> E) $  $ УМЕНЬШИТЬ (F -> (E')) $  $ УМЕНЬШИТЬ (T -> T * F) $  $ УМЕНЬШИТЬ 2 раза (T '-> T) (E -> T') $  $ ACCEPT

Рекомендации

• Альфред В. Ахо, Джеффри Д. Ульман (1977). Принципы построения компилятора. 1-е издание. Аддисон-Уэсли.
• Уильям А. Барретт, Джон Д. Коуч (1979). Построение компилятора: теория и практика. Научный сотрудник.
• Жан-Поль Трембле, П. Г. Соренсон (1985). Теория и практика написания компиляторов. Макгроу-Хилл.