3622
правки
Изменения
расписана грамматика для арифметических выражений
Рассмотрим, как будут строиться множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> на примере грамматики арифметических выражений. Ограничимся только операциями сложения, умножения и наличием скобок. Числа будем обозначать одной буквой <tex> n </tex> для простоты. Интуитивная грамматики для арифметических выражений выглядит следующим образом:
<tex> E \to E + E \mid E \cdot times E \mid (E) \mid n </tex> Однако данная грамматика содержит [[Устранение левой рекурсии | левую рекурсию]], [[LL(k)-грамматики, множества FIRST и FOLLOW#Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW | правое ветвление]] и является [[Существенно неоднозначные языки#defambigous |неоднозначной]]. Чтобы избавиться от данных проблем неявно, можно придумать более удачную грамматику для языка арифметических выражений. Например, она может иметь следующий вид: <tex> E \to T + E \mid T \\T \to F \times T \mid F \\F \to n \mid (E)</tex> Данная грамматика содержит только правое ветвление, от которого можно избавиться левой факторизацией, после чего грамматика пример вид: <tex> E \to TE' \\E' \to +E \mid \varepsilon \\T \to FT' \\T' \to \times T \mid \varepsilon \\F \to n \mid (E)</tex> А затем для простоты анализирования раскрыть нетерминалы <tex> E </tex> и <tex> T </tex> в правилах для <tex> E' </tex> и <tex> T' </tex>. <tex> E \to TE' \\E' \to +TE' \mid \varepsilon \\T \to FT' \\T' \to \times FT' \mid \varepsilon \\F \to n \mid (E)</tex> === Конструирование FIRST для арифметических выражений ==={| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Правило!style="background-color:#EEE"| FIRST!style="background-color:#EEE"| FOLLOW|-|style="background-color:#FFF;padding:2px 30px"| <tex>A</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex>|style="background-color:#FFF;padding:2px 40px"| <tex>\{\ ),\ \$\ \} </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex>B</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ ),\ \$\ \} </tex>|}=== Конструирование FOLLOW для арифметических выражений ===
== См. также ==
* [[LL(k)-грамматики, множества FIRST и FOLLOW]]
