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

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

Реализация парсера очень похожа на обычный восходящий парсер . Стек используется для хранения жизнеспособного префикса из предложенной формы крайнего правого вывода . Символы ⋖, ≐ и ⋗ используются для обозначения точки поворота и для определения того, когда смещать , а когда уменьшать .

Выполнение

• Вычислите таблицу отношений предшествования Вирта – Вебера для грамматики с начальным символом S.
• Инициализируйте стек стартовым маркером $.
• Добавьте конечный маркер $ к анализируемой строке ( Input ).
• Пока стек не станет равным «$ S», а вход не станет равным «$».
  • Найдите в таблице связь между Top(stack) и NextToken(Input).
  • если отношение ⋖ или ≐
    • Сдвиг :
    • Push(стек, связь)
    • Push(Стек, СледующийТокен(Вход))
    • RemoveNextToken (Вход)
  • если отношения ⋗
    • Уменьшать :
    • SearchProductionToReduce (стек)
    • Удалить опорную точку из стека
    • Найдите в таблице связь между нетерминалом из продукции и первым символом в стеке (начиная сверху).
    • Push(стек, связь)
    • Push(Стек, Нетерминал)

SearchProductionToReduce (стек)

• Найдите самый верхний ⋖ в стопке; этот и все символы над ним — это точка поворота .
• Найдите произведение грамматики, находится ось . в правой части которой

Пример

Дан следующий язык, который может анализировать арифметические выражения с помощью операций умножения и сложения:

E  --> E + T' | T'
T' --> T
T  --> T * F  | F
F  --> ( E' ) | num
E' --> E

num — это терминал, и лексер анализирует любое целое число как num ; E представляет собой арифметическое выражение, T — термин, а F — фактор.

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

	И	И'	Т	Т'	Ф	+	*	(	)	в	$
И						≐			⋗
И'									≐
Т						⋗	≐		⋗		⋗
Т'						⋗			⋗		⋗
Ф						⋗	⋗		⋗		⋗
+			⋖	≐	⋖			⋖		⋖
*					≐			⋖		⋖
(	⋖	≐	⋖	⋖	⋖			⋖		⋖
)						⋗	⋗		⋗		⋗
в						⋗	⋗		⋗		⋗
$	⋖		⋖	⋖	⋖			⋖		⋖

STACK                   PRECEDENCE    INPUT            ACTION

$                            ⋖        2 * ( 1 + 3 )$   SHIFT
$ ⋖ 2                        ⋗        * ( 1 + 3 )$     REDUCE (F -> num)
$ ⋖ F                        ⋗        * ( 1 + 3 )$     REDUCE (T -> F)
$ ⋖ T                        ≐        * ( 1 + 3 )$     SHIFT
$ ⋖ T ≐ *                    ⋖        ( 1 + 3 )$       SHIFT
$ ⋖ T ≐ * ⋖ (                ⋖        1 + 3 )$         SHIFT
$ ⋖ T ≐ * ⋖ ( ⋖ 1            ⋗        + 3 )$           REDUCE 4× (F -> num) (T -> F) (T' -> T) (E ->T ') 
$ ⋖ T ≐ * ⋖ ( ⋖ E            ≐        + 3 )$           SHIFT
$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ +        ⋖        3 )$             SHIFT
$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3    ⋗        )$               REDUCE 3× (F -> num) (T -> F) (T' -> T) 
$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T    ⋗        )$               REDUCE 2× (E -> E + T) (E' -> E)
$ ⋖ T ≐ * ⋖ ( ≐ E'           ≐        )$               SHIFT
$ ⋖ T ≐ * ⋖ ( ≐ E' ≐ )       ⋗        $                REDUCE (F -> ( E' ))
$ ⋖ T ≐ * ≐ F                ⋗        $                REDUCE (T -> T * F)
$ ⋖ T                        ⋗        $                REDUCE 2× (T' -> T) (E -> T')
$ ⋖ E                                 $                ACCEPT

Ссылки

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