http://neerc.ifmo.ru/wiki/index.php?action=history&feed=atom&title=LL%28k%29-%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0%2C_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_FIRST_%D0%B8_FOLLOW
LL(k)-грамматика, множества FIRST и FOLLOW - История изменений
2026-04-28T04:15:33Z
История изменений этой страницы в вики
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=LL(k)-%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_FIRST_%D0%B8_FOLLOW&diff=39717&oldid=prev
Shersh: Перенаправление на LL(k)-грамматики, множества FIRST и FOLLOW
2014-06-21T13:57:40Z
<p>Перенаправление на <a href="/wiki/index.php?title=LL(k)-%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_FIRST_%D0%B8_FOLLOW" title="LL(k)-грамматики, множества FIRST и FOLLOW">LL(k)-грамматики, множества FIRST и FOLLOW</a></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 13:57, 21 июня 2014</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">{{В разработке}}</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">#перенаправление [[</ins>LL(k)-грамматики, <ins class="diffchange diffchange-inline">множества </ins>FIRST и FOLLOW<ins class="diffchange diffchange-inline">]]</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">{{TODO | t = Небольшое введение}}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">{{Определение</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">|id=defLLK </del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">|definition=</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">КС-грамматика <tex> \Gamma </tex> называется '''</del>LL(k)-<del class="diffchange diffchange-inline">грамматикой''', если при возникновении следующей ситуации:</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* <tex> S \Rightarrow^* p A \beta \Rightarrow  p \alpha \beta \Rightarrow^* p y \eta </tex></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* <tex> S \Rightarrow^* p A \beta' \Rightarrow  p \alpha' \beta \Rightarrow^* p y \xi </tex></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">где <tex> S </tex> {{---}} стартовый нетерминал </del>грамматики, <del class="diffchange diffchange-inline"><tex> p </tex> {{---}} цепочка из терминалов, уже разобранная часть слова, {{---}} <br></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">и при выполнении условий, что <tex> |y| = k </tex> или <tex> |y| < k, \eta = \xi = \varepsilon </tex>, верно, что <tex> \alpha = \alpha' </tex>.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">}}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">{{TODO | t = LL(1)-грамматика}}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">{{TODO | t = </del>FIRST и FOLLOW<del class="diffchange diffchange-inline">, примеры (скобочные последовательности)}}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">{{TODO | t = Теорема об LL(1)-грамматиках}}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">{{TODO | t = Псевдокоды построения множеств FIRST и FOLLOW}}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">{{TODO | t = Примеры арифметических выражений с табличками, левая рекурсия правое ветвление}}</del></div></td><td colspan="2"> </td></tr>
</table>
Shersh
http://neerc.ifmo.ru/wiki/index.php?title=LL(k)-%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_FIRST_%D0%B8_FOLLOW&diff=39713&oldid=prev
Shersh: определение LL(k)-грамматики
2014-06-21T12:55:12Z
<p>определение LL(k)-грамматики</p>
<p><b>Новая страница</b></p><div>{{В разработке}}<br />
<br />
{{TODO | t = Небольшое введение}}<br />
<br />
{{Определение<br />
|id=defLLK <br />
|definition=<br />
КС-грамматика <tex> \Gamma </tex> называется '''LL(k)-грамматикой''', если при возникновении следующей ситуации:<br />
* <tex> S \Rightarrow^* p A \beta \Rightarrow p \alpha \beta \Rightarrow^* p y \eta </tex><br />
* <tex> S \Rightarrow^* p A \beta' \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi </tex><br />
где <tex> S </tex> {{---}} стартовый нетерминал грамматики, <tex> p </tex> {{---}} цепочка из терминалов, уже разобранная часть слова, {{---}} <br><br />
и при выполнении условий, что <tex> |y| = k </tex> или <tex> |y| < k, \eta = \xi = \varepsilon </tex>, верно, что <tex> \alpha = \alpha' </tex>.<br />
}}<br />
<br />
{{TODO | t = LL(1)-грамматика}}<br />
{{TODO | t = FIRST и FOLLOW, примеры (скобочные последовательности)}}<br />
{{TODO | t = Теорема об LL(1)-грамматиках}}<br />
{{TODO | t = Псевдокоды построения множеств FIRST и FOLLOW}}<br />
{{TODO | t = Примеры арифметических выражений с табличками, левая рекурсия правое ветвление}}</div>
Shersh