В информатике простой синтаксический анализатор приоритета — это тип восходящего синтаксического анализатора для контекстно-свободных грамматик , который может использоваться только простыми грамматиками приоритета .
Реализация парсера очень похожа на общий парсер снизу вверх . Стек используется для хранения жизнеспособного префикса сентенциальной формы из самого правого вывода . Символы ⋖, ≐ и ⋗ используются для идентификации опорной точки и для определения того, когда следует выполнить сдвиг или сокращение .
ПоискПроизводствоСнижение (Стек)
Дан следующий язык, который может анализировать арифметические выражения с операциями умножения и сложения:
Э --> Э + Т' | Т'Т' --> ТТ --> Т * Ф | ФF --> ( E' ) | числоЭ' --> Э
num — это терминал, и лексический анализатор анализирует любое целое число как num ; E представляет собой арифметическое выражение, T — это терм, а F — это фактор.
и таблица анализа:
ПРИОРИТЕТ СТЕКА ВХОДНОЕ ДЕЙСТВИЕ$ ⋖ 2 * ( 1 + 3 )$ СДВИГ$ ⋖ 2 ⋗ * ( 1 + 3 )$ УМЕНЬШИТЬ (F -> число)$ ⋖ F ⋗ * ( 1 + 3 )$ СОКРАЩЕНИЕ (T -> F)$ ⋖ T ≐ * ( 1 + 3 )$ СДВИГ$ ⋖ Т ≐ * ⋖ ( 1 + 3 )$ СДВИГ$ ⋖ Т ≐ * ⋖ ( ⋖ 1 + 3 )$ СДВИГ$ ⋖ T ≐ * ⋖ ( ⋖ 1 ⋗ + 3 )$ СОКРАЩЕНИЕ 4× (F -> число) (T -> F) (T' -> T) (E ->T ')$ ⋖ Т ≐ * ⋖ ( ⋖ Е ≐ + 3 )$ СДВИГ$ ⋖ Т ≐ * ⋖ ( ⋖ Е ≐ + ⋖ 3 )$ СДВИГ$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3 ⋗ )$ СОКРАТИТЬ 3× (F -> число) (T -> F) (T' -> T)$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T ⋗ )$ СОКРАЩЕНИЕ 2× (E -> E + T) (E' -> E)$ ⋖ Т ≐ * ⋖ ( ≐ Е' ≐ )$ СДВИГ$ ⋖ T ≐ * ⋖ ( ≐ E' ≐ ) ⋗ $ СОКРАЩЕНИЕ (F -> ( E' ))$ ⋖ T ≐ * ≐ F ⋗ $ СОКРАЩЕНИЕ (T -> T * F)$ ⋖ T ⋗ $ СОКРАЩЕНИЕ 2× (T' -> T) (E -> T')$ ⋖ E $ ПРИНЯТЬ