LL(k)-грамматики, множества FIRST и FOLLOW — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (LL(k)-грамматика)
(FIRST и FOLLOW: добавлены примеры)
Строка 34: Строка 34:
 
Другими словами, <tex> \mathrm{FIRST}(\alpha) </tex> {{---}} все символы (терминалы), с которых могут начинаться всевозможные выводы из <tex> \alpha </tex>, а <tex> \mathrm{FOLLOW}(A) </tex> {{---}} всевозможные символы, которые встречаются после нетерминала <tex> A </tex> во всех правилах грамматики.
 
Другими словами, <tex> \mathrm{FIRST}(\alpha) </tex> {{---}} все символы (терминалы), с которых могут начинаться всевозможные выводы из <tex> \alpha </tex>, а <tex> \mathrm{FOLLOW}(A) </tex> {{---}} всевозможные символы, которые встречаются после нетерминала <tex> A </tex> во всех правилах грамматики.
 
=== Примеры ===
 
=== Примеры ===
{{TODO | t = Какие-нибудь примеры}}
+
Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.
 +
 
 +
* <tex> A \rightarrow (A)A \mid \varepsilon </tex>
 +
* <tex> B \rightarrow BB \mid (B) \mid \varepsilon </tex>
 +
 
 +
 
 +
{| 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"| A
 +
|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"| B
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\  \varepsilon\ \} </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ ),\  \$\ \} </tex>
 +
|}
  
 
== Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW ==
 
== Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW ==

Версия 12:25, 28 июня 2014

Эта статья находится в разработке!

Наибольший интерес в построении синтаксических анализаторов (парсеров) представляют LL(1)-грамматики, так как для них возможно построение нисходящих парсеров без возврата, то есть без корректировки выбранных правил в грамматике. LL(1)-грамматики являются подмножеством КС-грамматик. Однако для достаточно большого количества формальных языков можно построить LL(1)-грамматику, например, для языка арифметических выражений и даже для некоторых языков программирования, в частности можно и для языка Java.

LL(k)-грамматика

Дадим теперь формально определение LL(k)-грамматики.

Определение:
Пусть [math]\Gamma =\langle \Sigma, N, S, P \rangle[/math] — КС-грамматика. Рассмотрим два произвольных левосторонних вывода слова [math] w [/math] в этой грамматике:
  • [math] S \Rightarrow^* p A \beta \Rightarrow p \alpha \beta \Rightarrow^* p y \eta [/math]
  • [math] S \Rightarrow^* p A \beta \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi [/math]

где [math] p [/math] и [math] y [/math] — цепочки из терминалов, уже разобранная часть слова [math] w [/math], [math] A [/math] — нетерминал грамматики, в которой есть правила [math] A \rightarrow \alpha [/math] и [math] A \rightarrow \alpha' [/math], причём [math] \alpha, \alpha', \beta, \eta, \xi [/math] — последовательности из терминалов и нетерминалов.

Тогда если при выполнении условий, что [math] |y| = k [/math] или [math] |y| \lt k, \eta = \xi = \varepsilon [/math], верно, что [math] \alpha = \alpha' [/math], то [math] \Gamma [/math] называется LL(k)-грамматикой.

LL(1)-грамматика является частным случаем. Её определение почти такое же, только вместо строки [math] y [/math] один символ [math] c \in \Sigma \cup \{\varepsilon\} [/math].

Неформально это означает, что, посмотрев на очередной символ после уже выведенной части слова, можно однозначно определить, какое правило из грамматики выбрать.

FIRST и FOLLOW

Ключевую роль в построении парсеров для LL(1)-грамматик играю множества [math] \mathrm{FIRST} [/math] и [math] \mathrm{FOLLOW} [/math].

Пусть [math] c [/math] — символ из алфавита [math] \Sigma [/math], [math] \alpha,\ \beta [/math] — строки из нетерминалов и терминалов (возможно пустые), [math] S,\ A [/math] — нетерминалы грамматики (начальный и произвольный соответственно), [math] \$ [/math] — символ окончания слова. Тогда определим [math] \mathrm{FIRST} [/math] и [math] \mathrm{FOLLOW} [/math] следующим образом:

Определение:
[math] \mathrm{FIRST}(\alpha) = \{c \mid \alpha \Rightarrow^* c \beta \} \cup \{ \varepsilon\ \mathrm{if}\ \alpha \Rightarrow^* \varepsilon \} [/math]


Определение:
[math] \mathrm{FOLLOW}(A) = \{c \mid S \Rightarrow^* \alpha A c \beta \} \cup \{ \$ \ \mathrm{if}\ S \Rightarrow^* \alpha A \} [/math]

Другими словами, [math] \mathrm{FIRST}(\alpha) [/math] — все символы (терминалы), с которых могут начинаться всевозможные выводы из [math] \alpha [/math], а [math] \mathrm{FOLLOW}(A) [/math] — всевозможные символы, которые встречаются после нетерминала [math] A [/math] во всех правилах грамматики.

Примеры

Множества [math] \mathrm{FIRST} [/math] и [math] \mathrm{FOLLOW} [/math] могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.

  • [math] A \rightarrow (A)A \mid \varepsilon [/math]
  • [math] B \rightarrow BB \mid (B) \mid \varepsilon [/math]


Правило FIRST FOLLOW
A [math]\{\ (,\ \varepsilon\ \} [/math] [math]\{\ ),\ \$\ \} [/math]
B [math]\{\ (,\ \varepsilon\ \} [/math] [math]\{\ (,\ ),\ \$\ \} [/math]

Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW

TODO: Теорема об LL(1)-грамматиках

TODO: Пара следствий

См. также

Источники информации