Изменения

Предиктивный синтаксический анализ

2625 байт добавлено, 15:21, 25 мая 2015

→‎Пример

=== Пример ===

Рассмотрим пример работы нерекурсивного парсера на всё той же грамматике арифметических выражений. Для начала пронумеруем все правила: {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Номер!style="background-color:#EEE"| Правило|-|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>1</tex> ~~(1) \~~ |style="background-color:#FFF;padding:2px 10px"| <tex>E \to TE' \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>2~~) \~~ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>E' \to +TE' \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>3~~) \~~ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>E' \to \varepsilon \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>4~~) \~~ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>T \to FT' \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>5~~) \~~ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>T' \to ~~\times~~ * FT' \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>6~~) \~~ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>T' \to \varepsilon \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>7~~) \~~ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>F \to n \\</tex>|-(|style="background-color:#FFF;padding:2px;text-align:center;"| <tex>8~~) \~~ </tex>|style="background-color:#FFF;padding:2px 10px"| <tex>F \to (E)</tex>|} Теперь можно построить часть таблицы <tex>\mathcal{M}</tex>, содержащей строки, отвечающие нетерминалам. Её построение легко осуществить, если известны <tex>\mathrm{FIRST}</tex> и <tex>\mathrm{FOLLOW}</tex>. По сути по этим множествам можно понять, какое правило использовать для данного нетерминала при текущем токене.

{| style="background-color:#CCC;margin:0.5px"

!style="background-color:#EEE"|

!style="background-color:#EEE;text-align:center;"| <tex>n</tex>!style="background-color:#EEE;text-align:center;"| <tex>(</tex>!style="background-color:#EEE;text-align:center;"| <tex>)</tex>!style="background-color:#EEE;text-align:center;"| <tex>+</tex>!style="background-color:#EEE;text-align:center;"| <tex>*</tex>!style="background-color:#EEE;text-align:center;"| <tex>\$</tex>

|-